集合

定义

集合难以严格定义

直观描述：若干个（有限或无限）具有某种共同性质的事物的全体

称：组成集合的单个事物为该集合元素或成员

通常用大写英文字母 $A,B,C,\cdots$ 表示集合
用小写英文字母 $a,b,c,\cdots$ 表示元素

例如：全中国人的集合，它的元素是每一个中国人，共同性质是中国人

元素与集合的关系

属于

若元素 $a$ 在集合 $A$ 中，则称 $a$ 属于 $A$，记作 $a\in A$

不属于

若元素 $a$ 不在集合 $A$ 中，则称 $a$ 不属于 $A$，记作 $a\notin A$

类型

有限集合

包含有限个元素（包含0个）的集合称为有限集合

无限集合

参考无限集合的定义

表示方法

列举法

将集合中的元素在一对大括号 “ { } \{\} { }” 中一一列举出来
如： { 1 , 2 , 3 } \{1,2,3\} { 1,2,3}

当集合的元素较多且具有一定规律时，可简写为
先列一些元素，用省略号表示其他元素，写出规律项，省略号，若是有限集还需列出末尾元素
如：

1. 正偶数集 { 2 , 4 , ⋯   , 2 n , ⋯   } \{2,4,\cdots,2n,\cdots\} { 2,4,⋯,2n,⋯}
2. 小于 $100$ 的正偶数集 { 2 , 4 , ⋯   , 2 n , ⋯   , 100 } \{2,4,\cdots,2n,\cdots,100\} { 2,4,⋯,2n,⋯,100}

适用情况：

1. 集合元素较少
2. 有规律的无限集和元素较多的有限集

描述法

描述出集合中元素的共同性质，描述法的形式为：
{ 代表元素 ∣ 满足的性质 } \{代表元素|满足的性质\} { 代表元素∣满足的性质}
如：中国省份集合 A = { x ∣ x 是中国的省份 } A=\{x|x是中国的省份\} A={ x∣x是中国的省份}

归纳定义法

一个集合 $S$ 的归纳定义由三部分组成：

1. 基础条款：给定集合 $S$ 初始元素，使得 $S$ 为非空集合
2. 归纳条款：给定由集合 $S$ 中已有的元素构造出新元素的方法
3. 极小性条款：集合 $S$ 中的元素必须能通过有限次应用基础条款和归纳条款构成，否则其不属于 $S$

   这个条款还可写成：
   集合 $S$ 是满足基础条款和归纳条款的最小集合或
   若 $T\subseteq S$，$T$ 又满足基础条款和归纳条款，那么 $T=S$

下面是用归纳定义发给出能被 $3$ 整除的正整数集合 $S$：

1. 基础：$3\in S$
2. 归纳：若 $x,y\in S$，则 $x+y\in S$
3. 极小性：当且仅当有限次使用条款1和条款2得到的元素才属于集合 $S$

集合中元素的特点

无序性

集合中的元素是无序的

如：集合 { 1 , 2 , 3 } \{1,2,3\} { 1,2,3} 等于集合 { 3 , 2 , 1 } \{3,2,1\} { 3,2,1}

互异性

集合中不能有两个相同的元素

如：不会有集合 { 1 , 2 , 2 } \{1,2,2\} { 1,2,2}

确定性

任意元素要么属于某个集合，要么不属于该集合

集合与集合的关系

子集（包含）

若集合 $A$ 的每个元素都是集合 $B$ 的元素，则称 $A$ 为 $B$ 的子集或 $A$ 包含 $B$，又称 $B$ 包含于 $A$，记作 $A\subseteq B$ 或 $B\supseteq A$
若 $A$ 不是 $B$ 的子集，则记作 $A⊈B$

用谓词公式表示为：$A\subseteq B\iff \forall x(x\in A\to x\in B)$

子集具有传递性，即
若 $A\subseteq B$ 且 $B\subseteq C$，则 $A\subseteq C$

子集具有自反性，即 $A\subseteq A$

真子集

若集合 $A$ 的每个元素都是集合 $B$ 的元素，但 $B$ 至少有一个元素不属于 $A$，则称 $A$ 是 $B$ 的真子集，记作 $A\subset B$ 或 $B\supset A$
若 $A$ 不是 $B$ 的真子集，则记作 $A\not\subset B$

用谓词公式表示为：
$$\begin{array}{rl}A\subset B& \iff \forall x(x\in A\to x\in B)\wedge \exists y(y\in B\wedge y\notin A)\\ & \iff (A\subseteq B)\wedge (A\ne B)\end{array}$$

相等

$A=B$ 当且仅当 $A$ 和 $B$ 具有相同的元素
不相等记作 $A\ne B$

用谓词公式表示为：
$$\begin{array}{rl}A=B& \iff \forall x(x\in Ax\in B)\\ & \iff (A\subseteq B)\wedge (B\subseteq A)\end{array}$$

属性

大小（基数或势）

对于一个有限集合 $A$，其大小为集合所含元素的个数，记作 $|A|$
如：集合 A = { 1 , 2 , 3 } A=\{1,2,3\} A={ 1,2,3} 的大小 $|A|=3$

对于无限集合的大小，请参考无限集合的大小

幂集

以集合 $A$ 的所有子集为元素的集合称作 $A$ 的幂集，记作 $\rho (A)$

如集合 A = { 1 , 2 , 3 } A=\{1,2,3\} A={ 1,2,3} 的幂集：
ρ ( A ) = { ∅ , { 1 } , { 2 } , { 3 } , { 1 , 2 } , { 1 , 3 } , { 2 , 3 } , { 1 , 2 , 3 } } \rho(A)=\{\varnothing,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\} ρ(A)={ ∅,{ 1},{ 2},{ 3},{ 1,2},{ 1,3},{ 2,3},{ 1,2,3}}

