本文最后更新于：2023年6月27日上午

DM2 集合论

DM2.1 集合

集合：指定范围内所有满足给定条件的对象的聚集。其中的每个对象称为该集合的元素。集合中的元素是无序且不同的。

通常用大写英文字母表示集合（ $A$ 、 $A_1$ ），用小写字母表示元素（ $a$ 、 $a_1$ ）

常用集合：

$N$ ：自然数集，也就是全体非负整数集
$Z$ ：整数集
$Q$ ：有理数集
$R$ ：实数集

如何描述一个集合

枚举法

列举出集合中的全部或部分元素，其余元素使用省略号表示

如： $A = \{1,2,3,4\}$ 、 $B = \{ a,b,c,d,…\}$
叙述法

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

如： $P=\{ x\mid P(x)\}$ 、 $L=\{ x\mid x是英文字母中的所有元音字母\}$
文氏图

利用平面上的点来做成对集合的图解方法。一般用平面上的方形或圆形表示集合，用平面上的圆点来表示元素

集合的基本概念

属于

若 $a$ 是 $A$ 中的元素，则称 $a$ 属于 $A$ 。记为 $a\in A$ 。否则，称 a 不属于 A，记为 $a\notin A$
子集

如果一个集合中的所有元素都是另一集合的元素，这种关系称为包含关系。记为 $A \subseteq B$ 。否则记为 $A \not\subseteq B$ 。

符号化形式：

$\quad B\subseteq A⇔∀x(x\in B → x\in A)$

$\quad B\not\subseteq A⇔∃x(x\in B ∧ x\not\in A)$
相等

当且仅当两个集合的元素完全相同时，称两个集合相等。记为 $A = B$ 。否则，称两个集合不相等，记为 $A\neq B$ 。

符号化形式：

$\quad A=B ⇔ (A \subseteq B)∧ (B \subseteq A)$

$\quad A=B ⇔∀x(x\in B ∧ x\in A)$
真子集

如果 $A \subseteq B$ 并且 $A \neq B$ 则称 A 是 B 的真子集，记为 $A \subset B$ 。否则记为 $A \not\subset B$

符号化形式：

$\quad B\subset A⇔A\subseteq B ∧ A \neq B$

$\quad B\not\subset A⇔∃x(x\in A∧ x\not\in B)∧ A \neq B$
基数

集合中的元素个数称为集合的基数。A 的基数记为 $\mid A\mid$

$\emptyset$ 是 0 元集，只含一个元素的集合是 1 元集，以此类推。

若一个集合的基数是有限的，称该集合为有限集。否则为无限集。
空集

不含任何元素的集合称为空集，记为 $\emptyset$ 。空集是最小的集合

空集是唯一的（ $\emptyset _1=\emptyset _2$ ）

空集是一切集合的子集（ $\emptyset\subseteq A$ ）
全集

针对一个具体范围，我们考虑的所有对象的集合叫做全集，记为 $U$ 或 $E$ 。全集是相对的。
幂集

由一个集合的所有子集组成的集合称为其幂集。记为 $P(A)$ 。用描述法表示为 $P(A)=\{ x\mid x\subseteq A\}$
集族

除幂集外，其他形式的由集合构成的集合称为集族
多重集

设全集为 $E$ ， $E$ 中元素可以多次出现的集合 $A$ 称为多重集。那个出现次数称为 $A$ 的重复度。

集合可以视为是重复度为 1 的多重集
并集

由两个集合 $A,B$ 所有元素构成的集合为其并集，记作 $A\cup B$

其描述法表示为： $A\cup B=\{ x\mid x\in A∨ x\in B\}$

并运算可以推广到有限个或可数个集合（初级并）

$\quad A_1{\cup}A_2{\cup}{…}{\cup}A_n=\{x\mid ∃i(1{\le}i{\le}n{∧}x{\in}A_i)\}$

$\quad {\bigcup_{i=1}^{n}\\}{A_i=A_1{\cup}A_2{\cup}{…}{\cup}A_n}$
交集

由两个集合 $A,B$ 共有的元素构成的集合为其交集，记作 $A\cap B$

其描述法表示为： $A\cap B=\{ x\mid x\in A∧ x\in B\}$

交运算可以推广到有限个或可数个集合（初级交）

$\quad A_1{\cap}A_2{\cap}{…}{\cap}A_n=\{x\mid ∀i(1{\le}i{\le}n{→}x{\in}A_i)\}$

$\quad {\bigcap_{i=1}^{n}\\}A_i=A_1{\cap}A_2{\cap}{…}{\cap}A_n$
不相交

如果 $A{\cap}B=Ø$ ，则称 $A$ 和 $B$ 是不相交的
相对补

对于集合 $A,B$ ，由属于 $A$ 但不属于 $B$ 的元素组成的集合称为 $B$ 对 $A$ 的相对补集。记作 $A-B$

描述法表示为： $A-B=\{x\mid x{\in}A{∧}x{\not\in}B\}$
对称差

由属于 $A$ 但不属于 $B$ ，或属于 $B$ 却不属于 $A$ 的元素组成的集合称为 $B$ 对 $A$ 的对称差。记为 $A{\oplus}B$

描述法表示为： $A{\oplus}B=\{x\mid (x{\in}A{∧}x{\not\in}B){∨}(x{\in}B{∧}x{\not\in}A)\}$

$A{\oplus}B=(A-B){\cup}(B-A)=(A{\cup}B)-(A{\cap}B)$
绝对补集

设 $E$ 为全集， $A{\subseteq}E$ ，称 $A$ 对 $E$ 的相对补集为 $A$ 的绝对补集。记为 $\tilde\ {A}$

描述法表示为：$\tilde\ {A}={x\mid x{\in}E{∧}x{\notin}A} $，由于 $x{\in}E=1$ 又有 $\tilde\ A =\{x\mid x{\notin}A\}$
广义并集

由一个集族 ${\mathcal A}$ 中全体元素的元素组成的集合为其广义并，记为 ${\bigcup}{\mathcal A}$ （大并 ${\mathcal A}$ ）

描述法表示为： ${\bigcup}{\mathcal A}=\{x\mid {∃}z(x{\in}z{∧}z{\in}{\mathcal A})\}$
广义交集

由一个集族 ${\mathcal A}$ 中全体元素的共有元素组成的集合为其广义交，记为 ${\bigcap}{\mathcal A}$ （大交 ${\mathcal A}$ ）

描述法表示为： ${\bigcap}{\mathcal A}=\{x\mid {∀}z(x{\in}{\mathcal A}{→}z{\in}z)\}$

空集不能求广义交。即 ${\cap}{Ø}$ 无意义

集合运算的优先级

优先级	运算	类型	顺序
1	绝对补、幂集、广义交、广义并	一元运算	从右向左
2	初级并、初级交、相对补、对称差等	二元运算	从左向右

容斥原理

设 $A_1,A_2,{\dots},A_n$ 为 n 个集合，则有

