LA1-2: 集合与关系补遗

no comments

Preview 04

问题一：什么是集合？集合无定义，通过外延法、概括法描述。

问题二：集合的基本概念有哪些？子集、空集、幂集、自然数（归纳集）、笛卡尔积。

问题三：如何进行集合运算与集合公式证明？集合交并补差、广义并交。集合定义、恒等式、逻辑推演等。

集合

集合论是现代数学的基础理论。

罗素悖论：$\{x|P(x)\}$（概括原则）未必产生集合：考虑 $R=\{x|x\notin x\}$，那么 $R\in R\iff R\notin R$ 矛盾，故 $R$ 不为集合。

公理化集合论：在朴素集合论基础上，通过公理对集合加以限制。

朴素集合论说：「相异而确定之物，其总括之全体谓之集合」。

ZF.1. 外延公理：集合有其元素完全决定：$A=B\leftrightarrow \forall x(x\in A\leftrightarrow x\in B)$.

概括原则：对于人们直观或者思维之对象 $x$ 的任一性质 $P(x)$，存在集合 $S$ 的元素恰为具有性质 $P$ 的哪些对象，记为 $S=\{x|P(x)\}$.

集合的大小：

• 有限集合及其基数：若 $S$ 恰有 $n$ 个不同的元素，$n$ 是自然数，就说 $S$ 是有限集合，而 $n$ 是 $S$ 的基数，记作 $|S|=n$.
• 无限集合：如果一个集合不是有限的，就说它是无限的。

子集：$A$ 为 $B$ 之子集，记作 $A\subseteq B$，指 $\forall x(x\in A\to x\in B)$；$A$ 为 $B$ 之真子集，记作 $A\subset B$，指 $A\subseteq B\wedge A\ne B$，$A\not\subset B$ 是指 $\exists x(x\in A\wedge x\notin B)$.

命题：$A=B\leftrightarrow (A\subseteq B\wedge B\subseteq A)$，常用于证明集合相等。

ZF.3*. 空集公理：存在一个集合其没有任何元素，称之为「空集」（null set），记作 $\varnothing$，其为任何集合（包括空集本省）之子集。

命题：空集唯一。

由集合定义自然数：定义设 $a$ 为集合，称呼 $a\cup \{a\}$ 为 $a$ 的后继，记作 $a^{+}$. 自然数的 von Neumann 定义：令 $0=\varnothing ,1=0^{+},2=1^{+},\cdots ,n+1=n^{+}$.

定义：设 $A$ 是集合，称 $A$ 为「归纳集」（inductive set），指 $\varnothing \in A\wedge (\forall x\in A)(x^{+}\in A)$.

ZF.7. 无穷公理：存在指标集。$\exists A(\varnothing \in A\wedge (\forall x\in A)(x^{+}\in A))$.

von Neumann 定义依无穷公理定义：$\mathbb{N}\stackrel{\mathrm{def}}{=}\cap \{A|A\text{ is inductive set}\}$.

对于自然数的 von Neumann 定义，可定义 $m\le n\stackrel{\mathrm{def}}{=}m\subseteq n$，于是有以下命题成立：

• $n+1=\{0,1,\cdots ,n\}$.
• $n\in n+1$.
• $n\le n$.
• $n\le m\le 1\to n\le 1;n\le m\le n\to n=m$.
• $m\le n\vee n\le m$.

集合的运算

ZF.8. 幂集公理：集合 $A$ 的幂集为 $A$ 之全体子集构成的集合。$P(A)=\{x|x\subseteq A\}$.

有序 $n$ 元组 $(a_1,\cdots ,a_n)$，两个有序 $n$ 元组相等当且仅当每一对对应的元素都相等。

笛卡尔积：$A\times B=\{(a,b)|a\in A\wedge b\in B\}$。笛卡尔积的子集 $R$ 称为集合 $A$ 到集合 $B$ 的关系。

笛卡尔积可推广到多个集合：$A_1\times \cdots \times A_n=\{(a_1,\cdots ,a_n)|a_i\in A_i,i=1,2,\cdots ,n\}$，因此需要注意 $A\times B\times C$ 和 $(A\times B)\times C$ 不同。

特别地，有序偶可以通过集合这样定义：$(a,b)=\{\{a\},\{a,b\}\}$.

笛卡尔积的几条性质如下：

• $A\times \varnothing =\varnothing \times A=\varnothing$.
• $A\times B=B\times A\iff ((A=\varnothing )\vee (B=\varnothing )\vee (A=B))$.
• 分配律：
  • $A\times (B\cup C)=(A\times B)\cup (A\times C)$.
  • $A\times (B\cap C)=(A\times B)\cap (A\times C)$.
  • $(B\cup C)\times A=(B\times A)\cup (C\times A)$.
  • $(B\cap C)\times A=(B\times A)\cap (C\times A)$.

