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 oneelement 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 oneelement set {A} would be its element. But then
we would take the setunion 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 oneelement 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, nelement set (it should be clear that no infinite set can have
149 subsets) is equal to nth 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 kelement subsets of an nelement set. So,
2^{n} is the number of all (i.e. 0element, 1element, ... and
nelement) subsets of an nelement 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
