集合的基本概念

定义

集合难以严格定义

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

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

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

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

元素与集合的关系

属于

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

不属于

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

类型

有限集合

直观定义

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

用于证明的定义

给定 $\mathbf N_k=\{0,1,2,\cdots,k-1\},\ k\in\mathbf Z$，对于集合 $A$，若存在双射函数 $f:\mathbf N_k\rightarrow A$，则称 $A$ 是有限集

无限集合

参考无限集合的定义

表示方法

列举法（穷举法或枚举法）

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

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

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

适用情况：

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

描述法

描述出集合中元素的共同性质，描述法的形式为：
$\{$代表元素$|$满足的性质$\}$，“$|$“ 表示“满足于“的意思
如：中国省份集合 $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\}$ 等于集合 $\{3,2,1\}$

互异性

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

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

确定性

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

集合与集合的关系

子集（包含）

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

用谓词公式表示为：$A\subseteq B\Leftrightarrow \forall x(x\in A\rightarrow 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{aligned} A\subset B&\Leftrightarrow \forall x(x\in A\rightarrow x\in B)\land \exists y(y\in B \land y\notin A) \\ &\Leftrightarrow (A\subseteq B)\land (A\neq B) \end{aligned}$$

相等

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

用谓词公式表示为：

$$\begin{aligned} A=B&\Leftrightarrow \forall x(x\in A\leftrightarrow x\in B)\\ &\Leftrightarrow (A\subseteq B)\land (B\subseteq A) \end{aligned}$$

属性

大小（基数或势）

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

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

等势

若集合 $A$ 到 $B$ 能建立一个双射函数，则称集合 $A$ 与集合 $B$ 等势，记作 $A\sim B$ 或 $|A|=|B|$
如：正整数集 $\mathbf Z^+$ 与自然数集 $\mathbf N$ 等势，因为可构造双射函数 $f:\mathbf Z^+\rightarrow \mathbf N,f(x)=x-1$

等势是任何集合簇上的等价关系，因为：
设有集合簇 $S$

1. 自反性
   任取 $A\in S$，可构造双射函数 $f:A\rightarrow A,\ f(x)=x$，则 $A\sim A$
2. 对称性
   任取 $A,\ B\in S$，若 $A\sim B$，则可构造双射函数 $f:A\rightarrow B$，而 $f^{-1}:B\rightarrow A$ 也是一个双射函数，因此 $B\sim A$
3. 传递性
   任取 $A,\ B,\ C\in S$，若 $A\sim B$ 且 $B\sim C$，则存在双射函数 $f:A\rightarrow B$ 和双射函数 $g:B\rightarrow C$，那么复合函数 $f\circ g:A\rightarrow C$ 也为双射函数，因此有 $A\sim C$

幂集

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

如集合 $A=\{1,2,3\}$ 的幂集：

$$\rho(A)=\{\varnothing,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}$$

若集合 $A$ 大小 $|A|=n$，则其幂集大小：

$$\begin{aligned} |\rho(A)|&=C_n^0+C_n^1+C_n^2+\cdots+C_n^n\\ &=2^n \end{aligned}$$

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

几个特殊的集合

空集

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

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

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

全集

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

基本运算

交

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

用谓词公式表示为：

$$A\cap B=\{x|x\in A\land x\in B\}$$

用文氏图表示为：

并

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

用谓词公式表示为：

$$A\cup B=\{x|x\in A\lor x\in B\}$$

用文氏图表示为：

补

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

用谓词公式表示为：

$$\begin{aligned} \overline A &=\{x|x\in A\land x\notin U\}\\ \end{aligned}$$

用文氏图表示为：

差（相对补）

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

用谓词公式表示为：

$$\begin{aligned} A-B&=\{x|x\in A\land x\notin B\}\\ &=A\cap \overline B \end{aligned}$$

用文氏图表示为：

对称差（环合）

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

用谓词公式表示为：

$$\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$ 的环积集就是属于 $A$ 且属于 $B$ 或不属于 $A$ 且不属于 $B$ 的元素所构成的集合，记作 $A\otimes 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\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] 集合的百度百科
[4] 集合论基础电子工业出版社