ZF.5. 并集公理：$A\cup B=\{x|x\in A\vee x\in B\}$.

集合的交：$A\cap B=\{x|x\in A\wedge x\in B\}$.

集合的相对补：$A-B=\{x|x\in A\wedge x\notin B\}$.

集合的对称差：$A\oplus B=(A-B)\cup (B-A)=\{x|(x\in A\wedge x\notin B)\vee (x\in B\wedge x\notin A)\}$.

广义并：集合所有元素的并：$\cup A=\{x|\exists y(y\in A)\wedge x\in y\}$.

广义交：非空集合所有元素的交：$\cap A=\{x|\forall y(y\in A\to x\in y)\}$，而 $\cap \varnothing$ 无意义，不是一个集合。

最小上界和最大下界。集合与谓词逻辑。

集合恒等式：

• 恒等律：$A\cup \varnothing =A,A\cap \mathbb{U}=A$.
• 支配律：$A\cup \mathbb{U}=\mathbb{U},A\cap \varnothing =\varnothing$.
• 幂等律：$A\cup A=A,A\cap A=A$.
• 补集律：$\sim (\sim A)=A$.
• 交换律：$A\cup B=B\cup A,A\cap B=B\cap A$.
• 结合律：$A\cup (B\cup C)=(A\cup B)\cup C,A\cap (B\cap C)=(A\cap B)\cap C$.
• 分配律：$A\cap (B\cup C)=(A\cap B)\cup (A\cap C),A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$.
• 德摩根（DeMorgan）律：$\sim (A\cup B)=\sim A\cap \sim B,\sim (A\cap B)=\sim A\cup \sim B$.
• 补律：$A\cup \sim A=\mathbb{U},A\cap \sim A=\varnothing$.

幂集性质：

• $P(A\cap B)=P(A)\cap P(B)$
• $P(A\cup B)\supseteq P(A)\cup P(B)$.

集合公式的基本证明方式

法一：直接使用集合包含或相等的定义。

法二：利用运算定义作逻辑等值式推演。

法三：利用已知恒等式或等式作集合代数推演。

法四：通过环证明路径证明一系列逻辑等值式。

其他证明方法：使用文氏图辅助推测结论。

ZFC 公理化集合论

1. 外延公理：两个集合含有相同元素则集合相等。$\forall x\forall y(\forall z(z\in x\leftrightarrow z\in y)\to x=y)$.
2. 正则公理：每一个非空集合 $x$ 总包含一元素 $y$ 使 $x$ 和 $y$ 不相交。$\forall x(\exists a(a\in x)\to \exists y(y\in x\wedge \neg \exists z(z\in y\wedge z\in x)))$.
3. 分类公理/子集公理：给出任意集合及命题 $P(x)$，存在着一个原来集合的子集包含且仅包含使 $P(x)$ 成立的元素。$\forall z\forall w_1\cdots w_n\exists x(x\in y\leftrightarrow (z\in z\wedge \varphi ))$.
4. 配对公理：$x,y$ 为集合则存在仅包含二者的集合 $\{x,y\}$. $\forall x\forall y\exists z(x\in z\wedge y\in z)$.
5. 并集公理：每一个集合其广义并存在。$\forall \mathcal{F}\exists A\forall Y\forall x((x\in Y\wedge Y\in \mathcal{F})\to x\in A)$.
6. 替代公理：若一个可定义的函数 $f$ 的定义域为一集合且对定义域的任一 $x$，$f(x)$ 也为集合，则 $f$ 的值域为一个集合的子集。$\forall A\forall w_1\cdots w_n(\forall x(x\in A\to \exists !y\varphi )\to \exists B\forall x(x\in A\to \exists y(y\in B\wedge \varphi )))$.
7. 无穷公理：存在集合 $x$，空集是其元素之一，且对于任何 $x$ 中的元素 $y$，$y\cup \{y\}$ 也是 $x$ 的元素。$\exists X(\varnothing \in A\wedge \forall y(y\in X\to S(y)\in X))$
8. 幂集公理：每一个集合其幂集存在。$\forall x\exists y\forall z(z\subseteq x\to z\in y)$.
9. 选择公理：给出一个集合 $x$，其元素皆为互不相交的非空集，那总存在着一个集合 $y$，作为 $x$ 的一个选择集合，包含 $x$ 每一个元素的仅一个元素。

皮亚诺公理

