Contents
Contents
0.1. * Proofs
1. The cardinal number of |R
1.1. Continuum Hypothesis
(Continued.)
We hardly proved anything previously in this section. Now it is time to prove. Before Theorem 3 (3), Schröder-Bernstein theorem, we prove the next two easier and more famous theorems, Theorem 5 and Theorem 6, using Cantor's diagonal argument.
Consider the set 2^{\mathbb N} of all functions from \mathbb N into \{0,1\}. Each element is an infinite sequence of binary digits. Cantor proved that 2^{\mathbb N} is uncountable. Assume it is countable, which means we can enumerate the sequences, say
\begin{align*}
s _ 1&:\, \underline0,0,0,0,\dots\\
s _ 2&:\, 1,\underline1,1,1,\dots\\
s _ 3&:\, 0,1,\underline0,1,\dots
\end{align*}
A new sequence is constructed by choosing the 1st digit as complementary to the 1st digit of s _ 1, 2nd digit as complementary to the 2nd digit of s _ 1, and so on. It is clear that the new sequence is different from any one of s _ 1, s _ 2, s _ 3, \dots. For the above example, the new sequence is
\[s:\, 1,0,1,\dots\]
By construction, s is an element of 2^{\mathbb N}, but it does not occur in the enumeraion. The contradiction shows that 2^{\mathbb N} is uncountable.
We want to show the set \mathbb R of real numbers, which is equinumerous to (0,1), is uncountable. Here we shall use the property of \mathbb R that every real number has a decimal expansion. The uncountable set 2^{\mathbb N} can be mapped injectively into [0,1), by mapping binary strings into decimal fractions. Clearly it is an injection because it maps different strings to different numbers in [0,1). We can simply remove 0 from the domain so we can conclude that (0,1)\sim\mathbb R is uncountable. Since \mathbb N\subseteq \mathbb R, \aleph _ 0\leqslant|\mathbb R|, and since \aleph _ 0\neq|\mathbb R|, \aleph _ 0<|\mathbb R|. Theorem 5 is proved.
The proof of Theorem 6 is similar. Obviously A\preccurlyeq\mathcal P(A). Suppose f:A\to \mathcal P(A) is an arbitrary injective mapping. We show A is not equinumerous to \mathcal P(A) by constructing a subset that is not in the range of f. Let
\[B=\{x\in A\mid x\notin f(x)\}.\]
Then B\subseteq A and B\in\mathcal P(A). By construction, x\in B\Leftrightarrow x\notin f(x), which means B is not in the range of f. Therefore |A|<|\mathcal P(A)|.
.
We return to prove Schröder-Bernstein theorem: If there is an injection f:A\to B and an injection g:B\to A, then we want A\sim B, i.e., the existence of a bijection h from A onto B. Here is a very standard proof.
Define A _ 0=A\setminus g(B). The image of A _ 0 under f is B _ 1:=f(A _ 0), and the image of B _ 1 under g is A _ 1:=g(B _ 1). Generally, the iamge of A _ n under f is B _ {n+1}:=f(A _ n), and the image of B _ {n+1} under g is A _ {n+1}:=g(B _ {n+1}).
\[
\begin{matrix}
A _ 0 && A _ 1 && A _ 2 & \cdots \\
&\hspace{-1em}\searrow\hspace{-1em} &
{\uparrow} &
{\hspace{-1em}\searrow\hspace{-1em}} &
{\uparrow} &
{\hspace{-1em}\searrow\hspace{-1em}} \\
&& B _ 1 && B _ 2 &\cdots
\end{matrix}
\]
Now the elements of A are partitioned into two parts. The first part consists of the elements occurring in the sequences of the form
\[
a _ 0,g(f(a _ 0)),g(f(g(f(a _ 0)))),\dots
\]
Here a _ 0\in A _ 0. Clearly the first part is just \bigcup _ {n=0}^\infty A _ n. The second part consists of the other elements. For an element a in the second part, the left direction of the "sequence"
\[\dots,f^{-1}(g^{-1}(a)),a,g(f(a)),\dots\]
may not terminate, or terminate in the set B (when it fails to take f^{-1}).
Consider the image of \bigcup _ {n=0}^\infty A _ n under f. The relative complement of it in B is mapped injectively by g into
\[
g\Big[B\setminus f\Big(\bigcup _ {n=0}^\infty A _ n\Big)\Big],
\]
which is just the second part of A.
Due to the consideration above, we define
\[h(a)=\begin{cases}
f(a),& a\in\bigcup _ {n=0}^\infty A _ n,\\
g^{-1}(a),& a\notin\bigcup _ {n=0}^\infty A _ n.
\end{cases}\]
It can be shown h:A\to B is a bijection. Note that h is well-defined.
We first show it is surjective. Since the range of h contains f(\bigcup _ {n=0}^\infty A _ n), it suffices to show B\setminus f(\bigcup _ {n=0}^\infty A _ n) is contained in the range of h. Take an element b of it and consider g(b). Then g(b)\notin A _ 0. If g(b)\in A _ n for n>0, then f^{-1}(b)=f^{-1}(g^{-1}(g(b)))\in A _ {n-1}. But f^{-1}(b)\notin A _ {n-1} by definition of b. Thus g(b)\notin A _ n for all n\in\mathbb N, so h(g(b))=g^{-1}(g(b))=b, indicating b is in the range of h. We have shown h is surjective.
Suppose a,a'\in A, a\neq a' and h(a)=h(a'). Since f is injective, we assert that one of a,a', say a, is in A _ n for a certain n\in\mathbb N and the other is not. Then g^{-1}(a')=h(a')=h(a)\in B _ {n+1}, indicating a'\in A _ {n+1}, a contradiction. Therefore h is injective.
Schröder-Bernstein theorem is proved.
.
As was pointed out, the proof of Theorem 7 requires the axiom of choice. This axiom was first introduced in Section Axiom of Choice: A First View in a specific form. It asserts that for any relation \mathcal R with domain X, there exists a mapping f on X such that f\subseteq \mathcal R. Here the "choice function" f is from a relation \mathcal R. Similarly, a choice function can come from the power set of a set.
Let A be an arbitrary set. We now define a choice function f:\mathcal P(A)\setminus\{\varnothing\}\to A, such that f(B)\in B for any nonempty B in the domain. Set D=\mathcal P(A)\setminus\{\varnothing\}, then define a relation \mathcal R to be a set of ordered pairs: \mathcal R=\{(B,b)\mid (B\in D)\wedge (b\in B)\}. The domain of \mathcal R is just D, since for any B\in D the nonemptyness of B ensures the existence of b\in B. For this relation we apply the axiom of choice, obtaining a mapping f:D\to A such that B\mathcal R f(B) for any B\in D, which means f(B)\in B for any B\in D.
This is useful when we want to show \mathbb N\preccurlyeq A for any infinite A, i.e., there is an injection from \mathbb N into A. A natural idea is to define 0\mapsto a _ 0 for some element a _ 0\in A, 1\mapsto a _ 1\in A\setminus\{a _ 0\}, and so on. It is the axiom of choice that makes "some element" precise.
Let C:\mathcal P(A)\setminus\{\varnothing\}\to A be the choice function for A, and define a mapping g:\mathbb N\to \mathcal P(A) recursively by g(0)=\varnothing and
\[g(n+1)=g(n)\cup \{f(n)\},\quad n\in\mathbb N,\]
where f(n) is a number to be defined. Generally, g(n)=\{f(0),\allowbreak f(1),\allowbreak \dots,\allowbreak f(n-1)\}. We now define f(n) for n\in\mathbb N. The set A is infinite and therefore nonempty, so we can set f(0)=a\in A. Then we use choice function C to choose an element from A\setminus\{a\} and assign it to f(1). Suppose f(0),\dots, f(n-1) are defined. Then the set of them, i.e. g(n), is defined, and f(n) is chosen by
\[f(n)=C(A\setminus g(n)).\]
This makes sense because A\setminus g(n), the difference of an infinite set and a finite set, is nonempty.
We have defined a mapping f:\mathbb N\to A, which can be verified to be injective. By construction f(n)\notin g(n). Suppose f(m)=f(n) for some m,n\in\mathbb N, and without loss of generality suppose further m\leqslant n. If m<n, then f(m)\in g(m+1)\subseteq g(n), a contradiction. Thus m=n.
Theorem 7 is proved.
We can easily obtain some corollaries with this theorem.
- A set A is finite if and only if |A|<\aleph _ 0. Suppose |A|<\aleph _ 0, then A is a finite set by the theorem. Here we have also used Theorem 3 (4) whose proof is postponed. Conversely, if A is finite, then \mathbb N _ {<n}\sim A\preccurlyeq\mathbb N. Clearly A\not\sim\mathbb N since \mathbb N is infinite, so |A|<\aleph _ 0.
- Subsets of finite sets are finite. Suppose B is a subset of a finite set A, then |B|\leqslant |A|< \aleph _ 0. If |B|=\aleph _ 0, then by Schröder-Bernstein theorem, |A|=\aleph _ 0, a contradiction. Therefore |B|<\aleph _ 0.
- Any infinite subset of \mathbb N is equinumerous to \mathbb N, for we have \mathbb N\preccurlyeq A\preccurlyeq\mathbb N.
- A set A is infinite if and only if it is equinumerous to a proper subset of itself. We have shown the "if" part. Now suppose A is infinite. Then there is an injection f:\mathbb N\to A. Define a mapping g:A\to A that maps f(n) to f(n+1) and maps the rest of A to themselves. It is easy to see g is an injection onto A\setminus f(0).
Next we prove Theorem 9. Suppose B\neq\varnothing and B\preccurlyeq A. Then there is an injection f:B\to A. By Theorem thm231, f has a left inverse g:A\to B such that g\circ f=\operatorname{Id} _ {B}, so g has a right inverse f. By Theorem thm232, g:A\to B is surjective. Conversely, assume g:A\to B is surjective. By Theorem thm232, there is a right inverse f:B\to A of g such that g\circ f=\operatorname{Id} _ {B}. (Note that this part uses axiom of choice.) Therefore f has a left inverse, indicating f:B\to A is injective. Thus B\preccurlyeq A.
We continue to prove Theorem 10, which also requires the axiom of choice. Suppose \mathcal A is countable and each element of \mathcal A is also countable. We may assume further \varnothing\notin\mathcal A and \mathcal A\neq\varnothing. Since \mathcal A is countable, by Theorem 9 there is a mapping g:\mathbb N\to \mathcal A that is surjective. For any n\in\mathbb N, the set g(n)\in\mathcal A is countable and nonempty by assumption, so by Theorem 9 again, there is a surjection from \mathbb N onto g(n).
We must use the axiom of choice to choose for each n such a surjection. Define a mapping F by
\[F:n\mapsto \{h:\mathbb N\to g(n) \mid h(\mathbb N)=g(n) \}.\]
Then F(n) is nonempty for every n\in\mathbb N. Hence we obtain a relation \mathcal R with domain \mathbb N: \mathcal R=\{(n,h)\mid h\in F(n)\}. By axiom of choice, there is a mapping G with domain \mathbb N such that G(n)\in F(n) for every n\in\mathbb N, indicating G(n) is a surjection from \mathbb N onto g(n).
Define a mapping H on \mathbb N\times\mathbb N by H(n,m)=G(n)(m). Then H(n,\mathbb N):=G(n)(\mathbb N)=g(n) and H(\mathbb N\times\mathbb N)=g(\mathbb N). We have known g(\mathbb N)=\bigcup \mathcal A, so H is a surjection from \mathbb N\times\mathbb N onto g(\mathbb N)=\bigcup \mathcal A. Since \mathbb N\times\mathbb N\sim\mathbb N, we can obtain a surjection from \mathbb N onto \bigcup \mathcal A. By Theorem 9, \bigcup \mathcal A is countable.
Theorem 10 is proved.
.
This theorem is powerful. We prove the two propositions following it.
Given a set A, the set A^{<\mathbb N} of finite sequences in A is defined by
\[A^{<\mathbb N}=\{f:\mathbb N _ {<n}\to A\mid n\in\mathbb N\}.\]
This is a legal set since a finite sequence is a subset of \mathbb N\times A and therefore A^{<\mathbb N} is a subset of \mathcal P(\mathbb N\times A). If A=\mathbb N, then A^{<\mathbb N}=\mathbb N^{<\mathbb N} consists of all finite sequences of \mathbb N. For a fixed length n\in\mathbb N, the set A _ n:=\{f:\mathbb N _ {<n}\to \mathbb N\}\sim\mathbb N^{n} is countable. Therefore \bigcup _ {n\in\mathbb N} A _ n=\mathbb N^{<\mathbb N} is countable. It is easy to see A^{<\mathbb N} is infinite, so it has cardinal number \aleph _ 0. With the same argument, if A is countable then A^{<\mathbb N} is countable.
Next we consider the cardinal number of the set of algebraic numbers. Let P be the set of non-zero polynomials with integer coefficients. The coefficients of such a polynomial is a finite sequence in \mathbb Z. Therefore we can map a polynomial to \mathbb Z^{<\mathbb N}. This mapping is clearly injective, so P\preccurlyeq\mathbb Z^{<\mathbb N}. It is easy to see that |\mathbb Z|=\aleph _ 0, so |P|\leqslant|\mathbb Z^{<\mathbb N}|\leqslant\aleph _ 0, indicating P is countable. A polynomial has finitely many roots, so the set of algebraic numbers is a countable union of finite sets. Hence it is countable. It is also infinite, so it has cardinal number \aleph _ 0.
We have known \mathbb R is uncountable. Then the set of transcendental numbers is uncountable.□
1. The cardinal number of |R
First we need a simple result. Recall that 2^{\mathbb N}=\{0,1\}^{\mathbb N} is the set of all functions from \mathbb N to \{0,1\}.
To prove the first proposition, we can define a mapping f:\mathcal P(A)\to 2^A by assigning each subset of A the corresponding indicator function. Specifically, if B\subseteq A, then f(B)(x)=1 if x\in B and f(B)(x)=0 if x\in A\setminus B. Clearly this is a one-to-one correspondence.
To prove the second proposition we show that 2^{\mathbb N}\preccurlyeq\mathbb R and \mathbb R\preccurlyeq 2^{\mathbb N}. The first statement 2^{\mathbb N}\preccurlyeq\mathbb R has been shown in the proof of Theorem 5, by mapping 2^{\mathbb N} injectively into [0,1), which is equinumerous to \mathbb R. Therefore we only need an injection from \mathbb R\sim(0,1) into 2^\mathbb N. Again we use the property of the real numbers in (0,1) that they all have a binary expansion, e.g. 0.0101\cdots _ 2. Using the binary digits we construct an injection into 2^\mathbb N. For example 0.0101\cdots _ 2 is mapped to 0,1,0,1,\cdots. The fact that a number may have different expansions such as 0.1 _ 2=0.0111\cdots _ 2 does not affect the proof here. We can simply choose the infinite expansion every time.□
.
The cardinal number of \mathbb N is \aleph _ 0. It seems natural to write |\mathbb R|=2^{\aleph _ 0}. To give it a precise meaning, we need some preparation.
To verify this is a well-defined definition, we need to show the result of this operation is unchanged if A (or B) is replaced by another set with the same cardinal number |A| (or |B|). This is not difficult to show.
Suppose A _ 1\sim A _ 2 and B _ 1\sim B _ 2. We can show there is a bijection from B _ 1^{A _ 1} onto B _ 2^{A _ 2}, indicating |B _ 1^{A _ 1}|=|B _ 2^{A _ 2}|. Let f be a mapping from A _ 1 to B _ 1. Since A _ 1\sim A _ 2 and B _ 1\sim B _ 2, there are bijections \varphi _ A: A _ 1\to A _ 2 and \varphi _ B: B _ 1\to B _ 2. Then we have a mapping \varphi _ B\circ f\circ\varphi _ A^{-1} from A _ 2 to B _ 2, so we define
\begin{align*}
F:B _ 1^{A _ 1}&\to B _ 2^{A _ 2}\\
f&\mapsto \varphi _ B\circ f\circ\varphi _ A^{-1}.
\end{align*}
Then F is surjective, because for any g:A _ 2\to B _ 2 we have \varphi _ B^{-1}\circ g\circ\varphi _ A\in B _ 1^{A _ 1} and F(\varphi _ B^{-1}\circ g\circ\varphi _ A)=g. To show F is also injective, suppose F(f _ 1)=F(f _ 2), i.e., \varphi _ B\circ f _ 1\circ\varphi _ A^{-1}=\varphi _ B\circ f _ 2\circ\varphi _ A^{-1}. By composition we obtain f _ 1=f _ 2, so F is injective. Since F is bijective, B _ 1^{A _ 1}\sim B _ 2^{A _ 2}.
This operation has some reasonable properties. For example, it coincides with the usual exponential operation if A,B are finite. This is not proved here for we haven't developed the theory of natural numbers yet, but it makes intuitive sense.
Some times the cardinal number of \mathbb R is denoted by \mathfrak c, meaning the cardinal number of continuum. Now we can write
\[\mathfrak c=2^{\aleph _ 0}.\]
1.1. Continuum Hypothesis The cardinal number of a countable set A satisfies |A|\leqslant\aleph _ 0. On the other hand, many examples of uncountable sets have cardinal number at least 2^{\aleph _ 0}. Then, is there a cardinal number between \aleph _ 0 and 2^{\aleph _ 0}? The continuum hypothesis states that the answer is negative.
Continuum Hypothesis: There is no set A such that \aleph _ 0<|A|<2^{\aleph _ 0}.
Cantor believed the continuum hypothesis (CH) to be true and for many years tried in vain to prove it. Gödel proved that the continuum hypothesis cannot be disproved in standard set theory, and later Cohen proved that the
continuum hypothesis could not be proved either.
New axioms are needed if we want to prove or disprove the CH. But is it worth doing it? The axiom of choice is widely accepted because it agrees with our informal intuition, and has many important consequences in many fields of mathematics. But the CH is less intuitive. It feels neither obviously true nor obviously false. However a candidate of axiom should closely match our intuitive, pre-axiomatic understanding of the concepts involved. Therefore it is unreasonable to accept CH as an axiom. Although it is still possible that there are suitable axioms that imply CH or refute CH, currently we leave it independent from our axiom list.
发表回复