$\quad\mid {\bigcup_{i=1}^{n}\\}A_i\mid ={\sum_{i=1}^{n}\\}\mid A_i\mid -{\sum_{i< j}\\}\mid A_i{\cap}A_j\mid +{\sum_{i<j<k}\\}\mid A_i{\cap}A_j{\cap}A_k\mid -{…}+(-1)^{n-1}\mid A_1{\cap}A_2{\cap}{…}{\cap}A_n\mid$

DM2.2 基本的集合恒等式

设 $E$ 为全集， $A,B,C$ 是 $E$ 的任意子集。则有：

幂等律： $A{\cup}A=A{\qquad}A{\cap}A=A$
交换律： $A{\cup}B=B{\cup}A{\qquad}A{\cap}B=B{\cap}A$
结合律： $A{\cup}(B{\cup}C)=(A{\cup}B){\cup}C{\qquad}A{\cap}(B{\cap}C)=(A{\cap}B){\cap}C$
分配律： $A{\cup}(B{\cap}C)=(A{\cup}B){\cap}(A{\cup}C){\qquad}A{\cap}(B{\cup}C)=(A{\cap}B){\cup}(A{\cap}C)$
德·摩根定律： $\tilde\ (A{\cup}B)=\tilde\ A{\cap}\tilde\ B{\qquad}\tilde\ (A{\cap}B)=\tilde\ A{\cup}\tilde\ B$

$E-(A{\cup}B)=(E-A){\cap}(E-B){\qquad}E-(A{\cap}B)=(E-A){\cup}(E-B)$

$\tilde\ (A_1{\cup}A_2{\cup…\cup}A_n)=\tilde\ A_1{\cap}\tilde\ A_2{\cap…\cap}\tilde\ A_n{\qquad}\tilde\ (A_1{\cap}A_2{\cap…\cap}A_n)=\tilde\ A_1{\cup}\tilde\ A_2{\cup…\cup}\tilde\ A_n$
吸收律： $A{\cup}(A{\cap}B)=A{\qquad}A{\cap}(A{\cup}B)=A$
零律： $A{\cup}E=E{\qquad}A{\capØ}={Ø}$
同一律： $A{\cap}E=A{\qquad}A{\cupØ}=A$
排中律： $A{\cup}\tilde\ A=E$
矛盾律： $A{\cap}\tilde\ A={Ø}$
余补律： ${\tilde\ E}={Ø}{\qquad}{\tilde\ Ø}=E$
双重否定律： ${\tilde\ \tilde\ A}=A$
补交转换律： $A-B=A{\cap}{\tilde\ B}$

设 $\{A_{\alpha} \} _{\alpha\in S}$ 为集族， $B$ 为一集合。则有：

分配律： $B{\cup}(\bigcap{ \{ {A_{\alpha} } \} }_{\alpha\in S})={\bigcap_{\alpha\in S}\\}(B{\cup}A_{\alpha}){\qquad}B{\cap}(\bigcup{ \{ {A_{\alpha} } \} }_{\alpha\in S})={\bigcup_{\alpha\in S}\\}(B{\cap}A_{\alpha})$
德·摩根律： ${\tilde\\}(\bigcup{ \{ {A_{\alpha} } \} }_{\alpha\in S})={\bigcap_{\alpha\in S}\\}{\tilde\\A_{\alpha} }{\qquad}{\tilde\\}(\bigcap{ \{ {A_{\alpha} } \} }_{\alpha\in S})={\bigcup_{\alpha\in S}\\}{\tilde\\A_{\alpha} }$

$\quad B-({\bigcup{ \{ {A_{\alpha} } \} }_{\alpha\in S} })={\bigcap_{\alpha\in S}\\}(B-A_{\alpha}){\qquad}B-({\bigcap{ \{ {A_{\alpha} } \} }_{\alpha\in S} })={\bigcup_{\alpha\in S}\\}(B-A_{\alpha})$
幂集： $A{\subseteq}B{⇔}P(A){\subseteq}P(B){\qquad}P(A-B){\subseteq}(P(A)-P(B)){\cup}{ \{Ø\} }$

DM2.3 有序对和笛卡尔积

有序对

$\quad {⟨}a,b{⟩}={ {a} ,{a,b} } $

其中 $a$ 为第一元素， $b$ 为第二元素。 ${⟨}a,b{⟩}$ 也记作 $(a,b)$

有定理： ${⟨}a,b{⟩}={⟨}c,d{⟩}{⇔}(a=c){∧}(b=d)$
有序三元组

$\quad {⟨}a,b,c{⟩}={⟨}{⟨}a,b{⟩},c{⟩}$
有序 n 元组

$\quad {⟨}a_1,a_2,{…},a_n{⟩}={⟨}{⟨}a_1,a_2,{…},a_{n-1}{⟩},a_n{⟩}$

有定理： ${⟨}a_1,a_2,{…},a_n{⟩}={⟨}b_1,b_2,{…},b_n{⟩}{⇔}a_i=b_i,i=1,2,{…},n$
笛卡尔积

有集合 $A,B$ ，由 $A$ 中的每个元素（做第一元素）与 $B$ 中的每个元素（做第二元素）组合，形成的所有有序对的集合称为笛卡尔积（卡式积），记为 $A{\times}B$

笛卡尔积的性质：
- 非交换性： $(A{\not=}B{∧}A{\not=Ø∧}B{\not=Ø}){⇔}(A{\times}B{\not =}B{\times}A)$
- 非结合性： $(A{\not=Ø∧}B{\not=Ø∧}C{\not=Ø}){⇔}((A{\times}B){\times}C{\not =}A{\times}(B{\times}C))$
- 分配律： $A\times (B\cup C)=(A\times B)\cup(A\times C)\quad$ 等
- 其他： $A{\times}B={Ø}{⇔}A={Ø∨}B={Ø}\qquad A\not=Ø∧ A\times B\subseteq A\times C⇔ B\subseteq C$
  
  $\quad A\subseteq C∧ B\subseteq D⇒ A\times B\subseteq C\times D$
n 维笛卡尔积

$\quad A_1\times A_2\times…\times A_n=\{⟨ x_1,x_2,…,x_n⟩\mid x_1\in A_1∧ x_2\in A_2∧…∧ x_n\in A_n\}$

$\quad A^n=A\times A\times A…\times A$

$\quad \mid A_i\mid =n_i,i=1,2,…,n⇒\mid A_1\times A_2\times…\times A_n\mid =n_1\times n_2\times…\times n_n$

n 维卡式积的性质与二维卡式积相似

DM2.4 二元关系

n 元关系

元素全是有序 n 元组的集合称为 n 元关系。

对于二元关系，有几种表示方法。设 $F$ 是二元关系，有：
- 中缀记法： $xFy\qquad$ 如 $2<15$
- 前缀记法： $F(x,y)\quad Fxy\qquad$ 如 $<(2,15)$
- 后缀记法： $⟨ x,y⟩\in F\quad xyF\qquad$ 如 $⟨ 2,15⟩\in <$
任何 $A\times B$ 的子集就是 $A$ 到 $B$ 的二元关系。