若集合 $A$ 大小 $|A|=n$，则其幂集大小：
$$\begin{array}{rl}|\rho (A)|& =C_n^0+C_n^1+C_n^2+\cdots +C_n^n\\ & =2^n\end{array}$$

由幂集可知：集合的元素可以是集合
如：可以有集合 A = { 1 , { 2 , 3 } } A=\{1,\{2,3\}\} A={ 1,{ 2,3}}，此时 { 2 , 3 } ∈ A \{2,3\}\in A { 2,3}∈A 但 $2\notin A$

几个特殊的集合

空集

不含任何元素的集合称为空集，记作 $\varnothing$

空集是任意集合的子集，是任意非空集合的真子集

需要注意的是：空集是唯一的

全集

一定范围内所有事物组成的集合称为该范围内的全集，记为 $U$

基本运算

交

集合 $A$ 与 $B$ 的交集就是同时属于 $A$ 和 $B$ 的元素所构成的集合，记作 $A\cap B$

用谓词公式表示为：
A ∩ B = { x ∣ x ∈ A ∧ x ∈ B } A\cap B=\{x|x\in A\land x\in B\} A∩B={ x∣x∈A∧x∈B}

用文氏图表示为：

并

集合 $A$ 与 $B$ 的并集就是属于 $A$ 或 $B$ 其中之一的元素所构成的集合，记作 $A\cup B$

用谓词公式表示为：
A ∪ B = { x ∣ x ∈ A ∨ x ∈ B } A\cup B=\{x|x\in A\lor x\in B\} A∪B={ x∣x∈A∨x∈B}

用文氏图表示为：

补

集合 $A$ 的就是属于全集 $U$ 但不属于 $A$ 的元素所构成的集合，记作 $\overline{A}$

用谓词公式表示为：
A ‾ = { x ∣ x ∈ A ∧ x ∉ U } \begin{aligned} \overline A &=\{x|x\in A\land x\notin U\}\\ \end{aligned} A​={ x∣x∈A∧x∈/U}​

用文氏图表示为：

差（相对补）

集合 $A$ 与 $B$ 的差集就是属于 $A$ 但不属于 $B$ 的元素所构成的集合，记作 $A-B$

用谓词公式表示为：
A − B = { x ∣ x ∈ A ∧ x ∉ B } = A ∩ B ‾ \begin{aligned} A-B&=\{x|x\in A\land x\notin B\}\\ &=A\cap \overline B \end{aligned} A−B​={ x∣x∈A∧x∈/B}=A∩B​

用文氏图表示为：

对称差

集合 $A$ 与 $B$ 的对称差集就是属于 $A$ 但不属于 $B$ 及属于 $B$ 但不属于 $A$ 的元素所构成的集合，记作 $A\oplus B$

用谓词公式表示为：
A ⊕ B = { x ∣ ( x ∈ A ∧ x ∉ B ) ∨ ( x ∈ B ∧ x ∉ A ) } = ( A ∪ B ) − ( A ∩ B ) = ( A − B ) ∪ ( B − A ) \begin{aligned} A\oplus B&=\{x|(x\in A\land x\notin B)\lor(x\in B\land x\notin A)\}\\ &=(A\cup B)-(A\cap B)\\ &=(A-B)\cup (B-A) \end{aligned} A⊕B​={ x∣(x∈A∧x∈/B)∨(x∈B∧x∈/A)}=(A∪B)−(A∩B)=(A−B)∪(B−A)​

用文氏图表示为：

环积

集合 $A$ 与 $B$ 的环积集就是属于 $A$ 且属于 $B$ 或不属于 $A$ 且不属于 $B$ 的元素所构成的集合，记作 $A\otimes B$

用谓词公式表示为：
A ⊗ B = { x ∣ ( x ∈ A ∧ x ∈ B ) ∨ ( x ∉ A ∧ x ∉ B ) } = A ⊕ B ‾ = ( A ∩ B ) ∪ ( A ‾ ∩ B ‾ ) \begin{aligned} A\otimes B&=\{x|(x\in A\land x\in B)\lor (x\notin A\land x\notin B)\}\\ &=\overline{A\oplus B}\\ &=(A\cap B)\cup(\overline A\cap \overline B) \end{aligned} A⊗B​={ x∣(x∈A∧x∈B)∨(x∈/A∧x∈/B)}=A⊕B​=(A∩B)∪(A∩B)​

用文氏图表示为：

交并补的运算定律

交、并、补运算是集合最基本的三种运算，其他运算都可用交、并、补的组合表示

基本定律

定律	描述
交换律	$A\cap B=B\cap A$ $A\cup B=B\cup A$
结合律	$A\cap (B\cap C)=(A\cap B)\cap C$ $A\cup (B\cup C)=(A\cup B)\cup C$
分配律	$A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$ $A\cup (B\cap C)=(A\cup B)\cap (A\cap C)$
吸收律	$A\cap (A\cup B)=A$ $A\cup (A\cap B)=A$
对合律	$\overline{\overline{A}}=A$
等幂律	$A\cap A=A$ $A\cup A=A$
零一律	$A\cap \varnothing =\varnothing$ $A\cup U=U$
同一律	$A\cap U=A$ $A\cup \varnothing =A$
矛盾律	$A\cap \overline{A}=\varnothing$
排中律	$A\cup \overline{A}=U$
德·摩根律	$\overline{A\cap B}=\overline{A}\cup \overline{B}$ $\overline{A\cup B}=\overline{A}\cap \overline{B}$
以上定理用真值表即可很容易地证明

容斥原理

参考容斥原理

参考

[1] 离散数学西安电子科技大学出版社第二版
[2] CSDN 博客离散数学 集合论
[3] 集合的百度百科