# Interactive Real Analysis

Next | Previous | Glossary | Map

## 2.1. Countable Infinity

### 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,

• 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 ? Next | Previous | Glossary | Map