离散数学：集合论基础

Set

Basis

Definition

• 外延公理
• 空集存在公理
• 无序对公理
• 并集公理
• 幂集公理
• 无穷公理
• 替换公理
• 正则公理 （以上为ZF公理化集合论）
• 选择公理 （以上为ZFC公理化集合论）

若a是集合A中的元素，则成a属于A，记为$s\in A$

若a不是集合A中的元素，则成a不属于A，记为$s\notin A$

Example

枚举法

$A=\{a,b,c,d\}$

$B=\{2,4,6,8,\cdots \}$

叙述法

通过刻画集合中元素所具备的某种性质或特性来表示一个集合

$P=\{x\mid P\left(x\right)\}$

$C=\{x\mid x=2k,k\in N\}$

文氏图

Base number

集合A中元素个数称为集合中的基数（base number）,记为$\mid A\mid$

若一个集合的基数是有限的，称该集合为有限集（finite set）

若一个集合的基数是无限的，称该集合为无限集（infinite set）

$A=\{a,\{b,c\}\}\mid A\mid =2$

empty set

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

空集是绝对唯一的

universal set

针对一个具体范围，我们考虑所有的集合叫做全集，记为U或E.

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

全集是相对唯一的

eg：

在立体集合中，全集是由空间的全体点构成的

集合的相等关系

集合中的元素是无序的。

集合中的元素是不同的。

外延性原理

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

集合的包含关系

设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 \mathrm{对}\mathrm{于}\mathrm{\forall }x,\mathrm{如}\mathrm{果}x\in B,\mathrm{则}x\in A$

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

  非常重要证明集合相等的一种重要的方式

• $$\begin{gathered} \mathrm{对}\mathrm{于}\mathrm{任}\mathrm{意}n\mathrm{元}\mathrm{集}\mathrm{合}A，\mathrm{它}\mathrm{的}m\mathrm{元}(0\le m\le n)\mathrm{子}\mathrm{集}\mathrm{个}\mathrm{数}\mathrm{为}{C}_m^n\mathrm{个}， \\ \mathrm{所}\mathrm{以}\mathrm{不}\mathrm{同}\mathrm{子}\mathrm{集}\mathrm{个}\mathrm{数}\mathrm{为}：C_n^0+C_n^1+\cdots +c_n^n=2^n. \end{gathered}$$

幂集

$$\begin{gathered} \mathrm{设}A\mathrm{为}\mathrm{任}\mathrm{意}\mathrm{集}\mathrm{合}，\mathrm{把}A\mathrm{的}\mathrm{所}\mathrm{有}\mathrm{不}\mathrm{同}\mathrm{子}\mathrm{集}\mathrm{构}\mathrm{成}\mathrm{的}\mathrm{集}\mathrm{合}\mathrm{叫}\mathrm{做}A\mathrm{的}\mathrm{幂}\mathrm{集}(powerset),\mathrm{记}\mathrm{作}P(A),\mathrm{即}， \\ P(A)=\{x\mid x\text{sube}A\} \\ \mathrm{推}\mathrm{论}：x\in P(A)\iff x\text{sube}A \end{gathered}$$

幂集也叫做集族或者集合的集合

集合的运算

并运算

$$\begin{gathered} \mathrm{设}A，B\mathrm{是}\mathrm{两}\mathrm{个}\mathrm{集}\mathrm{合}，\mathrm{则}\mathrm{集}\mathrm{合}A\mathrm{与}B\mathrm{的}\mathrm{并}\mathrm{集}\mathrm{定}\mathrm{义}\mathrm{为}： \\ A\cup B=\{x\mid x\in A\mathrm{或}x\in B\} \end{gathered}$$

交运算

$$\begin{gathered} \mathrm{设}A，B\mathrm{是}\mathrm{两}\mathrm{个}\mathrm{集}\mathrm{合}，\mathrm{则}\mathrm{集}\mathrm{合}A\mathrm{与}B\mathrm{的}\mathrm{交}\mathrm{集}\mathrm{定}\mathrm{义}\mathrm{为}： \\ a\cap B=\{x\mid x\in A\mathrm{并}\mathrm{且}x\in B\} \end{gathered}$$

补运算

$$\begin{gathered} \mathrm{设}U\mathrm{是}\mathrm{全}\mathrm{集}，\mathrm{则}\mathrm{集}\mathrm{合}A\mathrm{的}\mathrm{补}\mathrm{集}\mathrm{定}\mathrm{义}\mathrm{为}： \\ \bar{a}=\{x\mid x\notin A\} \end{gathered}$$

差运算

$$\begin{gathered} \mathrm{设}A，B\mathrm{是}\mathrm{两}\mathrm{个}\mathrm{集}\mathrm{合}，\mathrm{则}\mathrm{集}\mathrm{合}A\mathrm{与}B\mathrm{的}\mathrm{差}\mathrm{集}\mathrm{定}\mathrm{义}\mathrm{为}： \\ A-B=\{x\mid x\in A\mathrm{并}\mathrm{且}x\notin B\} \end{gathered}$$

