又名抽象代数、近式代数

学科の中で、一番好きのんです。

# 集合论

# 幂集

• 定义：A 的所有子集构成的集合。

  例:

  $$P(P(\varnothing))=P(\{\varnothing\})=\{\varnothing,\{\varnothing\}\}$$

# 集合的运算

• 集合的运算满足分配律
• 对称差定义：

$$A\bigoplus B=(A-B)\cup(B-A)=(A\cup B)-(A\cap B)$$

​ 对称差满足结合律，交换律。

# 有序 n 元组

• 相等定义：

• $$<a_{1},a_{2},...,a_{n}>=<b_1,b_2,...,b_n>\Leftrightarrow a_i=b_i,\forall i=1,2...,n$$

• 传递定义：

  $$<<x,y>,z>=<x,y,z>$$

  # 笛卡尔积

  • 定义：

    $$A\times B=\{<x,y>|x\in A,y\in B\}\\ A_1\times A_2\times ...\times A_n=\{<a_1,a_2,...,a_n>|a_i\in A_i\}$$

  • 笛卡尔积对集合交并满足分配律。

  • $$|A_1\times A_2\times...\times A_n|=|A_1|\times|A_2|\times...\times |A_n|$$

# 多重集

• 重复度定义：

  $$元素在多重集中出现次数记为该元素的重复度M_A(a)，例如：\\ A=\{b,c,c,a,a,a,..\}中M_A(a)=\infty,M_A(b)=1,M_A(c)=2$$

• 多重集的交、并、差、和运算：

  $$M_{A\cup B}(a)=max(M_A(a),M_B(a)),M_{A\cap B}(a)=min(M_A(a),M_B(a))\\ M_{A-B}(a)=M_A(a)-M_B(a),M_{A+B}(a)=M_A(a)+M_B(a)$$

# 关系

# 关系的概念

• 一个有序对的集合 R 称为一个二元关系，简称关系。

• $$当R\subseteq A\times B时，称R为A到B的关系，当R\subseteq A\times A时，称R为A上的关系$$

• $$关系的\textbf{定义域}domR=\{x|\exists y\in B,使<x,y>\in R\}\\ 关系的\textbf{值域}ranR=\{y|\exists x\in A,使<x,y>\in R\}$$

• 关系图：用点表示元素，用带箭头的线表示关系。

• 关系矩阵：关系图的邻接矩阵，只含 0\1 代表无 \ 有关系 $$ M_R $$

  $$*注：x与y是/否有关系也可记为xRy，x\not Ry,R 为关系$$

# 关系的性质

• 自反性：

  $$\forall x\in A,均有xRx$$

  反自反：

  $$\forall x\in A,均有x\not Rx$$

• 对称性：

  $$当xRy时，均有yRx$$

  反对称性：

  $$当xRy,yRx时，必有x =y。也可以说，\not\exists x\neq y使得xRy且yRx$$

• 传递性：

  $$若xRy,yRz,则有xRz$$

# 关系的复合

• 定义：

  $$R是A到B的关系，S是B到C的关系。则R\circ S为：\\ \{<a,c>|\exists b\in B,<a,b>\in R,<b,c>\in S\}$$

• 关系的复合满足结合律，不满足交换律，并且满足：

  $$R^m\circ R^n=R^{m+n},(R^m)^n=R^{mn}$$

# 关系的逆

• 定义：

$$R^{-1}=\{<y,x>|<x,y>\in R\}$$

• $$domR^{-1}=ranR,ranR^{-1}=domR,(R^{-1})^{-1}=R\\ (R\circ S)^{-1}=S^{-1}\circ R^{-1}$$

# 关系的闭包

• 定义：

$$若A上的关系R，R'满足：\\ （1）R'是传递（自反、或对称的）(2)R\subseteq R'\\ (3)\not\exists R''\subseteq R'，使R'' 满足(1)(2)\\$$

​ 则称 R‘为 R 的传递（自反、或对称）闭包，记为 t®,r®,s®

• 自反闭包：

  $$r(R)=R\cup I_A,其中I_A是A上的恒等关系，其关系矩阵为单位矩阵$$

• 对称闭包：

  $$s(R)=R\cup R^{-1}$$

• 传递闭包：

  $$t(R)=\bigcup_{i=1}^{|A|}R^{i}$$

# 等价关系

• 定义：如果 A 上的关系 R 是自反、对称、传递的，则称 R 为一个等价关系。通常用 “~” 表示
• 定理：

