Intuitively, for any property of sets, there should be a set which has as its members all and only those sets such that holds. But this can’t actually work, due to Russell’s Paradox: Let , and then you can derive a contradiction from both and .
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 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 of the universe of sets. Because any set is also a set of sets, we can also consider the related permutation defined by . That is, acts on a set by applying to ‘s elements. By iteration, we have for any .
For , say that a set is -symmetric if for all permutations of the universe of sets. We say that a set is symmetric if it’s -symmetric for some . 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 -symmetric where 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 -symmetric where 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:
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 will be -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 is represented as the set of all sets of cardinality . For each , Frege’s definition of 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 is not symmetric? We don’t, but an encouraging fact is the following: There is no known way to prove that for any formula , the set exists. Instead, one can prove that exists if is stratified: this means that one can assign a natural number to each variable in so that for any occurrence of the formula in , is assigned the number one less than that assigned to , and for any occurrence of the formula in , is assigned the same number as that assigned to . The formula defining 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.
One thought on “Avoiding Set-Theoretic Paradoxes using Symmetry”