集论初步
1.逻辑基础
1.1逻辑命题
定义1：命题是一个或真或假的陈述语句，即陈述事实的句子，但不能既真又假。其是逻辑的基本成分。
定义2：令p是一个命题，则⌝p表示p的否命题，表示“不是p说的情形”。
定义3：令p、q都是命题，p、q的合取命题用“p∧q”表示，指命题“p且q”。当且仅当p、q都真时该合取为真。
定义4：令p、q都是命题，p、q的析取命题用“p∨q”表示，指命题“p或q”。当且仅当p、q都假时该析取为假。
定义5：令p、q都是命题，p、q的异或命题用“p⊕q”表示。当且仅当p、q中只有一个为真时该异或命题为真。
定义6：令p、q都是命题，条件语句“pq”是一个命题（也称条件语句为蕴含），当且仅当p为真且q为假时该条件语句为假。
注意：条件语句p与q没有因果关系。
【蕴含规定的真值很好理解，假设有个人竞选总统时说“如果我当上总统，我将减少税收。”，则当且仅当他当上总统却没有减少税收时我们才认为他说谎了。】
上述6个基本命题的数学表达——真值表
|
p |
q |
⌝p |
p∧q |
p∨q |
p⊕q |
p→q |
|
T |
T |
F |
T |
T |
F |
T |
|
T |
F |
F |
F |
T |
T |
F |
|
F |
T |
T |
F |
T |
T |
T |
|
F |
F |
T |
F |
F |
F |
T |
关于条件语句的真值表
|
p |
q |
p→q |
q→p |
⌝q→⌝p |
⌝p→⌝q |
p↔q |
|
T |
T |
T |
T |
T |
T |
T |
|
T |
F |
F |
T |
F |
T |
F |
|
F |
T |
T |
F |
T |
F |
F |
|
F |
F |
T |
T |
T |
T |
T |
1.2 命题等价
定义1：命题称为永真式，如果无论复合命题中包括的命题的真值时什么，该复合命题总是真的（复合命题是由一些简单的基础的命题复合生成的）；复合命题称为矛盾式，如果无论复合命题中包括的命题的真值时什么，该复合命题总是假的；复合命题称为可能式，当其既非总真也非总假时。
定义2：在所有可能的情况下，都拥有相同真值的2个复合命题称为逻辑等价，用“≡”表示。（也可以这么定义：当p↔q为永真式时，p与q逻辑等价）。
关于逻辑等价记住德摩根定律和2个关于条件语句等价关系：
⌝(p∧q)=⌝p∨⌝q
⌝(p∨q)=⌝p∧⌝q
p→q≡⌝p∨q
p→q≡⌝q→⌝p
1.3 推理规则
定义：命题逻辑中的一个论证是一连串的命题，除了最后一个被称作结论外，其余的都是前提。当全部前提的真值为1时，如果结论的真值也为1，则称该论证是有效的。
命题逻辑推理规则中常用的永真式
|
表达式 |
名称 |
备注及证明提示 |
|
[p∧(p→q)]→q |
假言推理 |
显然地，重要 |
|
[⌝q∧(p→q)]→⌝p |
取拒式 |
倒置蕴含 |
|
[(p→q)∧(q→r)]→(p→r) |
假言三段论 |
重要 |
|
[(p∨q)∧⌝p]→q |
析取三段论 |
p∨q≡⌝p→q |
|
[(p∨q)∧(⌝p∨r)]→(q→r) |
消解 |
p∨q≡q∨p及假言三段论 |
|
p→(p∨q) |
附加 |
显然地 |
|
(p∧q)→p |
化简 |
显然地 |
|
[(p)∧(q)]→(p∧q) |
合取 |
显然地 |
备注：1 其他永真式要么显然地，要么可以用“假言推理”和“假言三段论”推出；
2 类似[p∧(p→q)]→ q，可以理解为如果p→q为T，当 p为T，那么必有q为T。
利用真值表可以证明，注意：其中[(⌝p∨q)∧(⌝q∨r)]≡[(p→q)∧(q→r)]，(⌝p∨r)≡p→r。
|
p |
q |
r |
⌝p |
⌝q |
⌝p∨q |
⌝q∨r |
(⌝p∨q)∧(⌝q∨r) |
⌝p∨r |
|
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
|
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
|
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
|
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
|
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1.4 证明导论
1 直接证明：依据永真式里的假言推理；
2 反证法：利用永真式里的取拒式，[⌝q∧(p→q)]→⌝p；
3 归谬发：没有利用上述永真式，而是构造了命题“when q is F, p is true→(⌝p→q)”，即当命题p的否命题推出一个矛盾式时，命题p的真值为T。道理：⌝p→q≡p∨q，q为假，故⌝p→q的真假由p决定。
4 等价性证明：p1↔p2↔⋯↔pn≡[(p1→p2)∧(p2→p3)∧⋯∧(pn→p1)]，该方法运用了假言三段论。
5 穷举证明（特例分情况证明）：利用条件语句的定义及德摩根定律。
p1∨p2∨⋯∨pn→q≡⌝（p1∨p2∨⋯∨pn）∨q
≡[(⌝p1∧⌝p2∧⋯∧⌝pn）∨q]
≡[（⌝p1∨q)∧(⌝p2∨q)∧⋯∧(⌝pn∨q）]
≡[（p1→q）∧⋯∧（pn→q）]
即就是：[（p1∨p2∨⋯∨pn）→q]≡[（p1→q）∧⋯∧（pn→q）]。
2 基本结构：集合
2.1基本概念
定义1：集合是一组无序的对象。
定义2：集合中的对象也称为该集合的元素或者成员，也说集合包含它的元素或该元素属于这个集合，记作：a∈A，反之记作：a∉A。
定义3：两个集合相等当其仅当它们拥有同样的元素。用逻辑命题描述为：A=B∀x(x∈A
x∈B)。
定义4：集合A是集合B的子集当其仅当A的每一个元素也是B的元素。即就是：
A⊆B∀x(x∈A→x∈B)
定义5：令S 是一个集合，若S 中恰有n个不同的元素，n是非负整数，就说S 是有限集，而n是S 的基数，用|S|表示。
【|A|=|B|(∃f:A→B)∧(f 是双射)；有限集或者与自然数集基数相等的集是可数(列)的。】
定义6：如果一个集合不是有限的，就说它是无限的，称为无限集。
定义7：集合S 的幂集合是集合S 所有子集构成的集合，用P(S)（或者）表示。
定义8：有序n元组(a1,a2,⋯an)是以a1为第1个元素，a2为第2个元素，…，an为第n个元素的有序组。
定义9：令A、B为集合，A和B的笛卡尔积定义为：
A×B={(a,b)|a∈A∧b∈B}
延伸：A1,A2,⋯,An的笛卡尔积定义为：
A1×A2×⋯×An={(a1,a2,⋯an) | ai∈Ai , i=1,2,⋯n.}
2.2 集合的运算
定义1：集合A和B的并集定义为：A∪B={x|x∈A∨x∈B}。若A∩B=∅，A∪B=A+B，称其为A和B的直和。
定义2：集合A和B的交集定义为：A∩B={x|x∈A∧x∈B}。
定义3：集合A和B的差集定义为：A-B={x|x∈A∧x∉B}，也称为B对于A的补集。若A为全集U，则U-B简记：，简称为B的补集，即
={x|x∉B}。
【这里补充两个关于差集的定理：
定理1：设A、B和C是三个集合，则有：C∩(A-B)=(C∩)A-(C∩B)。
定理2：设A和B是两个集合，则有：A∪B=A+B-A=A+∩B。
定理2推论：设A1,A2,⋯,An⋯是一集合序列，令B1=A1， =
⋯
，则有：
其中∑表示直和。
意义：已知一个和集的构成，利用其构成元素构造它的一个划分。
推论的两个结论可以用数学归纳法同时证明，下面给出该推论的一个例子：
定义4：包含恰属于A和B之一的那些元素的集合被称为A和B的对称差，记作A⊕B。
【A⊕B=(A∪B)-(A∩B)；A⊕B=(A-B)+(B-A)】
定义5：为了统一有限集和无限集，我们这么定义：
—— 表示对于i∈I集合Ai 的并集；
—— 表示对于i∈I 集合Ai 的交集。
2.3 关系
定义1：设A和B是集合，一个从A到B的二元关系是A×B的子集。
假设有一个子集为R，用记号aRb表示(a,b)∈R，其中a∈A∧b∈B，此时称a与b有关系R。
【为什么定义里要说明“子集”，因为其必须满足一定条件才能叫做关系。集合A和B并没有作任何说明，只要它们是集合就可以了。利用集合中元素的对应图示来理解关系很直观。】
定义2：如果∀a∈A((a,a)∈R)，那么集合A上的关系R叫做自反的。
定义3：如果只要a,b∈Aa,b∈R就有(b,a)∈R，则集合A上的关系R叫做对称的。如果只要a,b∈A，仅当a=b时，(a,b)∈R∧(b,a)∈R，则集合A上的关系R叫做反对称的。
定义4：如果∀a,b,c∈A[(a,b)∈R∧(b,c)∈R(a,c)∈R]，那么集合A上的关系R叫做传递的。
【研究关系的自反、对称和传递性的目的之一是给关系分类】
定义5：设R是从集合A和集合B的关系，S是从集合B和集合C的关系。R和S的合成是由有序对(a,c)构成的关系，其中a∈A，c∈C，并且对于它们 ∃b∈B[(a,b)∈R∧(b,c)∈R]，记作S∘R。
【关系的合成与函数复合类似。另外，由于关系是笛卡尔积的子集，故其可以做一切集合运算，这种操作被称作关系的组合】
定义6：设R是集合A上的关系。幂，n=1,2,3,⋯,递归地定义为:
=R 和
=
∘R
定理1：集合A上的关系R是传递的，当且仅当n=1,2,3,⋯，有⊆R。
定义7：设A1，A2，…，An是集合。在这些集合上的n元关系是A1×A2×⋯×An的子集。A1，A2，…，An叫做关系的域，n叫做它的阶。
【n元关系应用很广泛，其中关系型数据库就是经典的例子，具体理论参见数据库理论】
2.4 关系的表示
① 由于关系是笛卡尔积的子集，故关系可以用枚举有序组表示；
②用关系矩阵表示关系；(一般针对二元关系)
③用图表示关系。(一般针对二元关系)
例如，集合A={1,2,3,4}上的关系R={(1,2),(1,3),(2,3),(2,4),(3,3),(3,4),(4,1)}，用矩阵表示为：
|
A×A |
1 |
2 |
3 |
4 |
|
1 |
0 |
1 |
1 |
0 |
|
2 |
0 |
0 |
1 |
1 |
|
3 |
0 |
0 |
1 |
1 |
|
4 |
1 |
0 |
0 |
0 |
其中，矩阵MR=[0001 1000 1110 0110] 称为集合A上的关系R的关系矩阵。
引入关系矩阵后，我们可以用其来研究关系的性质和运算：
（1）具有自反性的关系，关系矩阵主对角线上的元素全部为1；
（2）具有对称性的关系，关系矩阵是对称阵；
（3） 具有反对称性的关系，关系矩阵关于主对角线对称位置上的两个元素至少有一个为0；
（4）设MR1、MR2和MR分别为R1、R2和R的关系矩阵，则
R=R1∪R2MR=MR1∨MR2 (i)
R=R1∩R2MR=MR1∧MR2 (ii)
R=R1∘R2MR=MR1⊙MR2 (iii)
其中，(i)是对应位置的元素做布尔加法运算，(ii)是对应位置的元素做布尔乘法运算，(iii)是矩阵的叉乘，只不过加法运算遵守布尔运算法则。
【1本处关系性质中没有考虑传递性的关系矩阵特征，是因为其特征太复杂，用图来描述较为直观；
2因为关系矩阵在集合元素的相对位置一定的情况下按照上述例子中方法得到的关系矩阵是唯一的，所以关系矩阵和关系之间是一一对应的，因此关系运算直接对应关系矩阵相应的运算。
3由关系矩阵可知，对称和反对称并不是一对相对的概念，当关系矩阵是对角阵时，该关系既是对称的，也是反对称的。】
同样，该关系用图表示则如下：
定义1：一个有向图G（graph）由顶点（或结点）集V（vertex）和边（或弧）集E（edge）组成，其中边集E是顶点集V中元素的有序对的集合。顶点a是边(a,b)的始点，顶点b是边(a,b)的终点。
【形如(a,a)的边用从顶点a到自身的有向弧表示，这种边叫做环】
引入图表示关系后，我们可以用其来研究关系的性质：
（1）具有自反性的关系，当其仅当每个顶点都有一个环；
（2）具有对称性的关系，当其仅当两个不同顶点之间的每一边都有方向相反的边；
（3）具有反对称性的关系，当其仅当两个不同顶点之间的每一边都每没有方向相反的边；
（4）具有传递性的关系，当其仅当只要存在顶点a到b的边和b到c的边，就存在a到c的边。
【1 这里用了“当其仅当”，即就是图与关系之间也是一一对应的；
2 因为图不具有运算性质，故这里没有用图研究关系运算。但是，借助图可以更深入研究关系的性质——关系的闭包。】
定义2：如果存在包含R的具有性质P的关系S，并且S是包含R且具有性质P的每一个关系的子集，那么S叫做R的关于P的闭包。
【3种闭包及其求法：①自反闭包：每个顶点都补充到有环状态，即:R'=R∪∆，∆={(a,a)|a∈A}；
②对称闭包：给每条边补上方向相反的一条边，即:R'=R∪，
={(b,a)|(a,b)∈R}；
③传递闭包：连通性关系R*是R的一个传递闭包，，传递闭包矩阵的具体计算可由沃舍尔算法执行。】
2.5 等价类
定义1：集合A上的关系叫做等价关系，如果它是自反的、对称的和传递的。
定义2：如果两个元素a和b由于等价关系而相联系，则称a和b是等价的。记法a~b 通常用来表示对于某个特定的等价关系来说，a和b是等价的元素。
定义3：设R是集合A上的等价关系，与A中元素a有关系的所有元素叫做a的等价类。记作，a叫做代表。
【】
定理：设R是集合A上的等价关系，下面命题等价：
i. aRb ii. =
iii.
∩
≠ ∅
【这条定理是在说明一个集合A中的两个元素的等价类或是相等或是不相交。
推论：1 ；
2 ≠
∩
= ∅ 。因为[ iii
ii]
[⌝ii
⌝iii].
很明显，由这两条推论，可以看出：1与2对集合A形成一个划分】
2.6 偏序
定义1：集合A上的关系R，如果它自反的、反对称的和传递的，就称R为偏序。集合A和偏序R一起就叫做偏序集，记作(S,R)。
【在一个偏序集中记号a≼b表示(a,b)∈R，a≺b表示(a≼b)∧(a≠b)。
这里≼读作“小于或等于”，但是≼不仅仅是“≤”关系，其表示任意偏序集的关系。】
定义2：偏序集(S,≼)的元素a和b叫做可比的，如果a≼b或者b≼a。当a和b是S的元素并且没有a≼b，也没有b≼a，则称a与b是不可比的。
【用“部分的（偏的）”描述偏序是由于有一些元素可能是不可比的。当集合中的每对元素都可比时，这个关系就叫做全序。】
定义3：如果(S,≼)是偏序集，且S的每对元素都是可比的，则S叫做全序集或线序集，且≼叫做全序或者线序。一个全序集也叫做链。
定义4：对于偏序集(S,≼)，如果≼是全序，并且S的每个非空子集都有一个最小元素，就称它为良序集。
定理（良序归纳原理）：设S为一个良序集，有以下结论：
∀y∈S ∀x∈S(x≺y)(P(x)P(y))
∀x∈S(P(x))
证明：假设∃y∈S (⌝P(y))，则集合A={x∈S|P(x) is false}非空。因为S是良序集，故A存在最小元素a。
又∀y∈S ∀x∈S(x≺y)P(x)→P(y)，取y=a，即就是：∀x∈S(x≺a)（P(x)→P(a)）
因为x≺a，故x∉A，故 P(x)为真，因此P(a)必为真（否则定理的条件为false），这与Pa为false矛盾。
定义5：n个偏序集(A1,)，(A2,
)，…，(An,
)的笛卡尔积上定义字典顺序如下：
如果 或者
那么(a1,a2,⋯,an)≺(b1,b2,⋯,bn)。
【例子：12341221<12351111，1a2<1b0，每个分量的偏序可以不一样】
定义7：∄b∈S(a≺b)，那么a在偏序集(S,≼)中是极大的；∄b∈S(b≺a)，那么a在偏序集(S,≼)中是极小的。∀b∈S(b≼a)，则a是偏序集(S,≼)的最大元素；∀b∈S(a≼b)，则a是偏序集(S,≼)的最小元素。
Zorn引理：每一个有穷非空偏序集(S,≼)都有极小元素。
证明：1 ∀x0若x0不是极小的→∃x1∈S(x1≺x0)；
2 若x1不是，则∃x2∈S(x2≺x1)；
3 若x2不是，则∃x3∈S(x3≺x2)；
… 按递归重复
4 最终找到极值。因为偏序集是有穷的，所以这个过程一定会结束并且找到极小元素。
2.7 映射
定义1：一般地，设A、B是两个非空集合，如果按某一个确定的对应关系f，使对于A中的每一个元素a，在集合B中都有唯一确定的元素b与之对应，那么就称对应 f:A→B 为从集合A到集合B的一个映射（mapping）。
其中，a称为b在f 下的一个原像，b称为a在f 下的像，记作f(a)；A称为f 的定义域（domain），B称为f 的陪域（codomain），f 的值域（range）：Imf = f(A)={f(a) | a∈A}。
定义2：设 f: A→B 为从集合A 到集合B 的一个映射，那么：
若 f(A)=B，则称f 为满射，即就是∀ b∈B∃a∈A(b=fa)；
若∀xi,xj∈A(xi≠xj→f(xi)≠f(xj))，称f 为单射；
若f 既是满射，也是单射，称f 为双射（也叫做一一对应）。
定义3：设f:A→B，g:B→C，令 (gf)(a)≔g(f(a)), ∀a∈A，称gf 是f 与g 的乘积（或合成）。
2.8 集类
定义1：以某个固定的空间Ω的某些子集为元素的集合称为集类。
【集类是幂集的子集】
定义2：如果集类F对F中的单调集列{An}极限封闭，则称F为单调类。
【∀An∈F(((An↑A)∨(An↓A))→A∈F)
因为单调有界列为cauchy列，所以单调类这个概念类似于某个空间上的完备集】
定义3：设{An}是单调增加集合序列，如果满足：∀n∈N*(An⊆An+1)，记作An↑；
设{An}是单调减少集合序列，如果满足：∀n∈N*(An⊇An+1)，记作An↓。
定义4：设A1,A2,⋯,An,⋯是任意集列，由属于上述集列中无限多个集和的那种元素的全体所组成的集合称为这一集列的上极限，即就是：
这一集列的下极限定义为：
我们称集列收敛于A，如果集列的上、下极限都等与A，记为 .
【1 A1,A2,⋯,An,⋯集合序列可以表示成集列{An}；
2 关于上、下极限，按照其定义与关于交并定义有如下关系:
】
定义5：F是空间Ω的某些子集所组成的非空集类，称F对有限和运算封闭，如果满足：
F是空间Ω的某些子集所组成的非空集类，称F对可数和运算封闭，如果满足：
定义6：F是空间Ω的某些子集所组成的非空集类，如果F对有限和与有限差运算封闭，则称F是一个环。
【1 特别地，若Ω∈F，则F是一个代数。
2 若将条件改成“对可数和与可数差封闭”，则F是一个σ-环；同理，若Ω∈σ-环，则F是一个σ-代数。
3 当F是一个环时，有限和+有限差运算封闭有限交运算封闭
证明：A∩B=A∪B-A-B-(B-A)，当涉及有限多个时，运用归纳法证明。
当F是一个代数时，有限和+有限差运算封闭 有限交+取余集运算封闭。
当F是一个σ-代数时，可数和+可数差运算封闭可数交+取余集运算封闭。】
引理：设T是非空数集，如果对每一个t∈T，集类 Ft 都对某运算封闭，则集类 也对这个运算封闭。
定理：设C是由空间Ω的某些子集为元素的集类，存在唯一的包含集类C的最小环F，记作R(C)。
证明：首先说明存在性：以空间Ω的所有子集为元素的集类就是包含集类C的环。
关于唯一性和最小：所有包含集类C的环取交就是所求的最小环F（由于引理，保证了取交后的集类仍是环）。当然，下面注解里的推论可以按此方法证明，因为以空间Ω的所有子集为元素的集类是环、σ-环、代数和σ-代数。
【推论： 1 存在唯一的包含集类C的最小σ-环，记作φ(C)；
2 存在唯一的包含集类C的最小代数F；
3 存在唯一的包含集类C的最小σ-代数，记作σ(C)；
4 存在唯一的包含集类C的最小单调类，记作m(C)。】
定理：φ(C)=m(C)
注：包含集类C的最小σ-环，记作φ(C)；包含集类C的最小单调类，记作m(C)。
证明：（1）当m(C)是环时，m(C)被称为单调环。由于m(C)对任何的单调集列极限封闭，于是m(C)对可数和与可数差运算封闭，所以它是一个σ-环，因此有：
φ(C)⊆m(C)
另一方面，φ(C)由于对可数和封闭，故必然对单调集列极限封闭，因此有：
φ(C)⊇m(C)
即就是φ(C)=m(C)。
【很显然，当集类C为代数时，σ-环变成了σ-代数，单调类还是单调类，此时我们会发现：σ(C)=m(C)】
2.9 测度的概念
定义：设F 是Ω上的一个环，。称f 为F上的测度，如果恒有：
；
;
.
【就是我们平时说的度量。想象一个物体的一个度量——体积，很显然：物体的体积非负、没有任何物质的物体的体积为0，物体的总体积等于将其不相交划分成很多块的小物体的体积之和。
因此，任一个测度必须满足：1 非负性；2 ∅的测度为0；3 可数可加性.