Finite, Countable and Uncountable Sets - Set Theory, CSIR-NET Mathematical Sciences | Mathematics for IIT JAM, GATE, CSIR NET, UGC NET PDF Download

Introduction - Equivalence of sets, countable and uncountable sets

Let's assume the set Z⁺ of positive integers, and the set N = Z⁺ U {0} of natural numbers. For any n ∈ Z⁺ , let's denote by [n] the set {1,...,n}. It is obvious that [n] has n elements, and also that the empty set Ø has 0 elements. Just out of mathematical fastidiousness, let's define [0] = Ø (why not?).

• It is pretty clear what it means for an arbitrary set S to have 0 elements: it must be the empty set.
• That is - and this is a somewhat curious property of the empty set - Ø as a set is uniquely characterized by the fact that it has 0 elements.
• What does it mean for an arbitrary set S to have n elements? By definition, it means that there exists a bijection i: S → [n], i.e., a function which is both injective and surjective; or, equivalently, a function for which there exists an inverse function i^-1 : [n] → S.
• Let us call a set finite if it has n elements for some n ∈ N, and a set infinite if it is not finite.

Certainly, there are some basic facts that should be satisfied by these definitions. For instance:

Fact 1. The set Z⁺ is infinite

Proof: 

• It is certainly non-empty, so let's show that for no n ∈ Z⁺ is there a bijection i: [n] → Z⁺. This seems obvious. 
• Unfortunately, sometimes in mathematics, it's a struggle to show that the obvious is true (and sometimes what seems obvious is not true!). 
• Here there is an additional problem of not having formally axiomatized things, so it's not completely clear what's "fair game" to use in a proof.

But consider the following: 

Does Z+ have one element?

Absolutely not: for any function i: [1] = {1} → Z⁺ , i is not surjective because it does not hit i(1) + 1.

Does Z⁺ have two elements? 

Still, no: if i is not injective, the same argument as before works; if i is injective, its image is a 2-element subset of Z⁺. Since Z⁺ is totally ordered (indeed well-ordered), one of the two elements in the image is larger than the other, and then that element plus one is not in the image of our map. It is possible to prove it for 3 as well, which makes us think we should probably work by induction on n. 

How to set it up properly? 

Let us try to show that for all n and all i : [n] → Z⁺ , there exists N = N (i) such that i([n]) ⊂ [N]. If we can do this, then since [N] is clearly a proper subset of Z⁺ (it does not contain N + 1, and so on) we will have shown that for no n is there a surjection [n]! Z+ (which is in fact stronger than what we claimed). But carrying through the proof by induction is now not obvious but (much better!) very easy, so is left to the reader.

What did we use about Z⁺ in the proof? 

Some of the Peano axioms for Z⁺, most importantly that it satisfies the principle of mathematical induction (POMI). Since it is hard to imagine rigorous proof of a nontrivial statement about Z⁺ that does not use POMI, this is a good sign: things are proceeding well so far.

What about Z: is it too infinite? It should be since it contains an infinite subset. This is logically equivalent to the following fact:

Fact 2. A subset of a finite set is finite

Proof: 

• More concretely, it suffices to show that for any n ∈ N and subset S ⊂ [n], then for some m ∈ N there exists a bijection i: S → [m]. As above, for any specific value of n, it is straightforward to show this, so again we should induct on n. 
• Let's do it this time: assume the statement for n, and let S ⊂ [n + 1]. Put S' = S ∩ [n], so by induction there exists a bijection i' : [m] → S' for some m' ∈ N.
• Composing with the inclusion of S' ⊂ S, we get an injection i : [m] → S . If n + 1 is not an element of S, then S' = S and i is a bijection. If n + 1 ∈ S , then extending i' to a map from [m + 1] to S by sending m + 1 to n + 1 gives a bijection. Done.
• Again, by contraposition, this shows that many of our most familiar sets of numbers - e.g. Z; Q; R; C - are infinite.
• There is one more thing that should be certainly checked: namely, we have said that a set S has n elements if it can be put in bijection with [n] for some n. But we have not shown that this n is unique: perhaps a set can have n elements and n + 691 elements? Of course not.