$\quad R\,是\,A\,到\,B\,的二元关系⇔ R\subseteq A\times B⇔ R\in P(A\times B)$

若 $\mid A\mid =m,\mid B\mid =n,\mid A\times B\mid =mn$ ，故 $\mid P(A\times B)\mid =2^{mn}$ ，即 $A$ 到 $B$ 的不同二元关系有 $2^{mn}$ 个
任何 $A\times A$ 的子集就是 $A$ 上的二元关系。

$\quad R\,是\,A\,上的二元关系⇔ R\subseteq A\times A⇔ R\in P(A\times A)$

若 $\mid A\mid =m,\mid A\times A\mid =m^2$ ，故 $\mid P(A\times A)\mid =2^{m^2}$ ，即不同的 $A$ 上二元关系有 $2^{m^2}$ 个
一些特殊关系

设 $A$ 是集合，则可定义 $A$ 上的：
- 空关系： $Ø$
- 恒等关系： $I_A=\{⟨ x,x⟩\mid x\in A\}$
- 全域关系： $E_A=A\times A=\{⟨ x,y⟩\mid x\in A∧ y\in A\}$
设 $A\subseteq Z$ ，则可定义 $A$ 上的：
- 整除关系： $D_A=\{⟨ x,y⟩\mid x\in A∧ y\in A∧ x\mid y\}$
- 小于等于关系： ${LE}_A$
  
  小于关系： $L_A$
  
  大于等于关系： ${GE}_A$
  
  大于关系： $G_A$
设 $A$ 是集合，则可定义 $P(A)$ 上的：
- 包含关系
- 真包含关系
定义域、值域、域

对于任意集合 $R$ ，可以定义

其定义域： $\operatorname{dom}R=\{ x\mid ∃ y(xRy)\}$

其值域： $\operatorname{ran}R=\{ y\mid ∃ y(xRy)\}$

其域： $\operatorname{fld}R=\operatorname{dom}R\cup\operatorname{ran}R$

如：集合 $R_1=\{ a,b\},R_2=\{ a,b,⟨ c,d⟩,⟨ e,f⟩\}$ ，当 $a,b$ 不是有序对时， $R_1,R_2$ 不是关系。

$\quad\operatorname{dom}R_1=Ø\qquad\operatorname{ran}R_1=Ø\qquad\operatorname{fld}R_1=Ø$

$\quad\operatorname{dom}R_2=\{ c,e\}\qquad\operatorname{ran}R_2=\{ d,f\}\qquad\operatorname{fld}R_2=\{ c,d,e,f\}$
逆、合成

对于任意集合 $F,G$ 可以定义

逆： $F^{-1}=\{⟨ x,y⟩\mid yFx\}$

合成（逆序合成、左合成）： $F\circ G=\{⟨ x,y⟩\mid ∃ z(xGz∧ zFy)\}$

也能定义右合成： $F\circ G=\{⟨ x,y⟩\mid ∃ z(xGz∧ zFy)\}$

一般情况下，合成指的是右合成

有以下定理：
- $(R_1\circ R_2)\circ R_3=R_1\circ (R_2\circ R_3)$
- $(F\circ G)^{-1}=F^{-1}\circ G^{-1}$
限制、象

对于任意集合 $F,A$ 可以定义

限制： $F\restriction A=\{⟨ x,y⟩\mid xFy∧ x\in A\}$

象： $F[A]=\operatorname{ran}(F\restriction A)$
单根

对于集合 $F$ 可以定义单根

$\quad F\,是单根的⇔∀ y(y\in\operatorname{ran}F→ ∃!x(x\in\operatorname{dom}F∧ xFy))⇔(∀ y\in\operatorname{ran}F)(∃!x\in\operatorname{dom}F)(xFy)$

上面的 $∃!$ 表示：存在唯一的

$∀ x(x\in A→ B(x))$ 缩写为 $(∀ x\in A)B(x)$

$∃ x(x\in A∧ B(x))$ 缩写为 $(∃ x\in A)B(x)$
单值

对于集合 $F$ 可以定义单值

$\quad F\,是单值的⇔∀ x(x\in\operatorname{dom}F→ ∃!y(y\in\operatorname{ran}F∧ xFy))⇔(∀ x\in\operatorname{dom}F)(∃!y\in\operatorname{ran}F)(xFy)$

函数就可以被视作单值的二元关系

DM2.5 关系的表示

关系的表示有三种方法

集合
关系矩阵
关系图

#关系矩阵

$\quad A=\{ a_1,a_2,…,a_n\},\,B=\{ b_1,b_2,…,b_m\},\,R=A\times B$

则 $R$ 的关系矩阵有

$\quad M(R)=(r_{ij})_{n\times m}\qquad M(R)(i,j)=r_{ij}=\begin{cases}1,\quad a_iRb_j\\0,\quad 否则\end{cases}$

如， $A=\{ a,b,c\},\,B=\{ d,e,f\},\,R=\{⟨ a,d⟩,⟨ a,f⟩,⟨ b,f⟩,⟨ c,e⟩\}$

则 $M(R)=\left[ \begin{matrix}1\quad 0\quad 1\\0\quad 0\quad 1\\0\quad 1\quad 0\end{matrix}\right]$

集合表达式与关系矩阵可以唯一相互确定

矩阵转置： $M(R^{-1})=(M(R))^{T}$
逻辑乘： $M(R_1\circ R_2)=M(R_2)• M(R_1)$ ，其中乘法对应逻辑的 $∧$ ，加法对应逻辑的 $∨$

有关矩阵的乘法

设 $A$ 为 $m\times p$ 的矩阵， $B$ 为 $p\times n$ 的矩阵，那么称 $m\times n$ 的矩阵 $C$ 为矩阵 $A$ 与 $B$ 的乘积，记作 $C=AB$ 或 $C=A\times B$

此时，矩阵 $C$ 中第 $i$ 行 $j$ 列的元素有： $\quad c_{ij}={\sum_{k=1}^{p}\\}(a_{ik}\times b_{kj})=a_{i1}\times b_{1j}+a_{i2}\times b_{2j}+…+a_{ip}\times b_{pj}$

对于矩阵 $A,B$ 仅当 $A\,的行数\,=\,B\,的列数$ 时才能进行矩阵相乘。

如存在矩阵 $A=\left[\begin{matrix}a_1\quad a_2\quad a_3\end{matrix}\right],\,B=\left[\begin{matrix}b_1\\b_2\\b_3\end{matrix}\right]$

则 $A\times B =\left[\begin{matrix}a_1\times b_1\quad a_1\times b_2\quad a_1\times b_3\\a_2\times b_1\quad a_2\times b_2\quad a_2\times b_3\\a_3\times b_1\quad a_3\times b_2\quad a_3\times b_3\end{matrix}\right]$

#关系图

$\quad A=\{ a_1,a_2,…,a_n\},\,B=\{ b_1,b_2,…,b_m\},\,R=A\times B$

则 $R$ 的关系图 $G(R)$ ：