对称差运算

$$\begin{gathered} \mathrm{设}A，B\mathrm{是}\mathrm{两}\mathrm{个}\mathrm{集}\mathrm{合}，\mathrm{则}\mathrm{集}\mathrm{合}A\mathrm{与}B\mathrm{的}\mathrm{对}\mathrm{称}\mathrm{差}\mathrm{定}\mathrm{义}\mathrm{为}： \\ A\oplus B=\{x\mid (x\in A\mathrm{并}\mathrm{且}x\notin B)\mathrm{或}\mathrm{者}(x\notin A\mathrm{并}\mathrm{且}x\in B)\} \end{gathered}$$

运算拓展

并集和交集的拓展

$$\begin{gathered} \mathrm{设}{A}_1,A_2,\cdots ,A_n\mathrm{是}\mathrm{任}\mathrm{意}n\mathrm{个}\mathrm{集}\mathrm{合}，\mathrm{则}\mathrm{这}n\mathrm{个}\mathrm{集}\mathrm{合}\mathrm{的}\mathrm{并}\mathrm{集}\mathrm{是}\mathrm{包}\mathrm{含}\mathrm{哪}\mathrm{些}\mathrm{至}\mathrm{少} \\ \mathrm{是}\mathrm{这}\mathrm{组}\mathrm{集}\mathrm{合}\mathrm{中}\mathrm{一}\mathrm{个}\mathrm{集}\mathrm{合}\mathrm{成}\mathrm{员}\mathrm{的}\mathrm{元}\mathrm{素}\mathrm{的}\mathrm{集}\mathrm{合}，\mathrm{即}， \\ \bigcup _{i=1}^n{A}_i=A_1\cup A_2\cup A_3\cup \cdots \cup A_n=\{x\mid x\in A_1\mathrm{或}\mathrm{者}x\in A_2\cdots \mathrm{或}\mathrm{者}x\in A_n\} \\ \mathrm{设}{A}_1,A_2,\cdots ,A_n\mathrm{是}\mathrm{任}\mathrm{意}n\mathrm{个}\mathrm{集}\mathrm{合}，\mathrm{则}\mathrm{这}n\mathrm{个}\mathrm{集}\mathrm{合}\mathrm{的}\mathrm{交}\mathrm{集}\mathrm{是}\mathrm{包}\mathrm{含}\mathrm{哪}\mathrm{些}\mathrm{属}\mathrm{于} \\ \mathrm{这}\mathrm{组}\mathrm{集}\mathrm{合}\mathrm{中}\mathrm{所}\mathrm{有}\mathrm{集}\mathrm{合}\mathrm{成}\mathrm{员}\mathrm{的}\mathrm{元}\mathrm{素}\mathrm{的}\mathrm{集}\mathrm{合}，\mathrm{即}， \\ \bigcap _{i=1}^n{A}_i=A_1\cap A_2\cap A_3\cap \cdots \cap A_n=\{x\mid x\in A_1\mathrm{并}\mathrm{且}x\in A_2\cdots \mathrm{并}\mathrm{且}x\in A_n\} \end{gathered}$$

集合的运算定律

定理

$$\begin{gathered} \frac{\mathrm{设}U\mathrm{为}\mathrm{全}\mathrm{集}，A,B,C\mathrm{为}\mathrm{任}\mathrm{意}\mathrm{集}\mathrm{合}。 \\ 1、A\cup A=A,A\cap A=A(\mathrm{幂}\mathrm{等}\mathrm{率}) \\ 2、A\cup B=B\cup A,A\cap B=B\cap A（\mathrm{交}\mathrm{换}\mathrm{律}） \\ 3、A\cup (B\cup C)=(A\cup B)\cup C,A\cap (B\cap C)=(A\cap B)\cap C(\mathrm{交}\mathrm{换}\mathrm{律}) \\ 4、A\cup \varnothing =A,A\cap U=A(\mathrm{同}\mathrm{一}\mathrm{律}) \\ 5、A\cup U=U,A\cap \varnothing =\varnothing （\mathrm{零}\mathrm{律}） \\ 6、A\cup (B\cup C)=(A\cup B)\cap (A\cup C),A\cap (B\cup C)=(A\cap B)\cup (A\cap C)(\mathrm{分}\mathrm{配}\mathrm{率}) \\ 7、A\cup (A\cap B)=A,A\cap (A\cup B)=A（\mathrm{吸}\mathrm{收}\mathrm{律}） \\ 8、\bar{A}\cap A=\varnothing ,\bar{A}\cup A=U(\mathrm{矛}\mathrm{盾}\mathrm{律}\mathrm{和}\mathrm{排}\mathrm{中}\mathrm{律}) \\ 9、\stackrel{=}{A}=A(\mathrm{双}\mathrm{重}\mathrm{否}\mathrm{定}\mathrm{率}) \\ 10、\overline{A\cup B}=\bar{A}\cap \bar{B},\overline{A\cap B}=\bar{A}\cup \bar{B}(\mathrm{德}\mathrm{摩}\mathrm{根}\mathrm{律})\mathrm{长}\mathrm{杠}\mathrm{变}\mathrm{短}\mathrm{杠}，\mathrm{符}\mathrm{号}\mathrm{变}\mathrm{方}\mathrm{向} \\ }{} \end{gathered}$$

