## 公理体系 ### 外延公理 - 具有相同元素的集合是相等的 $$ (\forall x)(x \in A \leftrightarrow x \in B) \Rightarrow A=B $$ ### 子集公理模式 - 对于任给一个集合$A$和集合的每一项性质$\phi$，存在一个集合$B$，它的成员恰是$A$中那些具有性质$\phi$的成员 $$ (\exists B)(\forall x)(x \in B \leftrightarrow x \in A \land \phi(x)) $$ - 其中，$B$不可在$\phi$中出现 ### 偶集公理 - 对于给定的任何两个集合$A, B$，存在一个集合$C$，其成员恰是$A$和$B$ $$ (\exists C)(\forall x)(x \in C \leftrightarrow x=A \lor x=B) $$ - 由外延公理知，$C$是唯一的 ### 联集公理 - 对于任何一个集合$A$，存在一个集合$C$，$C$的成员恰是$A$的成员的成员 $$ (\exists C)(\forall x)(x \in C \leftrightarrow (\exists B)(B \in A \land x \in B)) $$ - 由外延公理知，$C$是唯一的 $$ C=\cup A := \{x \vert (\exists B)(B \in A \land x \in B)\} $$ $$ A \cup B := \cup \{A, B\} = \{x \mid x \in A \lor x \in B\} $$ - 类似定义交 $$ \cap A := \{x \mid (\forall B)(B \in A \rightarrow x \in B)\} $$ $$ A \cap B := \{x \mid x \in A \land x \in B\} $$ - **重要定理：** 1. $x \in \cup A \Leftrightarrow (\exists B)(B \in A \land x \in B)$ 2. $x \in A \cup B \Leftrightarrow x \in A \lor x \in B$ 3. $\cup(A \cup B) = (\cup A) \cup (\cup B)$ 4. $A \in B \Rightarrow A \subseteq \cup B$ 5. $A \cup B = B \cup A$ 6. $A \cup (B \cup C) = (A \cup B) \cup C$ 7. $A \subseteq C \land B \subseteq C \Leftrightarrow A \cup B \subseteq C$ 8. $x \in \cap A \Leftrightarrow (\forall B)(B \in A \rightarrow x \in B) \land (\exists B)(B \in A)$ 9. $\cap(A \cup B) = (\cap A) \cap (\cap B)$ 10. $(A \cup B) \cap C = (A \cap C) \cup (B \cap C)$ 11. $(A \cap B) \cup C = (A \cup C) \cap (B \cup C)$ 12. $x \in A-B \Leftrightarrow x \in A \land x \not \in B$ 13. $(A \cup B)-B=A-B$ 14. $A-(B \cup C)=(A-B) \cap (A-C)$ 15. $A-(B \cap C)=(A-B) \cup (A-C)$ ### 极小元 - 对于任何集合$S_1$与$S_2$，当$S_1 \in S_2$且$S_1 \cap S_2=\emptyset$时，则称$S_1$为$S_2$的一极小元 ### 正则公理 - 每个不空的集合都有一极小元 $$ A \neq \emptyset \Rightarrow (\exists x \in A \land x \cap A = \emptyset) $$ ### 后继 - 对任意集合$S$，其后继记为$S^+$，定义为$S \cup \{S\}$ - $0:=\emptyset, 1:=0^+, 2:=1^+$，一般地，$n+1:=n^+$ - 若集合$A$有性质$\emptyset \in A \land (\forall x)(x \in A \rightarrow x^+ \in A)$，则称$A$是一个归纳集 ### 无穷公理 - 有一个归纳集的存在 $$ (\exists A)(\emptyset \in A \land (\forall x)(x \in A \rightarrow x^+ \in A)) $$ - 若用$Ind(A)$表示$A$是一个归纳集，则$(\exists A)(Ind(A))$ - $(\exists A)(Ind(A) \land (\forall B)(Ind(B) \rightarrow A \subseteq B))$ - 称最小归纳集 $$ \omega := \{x \mid (\forall B)(Ind(B) \rightarrow x \in B)\} $$ - 是自然数集合，$\omega$的元称为自然数 ### 幂集公理 - 对于任意一个集合$A$，存在一个集合$B$，它的元恰好是$A$的各个子集 $$ (\exists B)(\forall x)(x \in B \leftrightarrow (\forall y)(y \in x \rightarrow y \in A)) $$ - 集合$B$是集合$A$的一个幂集，当且仅当$(\forall x)(x \in B \leftrightarrow x \subseteq A)$，$A$的幂集$B$记作$P(A)$ - 对于一个集合$A$，如果存在自然数$n$，使得$A$恰有$n$个元，则称$A$是有限的 - 若$A$是一个有限集合，且$B \not \in A$，令$C=A \cup \{B\}$，则$C$的所有子集的个数恰是$A$的所以子集的个数的两倍 - 对于自然数$n$，如果集合$A$恰有$n$个元，则$P(A)$恰有$2^n$个元 - **幂集的一般性质：** 1. $B \in P(A) \Leftrightarrow B \subseteq A$ 2. $A \in P(A)$ 3. $A \subseteq B \Leftrightarrow P(A) \subseteq B$ 4. $P(A-B) \subseteq (P(A)-P(B)) \cup \{\emptyset\}$ 5. $P(A) \in P(B) \Rightarrow A \in B$ - 给定集合$A$，对于任何集合$x$和$y$，若$x \in y$且$y \in A$，则$x \in A$，称$A$为传递集 - 对于传递集$A$，有$\cup(A^+)=A$ - 集合$A$是传递集当且仅当$A \subseteq P(A)$ - 集合$A$是传递集当且仅当$P(A)$是传递集 - 每个自然数是个传递集 - $\omega$是个传递集 ## 关系与函数 ### 关系的性质 - $R$在$A$中自反$:=(\forall x)(x \in A \rightarrow xRx)$ - $R$在$A$中非自反$:=(\forall x)(x \in A \rightarrow \lnot (xRx))$ - $R$在$A$中对称$:=(\forall x)(\forall y)(x, y \in A \land xRy \rightarrow yRx)$ - $R$在$A$中非对称$:=(\forall x)(\forall y)(x, y \in A \land xRy \rightarrow \lnot (yRx)$ - $R$在$A$中反对称$:=(\forall x)(\forall y)(x, y \in A \land xRy \land x \neq y \rightarrow \lnot (yRx)$ - $R$在$A$中传递$:= (\forall x)(\forall y)(\forall z)(x, y, z \in A \land xRy \land yRz \rightarrow xRz)$ - $I_A=\{ \mid x \in A\}$ - $xI_Ax \Leftrightarrow x \in A$ - $I_A * I_A = I_A$ - $R$为关系$\Leftrightarrow I_{dm}(R) * R = R$ - $R$自反$\Leftrightarrow I_{fl(R)} \subseteq R$ - $R$非自反$\Leftrightarrow R \cap I_{fl(R)} = \emptyset$ - $R$对称$\Leftrightarrow R^{-1} = R$ - $R$非对称$\Leftrightarrow R \cap R^{-1} = \emptyset$ - $R$反对称$\Leftrightarrow R \cap R^{-1} \subseteq I_{dm(R)}$ - $R$传递$\Leftrightarrow R * R \subseteq R$ - **闭包：**通过添加最少数量的有序对，使原关系具备自反性、对称性或传递性而形成的新集合 - 自反闭包：$r(R)$，对称闭包$s(R)$，传递闭包：$t(R)$ - **构造性定理：** 1. $r(R) = R \cup I_{fl(R)}$ 2. $s(R) = R \cup R^{-1}$ 3. $t(R) = \bigcup^{\infty}_{i=1}R^i$ 4. $t(R) = \bigcup^k_{i=1}R^i$，其中$k \leq \vert fl(R) \vert$ - $R$为自反$\Rightarrow s(R), t(R)$ 是自反的 - $R$为对称$\Rightarrow r(R), t(R)$是对称的 - $R$为传递$\Rightarrow r(R)$是传递的 - $rs(R) = sr(R)$ - $rt(R) = tr(R)$ - $st(r) \subseteq ts(R)$ ### 等价关系与划分 - $R$为等价关系$:= R$为关系且$R$自反、对称和传递 - $R$为$A$上等价关系$:= R$为等价关系且$A=fl(R)$ - 若$R$为$fl(R)$上的关系，则$R$为等价关系$\Leftrightarrow R * R^{-1} = R$ - 设$R$是$A$上的等价关系，由$A$中元$x$产生$R$的等价类，记为$[x]_R$，它是由$A$中那些使$xRy$成立的所有$y \in A$组成的子集 $$ [x]_R := \{y \mid xRy\} $$ - 并且称$x$是等价类$[x]_R$的一个代表，有时也记作$x/R$ - $y \in [x]_R \Leftrightarrow xRy$ - 若$x, y \in fl(R)$且$R$为等价关系，则$[x]_R = [y]_R \Leftrightarrow xRy$ - $R$为等价关系$\Leftrightarrow [x]_R = [y]_R \lor [x]_R \cap [y]_R = \emptyset$ ### 函数 - $f$为函数$:= f$为关系$\land (\forall x)(\forall y)(\forall z)(xfy \land xfz \rightarrow y=z)$ - $f \circ g = g*f$ - $f$为$1-1$函数$:= f$和$f^{-1}$皆为函数 - 若$f$为$1-1$函数且$x_1, x_2 \in dm(f)$，则$f(x_1)=f(x_2) \Leftrightarrow x_1=x_2$ - 若$f$为$1-1$函数，则称$f^{-1}$为反函数 - 若$f$为$1-1$函数，则$f^{-1}(y)=x \Leftrightarrow f(x)=y$ - $f$为$1-1$函数$\land x \in dm(f) \Rightarrow f^{-1}(f(x))=x$ - $f, g$为$1-1$函数$\Rightarrow f \cap g$为$1-1$函数 - $f$为从$A$到$B$的函数$:=f$为函数 $\land$ $dm(f) = A \land rn(f) \subseteq B$ - $f$为从$A$到$B$中的函数$:=f$为函数 $\land$ $dm(f) = A \land rn(f) \subset B$ - $f$为从$A$到$B$上的函数或$f$为满射$:=f$为函数 $\land$ $dm(f) = A \land rn(f) = B$ - $f$为单射或$f$为一对一映射$:=f$为函数 $\land$ $(\forall x)(\forall y)(x, y \in A \land x \neq y \rightarrow f(x) \neq f(y))$ - $f$为双射或$f$为一一对应$:=f$既为单射又为满射或$f$为1-1函数 - 实数$x$的底函数，记为$\lfloor x \rfloor$，指的是小于或等于$x$的最大整数 - 实数$x$的顶函数，记为$\lceil x \rceil$，指的是大于或等于$x$的最小整数 - 散列函数$h: K \rightarrow D$，$h(k) = d$，其中$K$为大键码集合，$D$为地址集合。常用幂列函数是用除法求余、中平方方法和折叠叠方法得到 - 恒等函数，设$A \subseteq B$，若$id_A: A \rightarrow B$，使$id_A(x) = x$，则称$id_A$为$A$上的一个恒等函数。恒等函数自然是个单射函数，而且仅当$A = B$时，恒等函数才是满射，并且$id_A = I_A$ - 特征函数，设$A \subseteq B$，函数$f_A: B \rightarrow \{0, 1\}$定义为 $$ f_A(x) = \begin{cases} 1, & 若 x \in A \cr 0, & 若 x \notin A \end{cases} $$ - 则称$f_A: B \rightarrow \{0, 1\}$是集合$A$的一个特征函数 - $B^A := \{f \mid f$为函数 $\land$ $dm(f) = A \land rn(f) \subseteq B\}$，并称$B^A$是由集合$A$到集合$B$的幂集 - $f \in B^A \Leftrightarrow f$为函数 $\land$ $dm(f) = A \land rn(f) \subseteq B$ - $B^{(A)} = \{\,(x, y) \mid y \in B\,\}$ - $B \subseteq C \Rightarrow B^A \subseteq C^A$ - 设$F, P(B) \rightarrow \{0, 1\}^A$，并令$F(A) := f_A$，其中$A \in P(B)$，则$F$是双射。 - 一个集合$A$与其上的一个二元关系$R$（即$R \subseteq A \times A$）组成的有序对$$称为一个结构 - 若两个给定的结构$$和$$，存在一个双射函数$f:A \rightarrow B$，对于$x, y \in A$有$xRy \Leftrightarrow f(x)SF(y)$，则称$f$是从结构$$到结构$$的同构映射，记作$ \cong $ - 设$, , $是任意三个结构则它们满足自反、对称和传递，即 1. $ \cong $ 2. $ \cong \Rightarrow \cong $ 3. $ \cong , \cong \Rightarrow \cong $

Schabe Antimonfeld

离散数学概念整理（二）：集合论