$$若R_1,R_2 为A上的等价关系，则R_1\cap R_2,(R_1\cup R_2)^+为A上的等价关系\\ 其中，R^+=\bigcup_{i=1}^{\infty}R^{i}$$

# 等价类

• 定义：

$$[a]_R=\{x|x\in A,xRa\},其中R为A上的\textbf{等价关系},[a]记为由a生成的等价类$$

# 商集

• 定义：

$$A/R=\{[a]|a\in A\},称为A对R的商集，即由A中所有元素生成的等价类组成的集合\\ 特别地，Z/R_m通常称作模m剩余类集，用符号Z_m表示$$

• 性质：

$$(1)a\in[a]\\(2)[a]=[b]\Leftrightarrow aRb\\(3)[a]\cap[b]=\varnothing\Leftrightarrow a\not R b$$

# 划分与覆盖

• 定义：

$$集合族C=\{C_i|C_i是集合，i\in J\}若满足\bigcup_{i\in J}C_i=A，则称C是A的一个覆盖，\\ 若还有C_i\cap C_j=\varnothing(i\neq j),则称C为A的一个划分，C_i称为划分块$$

• 定理：

  • A/R 是 A 的一个划分（商集是原集合的一个划分）

  • 对于任意一个划分 C，可以决定一个等价关系 R，使 A/R=C

  • $$设R_1,R_2 是A上的等价关系，则R_1=R_2\Leftrightarrow A/R_1=A/R_2$$

# 偏序关系与偏序集

• 定义：

  • 若 A 上的一个关系 R 是自反、反对称、传递的，则称其为一个偏序关系。习惯用”≤“表示。

  • 若集合 P 上定义了一个偏序关系，则 <P,≤> 称为一个偏序集。

  • $$<P,\leq>为一偏序集，若a,b\in P ，a<b(a\leq b,a\neq b),且\not\exists c\in P使a<c<b\\ 则称b\textbf{盖住}a，或称b是a的\textbf{直接前辈}，a是b的\textbf{直接后辈}$$

  • Hasse 图：(1) 用原点表示 P 中元素 (2) 若 b 盖住 a，则把 b 画在 a 的上方并连一条线。

    • $$这里补充了一个习惯，S_n为n的所有正因子组成的集合$$

  • $$<P,\leq>中，若\forall x,y,总有x\leq y或y\leq x，则称\leq为\textbf{全序关系}，<P,\leq>为全序集$$

  • $$设<A,\leq>是偏序集，若B\subseteq A且<B,\leq>是全序集，则称B为\textbf{链}$$

  • $$偏序集<P,\leq>中，a\in P,若\forall b\in P，均有a\leq b，则称a为<P,\leq>中\textbf{最小元}。$$

    • $$\forall A,<P(A),\leq>的最大元是A，最小元是\varnothing$$

    • ​ 偏序集中最大（小）元若存在，则唯一，且它们一定是唯一 ** 极大（小）** 元

  • $$偏序集<P,\leq>中，a\in P,若\not \exists b\in P,使b<a,则称a为\textbf{极小元}。$$

    • 有限集中极大（小）元一定是最大（小）元

  • $$偏序集<P,\leq>中，A\subseteq P,b\in P,若\forall a\in A,都有a\leq b,则称b为A的一个\textbf{上界}$$

  • $$若a是A的一个上界，且\forall b是A的上界，a\leq b,则称a为A的最小上界（\textbf{上确界}）\\ 上确界记为supA，下确界记为infA$$

    • 偏序集上（下）确界若存在，则唯一。

# 函数

• 定义：

  $$f是A到B的关系，若\forall x\in A,存在唯一的y\in B,使<x,y>\in f,则f称为A到B的函数，记为f:A\rightarrow B\\ *<x,y>\in f可记为y=f(x),或f:x\mapsto y,y为x在f下的\textbf{象}，x为y在f下的\textbf{原象}。\\ *进一步地，对于集合A_1\subseteq A,A_1中所有元素在f下的象构成的集合称为A_1的象，记为f(A_1)\\ 同理对于集合B_1\subseteq B,B_1中所有元素在f下的原象构成的集合称为B_1的完全原象，记为f^{-1}(B_1)\\ *f(A)为f的值域domf，f^{-1}(B)为f的定义域ranf$$

  • $$*规定\varphi:a\mapsto [a]_R \forall a\in A,为A到A/R的\textbf{自然映射}$$

$$若f:A\rightarrow B,A_1\subseteq A,g=\{<x,y>|x\in A_1,y=f(x)\}，则称g为f在A_1上的\textbf{限制}，记为f|_{A_1},\\也称f为g在A上的\textbf{扩张}。$$