以 $∘$ 表示 $A,B$ 中元素（称为顶点），以 $→$ 表示 $R$ 中元素
若 $a_iRb_j$ 则从顶点 $a_i$ 向顶点 $b_j$ 引有向边 $⟨ a_i,b_j⟩$

下面是 $A=\{ a,b,c\},\,R=\{ {⟨ a,a⟩},{⟨ a,b⟩},{⟨ b,a⟩},{⟨ b,c⟩} \}$ 的关系图 $G(R)$ （我尽力了）

graph LR
a((a)) --> b((b)) --> c((c))
b --> a
a --> a

关系图、关系矩阵、关系表达式间都能相互确定。

对于 $G(A\times B)$ ，关系图中的边都是由 $A$ 中元素指向 $B$ 的

DM2.6 关系的性质

自反性（reflexivity）

对于关系 $R\subseteq A\times A$ ，其自反性有：

$\quad R\,是自反的⇔∀ x(x\in A→ xRx)⇔(∀ x\in A)xRx$

相反地有

$\quad R\,是非自反的⇔∃ x(x\in A∧\neg xRx)$

关于自反性有如下定理：

$\quad R\,是自反的$
$⇔ I_A\subseteq R$
$⇔ R^{-1}\,是自反的$
$⇔ M(R)\,主对角线上的元素全是\,1$
$⇔ G(R)的每个顶点处都有环$
反自反性

对于关系 $R\subseteq A\times A$ ，其反自反性有：

$\quad R\,是反自反的⇔∀ x(x\in A→ \neg xRx)⇔(∀ x\in A)\neg xRx$

相反地有

$\quad R\,是非反自反的⇔∃ x(x\in A∧ xRx)$

可以想见，对于 $R\subseteq A\times A,\,Q=(A\times A)-R$ ，如果 $R$ 是反自反的，那么 $Q$ 就是自反的

关于反自反性有如下定理：

$\quad R\,是反自反的$
$⇔ I_A\cap R=Ø$
$⇔ R^{-1}\,是反自反的$
$⇔ M(R)\,主对角线上的元素全是\,0$
$⇔ G(R)的每个顶点处都无环$
对称性（symmetry）

对于关系 $R\subseteq A\times A$ ，其对称性有：

$\quad R\,是对称的$
$⇔ ∀ x∀ y(x\in A∧ y\in A∧ xRy→ yRx)$
$⇔(∀ x\in A)(∀ y\in A)[xRy→ yRx]$

相反地有

$\quad R\,是非对称的⇔∃ x∃ y(x\in A∧ y\in A∧ xRy∧\neg yRx)$

关于对称性有如下定理：

$\quad R\,是对称的$
$⇔ R^{-1}=R$
$⇔ R^{-1}\,是对称的$
$⇔ M(R)\,是对称的$
$⇔ G(R)\,的所有边都有反向边$
反对称性

对于关系 $R\subseteq A\times A$ ，其反对称性有：

$\quad R\,是反对称的$
$⇔∀ x∀ y(x\in A∧ y\in A∧ xRy∧ yRx→ A=B)$
$⇔(∀ x\in A)(∀ y\in A)[xRy∧ yRx→ A=B]$

相反地有

$\quad R\,是非反对称的⇔∃ x∃ y(x\in A∧ y\in A∧ xRy∧ yRx ∧ A\not=B)$

可见，反对称性可能与对称性同时存在

关于非反对称性有如下定理：

$\quad R\,是反对称的$
$⇔R^{-1}\cap R\subseteq I_A$
$⇔R^{-1}\,是反对称的$
$⇔在\,M(R)\,中，∀ i∀ j(i\not=j∧ r_{ij}=1→ r_{ji}=0)$
$⇔G(R)\,的所有不同点间有不多于\,1\,条边$
传递性（transtivity）

对于关系 $R\subseteq A\times A$ ，其传递性有：

$\quad R\,是传递的$
$⇔∀ x∀ y∀ z(x\in A∧ y\in A∧ z\in A∧ xRy∧ yRz→ xRz)$
$⇔(∀ x\in A)(∀ y\in A)(∀ z\in A)[xRy∧ yRz→ xRz]$

相反地有

$\quad R\,是非传递的$
$⇔∃ x∃ y∃ z(x\in A∧ y\in A∧ z\in A∧ xRy∧ yRz∧ \neg xRz)$

关于传递性有如下定理：

$\quad R\,是传递的$
$⇔R\circ R\subseteq R$
$⇔R^{-1}\,是传递的$
$⇔∀ i∀ j,M(R\circ R)(i,j)\le M(R)(i,j)$
$⇔在\,G(R)\,中，∀ a_i∀ a_j∀ a_k，若有有向边\,⟨ a_i,a_j⟩\,和\,⟨ a_j,a_k⟩ ，则必有有向边\,⟨ a_i,a_k⟩$

DM2.7 关系的幂运算和闭包

关系的 n 次幂

对于关系 $R\subseteq A\times A,n\in N$ ，有 $\begin{cases}R^0=I_A\\R^{n+1}=R^n\circ R(n\ge0)\end{cases}$

显然 $R^n\subseteq A\times A,n\in N$

对于 $R\subseteq A\times A,\, m,n\in N$ ，有如下定理：

$\quad R^m\circ R^n=R^{m+n}\qquad (R^m)^n=R^{mn}$
闭包

包含给定元素，并具有指定性质的最小集合称为闭包

闭包是任何 $包含\,R\,的某种集合$ 的子集合，或者所有 $包含\,R\,的某种集合$ 的交集。
- 自反闭包： $r(R)$ ，包含 $R$ 的具有自反性的闭包
  
  $\quad R\subseteq r(R)\qquad r(R)是自反的\qquad ∀ S((R\subseteq S∧ S 自反)→ r(r)\subseteq S)$
  
  $\quad r(R)=R\cup I_A$
- 对称闭包： $s(R)$ ，包含 $R$ 的具有对称性的闭包
  
  $\quad R\subseteq s(R)\qquad s(R)是对称的\qquad ∀ S((R\subseteq S∧ S 对称)→ s(r)\subseteq S)$
  
  $\quad s(R)=R\cup R^{-1}$
  
  传递关系的对称闭包不一定是传递的
- 传递闭包： $t(R)$ ，包含 $R$ 的具有传递性的闭包
  
  $\quad R\subseteq t(R)\qquad t(R)是传递的\qquad ∀ S((R\subseteq S∧ S 传递)→ t(r)\subseteq S)$
  
  $\quad t(R)=R\cup R^2\cup R^3\cup\dots$
闭包有如下定理：

$\quad R\,是自反的⇔ r(R)=R\quad R\,是对称的⇔ s(R)=R\quad R\,是传递的⇔ t(R)=R$

$\quad R_1\subseteq R_2\subseteq A\times A⇒\quad r(R_1)\subseteq r(R_2)\quad s(R_1)\subseteq s(R_2)\quad t(R_1)\subseteq t(R_2)$

