请读者具备离散数学的基础
一、集合与类
外延原则与集合
外延原则：集合是由元素所决定的
元素常用\(a,b,c…\)小写字母表示，集合常用\(A,B,C…\)大写字母表示
其中元素要满足确定性、相异性（参考高中课本）
如\(N=\{0,1,2,…\}\)，集合的元素数可以有限也可以无限
那么可以有属于或不属于关系，如\(3∈N,π∉N\)
这里先引入不完整的概括原则
概括原则(不完整)：\(S=\{x~|~p(x)\}\)表示集合是由满足\(p(x)\)性质的元素所组成的
如\(A=\{x~|~x+1<0,x∈N\}\)
罗素悖论与类
罗素悖论：\(T=\{x~|~x∉x\}\)
来思考这个集合，会发现相矛盾的点
如果x是T的元素，那么就要满足x不是T的元素
如果x不是T的元素，那么根据其性质就是T的元素
可以发现不管怎样都是存在这样的矛盾，从命题逻辑来看就是\(A←→￢A,~~~A:x∈x\)这样的矛盾式
这里引入新的概念——类
用类的概念可以去解决这样的悖论
类是更加宽泛的概念，类分为集合、真类
\(类\begin{cases}集合:可作为元素属于集合\\ 真类:不可作为元素属于集合也不可为类的元素 \end{cases}\)
外延原则适用于集合、类
但概括原则有些不同，需要修改
回到罗素悖论，正是因为\(x∉x\)是决定了真类而非集合，导致了悖论的发生
概括原则被具体到下述六个原则，下述原则只会导出集合而不会导出真类从而避免悖论的发生
概括原则(1)——空集合的存在原则
存在着空类即空集合\(Ø\)满足性质\(x≠x\)
概括原则(2)——对集合的存在原则
存在任意集合\(x,y\)，其中集合\(S=\{x,y\}\)，那么\(S\)称为无序对集合
如果\(x=y\)那么集合\(S=\{x\}\)称为单元集合
第二条原则允许了集合是可以随意嵌套的，如\(A=\{Ø,\{Ø,1,\{2,3,4\}\}\}\)
有序对集合
利用第二条原则可以定义有序对集合
对于任意的对象\(a,b\)将\(\{\{a\},\{a,b\}\}\)称为有序对集合简记为\(<a,b>\)
(1)\(<a,b>=<u,v>\)当且仅当\(a=u,b=v\)
这个定义简单来说就是约束某一项从而可以确定该项的顺序
如\(<1,2>=\{\{1\},\{1,2\}\}≠<2,1>=\{\{2\},\{1,2\}\}\)
概括原则(3)——幂集的存在原则
子集/超集定义：有任意集合\(S1,S2\),若满足\(∀x,x∈S1→x∈S2\)，则称\(S1\)是\(S2\)的子集，或称\(S2\)是\(S1\)的超集，记作\(S1⊆S2\)，否则记作 \(S1 \not ⊆ S2\)
(1)空集是任意集合的子集
(2)任意集合是自身的子集
(3)传递性：若\(S1⊆S2,S2⊆S3\)则\(S1⊆S3\)
幂集定义：给定任意集合\(S\)一定存在幂集，其所有的子集构成的集合称为幂集
记作\(P(S)=\{x~|~x⊆S\}\)
幂集元素数：若\(S\)有\(n\)个元素，则\(P(S)\)有\(2^n\)个元素
这一点可以利用组合学的观点来证明（略）
概括原则(4)——并集合的存在原则
并集定义：给定任意集合\(S\)一定存在并集合，其中所有元素构成的集合称为并集合
记作\(∪S=\{x~|~∃y(x∈y~∧~y∈S)\}\)
如\(S=\{\{1,2\},2,3,4,\{5,Ø\}\}\)，\(∪S=\{Ø,1,2,3,4,5\}\)
(1)结合幂集易得：\(∪P(S)=S\)
高中所学一类运算实则是并集合的特殊情况，如
\(A∪B=∪\{A,B\}\)
罗素悖论产生的原因
考虑\(A=\{x~|~x∈Z,x ≤ 3\}\)
你很快就能得出答案，但无意识地忽略了某些内容，如果x=4或更大时，会是什么情况
\(\{4≤3,5≤3,6≤3…\}\)
这看起来很奇怪， 因为无法满足，但这恰恰是问题来源，如果不满足怎么办？
这正是忽略的问题，性质\(p(x)\)有分满足的情况和不满足的情况
用一阶逻辑的观点来看，朴素集合论用函数描述了性质，但却没有考虑函数是不满足的情况
函数有分重言式、可满足式、矛盾式
重言式是指不管取什么值都一定满足，如\(x∈R,x<x+1\)
可满足式是部分满足，如上述的A集合的性质
而矛盾式正是暴露其问题的根源，罗素悖论构造了这样的矛盾式让这一缺点放大变得致命
同样也能很快地构造矛盾式，如\(B=\{x~|~x>3~∧~x<3\}\)
可能会说这是空集，实质上是默认用了下面的分离原则，但套用在罗素悖论上就显得矛盾
因此在公理集合论中拓展了集合的概念
新增加了真类和类的概念，比如类A中的子类\(\{4≤3,5≤3,6≤3…\}\)这是真类而不是集合
\(\{3≤3,2≤3,…\}\)这个子类是集合
\(A\)是集合与真类的并运算后的类
但在高中所学简单的朴素集合论的观点中却忽略了这种情况，为什么x能取任意值就却忽略了\(4≤3\)这样虽然不满足但却在其范围内的例子呢
在之前类的定义中解决了这样的问题，真类不可作为类的元素，但确实存在
概括原则(5)——子集的分离原则
根据概括原则，假设有一类\(C=\{x~|~p(x)\}\)
这时候你虽然不确定其成分，但可以构造一集合\(S\)满足\(C⊆S\)（备注：真类不可作为元素，因此包含只针对集合部分）
那么可以有\(C∩S=\{x~|~x∈C~∧~x∈S\}\)这样子就能得到集合而避免取到真类
这个原则能通过构造集合来分离出类的集合
定义：\(S1=\{x~|~∃S,C⊆S,p(x)~∧~x∈S\}\)
通过此原则，罗素悖论也能解决\(S1=\{x~|~∃S,C⊆S,x∉x~∧~x∈S\}=Ø\)
集合运算
交运算：\(S1∩S2=\{x~|~x∈S1~∧~x∈S2\}\)
广义交：\(∩S=\{x~|∀y(y∈S→x∈y)\}\)
相对补：\(S1-S2=\{x~|~x∈S1~∧~x∉S2\}\)
笛卡尔积：\(S1×S2=\{<x,y>~|~x∈S1~∧~y∈S2\}\)
关系
为方便描述，常常将\(∀x(x∈y→A(x))\)简写成\(∀x∈yA(x)\)
类关系\(R\)满足条件\(∀x∈R∃y1∃y2(x=<y1,y2>)\)
根据定义得出\(R⊆C1×C2\)，换个定义——关系就是笛卡尔积的子集
(1)定义域：\(dom~R=\{x~|~∃y(<x,y>∈R)\}\)
(2)值域：\(ran~R=\{y~|~∃x(<x,y>∈R)\}\)
(3)域：\(fld~R=∪\{dom~R,ran~R\}\)
(4)若\(<x,y>∈R\)，则\(x,y∈∪∪R\)
（备注：\(∪R\)拆解成有序对集合，\(∪∪R\)拆解成最基本的元素）
(5)\(dom~R,ran~R,fld~R\)都是集合
(6)\(fld~R=∪∪R\)
常常将\(<x,y>∈R\)简记为\(xRy\)，将\(<x,y>∉R\)简记为\(x \not R y\)
关系复合运算：\(R1~。R2=\{<x,y>~|~∃z(xR2z~∧~zR1y)\}\)
(7)复合运算结合律：\((R1~。R2)~。R3=R1~。(R2~。R3)\)
逆运算：\(R^{-1}=\{<y,x>~|~xRy\}\)
(8)\(domR^{-1}=ranR\)
\(ranR^{-1}=domR\)
\((R^{-1})^{-1}=R\)
\((R1~。R2)^{-1}=R2^{-1}~。R1^{-1}\)
上述证明不算太难，可以简单证明
限制运算：\(R↾C=\{<x,y>~|~xRy~∧~x∈C\}\)
象：已知关系R和类C，象\(R[C]=\{y~|~∃x∈CxRy\}\)
限制运算是限制x的定义域在C中有什么有序对，象是根据限制运算限制后的有序对得到其x是定义域的子集
函数
函数在集合论中的描述非常简单，就是有序对的集合
包括之前关系所讲的运算中定义域、值域应该都能理解是什么意思
函数是特殊的类关系
定义：\(R=\{∀x∀y1∀y2(xRy1~∧~xRy2→y1=y2)\}\)
函数具有的特性称为【单值性】，所谓单值性就是同一x值只能对应唯一的y值
函数有类函数或是集合函数，一般常讨论集合函数
常用\(f(x)=y\)表示，用\(f\)表示函数（关系）
函数的某一点用有序对表示\(<x,f(x)>∈f\)
函数简记为\(f:C1→C2\)即集合到集合的特殊关系，其中\(domf=C1,ranf⊆C2\)
在值域方面比较特殊，C2称为上域
值域表示函数能取到的值
上域表示函数可能取到的值
特殊函数
函数有一定的特殊性质
[1]满射：若\(C2=ranf\)，则称该类函数是满射的。满射反应了值域与上域之间的性质。或者用复杂的性质表述是\(∀y∃x~f(x)=y\)
[2]单射：若类函数满足\(∀x∈C1~∀y∈C1~(x≠y→f(x)≠f(y))\)即不仅从x到y只有唯一的y对应，从y到x也只有唯一的x对应
[3]双射：如果类函数即是满射又是单射，则称为类函数是双射的
(1)类函数的逆至少要满足原函数是单射的，因为逆运算交换值域定义域后其也要满足单值性的要求
(2)对于单射的类函数来说，其逆函数的定义域为\(ranf\)
逆运算交换了定义域和值域看上去不需要写明这条性质，但稍有区别
假设有一类函数\(f:C1→C2,domf=C1,ranf⊆C2\)
那么此时\(f^{-1}:ranf→C1,domf^{-1}=ranf,ranf^{-1}=C1\)
关键在于交换后，原本的值域会从\(C2\)约束到\(ranf\)
如果再进行一次逆就发现不会满足\((f^{-1})^{-1}=f\)这样的性质，因为上域被约束了
\((f^{-1})^{-1}:C1→ranf,dom(f^{-1})^{-1}=domf,ran(f^{-1})^{-1}=ranf\)
因此有些课本会说逆函数存在的充要条件就是函数必须是双射的，但实际上不用满足满射也是可以的，但这样会损失某些性质，尤其是后面所讲关于左逆/右逆的性质
(3)如果类函数是双射的，那么逆函数也是双射的且满足\((f^{-1})^{-1}=f\)
(4)若类函数是单射的，则\(x∈domf,f^{-1}(f(x))=x\)或\(y∈ranf,f(f^{-1}(y))=y\)
(5)类函数的复合
已知类函数\(f:C1→C2,g:C2’→C3\)（备注:\(C2’⊆C2\)）
\(f~。g:C1→C3,dom(f~。g)=\{x~|~x∈domg~∧~g(x)∈domf\}\)
[4]恒等函数
根据关系相关结论可以构造\(f^{-1}~。f\)从而得到\(f^{-1}(f(x))=x\)
如果有一类函数\(I_c:C→C,I_c(x)=x\)则称为恒等函数（即互逆构成恒等），根据恒等函数可以得出以下结论
(6)若\(g~。f=I_c\)，则\(f,g\)互逆，其中\(g\)在左侧称为左逆，\(f\)称为右逆，其中要满足\(f≠Ø,g≠Ø\)
单值化原则
(1)单值化原则：对于任意的类关系\(R\)，存在类函数\(G\)使得\(G⊆R\)且\(domG=domR\)
这一原则构造了更加特殊的类函数，即关系的定义域与函数的定义域相同
(2)若类函数\(F≠Ø\)，则存在左逆\(G\)，当且仅当\(F\)是单射的
证明：
充分性证明：
条件：存在左逆\(G\)，即满足\(G~。F=I_c\)
假设\(F(x)=F(y)~~~(∃x∃y(x,y∈domF))\)
根据恒等函数性质有\(G(F(x))=x,G(F(y))=y\)
\(∴F(x)=F(y)→x=y\)即函数\(F\)是单射的
这里对单射的定义进行了简单的变换
要证明\(∀x∈C1~∀y∈C1~(x≠y→f(x)≠f(y))\)
根据一阶逻辑即要证明\(∃x∈C1~∃y∈C1~(f(x)=f(y)→x=y)\)
有关一阶逻辑的内容可以在离散数学中学到，这里默认你已有相关基础
另外的必要性就不做证明了也很简单
(3)若类函数\(F≠Ø\)，则存在右逆\(G\)，当且仅当\(F\)是满射的
充分性证明：
条件：存在右逆\(G\)，即满足\(F~。G=I_c\)
要证明满射即证明\(ranF=C\)集合论的观点可以拆解成证明\(ranF⊆C~∧~C⊆ranF\)
假设\(G:C1→C2,F:C2’→C1\)
因为是恒等函数，得\(∀x,x=F(G(x))\)，即\(x∈C1→x∈ranF\)即\(C1⊆ranF\)
\(ranF⊆C\)是作为函数本身具有的性质
因为得\(ranF=C\)
(4)弱形式的单值化原则：对于任意的集合关系\(R\)，存在集合函数\(G\)使得\(G⊆R\)且\(domG=domR\)
概括原则(6)——替换原则
(1)\(R\)为类关系，若\(domR,ranR\)为集合，则\(R\)为集合关系
\(∵R=\{z~|~∃x∈domR~∃yRank(z=<x,y>)~∧~z∈PP(fldR)\}\)
(2)若\(F\)为类函数，\(S\)为集合，则\(ran(F↾S)\)为集合
该原则表述了如何从类关系到集合关系
类的封闭性
类运算具有封闭性，不管如何运算得到的依然是类
\(C1∩C2,C1-C2,C1∪C2,￢C=V-C(C⊆V)\)等运算后依然为类
但集合经过运算后并不一定是集合，可能是真类
\(￢S=V-S(V=￢S∪S)\)都是集合但运算得到的\(￢S\)却是真类
存在极小元原则
极小元定义：\(S\)为非空集合且存在元素\(x∈S\)，若满足\(S∩x=Ø\)，则称x为S的极小元
如\(A=\{1,2,3\}\)这样的集合就以高中观点来看这并没有满足条件的极小元，但在下一章节会说明这个原因，实际上1,2,3都是集合并非元素，其中\(1=\{0\},2=\{0,1\},3=\{0,1,2\}\)因此集合\(A\)的极小元是\(1\)，\(A∩2=A∩\{0,1\}=\{1\},A∩3=\{1,2\}\)
参考哈斯图，极小元是一个集合中可推导出其他元素的基本元素
存在极小元原则：任意非空集合至少存在1个极小元，但可以有多个极小元
该原则证明了某些类一定不是集合
不存在奇异集合
奇异集合是非常特殊的一个集合，有元素\(x_0,x_1,…\)，满足下面之中的某一性质：
(1)\(x∈x\)
(2)\(x∈y,y∈x\)
(3)推广：\(x_0∈x_1~∧~x_1∈x_2…∧~x_{n-1}∈x_n~∧~x_n∈x_0\)
(4)降链：\(…∧~x_{n+1}∈x_n~∧~x_n∈x_{n-1}…∧x_1∈x_0\)
即奇异集合在有限的情况下，各个元素互相挨个属于形成闭环；在无限的情况下形成降链，无穷远的元素不断属于前面一个直到\(x_0\)
利用存在极小元原则反证即可
证明(1)：假设集合满足性质\(x∈x\)，\(∵x∩x≠Ø\)，因此不存在极小元，但根据存在极小元原则，至少要有极小元因此矛盾，不存在集合满足\(x∈x\)
证明(3)：假设集合\(A\)满足性质\(x_0∈x_1~∧~x_1∈x_2…∧~x_{n-1}∈x_n~∧~x_n∈x_0\)
\(∵∀i∃j,x_i∈x_j\)
\(∴∀i~~~A~∩~x_i≠Ø\)
同理也可以证明降链的情况，因此不存在满足这一性质的奇异集合
但对于类来说是存在，比如\(A=\{x~|~x>3~∧~x<3\}\)可以得到\(…\{5<3\}∈\{4<3\}\)
属于是针对集合运算的，因为真类不属于任何的类，所以真类之间可以认为是等价的，自然满足属于关系
总结
本章梳理了最基本的集合概念，并通过悖论引出类的概念。类是类型论研究的重点，但本篇研究的集合论固对于有些模棱两可无严谨数学定义的类不做过多说明
同时说明了集合应当遵守的法则，以及特殊的集合——关系、函数、奇异集合
参考书籍
《公理集合论导引》张锦文
原文地址：http://www.cnblogs.com/vntlly/p/16861371.html