$$f:A\rightarrow B,若\forall x,y\in A,x\neq y,f(x)\neq f(y),则称f为A到B的\textbf{单射}$$

$$f:A\rightarrow B,若ranf=B，则称f为A到B的\textbf{满射}$$

若 f 既为单射，也为满射，则称 f 为 A 到 B 的一一映射（双射）。

• $$*习惯规定，B^A为从所有从A到B的函数组成的集合。|B^A|=|B|^{|A|},A,B可为无限集$$

# 函数的复合

• 函数的符合即关系的复合，但特别地，规定：

$$(f\circ g)(x)=f(g(x))=g\diamond f(\diamond 指关系的复合)$$

• 函数的复合满足结合律，且保映射性质：

  • $$若f，g均为满(单/双)射，则f\circ g也为满(单/双)射$$

# 函数的求逆

• 函数 f 可逆，当且仅当 f 是双射。

• $$f的逆记为f^{-1},即关系f的逆$$

• $$设f:A\rightarrow B,g:B\rightarrow C均可逆，则g\circ f可逆，且(g\circ f)^{-1}=f^{-1}\circ g^{-1}$$

# 无限集

# 集合的势

• 定义：若存在集合 A 到集合 B 的双射，则称 A 与 B 等势（对等）。（等价于含有相同多元素）

  • $$例：N\sim 2N,(0,1)\sim R,[0,1]\sim(0,1)$$

• 显然，等势关系是一个等价关系。

• $$定理，若A_1\cap A_2=\varnothing,B_1\cap B_2=\varnothing,A_1\sim B_1,A_2\sim B_2,则A_1\cup A_2\sim B_1\cup B_2$$

• $$定理：\textbf{无限集必定与它的一个真子集等势},(A\sim A-\{a\},a\in A)$$

• 规定：

  $$与N等势的集合势记为\aleph_0,记为|N|=|Q|=\aleph_0,而|R|=|(0,1)|=\aleph$$

• $$定义：若A\not\sim B且A\sim C\subseteq B,则记为|A|<|B|,|A|\leq|B|\Leftrightarrow A到B存在单射\\ 特别地，\aleph_0 <\aleph\\ \textbf{康托猜想：}\aleph_0与\aleph之间不存在其他势$$

• Bernstein 定理：

  $$|A|\leq|B|,|B|\leq|A|\Longrightarrow |A|=|B|$$

• 三歧定理：|A|<|B|,|A|>|B|,|A|=|B | 必然有一个成立。

• 康托定理：

  $$\forall集合A，|A|<|2^A|$$

# 可数集

• 定义：与 N 等势的集合称为可数集。即其中的元素可不重复排成一个无穷序列。

• 定理：可数集的无穷子集均为可数集。

• 定理：任何无限集必有可数子集。

• 定理：在可数集中加入或删除有限个元素仍为可数集

• 定理：

  $$可数集A，B，则|A|=|B|=\aleph_0 ,A\cup B仍为可数集，但A\cap B 不一定为无限集。A\times B仍为可数集$$

• 定理：

  $$若A为无限集，B为\textbf{可数集或有限集},则A\sim A\cup B$$

# 连续势集

• 定义：与 R 等势的集合称为连续势集。

• $$若A为连续势集，B至多为连续势集，则A\cup B仍为连续势集。即:\\ |A|=\aleph,|B|\leq\aleph,则|A\cup B|=\aleph$$

• $$|(0,1)\times(0,1)|=\aleph,所以(0,1)\sim(0,1)\times(0,1)$$

• $$若|A|=|B|=\aleph,则|A\times B|=\aleph$$

• 特别地，有：

  $$|2^N|=\aleph$$

# 关于集合的几个有趣的东西

# Cantor 悖论

$$设C为所有集合构成的集合，则又康托定理，|C|<|2^C|，而2^C也是个集合所以2^C\subseteq C,矛盾$$

# Russell 悖论

$$记S=\{A|A\not\in A\},则S是否\in S?$$

# Godel 不完全定理

# 第一定理

• 任意一个包含一阶谓词逻辑与初等数论的形式系统，都存在一个命题，它在这个系统中既不能被证明为真，也不能被证明为否。（另外一种简单表达：一个不弱于初等数论的形式系统，如果一致则必不完全。）

# 第二定理

• 如果系统 S 含有初等数论，当 S 无矛盾时，它的无矛盾性不可能在 S 内证明。（另外一种简单表达：这样的系统如果一致，则一致性无法再系统内证明。）