[离散数学]集合论基础P

第一讲：集合论基础

集合论在数学中占有一个独特的地位，它的基本概念已渗透到数学的所有领域，是基础的基础。

在离散数学中，需要使用集合来表达各类离散量以及离散量之间的关系，所以首先学习集合论是重中之重。

本文可数集合与不可数集合是集合论基础的第五部分。

有限 → \rightarrow →无限，量变 → \rightarrow →质变

有限 1.0 1 365 = 37.783437 0.9 9 365 = 0.025518 1.01^{365}=37.783437 \\ 0.99^{365}=0.025518 1.01365=37.7834370.99365=0.025518 量变

无限 lim ⁡ n → ∞ 1.0 1 n = ∞ lim ⁡ n → ∞ 0.9 9 n = 0 \lim_{n\rightarrow \infty} 1.01^n=\infty \\ \lim_{n\rightarrow \infty} 0.99^n=0 n→∞lim​1.01n=∞n→∞lim​0.99n=0 质变

1891年，意大利数学家皮亚诺公开发表了基于序数的自然数定义公理。这组公理包括：

20世纪初，集合称为数学的基本概念之后，数学奇才，计算机之父冯·诺依曼基于基数，利用一个集合的序列来定义自然数：

空集属于自然数，空集’定义为空集并上以空集作为元素的集合属于自然数。

从而，这个集合序列的基数就可以来定义自然数：

比较下列的集合对，哪一个的元素个数更多？

对于两个有限集合而言，比较二者大小只需要看集合的基数，但对于无限集合却没有这么简单。如何比较无限集合的“大小”呢？这里需要采用一种通过判断两个无限集合之间是否存在一种一一对应的关系来解决这个问题。

设 A , B A,B A,B为两个集合，若在 A , B A,B A,B之间存在一种一一对应的关系： Ψ : A → B \varPsi :A\rightarrow B Ψ:A→B 则称 A A A与 B B B是等势的（equipotential），记作： A ∼ B A \sim B A∼B

由等势定义可以看出，如果 A = B A=B A=B，那么 A ∼ B A \sim B A∼B，反之不成立。

凡与自然数集合 N N N等势的集合，称为可数集合（countable set），该集合的基数记为 ℵ 0 \aleph _0 ℵ0​（读作阿列夫零）

试证明下列集合都是可数集合. (1) O + = { x ∣ x ∈ N , x 是正奇数 } O^+=\left\{ x\left| x\in N, x\text{是正奇数} \right. \right\} O+={x∣x∈N,x是正奇数}； (2) P = { x ∣ x ∈ N , x 是素数 } P=\left\{ x\left| x\in N, x\text{是素数} \right. \right\} P={x∣x∈N,x是素数}; (3) 有理数集合 Q Q Q；

证明：

在 O + O^+ O+与 N N N之间建立一个一一对应关系 φ 1 : N → O + \varphi _1:N\rightarrow O^+ φ1​:N→O+如下： 0 1 2 3 ⋯ n ⋯ ↓ ↓ ↓ ↓ ↓ 1 3 5 7 ⋯ 2 n + 1 ⋯ \begin{matrix} 0& 1& 2& 3& \cdots& n& \cdots\\ \downarrow& \downarrow& \downarrow& \downarrow& & \downarrow& \\ 1& 3& 5& 7& \cdots& 2n+1& \cdots\\ \end{matrix} 0↓1​1↓3​2↓5​3↓7​⋯⋯​n↓2n+1​⋯⋯​ 所以 O + O^+ O+是可数集合。

在 P P P与 N N N之间建立一个一一对应关系 φ 2 : N → P \varphi _2:N\rightarrow P φ2​:N→P如下： 0 1 2 3 4 5 6 7 ⋯ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 2 3 5 7 11 13 17 19 ⋯ \begin{matrix} 0& 1& 2& 3& 4& 5& 6& 7& \cdots\\ \downarrow& \downarrow& \downarrow& \downarrow& \downarrow& \downarrow& \downarrow& \downarrow& \\ 2& 3& 5& 7& 11& 13& 17& 19& \cdots\\ \end{matrix} 0↓2​1↓3​2↓5​3↓7​4↓11​5↓13​6↓17​7↓19​⋯⋯​

所以 P P P是可数集合。

正奇数集合、正偶数集合和素数集合都是自然数集合的真子集，通过证明它们都是可数集合，它们的基数都是 ℵ 0 \aleph _0 ℵ0​。

证明：

在 Q Q Q与 N N N之间建立一个一一对应关系 φ 3 : N → Q \varphi _3:N\rightarrow Q φ3​:N→Q如下图所示。注意，所有有理数以分数 p / q p/q p/q的形式表示，其上标表示对应的自然数。