• 零是自然数。$e\in S$.
• 每个自然数都有一个后继（也是一个自然数）。$\forall a\in S(f(a)\in S)$.
• 零不是任何自然数的后继。$\forall a\in S(f(a)\ne e)$.
• 不同的自然数有不同的后继。$\forall b\in S\forall c\in S((f(b)=f(c))\to (b=c))$.
• （归纳公理）：由自然数组成的某个集合含有零，且元素在集合中必有其后继在集合中，那么该集合含有全部自然数。$\forall A\subseteq S(((e\in A)\wedge (\forall a\in A(f(a\in A)))\to (A=S)))$.
• 戴德金-皮亚诺结构就描述了所有满足以上条件的三元组 $(S,f,e)$，$S$ 都可被视作为一个自然数集。

Preview 05

问题一：什么是关系？如何表示关系？如何进行关系运算？笛卡尔积的子集。集合矩阵有向图。交并补差，逆，复合，矩阵法。

问题二：什么是函数？什么是单射、满射函数？如何进行函数运算？函数是特殊的关系。像皆不同即单射，值域为伴域即满射。函数运算包括反函数、复合函数。

笛卡尔积。

从 $A$ 到 $B$ 的一个关系 $R$ 是 $A\times B$ 的一个子集，即 $R\subseteq A\times B$. 若 $A=B$ 则称为集合 $A$ 上的（二元）关系。

二元关系，相关记号：令 $R\subseteq A\times B$.

• $(a,b)\in R$ 可简记为 $aRb$.
• $(a,b)\notin R$ 可简记为 $\neg aRb$ 或 $a/Rb$.
• $aRb\wedge bRc$ 可简单记为 $aRbRc$.

特殊的二元关系：

• 空关系：$\varnothing$.
• 全域关系：$E_A:E_A=\{(x,y)|x,y\in A\}$.
• 恒等关系：$I_A:I_A=\{(x,x)|x\in A\}$.
• 函数 $f:A\to B$，从而 $R=\{x,f(x)|x\in A\}$ 是一个从 $A$ 到 $B$ 的关系。

函数的表示：

• 集合表示。
• 0-1 矩阵表示。
• 有向图表示。

关系的运算：

• 集合的运算：交并补差。
• $\mathrm{dom}R=\{x|\exists y(x,y)\in R\}$.
• $\mathrm{ran}R=\{y|\exists x(x,y)\in R\}$.
• $\mathrm{fld}R=\mathrm{dom}R\cup \mathrm{ran}R$.
• $R\uparrow A=\{(x,y)|x\in A\wedge xRy\}\subseteq R$，即 restriction，也记作 $R|A$ 或 $R\upharpoonright A$.
• $R[A]=\{y|\exists x(x\in A\cap (x,y)\in R)\}=\mathrm{ran}(R\uparrow A)\subseteq \mathrm{ran}R$.
• 逆运算 $R^{-1}=\{(x,y)|(y,x)\in R\}$. 显然有 $(R^{-1}{)}^{-1}=R$.
• 关系的复合（合成，composition）：$R_1$ 和 $R_2$ 的复合记作：$R_2\circ R_1=\{(a,c)\in A\times C|\exists b\in B((a,b)\in R_1\wedge (b,c)\in R_2)\}$，其中 $R_1\subseteq A\times B,R_2\subseteq B\times C$.

关系复合的性质：

• 结合律：$(R_3\circ R_2)\circ R_1=R_3\circ (R_2\circ R_1)$.
• 复合的逆：$(R_2\circ R_1{)}^{-1}=R_1^{-1}\circ R_2^{-1}$.
• 复合对集合并满足分配律：$(G\cup H)\circ F=(G\circ F)\cup (H\circ F)$
• 复合对集合交则是包含：$(G\cap H)\circ F\subseteq (G\circ F)\cap (H\circ F)$.
• 0-1 矩阵运算：$M_{R_1\cup R_2}=M_{R_1}\vee M_{R_2},M_{R_1\cap R_2}=M_{R_1}\wedge M_{R_2},M_{R_2\circ R_1}=M_{R_1}\otimes M_{R_2}$.

函数

设 $A$ 和 $B$ 为非空集合，从集合 $A$ 到集合 $B$ 的函数 $f$ 是对元素的一种指派，对 $A$ 的每个元素恰好指派 $B$ 的一个元素，记作 $f:A\to B$，这称为函数的型构。

函数的定义域（domain）是 $A$，伴域（codomain）是 $B$.

如果 $f$ 为 $A$ 中元素 $a$ 指派 $B$ 中元素 $b$，那么记作 $f(a)=b$，且称 $b$ 为 $a$ 的像（image），$a$ 为 $b$ 的一个原像。

