2. Infinity and Induction
2.2. Uncountable Infinity
The last section raises the question whether it is at all possible to have sets that contain more than countably many elements. After all, the examples of infinite sets we encountered so far were all countable. It was Georg Cantor who answered that question: not all infinite sets are countable.Proposition 2.2.1: An Uncountable Set  
The open interval (0, 1) is uncountable. 
Note that this proposition assumes the existence of the real numbers. At this stage, however, we have only defined the integers and rationals. We are not supposed to know anything about the real numbers. Therefore, this proposition should  from a strictly logical point of view  be rephrased:
 if there are 'real numbers' in the interval (0, 1) then there must be uncountably many.
 the set of all infinite sequences of 0's and 1's is uncountable
Are there sets that contain even more elements than the real numbers ? More generally, given any set, is there a method for constructing another set from the given one that will contain more elements than the original set ? For finite sets the answer is easy: just add one more element that was not part of the original set. For countable sets, however, this does not work, since the new set with one more element would again be countable.
But, there is indeed such a procedure leading to bigger and bigger sets:
Definition 2.2.3: Power Set  
The power set of a given set S is the set of all subsets of S, denoted by P(S). 
Theorem 2.2.5: Cardinality of Power Sets  
The cardinality of the power set P(S) is always bigger than the cardinality of S for an set S. 
Example 2.2.6: Logical Impossibilities  The Set of all Sets  
When dealing with sets of sets, one has to be careful that one does not by accident
construct a logical impossibility. For example, one might casually define the following
‘superset':

Example 2.2.7: A Hierarchy of Infinity  Cardinal Numbers  
We can now make a 'hierarchy' of infinity. The 'smallest' infinity is card(N).
The next infinity is card(R), then card(P(R)),
then card(P(P(R))), and so on. By the above theorem, we keep
getting bigger and bigger 'infinities'. The numbers card(S), where
S is any finite or infinite set, are called cardinal numbers, and one can
indeed establish rigorous rules for adding and subtracting them.
Try to establish the following definitions for dealing with cardinalities:

Example 2.2.9: The Continuum Hypothesis  
An
important question when dealing with cardinal numbers is: is there a set S whose
cardinal number satisfies the strict inequalities

In real analysis, we will (almost always) deal with finite sets, countable sets, or sets of the same cardinality as card(R). Larger sets will almost never appear in this text, and the existence of a set as described above will not be important to us.
In order to prove that two sets have the same cardinality one must find a bijection between them. That is often difficult, however. In particular, the difficulty in proving that a function is a bijection is to show that it is surjective (i.e. onto). On the other hand, it is usually easy to find injective (i.e. onetoone) functions. Therefore, the next theorem deals with equality of cardinality if only onetoone functions can be found.
Note that it should be the case that if you find a onetoone function from A to B (i.e. each element in A is matched with a different one from B, with possibly being unmatched elements in B left over) and another onetoone function from B to A (i.e. each element in B is matched with a different one from A, this time possibly leaving extra elements in A), then the two sets A and B should contain the same number of elements.
This is indeed true, and is the content of the next and last theorem:
Theorem 2.2.10: CantorBernstein  
Let A and B be two sets. If there exists a onetoone function f from A to B and another onetoone function g from B to A, then card(A) = card(B). 
This theorem can be used to show, for example, that R x R has the same cardinality as R itself, which is one of the exercises. It can also be used to prove that Q is countable by showing that Q and Z x Z have the same cardinality (another exercise).