Avoiding Set-Theoretic Paradoxes using Symmetry

Intuitively, for any property P(x) of sets, there should be a set \{x \mid P(x)\} which has as its members all and only those sets x such that P(x) holds. But this can’t actually work, due to Russell’s Paradox: Let b = \{x\mid x\notin x\}, and then you can derive a contradiction from both b\in b and b\notin b.

The standard solution to this is essentially to forbid the construction of any set which is too big. This solves the problem since you can prove that there are many sets which are not members of themselves, making b too big to be a set. But you also end up throwing out many sets which you might want to have: for example, the set of all sets, the set of all groups, etc.

Randall Holmes recently published a paper espousing another solution: instead of forbidding the construction of sets which are too big, forbid the construction of sets which are too asymmetric. Details below.

Imagine you have some permutation \pi of the universe of sets. Because any set is also a set of sets, we can also consider the related permutation j\pi defined by j\pi(x) = \{\pi(y) \mid y\in x\}. That is, j\pi acts on a set x by applying \pi to x‘s elements. By iteration, we have j^n\pi for any n\in\mathbb{N}.

For n\in\mathbb{N}, say that a set x is n-symmetric if j^n\pi(x) = x for all permutations \pi of the universe of sets. We say that a set is symmetric if it’s n-symmetric for some n. Holmes’s criterion is then to forbid the construction of any set which is not symmetric. (You may have noticed that this discussion is not quite rigorous. Holmes’s paper has a fully rigorous formalization of this.)

So which sets are symmetric? First of all, notice that the empty set \{\} is symmetric, as it’s 1-symmetric. Therefore the set \{\{\}\} consisting of solely the empty set is 2-symmetric and therefore symmetric. Similarly any hereditarily finite set (this means a set which can be written down with a finite number of \{‘s and \}‘s and ,‘s and nothing else) is symmetric, since it will be n-symmetric where n is the maximum depth of the braces.

It’s also the case that the set of all sets is 1-symmetric, so that exists. What about the set of all groups? A group will be encoded as some ordered pair of a set and a binary operation on that set, and a binary operation will be further encoded as a set of ordered pairs. The set of all groups will be n-symmetric where n is large enough to “pierce” the encoding, so that it ends up just permuting the group elements (and thus permuting the groups and sending the set of all groups to itself).

Can we develop mathematics in this theory? It seems that constructing the natural numbers will be a problem. The usual (von Neumann) definition of the natural numbers is that:

0 = \{\}

1 = \{0\}

2 = \{0,1\}

and, in general, each natural number is the set of all the preceding ones. All of these sets exist, since the von Neumann definition of n will be (n+1)-symmetric, but the set of all natural numbers is not symmetric.

However, we can go back instead to Frege’s original definition of the natural numbers: each n is represented as the set of all sets of cardinality n. For each n, Frege’s definition of n is 2-symmetric, and the set of all natural numbers is 3-symmetric. The rationals and reals can be constructed as usual.

So, how do we know that the set b is not symmetric? We don’t, but an encouraging fact is the following: There is no known way to prove that for any formula \phi(x), the set \{x\mid \phi(x)\} exists. Instead, one can prove that \{x \mid \phi(x)\} exists if \phi(x) is stratified: this means that one can assign a natural number to each variable in \phi(x) so that for any occurrence of the formula y \in z in \phi(x), y is assigned the number one less than that assigned to z, and for any occurrence of the formula y = z in \phi(x), y is assigned the same number as that assigned to z. The formula defining b is emphatically not stratified!

If you like working with universal sets, but it makes you uneasy to use a set theory which you don’t know is consistent, check out NFU. It uses the concept of stratified formulas to avoid Russell’s paradox, allows the existence of the set of all sets (and set of all groups, etc.) and is known to be consistent relative to ZFC. In fact, Randall Holmes proposed the system I’ve discussed here as a way of clarifying the semantics of a related set theory. A book developing mathematics in NFU is here.

About these ads

1 Comment

Filed under Uncategorized

One response to “Avoiding Set-Theoretic Paradoxes using Symmetry

  1. Pingback: The 79th Philosophers’ Carnival « Possibly Philosophy

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s