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: An Uncountable Set

The open interval (0, 1) is uncountable.

(Important)

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.

However, the real numbers, of course, do exist, and are thus uncountable. As for a more elementary uncountable set, one could consider the following:

the set of all infinite sequences of 0's and 1's is uncountable

The proof of this statement is similar to the above proposition, and is left as an exercise. What about other familiar sets that are uncountable ?

Examples:

As for other candidates of uncountable sets, we might consider the following:
1. What is the cardinality of the open interval (-1, 1) ?
2. What is the cardinality of any open interval (a, b) ?
3. Is the set R of all real numbers countable or uncountable ?

Now we know examples of countable sets (natural numbers, rational numbers) as well as of uncountable sets (real numbers, any interval of real numbers). Both contain infinitely many numbers, but, according to our counting convention via bijections, the reals actually have a lot more numbers than the rationals.

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: Power Set

The power set of a given set S is the set of all subsets of S, denoted by P(S).

Examples:

If S = {1,2,3}, then what is P(S) ? What is the power set of the set S = {1, 2, 3, 4} ? How many elements does the power set of S = {1, 2, 3, 4, 5, 6} have ?
Show that card(P(S)) card (S) for any set S (you don’t have to proof strict inequality, only greater or equal).

Theorem: Cardinality of Power Sets

The cardinality of the power set P(S) is always bigger than the cardinality of S for an set S.

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’:

Let S be the set of all those sets which are not members of themselves.

Do you see why this is an impossibility ? Ask yourself whether the set S is a member of itself ?

A Hierarchy of Infinity: Cardinal Numbers

We can now make a 'hierarchy' of infinity. The 'smallest' infinity is card(N). The next smallest 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:

Definition of a cardinal number
Comparing cardinal numbers
Addition of two cardinal numbers

Examples:

Using your above definitions, find the answers for the following examples:
1. What is card(N) + card(N) ?
2. What is card(N) - card(N) ?
3. What is card(R) + card(N) ?
4. What is card(R) + card(R) ?

The Continuum Hypothesis

An important question when dealing with cardinal number is: is there a set S whose cardinal number satisfies the strict inequalities

card(N) < card(S) < card(R)

What might be a possible candidate ?

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. one-to-one) functions. Therefore, the next theorem deals with equality of cardinality if only one-to-one functions can be found.

Note that it should be the case that if you find a one-to-one 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 one-to-one 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: Cantor-Bernstein

Let A and B be two sets. If there exists a one-to-one function f from A to B and another one-to-one 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).

Go Up |

Next Section |

Prev. Section |

Glossary |

Map

(bgw)