Fact 3. Let S be a set with m elements and T a set with n elements:

a) If there exists a surjection φ: S → T, then m > n.

b) If there exists an injection φ: S → T, then m < n.

Exercise 1: Give proof of Fact 4 which is rigorous enough for your taste.

Remark: 

• For instance, part b) is the famous “Pigeonhole" or “Dirichlet's box" principle, and is usually regarded as obvious. 
• Of course, if we play the game of formalized mathematics, then "obvious" means "following from our axioms in a way which is so immediate so as not to deserve mention," and Fact 3 is not obvious in this sense. (But one can give a proof in line with the above induction proofs, only a bit longer.)

Exercise 2: Show that for sets S and T, the following are equivalent:

a) There exists a surjection S → T.

b) There exists an injection T → S.

Let us press on to study the properties of infinite sets.

• Basic Definition (Cantor): We say that S and T as equivalent, and write S ≌ T if there exists a bijection i: S → T.
• Historical Remark: When there exists a bijection between S and T, Cantor first said that S and T have the same power. 
• As is often the case in mathematics, this forces us to play a linguistic-grammatical game {given that a definition has been made to have a certain part of speech} write down the cognate words in other parts of speech. 
• Thus a faithful rendition of Cantor's definition in adjectival form would be something like equipotent. The reader should be warned that it would be more common to use the term equinumerous at this point.
• However, there are reasons for choosing to use “equivalent." 
• The term “equinumerous," for instance, suggests that the two sets have the same number of elements, or in other words that there is some numerical invariant we are attaching to a single set with the property that two sets can be put in bijection exactly when both have the same value of this numerical invariant. 
• But let's view things in exactly the opposite way. Let us dilate a bit on this point.
• It was Cantor's idea that we should regard two sets as “having the same size" if they are equivalent, i.e., if their elements can be paired of via a one-to-one correspondence. Certainly, this is consistent with our experience with finite sets.
• There is, however, a brilliant and subtle twist: Colloquially one thinks of counting or measuring something as a process which takes as input one collection of objects and outputs a "number." 
• We, therefore, have to have names for all of the "numbers" which measure the sizes of things: if you like, we need to count arbitrarily high. 
• Not every civilization has worked out such a general counting scheme: It is known that in a certain "primitive tribe" they only have words for numbers up to 4 and anything above this is just referred to as "many." 
• Indeed we do not have proper names for arbitrarily large numbers in the English language (except by recourse to iteration, e.g., million million for a trillion).
• But notice that we do not have to have such an elaborate "number knowledge" to say whether two things have the same size or not. For instance, one may presume that shepherding predates verbal sophistication, so the proto-linguistic shepherd needs some other means of making sure that when he takes his sheep out to graze in the countryside he returns with as many as he started with. 
• The shepherd can do this as follows: on his first day on the job, as the sheep come in, he has ready some sort of sack and places stones in the sack, one for each sheep. Then in the future, he counts his sheep, not in some absolute sense, but in relation to these stones. If one day he runs out of sheep before stones, he knows that he is missing some sheep (at least if he has only finitely many sheep!).
• Even today there are some situations where we test for equivalence rather than count in an absolute sense. For instance, if you come into an auditorium and everyone is sitting in a (unique!) seat then you know that there are at least as many seats as people in the room without counting both quantities.
• What is interesting about infinite sets is that these sorts of arguments break down: the business of taking away from an infinite set becomes much more complicated than in the finite case, in which, given a set S of n elements and any element x ∈ S, then S \ x has n - 1 elements. (This is something that you can establish by constructing a bijection and is a good intermediate step towards Fact 4.)
•  On the other hand, Z⁺ and N are equivalent, since the map n → n - 1 gives a bijection between them. Similarly, Z⁺ is equivalent to the set of even integers (n→ 2n). Indeed, we soon see that much more is true.

Fact 4. For any infinite subset S ⊂ Z⁺, S and Z⁺ are equivalent

Proof: 

