公理体系

外延公理

• 具有相同元素的集合是相等的

$$ (\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} $$

• 重要定理：

• $x \in \cup A \Leftrightarrow (\exists B)(B \in A \land x \in B)$

• $x \in A \cup B \Leftrightarrow x \in A \lor x \in B$
• $\cup(A \cup B) = (\cup A) \cup (\cup B)$
• $A \in B \Rightarrow A \subseteq \cup B$
• $A \cup B = B \cup A$
• $A \cup (B \cup C) = (A \cup B) \cup C$
• $A \subseteq C \land B \subseteq C \Leftrightarrow A \cup B \subseteq C$
• $x \in \cap A \Leftrightarrow (\forall B)(B \in A \rightarrow x \in B) \land (\exists B)(B \in A)$
• $\cap(A \cup B) = (\cap A) \cap (\cap B)$
• $(A \cup B) \cap C = (A \cap C) \cup (B \cap C)$
• $(A \cap B) \cup C = (A \cup C) \cap (B \cup C)$
• $x \in A-B \Leftrightarrow x \in A \land x \not \in B$
• $(A \cup B)-B=A-B$
• $A-(B \cup C)=(A-B) \cap (A-C)$
• $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$个元

• 幂集的一般性质：

• $B \in P(A) \Leftrightarrow B \subseteq A$

• $A \in P(A)$
• $A \subseteq B \Leftrightarrow P(A) \subseteq B$
• $P(A-B) \subseteq (P(A)-P(B)) \cup {\emptyset}$

• $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)$

• 构造性定理：

• $r(R) = R \cup I_{fl(R)}$

• $s(R) = R \cup R^{-1}$
• $t(R) = \bigcup^{\infty}_{i=1}R^i$

• $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 $

• 设$, , $是任意三个结构则它们满足自反、对称和传递，即

• $ \cong $

• $ \cong \Rightarrow \cong $
• $ \cong , \cong \Rightarrow \cong $