Interactive Real Analysis - part of MathCS.org

Next | Previous | Glossary | Map | Discussion

Theorem 2.1.4: Dedekind Theorem

A set S is infinite if and only if there exists a proper subset A of S which has the same cardinality as S.

Proof:

The proof contains some gaps that you are supposed to fill in as an exercise.

Assume that S is countable. Then, by definition,

Next, consider the function g from N to N defined as Both functions, being bijections, have an inverse function. Define the function Because f and g are bijections, h is also a bijection between S and h(S). But h(S) is now a proper subset of S - which element is in S but not in h(S) ? Hence, S is equivalent to a proper subset of itself.

Assume that S is uncountable. Then we can extract a countable subset B of S. By the above proof, there is a bijection h from B to a proper subset A of B. Now define the function

Then f is a bijection between S and f(S), and f(S) is a proper subset of S - do you see why ? Hence, S is again equivalent to a proper subset of itself.

Assume that S is finite. If S has, say, N elements, then a proper subset of S contains at most N - 1 elements. But then it is impossible to find a bijection from S to this proper subset - do you see why ?

Next | Previous | Glossary | Map | Discussion