I'll write an introduction to lpetrich's posts, using different words.
Definitions:
- A function f : A → B is an injection ("one-to-one") if for each b ∈ B there is at most one a ∈ A with f(a) = b.
- A function f : A → B is a surjection ("onto") if for each b ∈ B there is at least one a ∈ A with f(a) = b.
- A function f : A → B is a bijection ("one-to-one and onto") if for each b ∈ B there is exactly one a ∈ A with f(a) = b.
- Sets A and B are said to have the same cardinal number if there is a bijection from A to B.
- (a,b) denotes {x | a < x < b}
- [a,b) denotes {x | a ≤ x < b}
- [a,b] denotes {x | a ≤ x ≤ b}
- P(A) denotes the power set of A; P(A) = {x | x ⊆ A}
- ℕ+ denotes the set of counting numbers; ℕ+ = {1, 2, 3, 4, 5, ...}
Theorem (the Cantor-Bernstein-Schroeder Theorem):
If there is an injection f : A → B and an injection g : B → A, then there exists a bijection h : A → B.
(The name "Cantor-Bernstein-Schroeder Theorem" is misleading. Cantor's proof unnecessarily required the Axiom of Choice (which was unknown when Cantor published); Schroeder's proof was incorrect; and anyway Dedekind developed a correct proof before any of the three who appear in the theorem's name.)
Proof: Wikipedia shows a Proof by Julius König which appears to be constructive. For each x ∈ A, construct a sequence with alternating elements from A and B:
. . . f-1(g-1(x)), g-1(x), x, f(x), g(f(x)), f(g(f(x))), . . .
As seen, we extend the sequence on the left with the inverse functions until we arrive at a non-existent inverse.
Each element of A or B will occur in exactly one of these sequences. The sequences will be one of four types
(a) a finite cycle
(b) a sequence which starts with an element of A and extends infinitely to the right.
(c) a sequence which starts with an element of B and extends infinitely to the right.
(d) a sequence which is infinite in both directions.
If x ∈ A occurs in a sequence of type (c), use h(x) = g
-1(x) for the bijection.
If x ∈ A occurs in a sequence of type (a), (b) or (d), use h(x) = f(x) for the bijection.
Q.E.D.
(I write "appears to be constructive" because, as
Schröder–Bernstein theorem mentions, the Proof relies on
Aristotle's Law of the Excluded Middle which is unacceptable to Intuitionists.)
- - - - - - - - - - - - - - -
With the above definitions we can set about the task of proving that two sets have the same cardinal number.
(1) (0, 1), (-π, π) and ℝ = (-∞, +∞), all three have the same cardinal number.
We can display bijections directly:
(0, 1) ↔ (-π, π) is easy
(-π, π) ↔ (-∞, +∞) is achieved via
f(x) = tan(x)
f-1( y) = tan-1( y)
(2) The integers ℤ and the rational numbers ℚ have the same cardinal number.
Here it is much easier to display two injections than a bijection. We need only show an injection f : ℤ → ℚ and another injection g : ℚ → ℤ
f(x) = x suffices for the first injection. For p/q ∈ ℚ where p/q is non-negative and in lowest terms, g(p/q) = 2p⋅3q suffices for the second injection. When p/q is negative, use g(p/q) = 5⋅q(|p/q|)
(3) The power-set P(ℕ
+) of the counting numbers has the same cardinal number as [0, 1) = {x | x∈ℝ and 0 ≤ x < 1}
I presented a bijection for this some months ago in another thread, but try it yourself. It's fun!
(4) The set of points on a line (ℝ) has the same cardinal number as the set of points on a plane (ℝ × ℝ)