$\quad r(R_1\cup R_2)=r(R_1)\cup r(R_2);\quad s(R_1\cup R_2)=s(R_1)\cup s(R_2)\quad t(R_1\cup R_2){\color{Red}{\supseteq} }t(R_1)\cup t(R_2)$

DM2.8 等价关系和划分

等价关系

有 $A\not=Ø\quad R\subseteq A\times A$ ，若 $R$ 是自反、对称的，则称 $R$ 是相容关系

若 $R$ 是自反、对称、传递的，则称 $R$ 是等价关系

由于 $st(R)\subseteq ts(R)$ ，对 $R$ 依次求闭包只有 $tsr(R)=trs(R)=rts(R)$ 是等价闭包
等价类

设 $R$ 是 $A\not=Ø$ 上的等价关系， $x\in A$ ，则 $x$ 关于 $R$ 的等价类是 $[x]_R=\{ y\mid y\in A∧ xRy\}$

简称 $x$ 的等价类，记为 $[x]$

设 $R$ 是 $A\not=Ø$ 上的等价关系， $∀ x,y\in A$ ，有以下定理

$\quad [x]_R\not=Ø$

$\quad xRy⇒[x]_R=[y]_R$

$\quad\neg xRy⇒[x]_R\cap[y]_R=Ø$

$\quad\bigcup\{[x]_R\mid x\in A\} =A$
商集

设 $R$ 是 $A\not=Ø$ 上的等价关系， $A$ 关于 $R$ 的商集是 $A/R=\{[x]_R\mid x\in A\}$

若 $A=\{ a_1,a_2,…,a_n\}$ 上有等价关系 $I_A,E_A,R_{ij}=I_A\cup\{⟨ a_i,a_j⟩,⟨ a_j,a_i⟩\},a_i,a_j\in A,i\not=j$

$\quad A/I_A={\{}\{a_1\}, \{ a_2\},…,\{ a_n\} \}$

$\quad A/E_A={\{}\{ a_1,a_2,…,a_n\} \}$

$\quad A/R_{ij}=A/I_A\cup{\{}\{ a_i,a_j\} \}-{\{}\{ a_i\},\{ a_j\} \}$
划分

$A\not=Ø$ 的一个划分是 ${\mathcal A}\subseteq P(A)$ 满足
1. $Ø\not\in\mathcal A$
2. $∀ x,y(x,y\in\mathcal A∧ x\not= y⇒ x\cap y=Ø)$
3. $\bigcup\mathcal A=A$
$\mathcal A$ 中的元素称为划分块

若 $A\not=Ø$ 则有以下定理

$\quad R\,是\,A\,上的等价关系⇒ A/R\,是\,A\,的划分$

$\quad\mathcal A\,是\,A\,的划分⇒ 同块关系\,R_{\mathcal A}\,是\,A上的等价关系\quad xR_{\mathcal A}y⇔∃ z(z\in\mathcal A∧ x\in z∧ y\in z)$ ，此时 $R_{\mathcal A}$ 称为 $\mathcal A$ 所定义的等价关系
Stirling 子集数

把 n 个编号的球放到 k 个相同的箱子里，不同放法的总数 $\begin{Bmatrix}n\\k\end{Bmatrix}$ 称为 Stirling 子集数

Srirling 子集数也是将 n 元集分成 k 个非空子集的分法总数

递推公式有 $\begin{Bmatrix}n\\k\end{Bmatrix}=\begin{cases}0\quad &k=0\\1\quad &n=k∨ k=1\\2^{n-1}-1\quad &k=2\\C_n^2\quad &n=k+1\\k\begin{Bmatrix}n-1\\k\end{Bmatrix}+\begin{Bmatrix}n-1\\k-1\end{Bmatrix}\quad &k > 1\end{cases}$

k>1 时，可以让 n-1 个元素分成 k 个子集后，加入第 n 个元素。或者让 n-1 个元素分成 k 个子集后，让第 n 个元素自成一个子集。
加细

有 $\mathcal{A,B}$ 是 $A$ 的划分。若 $\mathcal A$ 的划分块都含于 $\mathcal B$ 的某个划分块中，则称 $\mathcal A$ 是 $\mathcal B$ 的加细

DM2.9 序关系

偏序关系、偏序集

设 $A\not=Ø,\,R\subseteq A\times A$ ，若 $R$ 是 自反、反对称、传递的，则称 $R$ 是 $A$ 上的偏序关系。用 $\preccurlyeq$ 表示偏序关系，读作 “小于等于”

$\quad⟨ x,y⟩\in R⇔ xRy⇔ x\preccurlyeq y$

设 $\preccurlyeq$ 是 $A$ 上的偏序关系，则称 $⟨ A,\preccurlyeq⟩$ 为偏序集
可比、严格小于、覆盖

对于 $⟨ A,\preccurlyeq⟩,\,x,y\in A$ ，存在 $x\preccurlyeq y∨ y\preccurlyeq x$ ，则称 $x$ 和 $y$ 可比

若 $x\not= y$ ，则称 $x$ 严格小于 $y$ ，即 $x\preccurlyeq y∧ x\not=y⇔ x\prec y$

若不存在 $z$ 使 $x\prec z$ 且 $z\prec y$ ，则称 $y$ 覆盖 $x$ ，即 $x\prec y∧\neg∃ z(z\in A∧ x\prec z\prec y)$
哈斯图

对于 $⟨ A,\preccurlyeq⟩,\,x,y\in A$

用顶点表示 $A$ 中元素，当且仅当 $y$ 覆盖 $x$ 时， $y$ 在 $x$ 上方，在 $x,y$ 间画无向边，即形成哈斯图
全序关系（线序关系）

对于偏序集 $⟨ A,\preccurlyeq⟩$ ，若其中任意元素 $x,y$ 都可比，则称 $\preccurlyeq$ 是 $A$ 上从全序关系，称 $⟨ A,\preccurlyeq⟩$ 为全序集

$\quad ⟨ A,\preccurlyeq⟩\,是全序集⇔ 哈斯图是一条直线$
拟序关系

有 $A\not=Ø,\,R\subseteq A\times A$ ，若 $R$ 是 反自反、传递的（反自反性与传递性蕴含反对称性），则称 $R$ 为 $A$ 上的拟序关系。用 $\prec$ 表示拟序关系，称 $⟨ A,\prec⟩$ 为拟序集

若 $\preccurlyeq$ 是 $A$ 上的偏序关系， $\prec$ 是 $A$ 上的拟序关系，则
- $\prec$ 是反对称的
- $\preccurlyeq-I_A$ 是 $A$ 上的拟序关系
- $\prec\cup I_A$ 是 $A$ 上的偏序关系
若 $\prec$ 是 $A$ 上的拟序关系，则
- $x\prec y,\,x=y,\,y\prec x$ 中最多只有一个式子成立
- $(x\prec y∨ x=y)∧(y\prec x∨ x=y)⇒ x=y$
三歧性、拟线序

