1. 集合#

1.1. 集合的基本概念#

定义：装有不重复的元素的容器

空集是唯一的

不同研究范围不同，即：相对唯一的。

集合中元素的特性：
- 元素是无序的。
- 元素是不同的。
相等关系：所有的元素完全相同（元素数量也相同）
包含关系：B的元素都是A中的元素，则B是A的子集，叫做：A包含B，或者 B被A包含
- 真子集：A包含B且A != B，则B是A的真子集。叫做A真包含B，或者B被A真包含。

空集是任何集合的子集

任何n元集合的m元子集(0 <= m <= n)的个数为 C(m, n)

任何集合所有不同子集的个数是 C(0, n) + C(1, n) + … + C(n, n) = 2^n 个。

相等关系的证明：

A == B <=> A包含B 且 B包含A

幂集：A为任意集合，A所有不同子集构成的集合叫做A的幂集(power set)，记作：P(A)
- $P(A) = \{ X | X \subseteq A\}; (X \space is \space set)$

假设有任意集合A和集合B。

交集：既是A也是B的元素的集合
并集：是A的元素或者是B的元素的集合
补集：不属于A的元素的集合(全集范围内)
差集：属于A且不属于B的元素的集合
- $A - B == A \land \neg B$
对称差集：(属于A 且不属于B) 或者 (属于B 且不属于A) 的元素的集合
- $(A \land \neg B) \lor (B \land \neg A)$
- $A \lor B - A \land B$

幂等律： $A \land A = A; A \lor A = A；$
交换律
结合律
同一律： $A \lor \varnothing = A, A \land U = A$
零律： $A \lor U = U; A \land \varnothing = \varnothing$
分配律
吸收律： $A \lor (A \land B) = A \land (A \lor B) = A$
矛盾律和排中律： $\neg A \land A = \varnothing;\neg A \lor A = U$
双重否定律
德摩根律： $\neg (A \lor B) = (\neg A \land \neg B); \neg (A \land B) = (\neg A \lor \neg B)$

习题：证明德摩根律。

虽然无穷都是数不清的，但是无穷之间也有不同。

阿列夫将无穷分为不同的级别：此处我们使用阿列夫零和阿列夫一来表示可数和不可数集合。

皮亚诺公理：
- 0是自然数
- 每个自然数n都有一个自然数后继，记为S(n)
- 两个自然数相等且当且仅当二者有相同后继。
- 没有任何自然数的后继是0
- 归纳公理（数学归纳法）：若φ(0)为真，且若φ(n)为真，则φ(S(n))也为真 ==> 则φ(n)对任意自然数成立
冯·诺依曼自然数定义
- ∅ ∈N
- 若n∈N，则n’ = n ∪ {n} ∈N. {n}表示以n为元素的集合
- 通过不断地推导就能得出任意基数的自然数集合。
  - $0 = |\varnothing|$
  - $1 = |\varnothing \lor \{\varnothing\}| = |\{\varnothing\}|$
集合的比较
- 有限集：比较集合的基数大小
- 无限集：根据某种一一对应的关系来比较
等势：若两个集合A、B之间存在某种一一对应的关系，则称A与B等势，记作：A ~ B
可数集合(countable set)：与自然数集合N等势的几何，成为可数集合。记为： $\aleph_0$ （阿列夫零）
- 以下集合都是可数集合：
  - 正奇数
  - 素数
  - 有理数集合