又名抽象代数、近式代数

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

# 集合论

# 幂集

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

    例:

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

# 集合的运算

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

AB=(AB)(BA)=(AB)(AB)A\bigoplus B=(A-B)\cup(B-A)=(A\cup B)-(A\cap B)

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

# 有序 n 元组

  • 相等定义:

  • <a1,a2,...,an>=<b1,b2,...,bn>ai=bi,i=1,2...,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><<x,y>,z>=<x,y,z>

    # 笛卡尔积

    • 定义:

      A×B={<x,y>xA,yB}A1×A2×...×An={<a1,a2,...,an>aiAi}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\}

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

    • A1×A2×...×An=A1×A2×...×An|A_1\times A_2\times...\times A_n|=|A_1|\times|A_2|\times...\times |A_n|

# 多重集

  • 重复度定义:

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

  • 多重集的运算:

    MAB(a)=max(MA(a),MB(a)),MAB(a)=min(MA(a),MB(a))MAB(a)=MA(a)MB(a),MA+B(a)=MA(a)+MB(a)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 称为一个二元关系,简称关系。

  • RA×B时,称RAB的关系,当RA×A时,称RA上的关系当R\subseteq A\times B时,称R为A到B的关系,当R\subseteq A\times A时,称R为A上的关系

  • 关系的定义域domR={xyB,使<x,y>R}关系的值域ranR={yxA,使<x,y>R}关系的\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 $$

    注:xy/否有关系也可记为xRyxy,R为关系*注:x与y是/否有关系也可记为xRy,x\not Ry,R 为关系

# 关系的性质

  • 自反性

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

    反自反

    xA,均有xx\forall x\in A,均有x\not Rx

  • 对称性

    xRy时,均有yRx当xRy时,均有yRx

    反对称性

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

  • 传递性

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

# 关系的复合

  • 定义:

    RAB的关系,SBC的关系。则RS为:{<a,c>bB,<a,b>R,<b,c>S}R是A到B的关系,S是B到C的关系。则R\circ S为:\\ \{<a,c>|\exists b\in B,<a,b>\in R,<b,c>\in S\}

  • 关系的复合满足结合律不满足交换律,并且满足:

    RmRn=Rm+n,(Rm)n=RmnR^m\circ R^n=R^{m+n},(R^m)^n=R^{mn}

# 关系的逆

  • 定义:

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

  • domR1=ranR,ranR1=domR,(R1)1=R(RS)1=S1R1domR^{-1}=ranR,ranR^{-1}=domR,(R^{-1})^{-1}=R\\ (R\circ S)^{-1}=S^{-1}\circ R^{-1}

# 关系的闭包

  • 定义:

A上的关系RR满足:1R是传递(自反、或对称的)(2)RR(3)∄RR,使R满足(1)(2)若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)=RIA,其中IAA上的恒等关系,其关系矩阵为单位矩阵r(R)=R\cup I_A,其中I_A是A上的恒等关系,其关系矩阵为单位矩阵

  • 对称闭包:

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

  • 传递闭包:

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

# 等价关系

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

R1,R2A上的等价关系,则R1R2,(R1R2)+A上的等价关系其中,R+=i=1Ri若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={xxA,xRa},其中RA上的等价关系,[a]记为由a生成的等价类[a]_R=\{x|x\in A,xRa\},其中R为A上的\textbf{等价关系},[a]记为由a生成的等价类

# 商集

  • 定义:

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

  • 性质:

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

# 划分与覆盖

  • 定义:

集合族C={CiCi是集合,iJ}若满足iJCi=A,则称CA的一个覆盖,若还有CiCj=(ij),则称CA的一个划分,Ci称为划分块集合族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

    • R1,R2A上的等价关系,则R1=R2A/R1=A/R2设R_1,R_2 是A上的等价关系,则R_1=R_2\Leftrightarrow A/R_1=A/R_2

# 偏序关系与偏序集

  • 定义:

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

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

    • <P,>为一偏序集,若a,bPa<b(ab,ab),∄cP使a<c<b则称b盖住a,或称ba直接前辈ab直接后辈<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 的上方并连一条线。

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

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

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

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

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

      • ​ 偏序集中最大(小)元若存在,则唯一,且它们一定是唯一 ** 极大(小)** 元

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

      • 有限集极大(小)元一定是最大(小)元
    • 偏序集<P,>中,AP,bP,aA,都有ab,则称bA的一个上界偏序集<P,\leq>中,A\subseteq P,b\in P,若\forall a\in A,都有a\leq b,则称b为A的一个\textbf{上界}

    • aA的一个上界,且bA的上界,ab,则称aA的最小上界(上确界上确界记为supA,下确界记为infA若a是A的一个上界,且\forall b是A的上界,a\leq b,则称a为A的最小上界(\textbf{上确界})\\ 上确界记为supA,下确界记为infA

      • 偏序集上(下)确界若存在,则唯一。

# 函数

  • 定义:

    fAB的关系,若xA,存在唯一的yB,使<x,y>f,f称为AB的函数,记为f:AB<x,y>f可记为y=f(x),f:xy,yxf下的xyf下的原象进一步地,对于集合A1A,A1中所有元素在f下的象构成的集合称为A1的象,记为f(A1)同理对于集合B1B,B1中所有元素在f下的原象构成的集合称为B1的完全原象,记为f1(B1)f(A)f的值域domff1(B)f的定义域ranff是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

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

f:AB,A1A,g={<x,y>xA1,y=f(x)},则称gfA1上的限制,记为fA1,也称fgA上的扩张若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:AB,x,yA,xy,f(x)f(y),则称fAB单射f:A\rightarrow B,若\forall x,y\in A,x\neq y,f(x)\neq f(y),则称f为A到B的\textbf{单射}

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

若 f 既为单射,也为满射,则称 f 为 A 到 B 的一一映射(双射)

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

# 函数的复合

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

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

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

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

# 函数的求逆

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

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

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

# 无限集

# 集合的势

  • 定义:若存在集合 A 到集合 B 的双射,则称 A 与 B 等势(对等)。(等价于含有相同多元素)

    • 例:N2N,(0,1)R,[0,1](0,1)例:N\sim 2N,(0,1)\sim R,[0,1]\sim(0,1)

  • 显然,等势关系是一个等价关系

  • 定理,若A1A2=,B1B2=,A1B1,A2B2,A1A2B1B2定理,若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

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

  • 规定:

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

  • 定义:若A≁BACB,则记为A<B,ABAB存在单射特别地,0<康托猜想:0之间不存在其他势定义:若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 定理:

    AB,BAA=B|A|\leq|B|,|B|\leq|A|\Longrightarrow |A|=|B|

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

  • 康托定理

    集合AA<2A\forall集合A,|A|<|2^A|

# 可数集

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

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

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

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

  • 定理

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

  • 定理

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

# 连续势集

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

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

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

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

  • 特别地,有:

    2N=|2^N|=\aleph

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

# Cantor 悖论

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

# Russell 悖论

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

# Godel 不完全定理

# 第一定理

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

# 第二定理

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