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.
Context

Proof:

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

Assume that S is countable. Then, by definition,

there exists a bijection f from S to N

Next, consider the function g from N to N defined as

g(n) = n + 1, which is a bijection from N to N \ {1}.

Both functions, being bijections, have an inverse function. Define the function

h(s) = (f ^-1 o g o f)(s) = f ^-1(g(f(s))) from S to S

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

f(s) = s if s is in S \ B and f(s) = h(s) if s is in B.

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 ?

Interactive Real Analysis, ver. 1.9.5
(c) 1994-2007, Bert G. Wachsmuth
Page last modified: Mar 28, 2007