$A$ 中元素的像构成的集合称为 $f$ 的值域（range），函数也称为映射（mapping）或变换（transformation）。

函数是一种特殊的关系：对 $A$ 中的每个元素 $a$，$B$ 中有且仅有一个元素 $b$ 使得 $aFb$，也即 $\forall x,y,z(xFy\wedge xFz\to y=z)$.

函数的相等：

• $\mathrm{dom}f=\mathrm{dom}g$.
• $\mathrm{codom}f=\mathrm{codom}g$.
• $\forall x(x\in \mathrm{dom}f\to f(x)=g(x))$.

子集在函数下的像：$f:A\to B$ 而 $S\subseteq A$，那么 $f(S)=\{t|\exists s\in S(t=f(s))\}$ 称为 $S$ 在 $f$ 下的像，$f(A)$ 即 $A$ 的值域。

并集的像即像的并，交集的像包含于像的交。

单射/一对一的 injection, injective function, one-to-one function，满射/映上的 surjection, surjective function, onto function，双射/一一对应 bijection, bijective function, one-to-one correspondence.

反函数：对于一一对应的函数成立。

函数的复合：$(f\circ g)(x)=f(g(x)),x\in A$.

复合运算的性质：

• 结合律。
• 满射复合为满射，复合为满射则前满后不一定满。
• 单射复合为单射，复合为单射则后单前不一定单。
• 双射复合为双射。
• 和逆复合为单位。

递增（递减函数）：

• $\forall x\forall y(x<y\to f(x)\le f(y))$ 递增。
• $\forall x\forall y(x<y\to f(x)<f(y))$ 严格递增。

Preview 06

问题一：什么是集合的基数？类似于「集合的大小」。

问题二：（基数）最大的集合有多大？没有最大，任意集合的幂集比自身大。

问题三：如何比较两个（无限）集合的大小？双射函数，Bernstein 定理。

集合的基数

有限集合的基数就是元素个数。无限集合的基数则需要详细说明，当然我们接受无穷公理。

定义自然数个数为 ${\aleph }_0$（阿列夫零，Aleph-null），是最小的一个无限数。

比较集合的大小：等势关系：如果存在 $A$ 到 $B$ 的双射，则称二者等势，记作 $A\approx B$，否则不等势，记作 $A\not\approx B$.

集合的势就是集合的基数，记为 $|A|$ 或 $\mathrm{card}A$.

集合 $S$ 为有限集合当且仅当存在自然数 $n$ 使得 $S$ 的基数为 $n$，也即存在双射函数 $f:n\to S$.

集合 $S$ 为无穷集合当且仅当存在 $S$ 的真子集 $S^{\prime }$ 使得 $S\approx S^{\prime }$.

$\mathrm{card}\mathbb{N}={\aleph }_0,\mathrm{card}\mathbb{R}=\aleph$.

如果存在集合到自然数集合的单射，则称为可数集或可列集。

自然数集的笛卡尔积是可列积：对角线方法。

实数集不是可列集：对角线方法。

幂集的基数始终大于集合的基数。

Cantor 定理（1891）：

• $\mathbb{N}\not\approx \mathbb{R}$.
• $A\not\approx P(A)$.

集合的优势关系：

• 如果存在从集合 $A$ 到集合 $B$ 的单射，则称 $B$ 优势于 $A$，记作 $A⪯\bullet B$.
• 如果 $B$ 优势于 $A$ 且与 $A$ 不等势，那么称 $B$ 真优势于 $A$，记作 $A\prec \bullet B$.

Bernstein 定理：若 $A⪯\bullet B$ 且 $B⪯\bullet A$ 则 $A\approx B$.

$B^A$：定义域为 $A$ 且伴域为 $B$ 的函数构成的集合。

重要的等式，优势关系如下：

• $\mathbb{N}\approx \mathbb{Z}\approx \mathbb{Q}\approx \mathbb{N}\times \cdots \times \mathbb{N}$.
• $\mathbb{R}\approx (0,1)\approx P(\mathbb{N})\approx \{0,1{\}}^{\mathbb{N}}$.
• $\{0,1{\}}^A\approx P(A)$.
• $\mathbb{N}\prec \bullet \mathbb{R}$.
• $A\prec \bullet P(A)\prec \bullet P(P(A))\prec \bullet \cdots$.

连续统假设（CH, continuum hypothesis）：不存在集合 $S$ 使得 ${\aleph }_0<\mathrm{card}S<\aleph$.

等势关系是一种等价关系，优势关系满足自反性反对称性传递性。