⋯ ← − 3 / 1 [ 18 ] − 2 / 1 [ 5 ] ← − 1 / 1 [ 4 ] 0 / 1 [ 0 ] → 1 / 1 [ 1 ] 2 / 1 [ 10 ] → 3 / 1 [ 11 ] → ⋯ ⋯ ↑ ↓ ↑ ↓ ↑ ↓ ⋯ ⋯ − 3 / 2 [ 17 ] − 2 / 2 − 1 / 2 [ 3 ] ← 0 / 2 ← 1 / 2 [ 2 ] 2 / 2 → 3 / 2 [ 12 ] ⋯ ⋯ ↑ ↓ ↑ ↓ ⋯ ⋯ − 3 / 3 − 2 / 3 [ 6 ] → − 1 / 3 [ 7 ] → 0 / 3 → 1 / 3 [ 8 ] → 2 / 3 [ 9 ] 3 / 3 ⋯ ⋯ ↑ ↓ ⋯ ⋯ − 3 / 4 [ 16 ] ← − 2 / 4 ← − 1 / 4 [ 15 ] ← 0 / 4 ← 1 / 4 [ 4 ] ← 2 / 4 ← 3 / 4 [ 13 ] ⋯ \begin{matrix} \cdots& \gets& -3/1^{\left[ 18 \right]}& & -2/1^{\left[ 5 \right]}& \gets& -1/1^{\left[ 4 \right]}& & 0/1^{\left[ 0 \right]}& \rightarrow& 1/1^{\left[ 1 \right]}& & 2/1^{\left[ 10 \right]}& \rightarrow& 3/1^{\left[ 11 \right]}& \rightarrow& \cdots\\ \cdots& & \uparrow& & \downarrow& & \uparrow& & & & \downarrow& & \uparrow& & \downarrow& & \cdots\\ \cdots& & -3/2^{\left[ 17 \right]}& & -2/2& & -1/2^{\left[ 3 \right]}& \gets& 0/2& \gets& 1/2^{\left[ 2 \right]}& & 2/2& \rightarrow& 3/2^{\left[ 12 \right]}& & \cdots\\ \cdots& & \uparrow& & \downarrow& & & & & & & & \uparrow& & \downarrow& & \cdots\\ \cdots& & -3/3& & -2/3^{\left[ 6 \right]}& \rightarrow& -1/3^{\left[ 7 \right]}& \rightarrow& 0/3& \rightarrow& 1/3^{\left[ 8 \right]}& \rightarrow& 2/3^{\left[ 9 \right]}& & 3/3& & \cdots\\ \cdots& & \uparrow& & & & & & & & & & & & \downarrow& & \cdots\\ \cdots& & -3/4^{\left[ 16 \right]}& \gets& -2/4& \gets& -1/4^{\left[ 15 \right]}& \gets& 0/4& \gets& 1/4^{\left[ 4 \right]}& \gets& 2/4& \gets& 3/4^{\left[ 13 \right]}& & \cdots\\ \end{matrix} ⋯⋯⋯⋯⋯⋯⋯​←​−3/1[18]↑−3/2[17]↑−3/3↑−3/4[16]​←​−2/1[5]↓−2/2↓−2/3[6]−2/4​←→←​−1/1[4]↑−1/2[3]−1/3[7]−1/4[15]​←→←​0/1[0]0/20/30/4​→←→←​1/1[1]↓1/2[2]1/3[8]1/4[4]​→←​2/1[10]↑2/2↑2/3[9]2/4​→→←​3/1[11]↓3/2[12]↓3/3↓3/4[13]​→​⋯⋯⋯⋯⋯⋯⋯​

所以 Q Q Q是可数集合。

第一列是分母为1的分数； 第二列是分母为2的分数； 第一列是分母为3的分数； 第二列是分母为4的分数； …… 0/1=0对应有理数中的0 按照箭头一一对应。 1/1对应1，1/2对应2，0/2=0跳过， -1/2对应3，-1/1对应4，-2/1对应5，-2/2=-1跳过， -2/3对应6…… 螺旋往复地一一对应。

从有限到无限，不仅仅是简单数量上的变化（量变），而引起了本质的改变（质变）。

开区间 ( 0 , 1 ) (0,1) (0,1)称为不可数集合，凡与开区间 ( 0 , 1 ) (0,1) (0,1)等势的集合，称为不可数集合，该类集合的基数记为 ℵ \aleph ℵ（读作阿列夫）

本文介绍了集合论基础中的可数集合与不可数集合部分，对集合有更多的了解。