有 $A\not=Ø$ ， $\prec$ 是 $A$ 上的拟序关系，若 $x\prec y,\,x=y,\,y\prec x$ 中 有且仅有 一式成立，则称 $\prec$ 具有三歧性。同时称 $\prec$ 为 $A$ 上的拟线序关系，称 $⟨ A,\prec⟩$ 为拟线序集
最大（小）元、极大（小）元、上（下）界

对于偏序集 $⟨ A,\preccurlyeq⟩,B\subseteq A,y\in B$

$\quad y\,是\,B\,的最大元⇔∀ x(x\in B→ x\preccurlyeq y)$

$\quad y\,是\,B\,的最小元⇔∀ x(x\in B→ y\preccurlyeq x)$

$\quad y\,是\,B\,的极小元⇔∀ x(x\in B∧ y\preccurlyeq x→ x= y)$

$\quad y\,是\,B\,的极大元⇔∀ x(x\in B∧ x\preccurlyeq y→ x= y)$

对于 $z\in A$

$\quad z\,是\,A\,的上界⇔∀ x(x\in B→ x\preccurlyeq z)$

$\quad z\,是\,A\,的下界⇔∀ x(x\in B→ z\preccurlyeq x)$
良序

任何非空子集都有最小元的偏序关系

公理：任何集合都能被赋予一个良序

良序中的序数分为三类
- $0$
- 后继序数（有头有尾）： $1,2,\dots,\omega+1,\omega+2,\dots$
- 极限序数（有头无尾）： $\omega,2\omega,\omega^2,\omega^\omega,\dots$
链、反链

设 $⟨ A,\preccurlyeq⟩$ 为偏序集， $B\subseteq A$

$\quad B\,是\,A\,中的链⇔∀ x∀ y(x\in B∧ y\in B→ x\,与\,y\,可比)$

$\quad B\,是\,A\,中的反链⇔∀ x∀ y(x\in B∧ y\in B∧ x\not= y→ x\,与\,y\,不可比)$

$\quad\mid B\mid$ 称为（反）链的长度

设 $⟨ A,\preccurlyeq⟩$ 为偏序集， $A$ 中最长链长度为 $n$ ，则
- $A$ 中存在极大元
- $A$ 存在 $n$ 个划分块的划分，使每个划分块都是反链
- 若 $\mid A\mid =mn+1$ ，则 $A$ 中要么有长度为 $m+1$ 的反链，要么有长度为 $n+1$ 的链

DM2.10 函数

函数：也称映射。单值的二元关系。 $∀ x\in\operatorname{dom}F,\,∀ y,z\in\operatorname{ran}F,\,xFy∧ xFz→ y=z$

函数的记号： $F(x)=y⇔ ⟨ x,y⟩\in F⇔ xFy$

偏函数

设 $F$ 是函数， $\operatorname{dom}F\subseteq A∧\operatorname{ran}F\subseteq B$ 则称之为 $A$ 到 $B$ 的偏函数。记作 $F:A→ B$

其中 $A$ 称为 $F$ 的前域。

$A$ 到 $B$ 的全体偏函数记为 $A→ B=\{ F\mid F:A→ B\}$

显然 $A→ B\subseteq P(A\times B)$
真偏函数

${dom\,}F\subset A$ ，记作 $F:A\shortparallel\!\!\!→ B$ 。 $A$ 到 $B$ 的全体真偏函数记为 $A\shortparallel\!\!\!→ B=\{ F\mid F:A\shortparallel\!\!\!→ B\}$

所以，就有 $A\shortmid\!\!\!→ B=A→ B\cup A\shortparallel\!\!\!→ B\qquad F:A\shortmid\!\!\!→ B⇒ F:\operatorname{dom}F→ B$
全函数

$\operatorname{dom}F=A$ ，记作 $F:A\shortmid\!\!\!→ B$ 。 $A$ 到 $B$ 的全体全函数记为 $B^A=A→ B=\{ F\mid F:A\shortmid\!\!\!→ B\}$

$A,B$ 中存在空集 $Ø$ 时， $B^A$ 分为以下几种情况
- $A,B$ 是空集： $B^A=Ø^{Ø}=\{Ø\}$
- 仅 $A$ 是空集： $B^A=B^{Ø}=\{Ø\}$
- 仅 $B$ 是空集： $B^A=Ø^{A}=Ø$
其余时候， $\mid B^A\mid =\mid B\mid ^{\mid A\mid }$
全函数的性质
- 单射： $F$ 是单根的。即 $f(x)=f(y)→ x=y$
- 满射： $\operatorname{ran}F=B$
- 双射： $F$ 即是单射也是满射。
若有 $F:A→ B,\,\mid A\mid =n,\,\mid B\mid =m$ ，则
- $n<m$ 时， $A→ B$ 中无满射、双射。单射数量是 $m(m-1)…(m-n+1)$
- $n>m$ 时， $A→ B$ 中无单射、双射。满射数量是 $m!\begin{Bmatrix}n\\m\end{Bmatrix}$
- $n=m$ 时， $A→ B$ 中双射个数为 $n!$
象、原象

给定映射 $f:A→ B,\,A'\subseteq A,\,B'\subseteq B$

