On some sets which are not

What can be more simple than make a set out of some arbitrary real or imaginary objects? Isn't a set just a construction of the mind? If so, then just think of the objects as being elements of a set and you are done.

How nice. Unfortunately, about 90 years ago Bertrand Russell had the idea to consider the set (let's call it Z) of all those and only those sets that are not their own elements. In other words,

Z={ X: X does not belong to X}.

And suddenly something went wrong. Namely, is Z an element of Z? If it is, then Z cannot be in Z, for it does not satisfy the defining condition. If not, then it must be in Z, since it does satisfy the condition. This contradiction leads to the conclusion that there is no such set Z.

This was the first example of a set that is not a set for the simple reason that it does not exist. In fact, the example turned out to be very useful, since it made mathematicians construct the foundations of set theory in such a way that no contradictions of this kind arise.

Some time ago Georg Cantor proved that every set has less elements than subsets. More precisely, if a subset of A is assigned in any way to each element of A, then there will certainly remain many subsets without assignment. (Even more precisely, the power of A is strictly less than the power of the set P(A) of all subsets of A). This theorem of Cantor implies several interesting positive conclusions and many negative ones as well. The latter state that something does not exist.

First of all, there is no "set of all sets", i.e. the set of which every set is an element. Indeed, suppose U is such a set. Then each of its subsets, being a set, is also its element. Hence U has at least as many elements as it has subsets, contrary to Cantor's theorem.

It seems that we have asked too much. Maybe we will be more successful in constructing the set of all one-element sets? After all, there is less of those than of all the sets... Alas. If there were such a set, say J, then for any set A, the one-element set {A} would be its element. But then we would take the set-union of all the sets in J (i.e. the set of all the elements that belong to at least one element of J) - and what would we get? First of all, we get a set, since according to the axioms of set theory, the union over a set is a set again. But this new set would be the set of all sets! Indeed, each set A is an element of the set {A} in J. We know, however, that there is no set of all sets, so we must conclude that there is no set of all one-element sets.

Maybe we can find a set with exactly 149 subsets? Wrong again. There is no set with exactly 196 nor exactly 245 280 subsets either. To verify this claim there is no need to check every possible set for the number of its subsets. The answer is much more simple. The number of subsets of a finite, n-element set (it should be clear that no infinite set can have 149 subsets) is equal to n-th power of 2. This fact may be known to every college student or, in any case, to anyone who has ever seen the following equation:

which represents a combinatorial property. After all,

is precisely the number of k-element subsets of an n-element set. So, 2n is the number of all (i.e. 0-element, 1-element, ... and n-element) subsets of an n-element set.

If there is no chance of finding a set with 149 nor 196 nor 245 280 subsets, then perhaps we can find a set with as many subsets as there are natural numbers, which means denumerably many? I am sure you do not expect positive answers in this article - and you are right. No finite set has so many subsets, because it only has finitely many of them. On the other hand, if A is infinite, then it has at least as many elements as there are natural numbers, since after taking n elements away from A for arbitrary n, we can still find another, (n+1)-st element. If so, Cantor' theorem implies that A must have more subsets than there are natural numbers.

After reading all these examples you may ask whether there are any sets at all. The answer is yes. There is at least the empty set.

Wiktor Bartol