集合论：证明集合为可数集

编程入门行业动态更新时间:2024-10-26 06:29:23

集合论：证明集合为可数集

集合论

前言
对等
- 定义：对等、基数
- 性质
- - 定理1
  - 定理2：伯恩斯坦(Bernstein)定理
总结
- 例题

前言

数学，可是它懵逼双眼——《学 diss math》2023.6.6。

~ 福建大夏天气太热有感
汤谷黑齿北，一木十金乌。
彭者望其背，霞举还天枢。
感乎东极外，扶桑花正晖。
心景明复灭，天光古希窥。
少年青云志，意气四海行。
亟欲剑阁试，弓攥矢尤腥。
归尘亦狂酒，谈笑死生情。
老大历诸事，方知不年轻。
入世尚自哂，出世何宏图。
拳少八极力，文输诸葛庐。
冷铁多卷刃，言语总低俗。
不期堂前燕，万里语同君。
但求夜寐时，梦里无穷困。

对等

定义：对等、基数

1 ) \boldsymbol {1)} 1)若 A , B A,B A,B是非空集合，且存在双射 φ : A → B \varphi:A\rightarrow B φ:A→B，则称 A \boldsymbol A A与 B \boldsymbol B B对等，记为 A ∼ B ‾ \underline{A\sim B} A∼B.
2 ) \boldsymbol {2)} 2)若 A , B A,B A,B对等，则称 A , B A,B A,B具有相同的基数，记为 A = = B = \overset{=}{A}=\overset{=}{B} A==B=;
\quad 若 A , B A,B A,B不对等，但 ∃ B ∗ ⊊ B \exists B^* \subsetneq B ∃B∗⊊B， s . t . A ∼ B ∗ s.t. ~A\sim B^* s.t. A∼B∗，则称 A A A比 B B B有较小的基数 ( B B B比 A A A有较大的基数)，记为 A = < B = ( \overset{=}{A}<\overset{=}{B}~( A=<B= (或 B = > A = ) \overset{=}{B}>\overset{=}{A}) B=>A=).

性质

定理1

任何集合 A , B , C A,B,C A,B,C，均有
（1） A ∼ A A\sim A A∼A (自反性)；
（2）若 A ∼ B A\sim B A∼B，则 B ∼ A B\sim A B∼A (对称性)；
（3）若 A ∼ B , B ∼ C A\sim B,B\sim C A∼B,B∼C，则 A ∼ C A\sim C A∼C (传递性).

证明：若 ∃ A ∗ ⊆ A \exists A^* \subseteq A ∃A∗⊆A， s . t . B ∼ A ∗ s.t. ~B\sim A^* s.t. B∼A∗，那么 B = ≤ A = \overset{=}{B}\le\overset{=}{A} B=≤A=.
1）当 A , B A,B A,B不对等时，显然 A ∗ ≠ A A^* \ne A A∗=A，于是有 B = < A = \overset{=}{B} < \overset{=}{A} B=<A=；
2）当 A A A和 B B B对等时，根据传递性，有 A ∗ ∼ A A^*\sim A A∗∼A，显然 B = = A = \overset{=}{B} = \overset{=}{A} B==A=，
故， B = ≤ A = \overset{=}{B}\le\overset{=}{A} B=≤A=。

定理2：伯恩斯坦(Bernstein)定理

设 A A A和 B B B是两个非空集合。若 ∃ A ∗ ⊆ A , B ∗ ⊆ B \exists A^* \subseteq A,B^* \subseteq B ∃A∗⊆A,B∗⊆B， s . t . B ∼ A ∗ , A ∼ B ∗ s.t. ~B\sim A^*,A\sim B^* s.t. B∼A∗,A∼B∗，那么 A ∼ B A\sim B A∼B.

证明：根据假设，存在双射 φ 1 : A → B 1 ( B 1 ⊆ B ) \varphi_1:A\rightarrow B_1(B_1\subseteq B) φ1:A→B1(B1⊆B) 及 φ 2 : B → A 1 ( A 1 ⊆ A ) \varphi_2:B\rightarrow A_1(A_1\subseteq A) φ2:B→A1(A1⊆A)。
因为 B 1 ⊆ B B_1\subseteq B B1⊆B，记 A 2 = φ 2 ( B 1 ) A_2=\varphi_2(B_1) A2=φ2(B1)，显然， A 2 ⊆ A 1 A_2\subseteq A_1 A2⊆A1，并且 φ 2 \varphi_2 φ2也是 B 1 B_1 B1到 A 2 A_2 A2上的双射，于是有
A ∼ φ 1 B 1 ∼ φ 2 A 2 ( A 2 ⊆ A ) A \overset{\varphi_1}{\sim} B_1 \overset{\varphi_2}{\sim} A_2 ~ (A_2\subseteq A) A∼φ1B1∼φ2A2 (A2⊆A)