则 $A'$ 的像 $f(A')=\{ y\mid x\in A',xfy\}$

$B'$ 的原像 $f^{-1}(B')=\{ x\mid y\in B',xfy\}$

有 $f(A)=\operatorname{ran}f\quad f^{-1}(B)=\operatorname{dom}f=A$
特殊函数
- 常数函数： $f:A→ B,\,∃ b\in B,\,∀ x\in A,\,f(x)=b$
- 恒等函数： $I_A:A→ A,\,I_A(x)=x$
- 特征函数： $\chi_A:E→\{0,1\},\,\chi_A(x)=1⇔ x\in A$
  
  此时当 $Ø\subset A\subset E$ 时， $\chi_A$ 是满射
单调函数

设 $f:A→ B$ 且 $⟨ A,\le_A⟩,⟨ B,\le_B⟩$ 是偏序集

单调增： $∀ x,y\in A,\,x\le_Ay⇒ f(x)\le_Bf(y)$

单调减： $∀ x,y\in A,\,x\le_Ay⇒ f(y)\le_Bf(x)$

严格单调：将上面的 $\le$ 换为 $<$ 。此时是单射
自然映射

设 $R$ 是 $A$ 上的等价关系

自然映射（典型映射）： $f:A→ A/R,\,f(x)=[x]_R$

当 $R=I_A$ 时， $f$ 是单射

又有 $f:A→ B,\,g:B→ C$ 则 $f\circ g:A→ C,\,F\circ g(x)=f(g(x))$

若 $f:A→ B$ 是双射，则 $f^{-1}=B→ A$ 也是双射。此时称 $f^{-1}$ 为 $f$ 的 反函数
单边逆

若 $f:A→ B,\,g:B→ A$

左逆： $g\,是\,f\,的左逆⇔ g\circ f=I_A$

右逆： $g\,是\,f\,的右逆⇔ f\circ g=I_B$

$\quad f\,存在左逆⇔ f\,是单射$

$\quad f\,存在右逆⇔ f\,是满射$

$\quad f\,存在左逆、右逆⇔ f\,是双射⇔ f\,的左逆、右逆相等$

DM2.11 自然数

封闭

有函数 $F$ ， $A\subseteq\operatorname{dom}F$

则有： $A\,在函数\,F\,下封闭⇔ F(A)\subseteq A⇔ F:A→ A⇔ F\,是\,A\,上一元运算$
皮亚诺公理

皮亚诺公理定义了自然数的集合。

对于三元组 $⟨ M,F,e⟩,\,F:M→ M$
- $e\in M$
- $M$ 在 $F$ 下封闭
- $e\notin \operatorname{ran}F$
- $F$ 是单射
- $A\subseteq M∧ e\in A∧ A\,在\,F\,下封闭⇒ A=M$
  
  （极小性公理/数学归纳法原理。即 $M$ 是满足条件的最小集合）
后继

对于集合 $A$ ，其后继 $A^+=A\cup\{ A\}$

$\quad A\subseteq A^+∧ A\in A^+$
归纳集

$\quad A\,是归纳集$

$⇔Ø\in A∧∀ x(x\in A→ x^+\in A)$

$\Harr A\,含有\,Ø\,且对后继封闭$
后继函数

$\quad\sigma:N→ N,\,∀ n\in N,\,\sigma(n)=n^+$
传递集

对于集合 $A$ ， $∀ x\in a\in A⇒ x\in A$ ，则称 $A$ 为传递集

$\quad A\,是传递集$
$⇔{\bigcup\\}A\subseteq A$
$⇔∀ a(a\in A→ a\subseteq A)$
$⇔A\subseteq P(A)$
$⇔P(A)\,是传递集$

另外， $A\,是传递集⇒{\bigcup\\}(A^+)=A$

#集合论中的数学归纳法

目标：证明 $∀ n\in N$ ， $P(n)$ 为真

构造 $S=\{ n\mid n\in N∧ P(n)\}$
证明 $S$ 是归纳集

$\quadØ\in S$
$\quad∀ n(n\in s→ n^+\in S)$
$∴S=N$

#使用集合来构造 Peano 系统

自然数：属于每个归纳集的集合。

自然数集（ $N$ ）：包含于每个归纳集的集合。

$\quad 0=Ø$
$\quad 1=Ø^+=\{Ø\}=\{ 0\}$
$\quad 2=Ø^{++}=\{Ø,\{Ø\} \}=\{0,1\}$
$\quad \dots$
$\quad n=(n-1)^+=\{0,1,2,…,n-1\}$

如此一来，让自然数作为集合，可以进行运算

$\quad 2\cap3=\{0,1\}\cap\{0,1,2\}=\{0,1\}=2=\operatorname{min}(2,3)$
$\quad 2\cup3=\{0,1\}\cup\{0,1,2\}=\{0,1,2\}=3=\operatorname{max}(2,3)$
$\quad 3-2=\{0,1,2\}-\{0,1\}=\{2\}$
$\quad 2-3=\{0,1\}-\{0,1,2\}=Ø$
$\quad \bigcup n=\bigcup\{0,1,\dots,n-1\}=n-1=\operatorname{max}(0,1,\dots,n-1)$
$\quad \bigcap n=\bigcap\{0,1,\dots,n-1\}=0=\operatorname{min}(0,1,\dots,n-1)$
$\quad 0\in1\in2\in3\in\dots\qquad0\subseteq1\subseteq2\subseteq3\subseteq\dots$

于是有以下定理：

自然数集是归纳集，且是最小的归纳集

自然数是传递集，自然数集也是传递集
$⟨ N,\sigma,0⟩$ 是 Peano 系统
$∀ m,n\in N,m^+\in n^+⇔ m\in n$
任何自然数都不是自己的元素。
$Ø$ 属于 $0$ 以外的任意自然数
任何自然数的元素都是其子集

$\quad n\in N⇒∀ x(x\in n→ x\subseteq n)$
三歧性

对于 $∀ m,n\in N$ ，以下三式恰有一式成立

$\quad m\in n,\quad m=n,\quad n\in m$
$N$ 上的递归定理

设 $A$ 为集合， $a\in A,\,F:A→ A$

则存在唯一的函数 $h:N→ A$ ，使得 $h(0)=a$ ，且 $∀ n\in N,\,h(n^+)=F((h(n)))$

如此一来，就可以递归地定义函数。如

$\quad a\in A,\,F:A→ A$
$\quad \begin{cases}h(0)=a\\h(n+1)=F(h(n)),\,∀ n\in N\end{cases}$

定义自然数集上的二元运算：

加法

$\quad +:N\times N→ N$

$\quad+(⟨ 2,3⟩)=5,\quad2+3=5$

将 $m$ 看成固定值，就能定义一元函数 $+m$ 。再将 $m$ 扩展到每个自然数，就有了所有的 $+m$

$\quad m\in N,\,A_m:N→ N$
$\quad \begin{cases}A_m(0)=m\\A_m(n^+)=(A_m(n))^+\end{cases}$

加法有以下性质
- $m+0=m$
- $m+n^+=(m+n)^+\qquad m^++n=(m+n)^+$
- $m+n=n+m$
乘法

$\quad•:N\times N→ N$

$\quad•(⟨ 2,3⟩)=6,\quad2•3=6$

可以定义 $• m$ 函数

$\quad m\in N,\,M_m:N→ N$
$\quad \begin{cases}M_m(0)=0\\M_m(n^+)=M_m(n)+m\end{cases}$

乘法有如下性质
- $1• n=n• 1=n$
- $n• m=m• n$
- $(m• n)• k=m• (n• k)$
- $k\not=0∧ m• k=n• k⇒ m=n$
- $m• (n+k)=(m• n)+(m• k)$

自然数有两个基本性质

匹配

在自然数集合与另一集合间建立双射，可以统计集合的大小

$\quad\{ a\}→\{ 0\}=1$
$\quad\{ a,b\}→\{ 0,1\}=2$
$\quad\{ a,b,c\}→\{ 0,1,2\}=3$
$\quad …$
计数

任意自然数集合都有最小元素，任意自然数间可以比较大小

$\quad 0→1→2→3→…$
$\quad a→ b$
$\quad a→ b→ c$
$\quad …$

DM2.12 等势、有穷集、无穷集

等势

$\quad A\,与\,B\,等势⇔∃ 双射\,f:A→ B$

记作 $A\approx B$

则有：

$\quad Z\approx N\qquad N\times N\approx N\qquad N\approx Q\qquad (0,1)\approx R\qquad[0,1]\approx(0,1)$
$\quad P(A)\approx 2^A=A→ 2$
$\quad A\approx A\qquad A\approx B⇒ B\approx A\qquad A\approx B∧ B\approx C⇒ A\approx C$
$\quad N\not\approx R\qquad A\not\approx P(A)$
有穷集

与某一自然数 $n$ 等势的集合称为有穷集。

$\quad A\,是有穷集⇔ ∃ n(A\approx n∧ n\in N)⇔ B\subset A→ A\not\approx B$

不存在与自身真子集等势的自然数，也不存在与自身真子集等势的有穷集
无穷集

不能与任何自然数 $n$ 等势的集合

$\quad A\,是无穷集⇔ n\in N→ A\not\approx n⇔ B\subset A→ B\approx A$

与自身真子集等势的集合是无穷集，自然数集也是无穷集

DM2.13 基数

基数

对每个集合 $A$ ，定义 $\operatorname{card}A$
- $\operatorname{card}A=\operatorname{card}B⇔ A\approx B$
- 对于有穷集： $\operatorname{card}A=n⇔ A\approx n$
- 对于无穷集： $\operatorname{card}N=\aleph_0$
- 对于实数集： $\operatorname{card}R=\aleph_1=\aleph$
$0,1,2,\dots,\aleph_0,\aleph$ 都称作基数

其中 $0,1,2,…$ 称为有穷基数； $\aleph_0,\aleph$ 称为无穷基数

若 ${card\,}A=\aleph_i$ 则 $\operatorname{card}P(A)=\aleph_{i+1}$

可以用希腊字符 $\kappa,\lambda,\mu$ 等表示任意基数。 $\operatorname{card}A$ 是对 $\mid A\mid$ 的推广

有穷基数小于任何无穷基数， $0$ 是有穷基数的最小值。 $\operatorname{rand}A<\operatorname{rand}P(A)$
$K_\kappa$

设 $\kappa$ 是任意基数，令 $K_\kappa=\{ x\mid x\,是集合且\,\operatorname{card}x=\kappa\}$
- $\kappa=0$ 时， $K_\kappa=\{Ø\}$ 是集合
- $\kappa\not=0$ 时， $K_\kappa$ 不是集合，而是类
优势、劣势

如果存在 $A$ 到 $B$ 的单射，则必然有 $\operatorname{rand}A\le \operatorname{rand}B$

则称 $A$ 较 $B$ 劣势（ $B$ 较 $A$ 优势），记为 $A\preccurlyeq• B$ 或 $B\succcurlyeq• A$

若有 $\operatorname{rand}A<\operatorname{rand}B$ 则称为绝对劣势（绝对优势），记为 $A\prec• B$ 或 $B\succ• A$

显然 $A\subseteq B⇒ A\preccurlyeq• B\quad A\subset B⇒ A\succcurlyeq• B$

$\quad A\preccurlyeq\bull B∧ B\preccurlyeq\bull A⇒ A\approx B$

$\quad \kappa\le\lambda∧\lambda\le\kappa⇒\kappa=\lambda$

$\quad A\subseteq B\subseteq C∧ A\approx C⇒ A\approx B\approx C$

$\quad R\approx(N→2)=2^N$
可数集（可列集）

基数不超过 $\aleph_0$ 的集合称为可数集。 $n\in N$ 称为有穷可数集， $N$ 称为无穷可数集

倘若 $A$ 是有穷可数集，则其可以表示成 $A=\{ a_1,a_2,\dots,a_n\}$
基数运算

基数间也能进行运算

有集合 $K,L$ 且 $K\cap L=Ø$ ，基数 $\kappa = \operatorname{rand}K,\lambda=\operatorname{rand}L$

则 $\kappa+\lambda=\operatorname{rand}(K\cup L)\qquad\kappa\bull\lambda=\operatorname{rand}(K\times L)\qquad\kappa^\lambda=\operatorname{rand}\{ A\mid A:K→ L\}$

有 $rand\,P(K)=2^\kappa\qquad\aleph=2^{\aleph_0}$

基数运算的性质
- $\kappa+\lambda=\lambda+\kappa\qquad(\kappa+\lambda)+\mu=\kappa+(\lambda+\mu)\qquad\kappa\le\lambda⇒\kappa-\mu\le\lambda-\mu$
  
  $\kappa\bull(\lambda+\mu)=\kappa\bull\lambda+\kappa\bull\mu\qquad\kappa^\lambda\bull\kappa^\mu=\kappa^{\lambda+\mu}$
  
  $(\kappa\not=0∨\mu\not=0)∧\kappa\le\lambda⇒\mu^\kappa\le\mu^\lambda$
- 若 $\kappa$ 是无穷基数则有 $\kappa\bull\kappa=\kappa$
  
  即，对于任意无穷集都能和自身的二元关系建立双射
- 若 $\kappa$ 是无穷基数， $\lambda$ 是基数，则有 $\kappa+\lambda=\kappa•\lambda=max\{ \kappa,\lambda\}$
- 若 $\kappa$ 是无穷基数，则 $\kappa^\kappa=2^\kappa$

DM2.14 公理化集合论

罗素悖论：罗素悖论是由罗素发现的一个集合论悖论。若有 $A=\{ x\mid x\not\in x\}$ ，则无法判断 $A\in A$ 的真假。

罗素悖论的提出引发了第三次数学危机。为了尝试解决该危机，提出了公理化集合论。ZF 公理系统是其中的一种。

#ZF 公理系统

空集公理： $Ø\,是集合$
外延公理：所含元素相同的两个集合相等

$\quad A=B⇔∀ x(x\in A↔ x\in B)$
无序对公理： $a,b\,是集合⇒\{ a,b\}\,是集合$
子集公理： $A\,是集合⇒\{ x\in A\mid P(x)\}\,是集合$
并集公理： ${\mathcal A}\,是集族⇒{\bigcup\\}{\mathcal A}\,是集合$
幂集公理： $A\,是集合⇒ P(A)\,是集合$
替换公理： $F\,是\,A\,上的函数⇒ \{ f(x)\mid x\in A\}\,是集合$
正则公理： $A\not=Ø⇒∃ B(B\in A∧ B\cap A=Ø)$
无限公理：存在归纳集。

$\quad A\,是归纳集⇔(Ø\in A)∧(a\in A→ a\cup\{ a\}\in A)$

以上公理组成了 ZF 公理系统。加上下面的选择公理（策梅洛公理）即构成 ZFC 公理系统

选择公理： $\mathcal A$ 是元素互不相交的非空集族。从该集族每个元素中选择一个元素，那些选择的元素构成一个集合

$\quad∀ a,b\in{\mathcal A}(a\cap b\not=Ø→ a=b)⇒∃ C(∀ x\in{\mathcal A}→ \mid x\cap C\mid =1)$

以下公理都是该公理的等价形式：
- 广义选择公理：对于任何非空集族都有选择函数 $f:\mathcal{A→\bigcup A},\,f(x)\in x\in\mathcal A$
- 良序原理：任何集合都可以良序化
- Zorn 原理：链总有上界的非空偏序集存在极大元
- Hausdorff 极大原理：任何链都包含于极大链
- 三歧性原理： $A,B\,是集合⇒\mid A\mid \le\mid B\mid ∨\mid B\mid \le\mid A\mid$

数学

#基础课目 #数学 #离散数学

<离散数学> DM2 集合论

https://i-melody.github.io/2022/10/15/离散数学/2 集合论/

作者

Melody

发布于

2022年10月15日

许可协议