证明方法

证明框架

证明：

1. 首先证明 $A\subseteq B:\mathrm{\forall }x\in A,\cdots ,x\in B,\therefore A\subseteq B$

2. 首先证明 $B\subseteq A:\mathrm{\forall }x\in B,\cdots ,x\in A,\therefore B\subseteq A$

由以上两点，克制A=B。

Example

证明德摩根律的等式之一：$\overline{A\cup B}=\bar{A}\cap \bar{B}$

证明：

1. 首先证明$\overline{A\cup B}\subseteq \bar{A}\cap \bar{B}$ $$\begin{array}{rl}\mathrm{\forall }x\in \overline{A\cup B}& \Rightarrow x\notin A\cup B\Rightarrow x\notin A\mathrm{并}\mathrm{且}x\notin B\\ & \Rightarrow x\in \bar{A}\mathrm{并}\mathrm{且}x\in \bar{B}\Rightarrow x\in \bar{A}\cap \bar{B}\end{array}$$

2. 其次证明$\bar{A}\cap \bar{B}\subseteq \overline{A\cup B}$ $$\begin{array}{rl}\mathrm{\forall }x\in \bar{A}\cap \bar{B}& \Rightarrow x\in \bar{a}\mathrm{并}\mathrm{且}x\in \bar{B}\Rightarrow x\notin A\mathrm{并}\mathrm{且}x\notin B\\ & \Rightarrow x\notin A\cup B\Rightarrow \overline{A\cup B}\end{array}$$

由以上两点，克制等式$\overline{A\cup B}=\bar{A}\cap \bar{B}$成立

可数集合与不可数集合

自然数集的定义

Definition(皮亚诺定理)

1891年，意大利数学家皮亚诺公开发表了基于序数的自然数定义公理。这组公理包括：

1. 0是自然数
2. 每个自然数n都有一个后继，这个后继也是一个自然数，记为S（n）；
3. 两个自然数相等当且仅当它们有相同的后继，即m=n当且仅当S(m)=S(n);
4. 没有任何自然数的后继为0；
5. （归纳公理）$\mathrm{若}，\mathrm{如}\mathrm{果}1、(0)\mathrm{为}\mathrm{真};2、\mathrm{当}(n)\mathrm{为}\mathrm{真}，\mathrm{则}\mathrm{有}(S(n))\mathrm{为}\mathrm{真};\mathrm{则}(n)\mathrm{对}\mathrm{任}\mathrm{意}\mathrm{自}\mathrm{然}\mathrm{数}n\mathrm{成}\mathrm{立}。$

Definition(冯诺依曼的自然数定义)

20世纪初，集合成为数学的基本概念之后，数学奇才、计算机之父冯诺依曼基于基数，利用一个集合的序列来定义自然数：

1. $\varnothing \in N$

2. $\mathrm{若}n\in N,\mathrm{则}{n}^{\prime }\equiv n\cup \{n\}\in N$

从而，这个集合序列的基数就可以来定义自然数

• $0\equiv \mid \varnothing \mid ;$
• $1\equiv \mid \varnothing \cup \{\varnothing \}\mid =\mid \{\varnothing \}\mid$
• $2\equiv \mid \{\varnothing \}\cup \{\{\varnothing \}\}\mid =\mid \{\varnothing ,\{\varnothing \}\}\mid$
• $\cdots$

集合比较

有限集合比较集合的基数

Definition

设A，B为两个集合，若在A，B之间存在一种一一对应的关系：

$\mathrm{\Psi }:A\to B$

则称A与B是等势的(equipotential)，记作

$A\sim B$

由等势定义可以看书，如果A=B，那么$A\sim B$,反之却不成立

可数集合

Definition

凡是自然数集合N等势的集合，成为可数集合(countable set),该集合的基数记为${\mathrm{\aleph }}_0$(读作阿列夫零)

正奇数集合是可数集合

素数集合是可数集合

有理数集合Q是可数集合

从有限到无限，不仅仅是简单数量上的变化（量变），而引起了本质的改变（质变）。

• 两个无限集合的“大小”已经不能使用集合中的元素个数来衡量。${\mathrm{\aleph }}_0$可以表示一切可数集合的基数，是一种抽象的表达。
• 表面上个数完全不相等的两个集合之间仍可能存在等势关系，如集合与其真子集之间，这体现了有限集合和无限集合的根本差别。

不可数集合

Definition

开区间(0,1)成为不可数集合，凡与开区间(0,1)等势的集合，称为不可数集合，该类集合的基数记为$\mathrm{\aleph }$

eg:

闭区间[0,1]是不可数集合

实数集合R是不可数集合.$n\to \tan (\pi \frac{2n-1}{2})$