离散数学学习笔记——集合论基础

空集

Definition

不含任何元素的集合叫做空集(empty set)，记作 $\varnothing .$

空集可以符号化为 ∅ = { x ∣ x ≠ x } . \varnothing=\{x \mid x \neq x\} . ∅={x∣x​=x}.

Example

• 设 $A=\left\{x\mid x\in R,x^2<0\right\},$ 则 $A=\varnothing$
• ∣ ∅ ∣ = 0 , ∣ { ∅ } ∣ = 1 |\varnothing|=0,|\{\varnothing\}|=1 ∣∅∣=0,∣{∅}∣=1

空集是绝对唯一的。

全集

Definition

针对一个具体范围，我们考虑的所有对象的集合叫做全集(universal set)，记作 $U$ 或 $E$。

在文氏图一般使用方形表示全集。

Example

• 在立体几何中，全集是由空间的全体点组成的 ;
• 在我国的人口普查中，全集是由我国所有人组成的。

全集是相对唯一的。

集合的相等关系

• 集合中的元素是无序的。 { 1 , 2 , 3 , 4 } \{1, 2, 3, 4\} {1,2,3,4} 与 { 2 , 3 , 1 , 4 } \{2, 3, 1, 4\} {2,3,1,4}相同。
• 集合中的元素是不同的。 { 1 , 2 , 2 , 3 , 4 , 3 , 4 , 2 } \{1, 2, 2, 3, 4, 3, 4, 2\} {1,2,2,3,4,3,4,2}与 { 1 , 2 , 3 , 4 } \{1, 2, 3, 4\} {1,2,3,4}相同。

citing example

设 E = { x ∣ ( x − 1 ) ( x − 2 ) ( x − 3 ) = 0 , x ∈ R } , F = { x ∣ x ∈ Z + , x 2 < 12 } \quad E=\{x \mid(x-1)(x-2)(x-3)=0, x \in R\}, F=\left\{x \mid x \in Z^{+}, x^{2}<12\right\} E={x∣(x−1)(x−2)(x−3)=0,x∈R},F={x∣x∈Z+,x2<12}
可见 $E$ 和 $F$ 具有相同的元素 { 1 , 2 , 3 } , \{1,2,3\}, {1,2,3}, 此时称两个集合相等。

Theorem (外延性原理)

两个集合 $A$ 和 $B$ 相等，当且仅当它们的元素完全相同，记为 $A=B,$ 否则 $A$ 和 $B$ 不相等，记为$A\ne B$

集合的包含关系

设 A = { B A S I C , P A S C A L , A D A } , B = { A D A , P A S C A L } A=\{B A S I C, P A S C A L, A D A\}, B=\{A D A, P A S C A L\} A={BASIC,PASCAL,ADA},B={ADA,PASCAL}，此时 $A$ 中含有 $B$ 中所有的元素，这种情况称为A 包含 $B$。

Definition

设 $A,B$ 是任意两个集合，

• 如果 $B$ 的每个元素都是 $A$ 中的元素，则称 $B$ 是 $A$ 的子集，也称做 $B$ 被 $A$ 包含或$A$ 包含$B,$ 记作 $B\subseteq A,$ 否则记作 $B⊈A.$
• 如果 $B\subseteq A$ 并且 $A\ne B,$ 则称 $B$ 是 $A$ 的真子集，也称做$B$ 被 $A$ 真包含或 $A$ 真包含 $B$, 记 作 $B\subset A,$ 否则记作 $B\not\subset A.$

“ $\subseteq$”关系的数学语言描述为： $B\subseteq A\iff$ 对 $\forall x,$ 如果 $x\in B,$ 则 $x\in A.$

由子集定义可有

(1) $\varnothing \subseteq A$
(2) $A\subseteq A$

Example
已知 A = { 1 , 2 , 3 , 4 } , B = { 1 , 2 , 4 } , C = { 2 , 3 } , D = { 3 , 2 } , A=\{1,2,3,4\}, B=\{1,2,4\}, C=\{2,3\}, D=\{3,2\}, A={1,2,3,4},B={1,2,4},C={2,3},D={3,2}, 可见
(1) $A\subseteq A,B\subseteq A,C\subseteq A,D\subseteq A,$
(2) $C\subseteq D,D\subseteq C,$ 同时, $C=D$

证明集合相等

Theorem
设 $A,B$ 为任意两个集合，则 $A=B\iff A\subseteq B$ 并且 $B\subseteq A$

⋆⋆⋆ 上面的定理非常重要，这是证明集合相等的一种非常有效的方式。

证明框架

证明：

(1) 首先证明 $A\subseteq B:\forall x\in A,\cdots ,x\in B.\therefore A\subseteq B.$

( 2 其次证明 $B\subseteq A:\forall x\in B,\cdots ,x\in A.\therefore B\subseteq A.$

元集的子集

对于任意 $n$ 元集合 $A$, 它的 $m$ 元 $(0⩽m⩽n)$ 子集个数为 $C_n^m$ 个, 所以不同的子集个数为 $:C_n^0+C_n^1+\cdots +C_n^n=(1+1{)}^n=2^n.$

幂集

设 $A$ 为任意集合，把 $A$ 的所有不同子集构成的集合叫做 $A$ 的幕集(power set), 记作 $P(A)$, 即，
P ( A ) = { x ∣ x ⊆ A } P(A)=\{x \mid x \subseteq A\} P(A)={x∣x⊆A}

可知以下关系等价
$$x\in P(A)\iff x\subseteq A$$

Example

设 A = { a , b , c } , B = { a , { b , c } } , A=\{a, b, c\}, B=\{a,\{b, c\}\}, A={a,b,c},B={a,{b,c}}, 求他们的幕集 $P(A)$ 和 $P(B)$ 。

解 : P ( A ) = { ∅ , { a } , { b } , { c } , { a , b } , { b , c } , { a , c } , { a , b , c } } : P(A)=\{\varnothing,\{a\},\{b\},\{c\},\{a, b\},\{b, c\},\{a, c\},\{a, b, c\}\} :P(A)={∅,{a},{b},{c},{a,b},{b,c},{a,c},{a,b,c}}
P ( B ) = { ∅ , { a } , { { b , c } } , { a , { b , c } } } P(B)=\{\varnothing,\{a\},\{\{b, c\}\},\{a,\{b, c\}\}\} P(B)={∅,{a},{{b,c}},{a,{b,c}}}

幂集也叫做集族或集合的集合，对集族的研究在数学方面、知识库和表处理语言以及人工
智能等方面都有十分重要的意义。