用來比較集合的函數
設 f : X → Y f:X\to Y f : X → Y
f ( X ) = { f ( x ) ∣ x ∈ X } ⊆ Y , f(X)=\{f(x)\mid x\in X\}\subseteq Y, f ( X ) = { f ( x ) ∣ x ∈ X } ⊆ Y , 對 B ⊆ Y B\subseteq Y B ⊆ Y
f − 1 ( B ) = { x ∈ X ∣ f ( x ) ∈ B } . f^{-1}(B)=\{x\in X\mid f(x)\in B\}. f − 1 ( B ) = { x ∈ X ∣ f ( x ) ∈ B } . 記號 f − 1 ( y ) f^{-1}(y) f − 1 ( y ) { y } \{y\} { y }
定義
單射、滿射與雙射 函數 f : X → Y f:X\to Y f : X → Y 單射 ，如果
f ( x 1 ) = f ( x 2 ) ⟹ x 1 = x 2 ( x 1 , x 2 ∈ X ) . f(x_1)=f(x_2)\Longrightarrow x_1=x_2
\qquad (x_1,x_2\in X). f ( x 1 ) = f ( x 2 ) ⟹ x 1 = x 2 ( x 1 , x 2 ∈ X ) . 因此 Y Y Y 滿射 ，如果
∀ y ∈ Y ∃ x ∈ X 使得 f ( x ) = y , \forall y\in Y\;\exists x\in X\text{ 使得 }f(x)=y, ∀ y ∈ Y ∃ x ∈ X 使得 f ( x ) = y , 等價地說 f ( X ) = Y f(X)=Y f ( X ) = Y 雙射 。
陪域很重要。例如 f : N → N f:N\to N f : N → N f ( n ) = n + 1 f(n)=n+1 f ( n ) = n + 1 0 0 0 N ∖ { 0 } N\setminus\{0\} N ∖ { 0 }
例題
檢查三種性質 考慮 u : { 0 , 1 , 2 } → { a , b , c , d } u:\{0,1,2\}\to\{a,b,c,d\} u : { 0 , 1 , 2 } → { a , b , c , d }
u ( 0 ) = a , u ( 1 ) = c , u ( 2 ) = a . u(0)=a,\qquad u(1)=c,\qquad u(2)=a. u ( 0 ) = a , u ( 1 ) = c , u ( 2 ) = a . 它不是單射，因為 u ( 0 ) = u ( 2 ) u(0)=u(2) u ( 0 ) = u ( 2 ) 0 ≠ 2 0\ne2 0 = 2 b b b d d d
相同基數與可數性
概念視角 結構
把基數理解為數數與配對 對於有限集合，大小很容易令人聯想到清點：把元素逐一數出來。對於任意集合，定義則把這種清點改成配對檢驗：能否把 X X X Y Y Y N N N 2 N = { 0 , 2 , 4 , … } 2N=\{0,2,4,\ldots\} 2 N = { 0 , 2 , 4 , … } n ↦ 2 n n\mapsto 2n n ↦ 2 n 2 N 2N 2 N N N N
定義
相同基數 若存在雙射 f : X → Y f:X\to Y f : X → Y X X X Y Y Y 相同基數 ，並寫成
∣ X ∣ = ∣ Y ∣ |X|=|Y| ∣ X ∣ = ∣ Y ∣ 被配對的元素不必具有相同性質。把數與有序對配對，與把兩列數字配對一樣合
法。對有限集合，這個定義與普通數數一致。
定義
有限集合 若某個 n ∈ N n\in N n ∈ N ∣ X ∣ = ∣ n ∣ |X|=|n| ∣ X ∣ = ∣ n ∣ n n n n = { 0 , … , n − 1 } n=\{0,\ldots,n-1\} n = { 0 , … , n − 1 } n = 0 n=0 n = 0 n = ∅ n=\varnothing n = ∅ X X X 有限集合 ，並寫 ∣ X ∣ = n |X|=n ∣ X ∣ = n ∣ ∅ ∣ = 0 |\varnothing|=0 ∣ ∅ ∣ = 0
定義
可數與至多可數 在本課程中，如果 X X X
∣ X ∣ = ∣ N ∣ |X|=|N| ∣ X ∣ = ∣ N ∣ 就稱 X X X 可數 。等價地，若 X X X 至多可數 。有
些教材只把無限情形稱為 countable，因此「至多可數」可以消除這種約定差異。
不是至多可數的集合稱為不可數 。
對可數無限集合來說，一個列舉是序列 x 0 , x 1 , x 2 , … x_0,x_1,x_2,\ldots x 0 , x 1 , x 2 , …
可數集合的明確列舉
整數
設 N = { 0 , 1 , 2 , … } N=\{0,1,2,\ldots\} N = { 0 , 1 , 2 , … }
e ( 0 ) = 0 , e ( 2 k − 1 ) = k , e ( 2 k ) = − k ( k ≥ 1 ) e(0)=0,\qquad e(2k-1)=k,\qquad e(2k)=-k\quad(k\ge1) e ( 0 ) = 0 , e ( 2 k − 1 ) = k , e ( 2 k ) = − k ( k ≥ 1 ) 這給出序列 0 , 1 , − 1 , 2 , − 2 , 3 , − 3 , … 0,1,-1,2,-2,3,-3,\ldots 0 , 1 , − 1 , 2 , − 2 , 3 , − 3 , …
證明。 每個整數或者是 0 0 0 k k k k ≥ 1 k\ge1 k ≥ 1 − k -k − k 0 0 0 2 k − 1 2k-1 2 k − 1 2 k 2k 2 k e e e k k k e e e e e e N N N 1 1 1
這個例子體現無限集合的基本驚訝之處：把所有負整數加入 N N N
有理數
定理
有理數是可數的 有理數集合 Q Q Q
每個正有理數都有唯一的最簡表示 p / q p/q p / q p , q ∈ { 1 , 2 , 3 , … } p,q\in\{1,2,3,\ldots\} p , q ∈ { 1 , 2 , 3 , … } gcd ( p , q ) = 1 \gcd(p,q)=1 g cd( p , q ) = 1 p / q p/q p / q p p p q q q p + q = 2 , 3 , 4 , … p+q=2,3,4,\ldots p + q = 2 , 3 , 4 , …
1 , 1 2 , 2 , 1 3 , 3 , 1 4 , 2 3 , 3 2 , 4 , … . 1,\ \frac12,\ 2,\ \frac13,\ 3,\ \frac14,\ \frac23,\ \frac32,\ 4,\ldots. 1 , 2 1 , 2 , 3 1 , 3 , 4 1 , 3 2 , 2 3 , 4 , … . 例題
為甚麼有理數的對角掃描有效 例如 7 / 5 7/5 7/5 p + q = 12 p+q=12 p + q = 12 7 / 5 7/5 7/5 ( p , q ) (p,q) ( p , q ) Q + Q_+ Q +
這個論證同時證明了兩個方向。每個正有理數都有最簡數對，所以沒有遺漏；最
簡數對唯一，所以沒有重複。若所得列舉為 q 1 , q 2 , q 3 , … q_1,q_2,q_3,\ldots q 1 , q 2 , q 3 , …
0 , q 1 , − q 1 , q 2 , − q 2 , q 3 , − q 3 , … 0,q_1,-q_1,q_2,-q_2,q_3,-q_3,\ldots 0 , q 1 , − q 1 , q 2 , − q 2 , q 3 , − q 3 , … 列出每個有理數恰好一次。零出現一次，每個非零有理數都有唯一的符號和唯一
的正絕對值。因此 Q Q Q n ↦ n n\mapsto n n ↦ n N N N Q Q Q Q Q Q
圖示。對角掃描把二維格點變成一條序列；最簡形式條件消除了同一個有理數
的不同表示。
稠密性是另一個性質。有理數與實線的每個非空開區間相交，但對角線程序仍然
能把它們放入一條序列。稠密不等於不可數。
可數集合的乘積
網格論證也給出兩個 N N N a , b ∈ N a,b\in N a , b ∈ N
π ( a , b ) = ( a + b ) ( a + b + 1 ) 2 + b \pi(a,b)=\frac{(a+b)(a+b+1)}2+b π ( a , b ) = 2 ( a + b ) ( a + b + 1 ) + b 滿足固定 a + b = s a+b=s a + b = s s ( s + 1 ) / 2 s(s+1)/2 s ( s + 1 ) /2 π \pi π n = π ( a , b ) n=\pi(a,b) n = π ( a , b ) s s s s ( s + 1 ) / 2 ≤ n < ( s + 1 ) ( s + 2 ) / 2 s(s+1)/2\le n\lt(s+1)(s+2)/2 s ( s + 1 ) /2 ≤ n < ( s + 1 ) ( s + 2 ) /2 b = n − s ( s + 1 ) / 2 b=n-s(s+1)/2 b = n − s ( s + 1 ) /2 a = s − b a=s-b a = s − b π : N × N → N \pi:N\times N\to N π : N × N → N
定理
可數三元組仍然可數 ∣ N × N × N ∣ = ∣ N ∣ |N\times N\times N|=|N| ∣ N × N × N ∣ = ∣ N ∣
證明。 定義
Φ ( a , b , c ) = π ( π ( a , b ) , c ) \Phi(a,b,c)=\pi(\pi(a,b),c) Φ ( a , b , c ) = π ( π ( a , b ) , c ) 兩次使用的 π \pi π N 3 N^3 N 3 N N N ( π ( a , b ) , c ) (\pi(a,b),c) ( π ( a , b ) , c ) ( a , b ) (a,b) ( a , b ) N N N
同一個配對也能處理有限個帶標籤的可數集合。例如用
( n , i ) ↦ π ( n , i ) (n,i)\mapsto\pi(n,i) ( n , i ) ↦ π ( n , i ) ( n , 0 ) (n,0) ( n , 0 ) ( n , 1 ) (n,1) ( n , 1 ) N N N N N N N N N
更一般地，基數比較可以沿映射傳遞。若 X → Y X\to Y X → Y Y → Z Y\to Z Y → Z ∣ X ∣ ≤ ∣ Z ∣ |X|\le|Z| ∣ X ∣ ≤ ∣ Z ∣
基數不等式
定義
基數不等式 對集合 X X X Y Y Y X → Y X\to Y X → Y
∣ X ∣ ≤ ∣ Y ∣ |X|\le |Y| ∣ X ∣ ≤ ∣ Y ∣ 若 ∣ X ∣ ≤ ∣ Y ∣ |X|\le|Y| ∣ X ∣ ≤ ∣ Y ∣ ∣ X ∣ ≠ ∣ Y ∣ |X|\ne|Y| ∣ X ∣ = ∣ Y ∣ ∣ X ∣ < ∣ Y ∣ |X|\lt|Y| ∣ X ∣ < ∣ Y ∣
箭頭方向不可忽略：從 X X X Y Y Y Y Y Y X X X N → Z N\to Z N → Z n ↦ n n\mapsto n n ↦ n ∣ N ∣ ≤ ∣ Z ∣ |N|\le|Z| ∣ N ∣ ≤ ∣ Z ∣
例題
陪域有未使用元素的有限比較 定義 r : { 1 , 2 , 3 } → { a , b , c , d } r:\{1,2,3\}\to\{a,b,c,d\} r : { 1 , 2 , 3 } → { a , b , c , d } r ( 1 ) = b r(1)=b r ( 1 ) = b r ( 2 ) = d r(2)=d r ( 2 ) = d r ( 3 ) = a r(3)=a r ( 3 ) = a ∣ { 1 , 2 , 3 } ∣ ≤ ∣ { a , b , c , d } ∣ |\{1,2,3\}|\le|\{a,b,c,d\}| ∣ { 1 , 2 , 3 } ∣ ≤ ∣ { a , b , c , d } ∣ c c c
定理
基數不等式具有偏序結構 基數上的關係 ≤ \le ≤ < \lt <
證明。 恆等映射 i d X : X → X id_X:X\to X i d X : X → X f : X → Y f:X\to Y f : X → Y g : Y → Z g:Y\to Z g : Y → Z g ∘ f g\circ f g ∘ f f f f ∣ X ∣ = ∣ X ∣ |X|=|X| ∣ X ∣ = ∣ X ∣ ∣ X ∣ < ∣ X ∣ |X|\lt|X| ∣ X ∣ < ∣ X ∣ ≤ \le ≤
不存在一個以所有集合為元素的集合。假設有這樣的全集，就可以構造
Russell 類型的自指成員關係而得到矛盾。因此，這裏的 ≤ \le ≤
滿射 X → Y X\to Y X → Y Y Y Y X X X Y → X Y\to X Y → X y ∈ Y y\in Y y ∈ Y
Cantor-Bernstein：把兩個單射拼起來
定理
Cantor-Bernstein 定理 若 f : X → Y f:X\to Y f : X → Y g : Y → X g:Y\to X g : Y → X ∣ X ∣ = ∣ Y ∣ |X|=|Y| ∣ X ∣ = ∣ Y ∣
若所有點都使用 f f f Y Y Y g − 1 g^{-1} g − 1 g ( Y ) g(Y) g ( Y ) g ( Y ) g(Y) g ( Y ) f f f x x x f f f g ( f ( x ) ) g(f(x)) g ( f ( x )) g − 1 g^{-1} g − 1 g ∘ f g\circ f g ∘ f
令
A 0 = X , B 0 = g ( Y ) , A_0=X,\qquad B_0=g(Y), A 0 = X , B 0 = g ( Y ) , 再遞歸定義後續各項。這與
3.2 歸納法與遞歸算術
一樣，由初值和後繼規則確定整個序列：
A n + 1 = g ( f ( A n ) ) , B n + 1 = g ( f ( B n ) ) . A_{n+1}=g(f(A_n)),\qquad B_{n+1}=g(f(B_n)). A n + 1 = g ( f ( A n )) , B n + 1 = g ( f ( B n )) . 由於 g ( Y ) ⊆ X g(Y)\subseteq X g ( Y ) ⊆ X
A 0 ⊇ B 0 ⊇ A 1 ⊇ B 1 ⊇ A 2 ⊇ B 2 ⊇ ⋯ A_0\supseteq B_0\supseteq A_1\supseteq B_1\supseteq A_2\supseteq B_2\supseteq\cdots A 0 ⊇ B 0 ⊇ A 1 ⊇ B 1 ⊇ A 2 ⊇ B 2 ⊇ ⋯ 這些包含關係可以歸納得到：先有 A 1 ⊆ B 0 A_1\subseteq B_0 A 1 ⊆ B 0 B n + 1 ⊆ A n + 1 B_{n+1}\subseteq A_{n+1} B n + 1 ⊆ A n + 1 A n ⊆ B n − 1 A_n\subseteq B_{n-1} A n ⊆ B n − 1 A n + 1 ⊆ B n A_{n+1}\subseteq B_n A n + 1 ⊆ B n X X X Y Y Y
層 A n ∖ B n A_n\setminus B_n A n ∖ B n f f f g ( Y ) g(Y) g ( Y ) g g g
證明。 首先 g ∘ f : X → X g\circ f:X\to X g ∘ f : X → X n n n A n ∖ B n A_n\setminus B_n A n ∖ B n A n + 1 ∖ B n + 1 A_{n+1}\setminus B_{n+1} A n + 1 ∖ B n + 1 z ∈ A n + 1 ∖ B n + 1 z\in A_{n+1}\setminus B_{n+1} z ∈ A n + 1 ∖ B n + 1 z = g ( f ( x ) ) z=g(f(x)) z = g ( f ( x )) x ∈ A n x\in A_n x ∈ A n x ∈ B n x\in B_n x ∈ B n z ∈ g ( f ( B n ) ) = B n + 1 z\in g(f(B_n))=B_{n+1} z ∈ g ( f ( B n )) = B n + 1 x ∈ A n ∖ B n x\in A_n\setminus B_n x ∈ A n ∖ B n
定義 h : X → Y h:X\to Y h : X → Y
h ( x ) = { f ( x ) , x ∈ A n ∖ B n 對某個 n , g − 1 ( x ) , x ∉ A n ∖ B n 對所有 n h(x)=
\begin{cases}
f(x),&x\in A_n\setminus B_n\text{ 對某個 }n,\\
g^{-1}(x),&x\notin A_n\setminus B_n\text{ 對所有 }n
\end{cases} h ( x ) = { f ( x ) , g − 1 ( x ) , x ∈ A n ∖ B n 對某個 n , x ∈ / A n ∖ B n 對所有 n 這裏 g − 1 g^{-1} g − 1 g : Y → g ( Y ) g:Y\to g(Y) g : Y → g ( Y ) X X X A 0 ∖ B 0 = X ∖ g ( Y ) A_0\setminus B_0=X\setminus g(Y) A 0 ∖ B 0 = X ∖ g ( Y ) g ( Y ) g(Y) g ( Y ) h h h
證明單射性。若 h ( x 1 ) = h ( x 2 ) h(x_1)=h(x_2) h ( x 1 ) = h ( x 2 ) f f f x 1 = x 2 x_1=x_2 x 1 = x 2 g − 1 g^{-1} g − 1 x 1 ∈ A n ∖ B n x_1\in A_n\setminus B_n x 1 ∈ A n ∖ B n h ( x 2 ) = g − 1 ( x 2 ) h(x_2)=g^{-1}(x_2) h ( x 2 ) = g − 1 ( x 2 ) x 2 = g ( f ( x 1 ) ) x_2=g(f(x_1)) x 2 = g ( f ( x 1 )) x 2 ∈ A n + 1 ∖ B n + 1 x_2\in A_{n+1}\setminus B_{n+1} x 2 ∈ A n + 1 ∖ B n + 1
證明滿射性。任取 y ∈ Y y\in Y y ∈ Y x = g ( y ) ∈ X x=g(y)\in X x = g ( y ) ∈ X x x x h ( x ) = g − 1 ( x ) = y h(x)=g^{-1}(x)=y h ( x ) = g − 1 ( x ) = y x ∈ A n ∖ B n x\in A_n\setminus B_n x ∈ A n ∖ B n X ∖ g ( Y ) X\setminus g(Y) X ∖ g ( Y ) x ∈ g ( Y ) x\in g(Y) x ∈ g ( Y ) n ≥ 1 n\ge1 n ≥ 1 x ′ ∈ A n − 1 ∖ B n − 1 x'\in A_{n-1}\setminus B_{n-1} x ′ ∈ A n − 1 ∖ B n − 1 g ( f ( x ′ ) ) = x = g ( y ) g(f(x'))=x=g(y) g ( f ( x ′ )) = x = g ( y ) g g g f ( x ′ ) = y f(x')=y f ( x ′ ) = y h ( x ′ ) = y h(x')=y h ( x ′ ) = y h h h ∣ X ∣ = ∣ Y ∣ |X|=|Y| ∣ X ∣ = ∣ Y ∣ f f f g g g
冪集與 Cantor 定理
定義
冪集記號 對集合 X X X 2 X 2^X 2 X X X X X X X
因此
T ∈ 2 X T\in 2^X T ∈ 2 X 正是說 T ⊆ X T\subseteq X T ⊆ X
記號 2 X 2^X 2 X X X X n n n 2 n 2^n 2 n
對空集，這個記號已經說明了一個重要的起點：
2 ∅ = { ∅ } . 2^\varnothing=\{\varnothing\}. 2 ∅ = { ∅ } . 空集只有一個子集，就是空集本身。因此有限集合的計數模式
∣ 2 X ∣ = 2 ∣ X ∣ |2^X|=2^{|X|} ∣ 2 X ∣ = 2 ∣ X ∣ 2 0 = 1 2^0=1 2 0 = 1
構造列表遺漏的子集
設 f : X → 2 X f:X\to2^X f : X → 2 X X X X f f f x x x f ( x ) f(x) f ( x ) x x x f ( x ) f(x) f ( x ) x x x x x x
下面用 X = { a , b , c } X=\{a,b,c\} X = { a , b , c } f f f 1 1 1 0 0 0
沿對角線讀到 1 , 0 , 1 1,0,1 1 , 0 , 1 0 , 1 , 0 0,1,0 0 , 1 , 0 T = { b } T=\{b\} T = { b } f ( a ) f(a) f ( a ) a a a f ( b ) f(b) f ( b ) b b b f ( c ) f(c) f ( c ) c c c
對任意集合，同一規則就是 x ∈ T x\in T x ∈ T x ∉ f ( x ) x\notin f(x) x ∈ / f ( x ) X X X T T T X X X
Cantor 定理
定理
Cantor 定理 設 X X X
∣ X ∣ < ∣ 2 X ∣ . |X|\lt |2^X|. ∣ X ∣ < ∣ 2 X ∣. 證明分兩部分。
首先，有單射
X → 2 X , x ↦ { x } . X\to 2^X,\qquad x\mapsto \{x\}. X → 2 X , x ↦ { x } . 所以 ∣ X ∣ ≤ ∣ 2 X ∣ |X|\le |2^X| ∣ X ∣ ≤ ∣ 2 X ∣ X = { a , b } X=\{a,b\} X = { a , b } ∅ , { a } , { b } , { a , b } \varnothing,\{a\},\{b\},\{a,b\} ∅ , { a } , { b } , { a , b }
其次，不存在由 X X X 2 X 2^X 2 X f : X → 2 X f:X\to 2^X f : X → 2 X
T = { x ∈ X ∣ x ∉ f ( x ) } . T=\{x\in X\mid x\notin f(x)\}. T = { x ∈ X ∣ x ∈ / f ( x )} . 因為 T T T X X X T ∈ 2 X T\in 2^X T ∈ 2 X f f f y ∈ X y\in X y ∈ X
f ( y ) = T . f(y)=T. f ( y ) = T . 現在考慮 y y y T T T
若 y ∈ T y\in T y ∈ T T T T y ∉ f ( y ) = T y\notin f(y)=T y ∈ / f ( y ) = T
若 y ∉ T y\notin T y ∈ / T T T T y ∈ f ( y ) = T y\in f(y)=T y ∈ f ( y ) = T
兩種情況都不可能。因此不存在雙射 X → 2 X X\to 2^X X → 2 X ∣ X ∣ < ∣ 2 X ∣ |X|\lt |2^X| ∣ X ∣ < ∣ 2 X ∣
當 X = ∅ X=\varnothing X = ∅
證明透視
滿射性用在哪裏 等式 f ( y ) = T f(y)=T f ( y ) = T X X X 2 X 2^X 2 X
實數不可數
定理
實數不可數 實數集合 R R R
∣ N ∣ < ∣ R ∣ . |N|\lt |R|. ∣ N ∣ < ∣ R ∣. 這裏的證明使用 Cantor 定理，以及一個由 2 N 2^N 2 N R R R
由 Cantor 定理，
∣ N ∣ < ∣ 2 N ∣ . |N|\lt |2^N|. ∣ N ∣ < ∣ 2 N ∣. 所以只需證明
∣ 2 N ∣ ≤ ∣ R ∣ . |2^N|\le |R|. ∣ 2 N ∣ ≤ ∣ R ∣. 給定子集 S ⊆ N S\subseteq N S ⊆ N 0 0 0 1 1 1
a n = { 1 , n ∈ S , 0 , n ∉ S . a_n=
\begin{cases}
1, & n\in S,\\
0, & n\notin S.
\end{cases} a n = { 1 , 0 , n ∈ S , n ∈ / S . 然後定義
ϕ ( S ) = ∑ n = 0 ∞ a n 3 n + 1 ∈ [ 0 , 1 ] . \phi(S)=\sum_{n=0}^{\infty}\frac{a_n}{3^{n+1}}\in [0,1]. ϕ ( S ) = n = 0 ∑ ∞ 3 n + 1 a n ∈ [ 0 , 1 ] . 這把 N N N 2 N 2^N 2 N
例題
把 N 的子集編碼成實數 若
S = { 0 , 2 , 5 , … } , S=\{0,2,5,\ldots\}, S = { 0 , 2 , 5 , … } , 則序列開頭為
a 0 = 1 , a 1 = 0 , a 2 = 1 , a 3 = 0 , a 4 = 0 , a 5 = 1. a_0=1,\quad a_1=0,\quad a_2=1,\quad a_3=0,\quad a_4=0,\quad a_5=1. a 0 = 1 , a 1 = 0 , a 2 = 1 , a 3 = 0 , a 4 = 0 , a 5 = 1. 對應的實數開頭可寫成
ϕ ( S ) = 1 3 + 1 3 3 + 1 3 6 + ⋯ . \phi(S)=\frac13+\frac1{3^3}+\frac1{3^6}+\cdots . ϕ ( S ) = 3 1 + 3 3 1 + 3 6 1 + ⋯ . 部分和非遞減且以 1 / 2 1/2 1/2 4.6 小數展開與無理數
中由有限近似確定實數的原理相同，毋須再轉換成十進制。
為甚麼用底數 3 3 3 2 2 2 3 3 3
若 S ≠ S ′ S\ne S' S = S ′ k k k k k k
1 3 k + 1 . \frac1{3^{k+1}}. 3 k + 1 1 . 更精確地，後面尾項的總和至多為
∑ n = k + 1 ∞ 1 3 n + 1 = 1 2 ⋅ 3 k + 1 , \sum_{n=k+1}^{\infty}\frac1{3^{n+1}}
=\frac1{2\cdot 3^{k+1}}, n = k + 1 ∑ ∞ 3 n + 1 1 = 2 ⋅ 3 k + 1 1 , 嚴格小於第一個不同項的差距。因此兩個實數不可能相等。故 ϕ \phi ϕ ∣ 2 N ∣ ≤ ∣ R ∣ |2^N|\le |R| ∣ 2 N ∣ ≤ ∣ R ∣
合併得到
∣ N ∣ < ∣ 2 N ∣ ≤ ∣ R ∣ , |N|\lt |2^N|\le |R|, ∣ N ∣ < ∣ 2 N ∣ ≤ ∣ R ∣ , 所以 R R R
常見錯誤
證明只需要單射到 R 要證明 ∣ 2 N ∣ ≤ ∣ R ∣ |2^N|\le |R| ∣ 2 N ∣ ≤ ∣ R ∣ ϕ \phi ϕ N N N
例題
底數 3 分離的有限版 取兩個在位置 k = 2 k=2 k = 2 1 27 \frac1{27} 27 1
1 3 4 + 1 3 5 + ⋯ = 1 54 , \frac1{3^4}+\frac1{3^5}+\cdots=\frac1{54}, 3 4 1 + 3 5 1 + ⋯ = 54 1 , 只有首個差距的一半，所以首次不同不能被抵消。任意首次不同的位置都可用
同一個幾何級數估計。
反方向固定有理數枚舉
Q = { q 1 , q 2 , … } Q=\{q_1,q_2,\ldots\} Q = { q 1 , q 2 , … }
ρ ( r ) = { n − 1 : n ≥ 1 , q n < r } ⊆ N . \rho(r)=\{n-1:n\ge1,\ q_n\lt r\}\subseteq\mathbb N. ρ ( r ) = { n − 1 : n ≥ 1 , q n < r } ⊆ N . 這把 r r r 4.4 實數公理與第一次近似構造
已證明有理數稠密性：若 r < s r\lt s r < s n n n r < q n < s r\lt q_n\lt s r < q n < s ρ ( r ) ≠ ρ ( s ) \rho(r)\ne\rho(s) ρ ( r ) = ρ ( s ) ρ : R ↪ 2 N \rho:R\hookrightarrow2^N ρ : R ↪ 2 N
確認連續統的基數
記 P ( N ) = 2 N \mathcal P(\mathbb N)=2^{\mathbb N} P ( N ) = 2 N N \mathbb N N c = ∣ R ∣ \mathfrak c=|\mathbb R| c = ∣ R ∣ P ( N ) ↪ R \mathcal P(\mathbb N)\hookrightarrow\mathbb R P ( N ) ↪ R R ↪ P ( N ) \mathbb R\hookrightarrow\mathcal P(\mathbb N) R ↪ P ( N )
c = ∣ R ∣ = ∣ P ( N ) ∣ = 2 ℵ 0 . \mathfrak c=|\mathbb R|=|\mathcal P(\mathbb N)|=2^{\aleph_0}. c = ∣ R ∣ = ∣ P ( N ) ∣ = 2 ℵ 0 . 這裏 2 ℵ 0 2^{\aleph_0} 2 ℵ 0 N \mathbb N N { 0 , 1 } \{0,1\} { 0 , 1 } c = ℵ 1 \mathfrak c=\aleph_1 c = ℵ 1 ℵ 1 \aleph_1 ℵ 1
連續統假設
假設 — 連續統假設.
連續統假設說：不存在集合 S S S
∣ N ∣ < ∣ S ∣ < ∣ R ∣ . |N|\lt |S|\lt |R|. ∣ N ∣ < ∣ S ∣ < ∣ R ∣. 在知道 R R R N N N
這個猜想的地位非常特殊。連續統假設獨立於通常的集合論公理 ZFC。更準確
地說，如果 ZFC 是相容的，那麼 CH 和它的否定都不能由 ZFC 證明：
Godel 的結果給出 ZFC+CH 的相對相容性，Cohen 的 forcing 結果給出
Z F C + ¬ C H ZFC+\neg\mathrm{CH} ZFC + ¬ CH
獨立性不表示這句話沒有意義，也不表示所有基數命題都無法判定。Cantor 定理
和實數不可數性仍是 ZFC 定理；CH 只是詢問它們之間更精細的比較，通常公理沒
有決定這個問題。因此寫證明時，要標出映射方向以及選擇或極大性原理的使用。
可數個可數集合的並仍可數
定理
可數個可數集合的並仍可數 假設選擇公理，若 A n n ∈ N {A_n}_{n\in N} A n n ∈ N A n A_n A n
A = ⋃ n ∈ N A n A=\bigcup_{n\in N} A_n A = n ∈ N ⋃ A n 可數。
若 A = ∅ A=\varnothing A = ∅ N N N A A A A n A_n A n n n n
i n : A n → N . i_n:A_n\to N. i n : A n → N . 當 A n = ∅ A_n=\varnothing A n = ∅ i n {i_n} i n
定義
h : A → N × N , h ( x ) = ( n ( x ) , i n ( x ) ( x ) ) , h:A\to N\times N,\qquad h(x)=(n(x),i_{n(x)}(x)), h : A → N × N , h ( x ) = ( n ( x ) , i n ( x ) ( x )) , 其中
n ( x ) = min { n ∈ N ∣ x ∈ A n } . n(x)=\min\{n\in N\mid x\in A_n\}. n ( x ) = min { n ∈ N ∣ x ∈ A n } . 因為 x x x 6.3 區間、Cantor 集、稠密性與良序 。
映射 h h h h ( x ) = h ( x ′ ) h(x)=h(x') h ( x ) = h ( x ′ ) n ( x ) = n ( x ′ ) = n n(x)=n(x')=n n ( x ) = n ( x ′ ) = n i n ( x ) = i n ( x ′ ) i_n(x)=i_n(x') i n ( x ) = i n ( x ′ ) i n i_n i n x = x ′ x=x' x = x ′
最後，N × N N\times N N × N N × N → N N\times N\to N N × N → N h h h A → N A\to N A → N ( 0 , 0 ) (0,0) ( 0 , 0 ) 1 1 1 2 2 2
常見錯誤
可數並不等於任意並 這個定理處理的是可數族 A n {A_n} A n
我們使用通常的經典集合論框架；討論有序 aleph 基數時包含選擇公理。使用前面材料中的可數性、Cantor 定理、基數比較和連續統假設的定義與結論。
例子
區間的基數是連續統。 映射 x ↦ x / 1 + x 2 x\mapsto x/\sqrt{1+x^2} x ↦ x / 1 + x 2 R \mathbb R R ( − 1 , 1 ) (-1,1) ( − 1 , 1 ) u ↦ u / 1 − u 2 u\mapsto u/\sqrt{1-u^2} u ↦ u / 1 − u 2 ( − 1 , 1 ) (-1,1) ( − 1 , 1 )
無理數集的基數也是連續統。 令 T = { 2 + n : n ∈ Z } T=\{\sqrt2+n:n\in\mathbb Z\} T = { 2 + n : n ∈ Z } Q ∪ T \mathbb Q\cup T Q ∪ T T T T R \mathbb R R Q ∪ T \mathbb Q\cup T Q ∪ T T T T T T T ∣ R ∖ Q ∣ = c |\mathbb R\setminus\mathbb Q|=\mathfrak c ∣ R ∖ Q ∣ = c
稠密性與中間基數問題不同。 有理數稠密且可數；無理數稠密且具有連續統基數。二者都不能決定每個可能的中間大小子集。列舉許多基數為 c \mathfrak c c
練習
P01. 表述。 用基數不等式及關於 R \mathbb R R ℵ 1 \aleph_1 ℵ 1
P02. 證明。 僅使用實數不可數和有理數可數，證明無理數不可數。指出「無理數稠密，所以不可數」的無效推理。
P03. 驗證逆映射。 對 x / 1 + x 2 x/\sqrt{1+x^2} x / 1 + x 2
P04. 邏輯檢查。 有學生說：「實數不可數，ℵ 1 \aleph_1 ℵ 1
P05. 單射與雙射。 解釋映射 r ↦ { q ∈ Q : q < r } r\mapsto\{q\in\mathbb Q:q<r\} r ↦ { q ∈ Q : q < r } c = 2 ℵ 0 \mathfrak c=2^{\aleph_0} c = 2 ℵ 0
P06. 區分結論。 不假設 CH，判斷以下哪些成立：有理數可數；實數不可數；無理數有連續統基數；R \mathbb R R
完整解答
P01. CH 斷言沒有基數嚴格位於 ℵ 0 \aleph_0 ℵ 0 c \mathfrak c c R \mathbb R R ℵ 1 \aleph_1 ℵ 1 c = ℵ 1 \mathfrak c=\aleph_1 c = ℵ 1
P02. 若 Q \mathbb Q Q Q \mathbb Q Q
P03. 對 u = x / 1 + x 2 u=x/\sqrt{1+x^2} u = x / 1 + x 2 1 − u 2 = 1 / ( 1 + x 2 ) > 0 1-u^2=1/(1+x^2)>0 1 − u 2 = 1/ ( 1 + x 2 ) > 0 1 / 1 + x 2 1/\sqrt{1+x^2} 1/ 1 + x 2 u / 1 − u 2 = x u/\sqrt{1-u^2}=x u / 1 − u 2 = x ∣ u ∣ < 1 |u|<1 ∣ u ∣ < 1 x = u / 1 − u 2 x=u/\sqrt{1-u^2} x = u / 1 − u 2 1 + x 2 = 1 / ( 1 − u 2 ) 1+x^2=1/(1-u^2) 1 + x 2 = 1/ ( 1 − u 2 ) x / 1 + x 2 = u x/\sqrt{1+x^2}=u x / 1 + x 2 = u
P04. 不可數不是單一的基數值，只是排除可數大小。ℵ 1 \aleph_1 ℵ 1 ℵ 1 ≤ c \aleph_1\le\mathfrak c ℵ 1 ≤ c
P05. 若 r < s r<s r < s q q q r < q < s r<q<s r < q < s s s s r r r
P06. 前三項分別由前面材料和例子中的枚舉、對角線和可數重排論證得到，不需要 CH。最後一條全稱命題在所述框架下等價於 CH，因此不是前述證明的推論。區別在於具體構造出的雙射，與排除所有中間大小的全稱斷言。