• Using the fact that Z⁺ is well-ordered, let's define a function from S to Z⁺ by mapping the least element s₁ of S to 1, the least element s₂ of S \ {s₁} to 2, and so on. 
• If this process terminates after n steps then S has n elements, so is finite, a contradiction. Thus it goes on forever and clearly gives a bijection.
• It is now natural to wonder which other familiar infinite sets are equivalent to Z⁺ (or N). For this, let's call a set equivalent to Z⁺ countable. A slight variation of the above argument gives

Fact 5. Every infinite set has a countable subset

(Indeed, for infinite S just keep picking elements to define a bijection from Z⁺ to some subset of S. We can't run out of elements since S is infinite!)

Fact 6. The two sets Z and Z⁺ are equivalent

Let's define an explicit bijection Z → Z⁺ as follows: we map 0 → 1, then 1 → 2, 1 → 3, 2 → 4, -2 → 5 and so on. (If you are the kind of person who thinks that having a formula makes something more rigorous, then we define for positive n, n → 2n and for negative n, n → 2|n| + 1.)

The method proves something more general, a "splicing" result. 

Fact 7. Suppose that S₁ and S₂ are two countable sets. Then S₁ ∪ S₂ is countable

Fact 8. Let {S_i} _i∈I be an indexed family of pairwise disjoint nonempty sets; assume that I and each S_i is at most countable (i.e., countable or finite). Then S: = U_i∈I S_i is at most countable

Moreover, S is finite if I and all the S_i are finite.

• Let's sketch the construction: Since each S_i is at most countable, order the elements as s_ij where either 1 <  j < ∞ or 1 < j < N_j .
• If everything in sight is finite, it is obvious that S will be finite (a finite union of finite sets is finite). Otherwise, define a bijection from Z⁺ to S as follows: 1 → s₁₁ → 2 → s₁₂ → 3 → s₂₂ → 4 → s₁₃ → 5 → s₂₃ →6 → s₃₃ , and so on. 
• Here we need the convention that when s_ij does not exist, omit that term and go on to the next element in the codomain.

Remark: Perhaps more standard is to say countably infinite and reserve “countable" to mean countably infinite or finite. Here we suggest simplifying the terminology.

 Fact 8 is used very often in mathematics.

Fact 9. The set of rational numbers Q is countable

Proof:

• Each nonzero rational number α can be written uniquely as + a/b, where a, b ∈ Z⁺. We define the height h(α) of α to be max a; b and also h(0) = 0. 
• It is clear that for any height n > 0, there are at most 2n² rational numbers of height n, and also that for every n ∈ Z⁺ there is at least one rational number of height n, namely the integer n = n/1. 
• Therefore taking I = N and putting some arbitrary ordering on the finite set of rational numbers of height n, Fact 9 gives us a bijection Z⁺ → Q.
• In a similar way, one can prove that the set  of algebraic numbers is countable.

Fact 10. If A and B are countable, then the Cartesian product A x B is countable

Proof: 

• Strategy 1: Reduce to the case of Z⁺ x Z⁺ and use the diagonal path from the proof of Fact 8.
• Strategy 2: Observe that A x B ≌ U_a∈A B and apply Fact 8 directly.

The buck stops with R. Let's first prove the following theorem of Cantor, which is arguably the single most important result in set theory. Recall that for a set S, its power set 2^S is the set of all subsets of S.

Theorem 11. (First Fundamental Theorem of Set Theory)

There is no surjection from a set S to its power set 2^S.

Remark: When S is finite, this is just saying that for all n ∈ N, 2ⁿ > n, which is, albeit true, not terribly exciting. On the other hand, taking S = Z⁺ Cantor's Theorem provides us with an uncountable set of 2^Z+. In fact, it tells us much more than this, as we shall see shortly.

Proof of Cantor's Theorem:  
Suppose that f: S →2^S is any function. Let's produce an element of 2^S which is not in the image of f. Namely, let T be the set of all x ∈ S such that x is not an element of f (x), so T is some element of 2^S. 

Could it be f (s) for some s ∈ S? 

Well, suppose T = f (s) for some s ∈ S. We ask the innocent question, "Is s ∈ T ?" Suppose first that it is: s ∈ T; by definition of T, this means that s is not an element of f (s). But f (s) = T, so in other words, s is not an element of T, a contradiction. Okay, what if s is not in T ? Then s ∈ f (s), but again, since f (s) = T, we conclude that s is in T. In other words, we have managed to define, in terms of f, a subset T of S for which the notion that T is in the image of f is logically contradictory. So f is not surjective!

What does this have to do with R? 

Let us try to show that the interval (0; 1] is uncountable. By Fact 5 this implies that R is uncountable. Now using binary expansions, we can identify (0; 1] with the power set of Z⁺. Well, almost, there is the standard slightly annoying ambiguity in the binary expansion, that a₁ a₂ a₃ .... a_n01111111111 ... = a₁ a₂ a₂ ... a_n1000000000 ...There are various ways around this: for instance, suppose we agree to represent every element of (0; 1] by an element which does not terminate in an infinite string of zeros. Thus we have identified (0; 1] with a certain subset T of the power set of Z⁺, the set of infinite subsets of Z⁺. But the set of finite subsets of Z⁺ is countable (Fact 8 again), and since the union of two countable sets would be countable (and again!), it must be that T is uncountable. Hence so is (0; 1], and so is R.

There are many other proofs of the uncountability of R. 

• For instance, we could contemplate a function f: Z⁺ → R and, imitating the proof of Cantor's theorem, show that it cannot be surjective by finding an explicit element of R not in its image. 
• We can write out each real number f(n) in its decimal expansion, and then construct a real number α ∈ [0; 1] whose nth decimal digit α_n is different from the nth decimal digit of f (n).
• Again the ambiguity in decimal representations needs somehow to be addressed: here we can just stay away from 9's and 0's. Details are left to the reader.
• A more appealing, albeit more advanced, proof comes from a special case of the Baire category theorem: in any complete metric space, the intersection of a countable number of dense open subsets remains dense (although not necessarily open, of course). Dualizing (i.e., taking complements), we get that in any complete metric space, the union of a countable number of closed subsets with an empty interior also has an empty interior. Thus:

Corollary 13. A complete metric space without isolated points is uncountable

Proof:

• Apply the dual form of Baire's theorem to the one-point subsets of the space.
• Thus, since R is by definition the completion of Q with respect to the standard Euclidean metric, and has no isolated points, R must be uncountable. 
• For that matter, even Q has no isolated points (which is strictly stronger: no element of the completion of a metric space minus the space itself can be isolated since this would contradict the density of space in its completion), so since we know it is countable, we deduce that it is incomplete without having to talk about √2 or any of that sort of thing.
  Indeed, the same argument holds for Q endowed with a p-adic metric: there are no isolated points, so Q_p is uncountable and not equal to Q.
• The above was just one example of the importance of distinguishing between countable and uncountable sets. briefly mention some other examples:

Example 1: Measure theory 

• A measure is a [0; ∞]-valued function defined on a certain family of subsets of a given set; it is required to be countably additive but not uncountably additive. 
• For instance, this gives us a natural notion of size on the unit circle, so that the total area is π and the area of any single point is 0.
• The whole can have greater measure than the sum of the measures of the parts if there are uncountably many parts!

Example 2:

• Given a differentiable manifold M of dimension n, then any submanifold of dimension n- 1 has, in a sense which is well-defined independent of any particular measure on M, measure zero. 
• In particular, one gets from this that a countable family of submanifolds of dimension at most n - 1 cannot "fill out" an n-dimensional manifold. 
• In complex algebraic geometry, such stratifications occur naturally, and one can make reference to a "very general" point on a variety as a point lying on the complement of a (given) countable family of lower-dimensional subvarieties, and be confident that such points exist!

Example 3: 

• Model theory is a branch of mathematics which tends to exploit the distinction between countable and uncountable in rather sneaky ways. 
• Namely, there is the Lowenheim-Skolem theorem, which states in particular that any theory (with a countable language) that admits an infinite model admits a countable model. 
• Moreover, given any uncountable model of a theory, there is a countable submodel which shares all the same "first order" properties, and conversely, the countable/uncountable dichotomy is a good way to get an intuition on the difference between first-order and second-order properties.

Some further basic results

Dedekind's characterization of infinite sets.

Fact 14. A set S is infinite if it is equivalent to a proper subset of itself.

Proof:

• One direction expresses an obvious fact about finite sets. 
• Conversely, let S be an infinite set; as above, there is a countable subset T ⊂ S . 
• Choose some bijection i between T and N. Then there is a bijection i' between T':= T \ i^-1 (0) and T (just because there is a bijection between N and Z⁺. 
• We, therefore, get a bijection between S':= S \ i ^-1 (0 and S by applying i' from T' to T and the identity on S \ T.
• This characterization of infinite sets is due to Dedekind. 
• What is ironic is that in some sense it is cleaner and more intrinsic than our characterization of finite sets, in which we had to compare against a distinguished family of sets {[n]  | n ∈ N}.
• Thus perhaps we should define a set to be finite if it cannot be put in bijection with a proper subset of itself! (On the other hand, this is not a "first order" property, so is not in reality that convenient to work with.)

An uncountable set not of continuum type. Notice that in making the definition "uncountable," i.e., an infinite set which is not equivalent to Z⁺, we have essentially done what we earlier discussed about the "primitive tribes": giving up distinguishing between very large sets. In some sense, the set theory begins when we attempt to classify uncountable sets up to equivalence.

Let us define a set S to be of continuum type (or, more briefly, a continuum) if there is a bijection i: S → R. 

Fact 15. There exists an uncountable set which is not of continuum type, namely 2^R.

• By Theorem 11 there is no surjection from R to 2^R, so 2^R is certainly not of continuum type. We must however confirm what seems intuitively plausible: that 2^R is indeed uncountable. 
• It is certainly infinite, since via the natural injection i: R → 2R, r → {r}, it contains an infinite subset. But indeed, this also shows that 2^R is uncountable since if it were countable, its subset i(R) ≌ R would be countable, which it isn't.

Some sets of continuum types. For any two sets S and T, we define T^S as the set of all functions f S → T . When T = [2], the set of all functions f: S → [2] is naturally identified with the power set 2^S of S (so the notation is almost consistent: for full consistency, we should be denoting the power set of S by [2]^S, which we will not trouble ourselves to do).

Fact 16. The sets (0; 1], 2^Z+ and R^Z+ are of continuum type.

Proof: Earlier we identified the unit interval (0; 1] in R with the infinite subsets of Z⁺ and remarked that, since the finite subsets of Z⁺ form a countable set, this implies that (0; 1] hence R itself is uncountable. Let us refine this latter observation slightly.

Lemma 17. Let S be an uncountable set and C ⊂ S an at most countable subset. Then S \ C ≌ S.

Proof: 

• Suppose first that C is finite, say C ≌ [n]. Then there exists an injection i: Z⁺ → S such that i([n]) = C (as follows immediately from Fact 6). Let C_∞ = i(Z⁺). 
• Now let's define an explicit bijection β from S \ C to S: namely, take β to be the identity on the complement of C_∞ and on C_∞ we define β (i(k)) = i(k - n).
• Now suppose C is countable. We do something rather similar. Namely, taking C₁ = C, since S \ C₁ is uncountable, we can find a countably infinite subset C₂ ⊂ S \ C₁. 
• Proceeding in this way we can find a family {C_i}_i∈Z+ of pairwise disjoint countable subsets of S. 
• Let us identify each of these subsets with Z⁺, getting a doubly indexed countable subset C_∞ := U_iC_i = {c_ij} - here c_ij is the jth element of C_i. Now let's define a bijection β from S \ C₁ to S by taking β to be the identity on the complement of C_∞ and by putting β (c_ij) = c_(i-1)j. This completes the proof of the lemma.
• Thus the collection of infinite subsets of Z⁺ - being a subset of 2^Z+ with countable complement - is equivalent to 2^Z+, and hence (0; 1]≌  2^Z+.

Let us see that (0; 1] is of continuum type.
One way is as follows: Again by the above lemma, [0; 1] ≌ (0; 1), and R is even homeomorphic to (0; 1): for instance, the function

For the case of (Z⁺)^R: since R ≌ 2^Z+, it is enough to find a bijection from (Z⁺)2^Z+ to 2^Z+. This is in fact quite easy: we are given a sequence a_ij of binary sequences and want to make a single binary sequence. But we can do this just by choosing a bijection Z⁺ x Z⁺ → Z⁺.

A little more abstraction will make this argument seem much more reasonable:

Lemma 18. Suppose A, B and C are sets. Then there is a natural bijection

(A^B)^C ≌ A^CxB

Proof: 

• Indeed, given a function F from C to A^B and an ordered pair (c, b) ∈ C x B, F(c) is a function from B to A and so F(c)(b) is an element of a.
• Conversely, every function from C x B to A can be viewed as a function from C to the set A^B of functions from B to A, and these correspondences are evidently mutually inverse. So what we said above amounts to
  

Exercise 4: A subinterval of R containing more than one point is of continuum type.

• It is also the case that (Z⁺)^Z+ is of continuum type. 
• At the moment I do not see proof of this within the framework we have developed. What we can show is that there exists an injection R,→ (Z⁺)^Z+ { indeed, since R ≌ 2^Z+, this is obvious } and also that there exists an injection (Z⁺)^Z+,→ 2^Z+ ≌ R.
• To see this latter statement: given any sequence of positive integers, we want to return a binary sequence { which it seems helpful to think of as "encoding" our original sequence } in such a way that the decoding process is unambiguous: we can always reconstruct our original sequence from its coded binary sequence. 
• The first thought here is to just encode each positive integer a_i in binary and concatenate them. 
• Of course, this doesn't quite work: the sequence 2, 3, 1, 1, 1 ... get coded as 1011 followed by an infinite string of ones, as does the sequence 11, 1, 1, 1...
• But this can be remedied in many ways. One obvious way is to retreat from binary notation to unary notation: we encode a_i as a string of i ones, and in between each string of ai ones we put a zero to separate them. This clearly works (it seems almost cruelly inefficient from the perspective of information theory, but no matter).
• Roughly speaking, we have shown that (Z⁺)^Z+ is "at least of continuum type" and at most of the continuum type," so if equivalences of sets do measure some reasonable notion of their size, we ought to be able to conclude from this that (Z⁺)^Z+ is itself of continuum type. This is true, a special case of the important SchrÄoderBernstein theorem.

Lots of inequivalent uncountable sets. From the fundamental Theorem 12 we first deduced that not all infinite sets are equivalent to each other, because the set 2^Z+ is not equivalent to the countable infinite set Z⁺ . We also saw that 2^Z+ ≌ R so called it a set of continuum type. Then we noticed that Cantor's theorem implies that there are sets not of continuum type, namely 2^R ≌ 2^2Z+ . By now one of the most startling mathematical discoveries of all time must have occurred to the reader: we can keep going!

To simplify things, let us use (and even slightly abuse) an obscure but colorful notation due to Cantor: instead of writing Z⁺ we shall write Z₀ . For 2^Z+ we shall write Z₁ , and in general, for n ∈ N, having defined in (informally, as the n-fold iterated power set of Z⁺), we will define Z_n+1 as 2^Zn. Now hold on to your hat:

Fact 19. The infinite sets fin {Z_n}_n∈N are pairwise inequivalent.

• Let us first make the preliminary observation that for any nonempty set S, there is a surjection 2^S → S.
• Indeed, pick your favourite element of S, say x; for every s ∈ S we map fsg to s, which is "already" a surjection; we extend the mapping to all of 2^S by mapping every other subset to x.

This canonical bijection is sometimes called "adjunction."

• Now we argue by contradiction: Suppose that for some n > m there exists even a surjection s: Z_m → Z_n. 
• We may write n = m + k. By the above, by concatenating (finitely many) surjections we get a surjection β: Z_m+k → Z_m+1 . 
• But then β º s: Z_m → Z_m+1 = 2^Zm is a surjection, contradicting Cantor's theorem. 
• Thus there are rather a lot of inequivalent infinite sets.

Is it possible that the Z_n 's are all infinite sets? 

In fact, it is not: define Z_w:= U_n∈N Z_n. This last set Z_w is certainly not equivalent to Z_n for any n, because it visibly surjects onto Z_n+1. Are we done yet? No, we can keep going, defining Z_w+1:= 2^Zw.

To sum up! There is a two-step process for generating a mind-boggling array of equivalence classes of sets. 

The first step is to pass from a set to its power set, and the second stage is to take the union over the set of all equivalence classes of sets we have thus far considered. Inductively, it seems that each of these processes generates a set which is not surjected onto by any of the sets we have thus far considered, so it gives a new equivalence class.

Does the process ever end?!?

Well, the above sentence is an example of the paucity of the English language to describe the current state of affairs, since even the sequence Z₀; Z₁; Z₂ ... does not end in the conventional sense of the term. Better is to ask whether or not we can reckon the equivalence classes of sets even in terms of infinite sets. At least we have only seen countably many equivalence classes of sets thus far.

Is it possible that the collection of all equivalence classes of sets is countable?

No again, and in fact, that's easy to see. Suppose {S_i} _i∈N is any countable collection of pairwise inequivalent sets. Then - playing both of our cards at once! - one checks immediately that there is no surjection from any S_i onto .

Fact 20. For no set I does there exist a family of sets {S_i}_i∈I such that every set S is equivalent to S_i for at least one i.

Proof: Again, take . There is no surjection from U^i∈I S_i onto S_bigger, so for sure there is no surjection from any S_i onto S_bigger.

Some Final Remarks

Fact 20 is a truly amazing result. Once you notice that it follows readily from Cantor's Theorem 12, you may believe, that this theorem is the single most amazing result in all of mathematics.

There is also the question of whether this result is disturbing, or paradoxical. 

Can we then not speak of the set of all equivalence classes of sets (let alone, the set of all sets)?

• Evidently we cannot. There are too many sets to wrap all of them up into a single set. 
• Some people have referred to this as Cantor's Paradox, although Cantor did not regard his results as paradoxical. It does destroy the "ultranaive" notion of a set, namely, that given any "property" P, there is a set S_P = [x | P (x)}: according to Cantor's result, we cannot take P to be the property x = x. 
• This was surprising in the late 19th century. But now we know of such things as Russell's paradox, which shows that the property P (x) given by x ∉ x does not give rise to a set: the set of all sets which are not members of itself is a logical contradiction.
• But in truth it is hard to find anyone in the 21st century who has thought for more than a few hours about sets and is this naive, i.e., who thinks that every "property" of "objects" should give rise to a set. 
• Indeed, as you can see from the quotation marks in the previous sentence, the idea that "all mathematical objects" is well-defined and meaningful has itself come to be regarded as problematic: what is the definition of a "mathematical object"? 
• In some sense our idea of what sets are has come to be more dynamic and iterative following Cantor's work: we start with some simple sets and some operations (like union, subsets, and power sets), and by applying various procedures these operations allow us to create new and more complicated sets.
• It is certainly true that deciding what "procedures" are legal is a difficult point: none of these procedures are of the sort that the truly finitistic mind need admit to as meaningful or possible. 
• One can only say that in order to do mathematics the vast majority of us are willing to admit (indeed, unwilling to deny) the existence of certain infinite structures and processes: note that we began by saying "[w]e assume known the set Z⁺," i.e., we assumed the existence of an infinite set. 
• If you decide to press on to read about a more explicit examination of what properties we think sets should satisfy, you will see that one of them baldly asserts the existence of infinite sets (of a certain kind). 
• If we remove this axiom from the list, then the collection of sets {[n] | n ∈ N} becomes a model (in the sense of mathematical logic) for all the remaining axioms: that is, it is entirely consistent and logical to believe that sets of n elements exist for every n and not to believe that the collection of all n's makes sense as a set. 
• It just happens to be extraordinarily useful and interesting - and, apparently, noncontradictory - to believe in the existence of infinite sets. When contemplating the "legality" of certain abstruse-looking set-theoretic constructions, it seems wise to keep in mind the leap of faith we make even to entertain Z⁺.