集合论

集合与元素

集合与元素：集合是元素的全体。

集合元素的性质: 无序性, 独特性, 确定性, 任意性

集合的全体子集构成的集合叫做幂集. $|P(A) = 2 ^ n|$

标记法

集合通常使用大写字母表示，元素通常使用小写字母表示。

因此术语“p是A的元素”或等价于“p属于A”记作： p ∈ A

外延公理

两个集合A和B相等当且仅当其元素相同。

如果集合A与B相等，则记作 A = B，否则 A ≠ B。

集合的表示

集合有两种基本素方法，一是枚举元素，二是描述元素特征性质。

如：

V = {a, e, i, o, u}, 或
V = {x: x是英文字母，x是元音字母}

E = {x: x > 0, x mod 2 = 0} 或
E = {2, 4, 6, 8, 10, ...}

常用的集合及其表示

符号 意义
N 全体正整数
Z 全体整数
Q 全体有理数
R 全体实数
C 全体复数

抽象原则

给定集合U和性质P，则存在集合A恰好包含U中具有性质P的那些元素。

全集与空集

全集

记号为U。

空集

没有元素的集合；又称“零集”，记号为 ∅，或者 {}。

空集的特性：

- ∀A: A ⊆ ∅ ⇒ A = ∅
- P(∅) = \{∅}
- card(∅) = 0
- ∀A: ∅ ⊆ A
- ∀A: A ∪ ∅ = ∅
- ∀A: A ∩ ∅ = ∅
- ∀A: A × ∅ = ∅

子集

如果集合A的每个元素都是集合B的元素，则称A为B的一个子集。也称A包含于B或者B包含A。记作：

A ⊆ B 或 B ⊇ A

或者A不是B的子集，即A至少有一个元素不属于B，则记作 A \nsubseteq B 或者 A \not\subseteq B， A \nsuperseteq A 或者 B \not\superseteq A。

定理1.1

  • 对于任意集合A, ∅ <= A <= U
  • 对于任意集合A，A <= A
  • 如果A <= B，且 B <= C，则 A<= C
  • A = B 当且仅当 A <= B 且 B <= A

集合运算

笛卡尔乘积

有序偶是两个对象的搜集，使得可以区分出其中一个是“第一个元素”而另一个是“第二个元素”（第一个元素和第二个元素也叫做左投影和右投影）。带有第一个元素a和第二个元素b的有序偶通常写为\。

$A * B = { \lt x,y\gt|x \in A , y \in B }$

关系

二元关系

如果一个集合的元素都是有序偶(非空), 则该集合为一个二元关系. 记作R.

并与交

属于A或者属于B的所有元素的集合，称为集合A和B的并集，记作：A∪B.

属于A并且属于B的所有元素的集合，称为集合A和B的交集，记作：A∩B

如果A和B没有公共元素，则称集合A和B是不交的， A∩B = ∅。

此时，A与B的并集称为不交的并(disjoint union)。

下述语句等价：A ⊆ B，A ∩ B = A，A ∪ B = B。

补

所有属于全集U但不属于A的元素构成的集合：

$ A^c = {x: x \in \mathbb{U}, x \not\in A } $

也记作 A` 或者 Aᶜ。

相对补/差

集合B关于集合A的相对补，或称集合A与集合B的差，记作 A\B，是由所有属于A但不属于B的元素构成的集合.

也记作：A-B 或者 A~B。本质上：A\B = A ∩ B`。

对称差

集合A和B的对称差，记作 A ⊕ B 是所有属于A或B但不同时属于A和B的元素的集合。即：

$ A \oplus B = {x | (x \in A \land x \not\in B) \lor (x \in B \land x \not\in A)} $

性质： $ A \oplus B = (A \cup B) \setminus (A \cap B) A \oplus B = (A \setminus B) \cup (B \setminus A) $

集合的代数运算及对偶性

定理1.3，集合满足以下表所列的规律：

对偶性

设E为集合代数运算的一个方程，则E的对偶E是由将E中的并与交互换，全集与空集互换，得到的方程。 在集合的代数运算中，对偶原理成立。即如果一个方程E成立，则其对偶方程E必定成立。

有限集及计数原理

一个集合称为有限集，如果它恰好含有m个相异的元素，其中m为某非负整数；否则，称集合为无限集。

用记号n(A)表示有限集A中元素的个数，也可以用 #(A)，|A| 或者 card(n)。

引理1.4

如果A，B为不交的有限集，则A∪B为有限集且

n(A ∪ B) = n(A) + n(B)。

定理1.5

如果A，B均为有限集，则A ∪ B和A ∩ B均为有限集，且

n(A ∪ B) = n(A) + n(B) - n(A ∩ B)。

推论1.6

如果A，B，C均为有限集，则A ∪ B ∪ C均为有限集，且

n(A ∪ B ∪ B) = n(A) + n(B) + n(C) - n(A ∩ B) - n(A ∩ C) - n(B ∩ C) + n(A ∩ B ∩ C)。

集族，幂集和集合的划分

集合的集合称为集类或者集族。集族中的元素（集合），称为子类或子族。

幂集

对于给定的集合S，其所有可能子集的族，称为集合S的幂集。记作：Power(S)。如果S为有限集，则Power(S)也是有限集。并且：

n(Power(S)) = 2 ^ n(S)

划分

设S是一个非集合，S的一个划分是将S剖分为一些不交叠的非空子集。即：S的一个划分是S的一族非空子集{A_i}，满足： 1. S中的每个元素a属于一个A_i； 2. {A_i}中的集合互不相交，即对于两个不同的集合， A_i ∩ A_j = 0。

划分中的子集叫胞腔。

$ partition(S) = { A | (\forall x \in S, \exists A \to x \in A) \land (\forall A_i, \forall A_j, A_i \neq A_j \to A_i \cap A_j = \emptyset)} $

集合运算的推广

定理1.7

设 $\mathscr{A}$ 为集族，则： $ [ \cup(A | A \in \mathscr{A}) ]^c = \cap(A^c | A \in \mathscr{A}) [ \cap(A | A \in \mathscr{A}) ]^c = \cup(A^c | A \in \mathscr{A}) $

数学归纳法

数学归纳法原理I

设 P 是定义于正整数集合N上的一个命题，即对N中的每个n，P(n) 或者正确或者不正确。假设P具有下列两个性质：

1. P(1)为真，
2. 只要P(n)为真，P(n+1)亦为真

则对任意正整数，P都为真。

数学归纳法原理II

设P是定义于正整数N上的一个命题，使得：

1. P(1)为真，
2. 当对于所有的 1 \<= k < n，P(k) 为真时，有P(n)为真，

则P对于所有的正整数为真。

良序集

群

环