集合

集合的特性

  1. 集合元素各不相同 distinct
    1. 对于多集合 multiset 是可以存在重复的集合内元素的
  2. 元素没有顺序区别 unordered
  3. 两种表示法可以相互转化 (枚举/描述)

基数 Cardinality

表示集合的尺寸，或者说集合内元素的数量
表示为 #A\#A 或者 ∣A∣|A| 或者 cardA\text{card}A

集合之间的关系

包含(子集) Inclusion (subset)

符号: ⊆\subseteq 或者 ⊂\subset
定义: A⊂B⇔∀x∈A→x∈BA\subset B \Leftrightarrow \forall x \in A\to x\in B
不包含: ⊄\not\subset 或者 ⊈\not\subseteq, 定义 ∃x∈A,x∄B⇒A⊈B\exists x \in A, x\not\exists B \Rightarrow A\not\subseteq B

性质
  1. A⊆AA\subseteq A 集合包含自身
  2. 若 A⊆BA \subseteq B 且 A≠BA\not= B 则 B⊈AB\not\subseteq A: 这里定义了集合的等号 A=B⇔A⊆B∧B⊆AA = B \Leftrightarrow A\subseteq B \wedge B\subseteq A
  3. 若 A⊆BA\subseteq B 且 B⊆CB\subseteq C 则 A⊆CA\subseteq C: 这里定义了包含的传递性

真子集 proper subset / superset

符号 ⊂\subset 要求 A≠B∧∀x∈A→x∈BA\not = B \wedge \forall x \in A\to x\in B

性质
  1. A⊄AA\not\subset A
  2. A⊂B→B⊄AA\subset B\to B\not\subset A
  3. A⊂B∧B⊂C→A⊂CA\subset B \wedge B\subset C\to A\subset C

空集 Emptyset

不拥有任何元素的集合称为空集 ∅\emptyset

定理: 空集是一切集合的子集
推论: 空集是唯一的

证明: ∅1⊆∅2∧∅2⊆∅1⇒∅1=∅2\emptyset_1 \subseteq \emptyset_2 \wedge \emptyset_2\subseteq\emptyset_1 \Rightarrow \emptyset_1 = \emptyset_2
也就是说空集是最小的唯一的集合，那么有没有最大的集合呢？

全集

讨论的集合都是某个集合的子集，该集合就是全集，记作 EE

并集 Union

定义: A∪B:={x∣x∈A∨x∈B}A\cup B:=\{x| x\in A \lor x\in B\}
共同并集: ⋃C={x∣∃X⊆C,s.t. x∈X}\bigcup \mathcal{C} = \{x|\exists X\subseteq\mathcal C ,\text{s.t.}\ x\in X\}

交集 Intersection

定义: A∩B:={x∣x∈A∧x∈B}A\cap B:=\{x|x\in A \wedge x\in B\}
共同交集: ⋂C\bigcap\mathcal C
注意: 共同并集的定义是避开 空集 ∅\emptyset 的，或者说 ⋃{∅}\bigcup\{\emptyset\} 是未定义的

差异 Difference

我们用 −- 或者 \\backslash 来表示集合的差异
A−B:={x∣x∈A∧x∉B}A- B :=\{x|x\in A \land x\not\in B\}

对称差异 Symmetric Difference

AΔB:=(A−B)∪(B−A)A\Delta B:= (A - B)\cup (B - A)

指数集合 power set

我们称集合 A 的所有子集的集合为 power set P(A)\mathcal P(A) 或者 2A2^A
包括空集、集合本身
注意 P({∅})={∅,{∅}}\mathcal P(\{\emptyset\}) =\{\emptyset, \{\emptyset\}\}
这里指数集合的元素是集合而不再是单纯元素了

指数集合的尺寸

∣2A∣=∣P(A)∣=2∣A∣|2^A| = |\mathcal{P}(A)| = 2^{|A|}

有序对 ordered pair

(a,b):={{a},{a,b}}(a,b) := \{\{a\},\{a,b\}\}

指数集合的扩展定理

内容：若 a∈C,b∈Ca\in C, b\in C, 则 (a,b)∈P(P(C))(a,b) \in \mathcal P(\mathcal P(C))
理解：(a,b)(a,b) 表示 {{a},{a,b}}\{\{a\},\{a,b\}\}, P(C)={∅,{a},{b},{a,b}}P(C) = \{\emptyset, \{a\}, \{b\}, \{a, b\}\}

P(P(C))={∅,{∅},{{a}},{{b}},{{a,b}},{∅,{a}},{∅,{b}},{∅,{a,b}},{{a},{b}},{{a},{a,b}},{{b},{a,b}},{∅,{a},{b}},{∅,{a},{a,b}},{∅,{b},{a,b}},{{a},{b},{a,b}},{∅,{a},{b},{a,b}}}P(P(C)) = \{\emptyset, \{\emptyset\}, \{\{a\}\}, \{\{b\}\}, \{\{a, b\}\}, \{\emptyset, \{a\}\}, \{\emptyset, \{b\}\}, \{\emptyset, \{a, b\}\}, \{\{a\}, \{b\}\}, \{\{a\}, \{a, b\}\}, \{\{b\}, \{a, b\}\}, \{\emptyset, \{a\}, \{b\}\}, \{\emptyset, \{a\}, \{a, b\}\}, \{\emptyset, \{b\}, \{a, b\}\}, \{\{a\}, \{b\}, \{a, b\}\}, \{\emptyset, \{a\}, \{b\}, \{a, b\}\} \}

我们大概可以看出，每嵌套一层 power set 我们就会将一层元素变成集合
这个操作和 ⋃\bigcup , ⋂\bigcap 的操作是相反的

⋃{A,B}=A∪B\bigcup\{A,B\} = A\cup B

子集的区分

我们定义一个正整数 k 用来标记拥有 k 个元素的子集 (Xk)\begin{pmatrix}X \\ k\end{pmatrix} , 其中我们有等式∣(Xk)∣=(∣X∣k)|\begin{pmatrix}X \\ k\end{pmatrix}| = \begin{pmatrix}|X| \\ k\end{pmatrix}

图 Graph

点的集合 vertex V(G)V(G)
线的集合 edge E(G)E(G)
源函数集合 source functions ss
目标函数集合 target function tt