• Real Analysis
• 1. Sets and Relations
• 2. Infinity and Induction
• 2.1. Countable Infinity
• 2.2. Uncountable Infinity
• 2.3. The Principle of Induction
• 2.4. The Real Number System
• 2.5. Pi and e are irrational
• 3. Sequences of Numbers
• 4. Series of Numbers
• 5. Topology
• 6. Limits, Continuity, and Differentiation
• 7. The Integral
• 8. Sequences of Functions
• 9. Historical Tidbits
• Java Tools

Theorem 2.1.4: Dedekind Theorem

Why these ads ...

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. 2.0.1(b)
(c) 1994-2017, Bert G. Wachsmuth
Page last modified: Mar 3, 2017