即，存在复合映射 φ 2 ∘ φ 1 = φ : A → A 2 \varphi_2\circ\varphi_1=\varphi:A\rightarrow A_2 φ2∘φ1=φ:A→A2，使得 A ∼ φ A 2 A \overset{\varphi}{\sim} A_2 A∼φA2.
记 A 3 = φ ( A 1 ) A_3=\varphi(A_1) A3=φ(A1)，同理，有 A 3 ⊆ A 2 A_3\subseteq A_2 A3⊆A2，反复进行这样的操作，可得一列子集
A ⊇ A 1 ⊇ A 2 ⊇ ⋯ ⊇ A n ⊃ ⋯ A\supseteq A_1 \supseteq A_2 \supseteq \cdots \supseteq A_n \supset \cdots A⊇A1⊇A2⊇⋯⊇An⊃⋯

将集合 A , A 1 A,A_1 A,A1分解为互不相交的集合的并集，有
{ A = ( A − A 1 ) ∪ ( A 1 − A 2 ) ∪ ⋯ ∪ ( A n − A n + 1 ) ∪ ⋯ ∪ D A 1 = ( A 1 − A 2 ) ∪ ⋯ ∪ ( A n − A n + 1 ) ∪ ⋯ ∪ D 1 \left\{ \begin{aligned} A &= (A-A_1)\cup (A_1-A_2)\cup \cdots \cup (A_n - A_{n+1}) \cup \cdots \cup D \\ A_1 &= (A_1-A_2)\cup \cdots \cup (A_n - A_{n+1}) \cup \cdots \cup D_1 \end{aligned} \right. {AA1=(A−A1)∪(A1−A2)∪⋯∪(An−An+1)∪⋯∪D=(A1−A2)∪⋯∪(An−An+1)∪⋯∪D1

其中，
{ D = A ∩ A 1 ∩ A 2 ∩ ⋯ ∩ A n ∩ ⋯ D 1 = A 1 ∩ A 2 ∩ ⋯ ∩ A n ∩ ⋯ \left\{ \begin{aligned} D &= A \cap A_1 \cap A_2 \cap \cdots \cap A_n \cap \cdots \\ D_1 &= A_1 \cap A_2 \cap \cdots \cap A_n \cap \cdots \end{aligned} \right. {DD1=A∩A1∩A2∩⋯∩An∩⋯=A1∩A2∩⋯∩An∩⋯

显然， D = A ∩ D 1 D=A\cap D_1 D=A∩D1，因为 A ⊇ A i ( i = 1 , 2 , ⋯ ) A\supseteq A_i(i=1,2,\cdots) A⊇Ai(i=1,2,⋯)，故 D = D 1 D=D_1 D=D1.
又因为，映射 φ \varphi φ是 A i − 1 − A i A_{i-1}-A_i Ai−1−Ai上到 A i + 1 − A i + 2 A_{i+1}-A_{i+2} Ai+1−Ai+2的双射 ( i = 1 , 2 , ⋯ ) (i=1,2,\cdots) (i=1,2,⋯)，故
A i − 1 − A i ∼ A i + 1 − A i + 2 A_{i-1}-A_i \sim A_{i+1}-A_{i+2} Ai−1−Ai∼Ai+1−Ai+2

于是，有
A = ( A − A 1 ) ∪ ( A 1 − A 2 ) ⋯ ( A 2 n − A 2 n + 1 ) ∪ ( A 2 n + 1 − A 2 n + 2 ) ⋯ ∪ D A 1 = ( A 2 − A 3 ) ∪ ( A 1 − A 2 ) ⋯ ( A 2 n + 2 − A 2 n + 3 ) ∪ ( A 2 n + 1 − A 2 n + 2 ) ⋯ ∪ D \begin{aligned} A &= (A-A_1)\cup (A_1-A_2) \cdots (A_{2n} - A_{2n+1}) \cup (A_{2n+1} - A_{2n+2}) \cdots \cup D \\ A_1 &= (A_2-A_3)\cup (A_1-A_2) \cdots (A_{2n+2} - A_{2n+3}) \cup (A_{2n+1} - A_{2n+2}) \cdots \cup D \end{aligned} AA1=(A−A1)∪(A1−A2)⋯(A2n−A2n+1)∪(A2n+1−A2n+2)⋯∪D=(A2−A3)∪(A1−A2)⋯(A2n+2−A2n+3)∪(A2n+1−A2n+2)⋯∪D

故， A ∼ A 1 ∼ B A\sim A_1 \sim B A∼A1∼B，推得 A ∼ B A\sim B A∼B.
反证法
假设 A , B A,B A,B不对等，且 A = > B = \overset{=}{A}>\overset{=}{B} A=>B=，则
不存在 B ∗ ⊆ B B^* \subseteq B B∗⊆B，使得 B ∗ ∼ A B^* \sim A B∗∼A，与条件矛盾，
故， A ∼ B A\sim B A∼B.

总结

要证明集合为可数集，一般思路就是证明集合与自然数集对等。
但可数集，有时也指代有限集和无限可数集，下面是该情况的例题。

例题

设 f : [ 0 , 1 ] → R f:[0,1]\rightarrow R f:[0,1]→R 满足对任意的正整数 n n n，任意的 x 1 , x 2 , ⋯ , x n ∈ [ 0 , 1 ] ( x i ≠ x j ) x_1,x_2,\cdots,x_n \in [0,1]~(x_i\ne x_j) x1,x2,⋯,xn∈[0,1] (xi=xj) 均有 ∣ f ( x 1 ) + f ( x 2 ) + . . . f ( x n ) ∣ ≤ M |f(x_1)+f(x_2)+...f(x_n)|\le M ∣f(x1)+f(x2)+...f(xn)∣≤M，其中 M M M为常数，则证明： { x ∈ [ 0 , 1 ] ∣ f ( x ) ≠ 0 } \{x\in [0,1] \mid f(x)≠0\} {x∈[0,1]∣f(x)=0}为可数集

注：题中的“可数”指至多可数。

证明：根据题意，不妨记 A k = { x ∈ [ 0 , 1 ] ∣ ∣ f ( x ) ∣ > 1 k } A_k=\{x\in [0,1] \mid |f(x)|>\frac 1k \} Ak={x∈[0,1]∣∣f(x)∣>k1}，显然有
{ x ∈ [ 0 , 1 ] ∣ f ( x ) ≠ 0 } = ⋃ k = 1 ∞ A k \{x\in [0,1] \mid f(x)≠0\} = \bigcup_{k=1}^\infty A_k {x∈[0,1]∣f(x)=0}=k=1⋃∞Ak 假设 ∃ m > 0 , m ∈ N \exists m > 0 ,m\in \mathbb N ∃m>0,m∈N，使得集合 A m A_m Am为不可数集，则 A m A_m Am存在可列子集 A m ∗ = { x 1 , x 2 , ⋯ , x n , ⋯ } A_m^* = \{ x_1, x_2, \cdots, x_n, \cdots \} Am∗={x1,x2,⋯,xn,⋯}，其中必有
x ∈ A m ∗ : f ( x ) > 1 m ∨ f ( x ) < − 1 m x\in A_m^* : f(x)>\frac 1m \vee f(x)<-\frac1m x∈Am∗:f(x)>m1∨f(x)<−m1于是，
1 ◯ {\textcircled{\small {1} } } 1◯若 A m ∗ A_m^* Am∗中存在无限个元素 x x x，使得 f ( x ) > 1 m f(x)>\frac1m f(x)>m1，
显然，对于 A m ∗ A_m^* Am∗的可列子集 S = { x ∈ A m ∗ : f ( x ) > 1 m } S=\{ x\in A_m^*: f(x)>\frac1m \} S={x∈Am∗:f(x)>m1}，不满足 ∃ M > 0 , ∀ x i ∈ S , ∣ ∑ i = 0 n f ( x i ) ∣ < M \exists M>0,\forall x_i\in S, |\sum_{i=0}^nf(x_i)|<M ∃M>0,∀xi∈S,∣∑i=0nf(xi)∣<M；

2 ◯ {\textcircled{\small {2} } } 2◯若 A m ∗ A_m^* Am∗中存在有限个元素 x x x，使得 f ( x ) > 1 m f(x)>\frac1m f(x)>m1，
则 A m ∗ A_m^* Am∗中存在无限个元素 x x x，使得 f ( x ) < − 1 m f(x)<-\frac1m f(x)<−m1时，同理，结论不成立；

故， A m ∗ A_m^* Am∗中存在有限个元素 x x x，使得 ∣ f ( x ) ∣ > 1 m |f(x)|>\frac1m ∣f(x)∣>m1，即 ∀ k ∈ N + , A k \forall k\in \mathbb N^+, A_k ∀k∈N+,Ak为有限集， ⋃ k = 1 ∞ A k \bigcup_{k=1}^\infty A_k ⋃k=1∞Ak是可数集。
所以， { x ∈ [ 0 , 1 ] ∣ f ( x ) ≠ 0 } \{x\in [0,1] \mid f(x)≠0\} {x∈[0,1]∣f(x)=0}为可数集