集合论是以集合概念为基础，研究集合的一般性质的数学分支学科。
集合是简单而又基本的不作定义的初始概念一般来说，集合是一些确定的、相异的事物的总体
按照集合中事物数目是否有限，可以分为有限集合和无限集合无限集合是集合论研究的主要对象，也是集合论建立的关键和难点
潜无限
实无限
亚里士多德(Aristotle,B.C.384-322)最先提出要区分潜无限和实无限并认为只存在潜无限，实无限即无限集合是不存在的，因为无限多个事物不能构成一个固定的整体。
由于无限集合不符合常识和经验，两千多年来，数学家都和亚里士多德一样对无限集合持否定态度
普罗克拉斯(Proclus,410-485)在研究直径分圆的问题时发现直径数量和将圆分成部分的数量有一一对应的关系
两个大小不同的同心圆上面的点可以通过公共半径来一一对应
伽利略(G.Galileo,1564-1642)也发现不等长线段上的点可以构成一一对应关系。
捷克数学家波尔察诺(B.Bolzano,1781-1848)最先明确承认并坚决拥护无限集合的概
和自然数构成一一对应关系的可数集
和实数区间[0,1]构成一一对应的具有连续统的势的集
康托尔进一步证明了一条直线上的点和整个n维空间中的点具有一一对应的关系
又引入了基数、序数、超限基数、超限序数等概念，并规定了它们的运算
集合论需要严格运用纯理性的论证，其结论不是人的直观和常识所能够掌握的
康托尔的朴素集合论成为整个数学的基础
为了在朴素集合论中消除悖论，人们想了各种办法来限制“病态集合”的产生
最成功的是采用希尔伯特公理化思想对朴素集合论进行公理化
公理化集合论产生发展以后，普遍认为它给数学提供了一个可靠的基础
集合(set):做为整体识别的、确定的、互相区别的一些对象的总体。
整体识别:不再分割
确定:属于或者不属于整体
互相区别:各异的对象
集合的例子
组成集合的对象称为成员(member)或者元素(element)
集合的记号“{,}”
元素和集合的隶属关系
空集
有限集(finitesets)
基数(cardinality)有限集合中成员的个数称作集合的基数(无限集合的基数定义更为复杂)
集合A的基数记做|A|
外延公理、概括公理、正规公理:规定了集合概念的意义
外延公理(extensionalityaxiom)
概括公理(comprehensionaxiom)
正规公理(regularityaxiom)
康托尔的朴素集合论中没有考虑个体域的概念
〉S={x|P(x)}〉罗素悖论:考虑
谓词Q(x)=xx，和集合B={x|Q(x)}〉要判定Q(B)的真值:
如果Q(B)为真，那么B∈B，但得到Q(B)假如果Q(B)为假，那么BB，但得到Q(B)真
集合A称作集合B的子集合，如果A的每一个元素都是B的元素
集合的两个基本关系:隶属和包含
定理1:对于任意集合A和B，A=B当且仅当AB且BA特别的，对于任意集合A，有AA
证明:
A=Bx(x∈Ax∈B)......外延公理x((x∈A→x∈B)∧(x∈B→x∈A))x(x∈A→x∈B)∧x(x∈B→x∈A)(AB)∧(BA)定理2:设A,B,C为任意集合，若(AB)∧(BC)，则有AC
利用逻辑蕴涵式I6:(A→B)∧(B→C)╞A→C来证明
定理3:对于任意集合A，AU
因为x∈U是恒真的，所以x(x∈A→x∈U)也是恒真的
定理4:对于任何集合A，A
因为x∈是恒假的，所以x(x∈→x∈A)是恒真的
定理5:空集是唯一的
假设有两个空集1和2，根据定理4，有12，而且21再根据定理1，1=2定理6:设A为一有限集合，|A|=n，那么A的子集个数为2n次幂
A的子集有::Cn0=1个只有包含A中1个元素的子集:Cn1个只有包含A中2个元素的子集:Cn2个......包含A中所有元素的子集:A本身，Cnn=1个总和:Cn0+Cn1+...+Cnn=2n个例:{1,2}的子集:,{1},{2},{1,2}真子集(propersubset)如果AB且A=B，记做:AB空集是所有非空集合的真子集
判断题:
∈{}∈{}如果A∈B且B∈C，那么A∈C四、集合运算集合基本运算集合运算指以集合作为运算对象，结果还是集合的运算
并运算:∪(union)定义:A∪B={x|x∈A∨x∈B}{1,2}∪{1,3,4}={1,2,3,4}交运算:∩(intersection)定义:A∩B={x|x∈A∧x∈B}{1,2}∩{2,3}={2}差运算-(difference)定义:A-B={x|x∈A∧xB}{1,2,3}-{2,3,4}={1}补运算~(complement)定义:A~=U-A={x|xA}{0,1,2,3,4}~={5,6,7,...}(U=N)交和并运算性质A∪A=A;A∩A=A交换律:A∪B=B∪A;A∩B=B∩A结合律:A∪(B∪C)=(A∪B)∪C;A∩(B∩C)=(A∩B)∩CA∪=A;A∪U=U;A∩=;A∩U=A分配律:A∪(B∩C)=(A∪B)∩(A∪C)，A∩(B∪C)=(A∩B)∪(A∩C)A∩(A∪B)=A，A∪(A∩B)=A差和补运算性质A-A=，A-=A，A-U=A-(B∪C)=(A-B)∩(A-C)A-(B∩C)=(A-B)∪(A-C)利用德摩根律得证A~~=A，U~=，~=UA∪A~=U，A∩A~=(A∪B)~=A~∩B~，(A∩B)~=A~∪B~A-B=A∩B~集合运算和子集关系AA∪BA∩BAA-BAABA-B=A∪B=BA∩B=A如果AB，则有B~A~利用运算性质证明对于任意集合A,B，如果有A∪B=U且A∩B=，那么A=B~
证明1:按照A=B的定义
证明2:按照运算性质的等式
A=A∩U=A∩(B∪B~)=(A∩B)∪(A∩B~)=∪(A∩B~)=(B∩B~)∪(A∩B~)......分配律，提出B~=(B∪A)∩B~=U∩B~幂集(powerset)运算对任意集合A，ρ(A)称作A的幂集，定义为:
ρ(A)={x|xA}A的所有子集作为元素构成的集合(族)
因为A，AA;所以必有∈ρ(A)，A∈ρ(A)
例:ρ({1,2})={,{1},{2},{1,2}}幂集的基数:|ρ(A)|=2|A|
设A,B为任意集合:AB当且仅当ρ(A)ρ(B)证明必要性:(AB)→(ρ(A)ρ(B))设AB，又设任意X∈ρ(A)，有XA因为AB，所以XB有X∈ρ(B)根据子集定义，ρ(A)ρ(B)证明充分性:(ρ(A)ρ(B))→(AB)
〉设ρ(A)ρ(B)，假设AB不成立〉则存在a∈A，但是aB〉也就是{a}∈ρ(A)，但是{a}ρ(B)〉这个与ρ(A)ρ(B)矛盾〉所以AB得证五、集合族及运算集合族与标志集集合族(collections)
集合族的标志集(indexset)
标志集可以是自然数、某些连续符号
广义并:集合族中所有集合的并集
∪C={x|S(S∈C∧x∈S)}广义交:集合族中所有集合的交集
∩C={x|s(S∈C→x∈S)}如果C恰含两个集合A,B
则∪C=A∪B，∩C=A∩B有标志集的表示方法:C={Ad|d∈D}
∪C=∪d∈DAd，∩C=∩d∈DAd集合族运算例子C={{0},{0,1},{0,1,2},...}∪C=N∩C={0}C={{1},{1,2},{1,3,5}}∪C={1,2,3,5}∩C={1}集合族运算性质任意集合A和集合族C，有
A∩(∪C)=∪{A∩S:S∈C}A∪(∩C)=∩{A∪S:S∈C}A-(∩C)=∪{A-S:S∈C}A-(∪C)=∩{A-S:S∈C}(∪C)~=∩{S~:S∈C}(∩C)~=∪{S~:S∈C}证明:A-(∪C)=∩{A-S:S∈C}x∈A-(∪C)<=>x∈A∧xUC<=>x∈A∧(S(S∈C∧x∈S))<=>x∈A∧S(SC∨xS)<=>S((x∈A∧SC)∨(x∈A∧xS))<=>S((xA∨S∈C)→(x∈A-S))<=>S(((xA)→(x∈A-S))∧((S∈C)→(x∈A-S)))<=>S((S∈C)→(x∈A-S))<=>x∈∩{A-S:S∈C}幂集与集合族运算证明:对任意集合A，∪ρ(A)=A
x∈∪ρ(A)<=>S(S∈ρ(A)∧x∈S)<=>S(SA∧x∈S)<=>S(x∈A)<=>x∈A六、归纳定义集合的归纳定义〉集合定义的另两种方式:列举法、描述法〉归纳定义(inductivedefinition)基础条款:规定某些元素为待定义集合成员，集合其它元素可以从基本元素出发逐步确定
归纳条款:规定由已确定的集合元素去进一步确定其它元素的规则
终极条款:规定待定义集合只含有基础条款和归纳条款所确定的成员
〉基础条款和归纳条款称作“完备性条款”，必须保证毫无遗漏产生集合中所有成员
〉终极条款又称“纯粹性条款”，保证集合中仅包含满足完备性条款的那些对象
基础条款:v:=e是程序(其中v是变量，e是算术表达式)
归纳条款:若p1,p2是程序，则p1;p2也是程序若p1,p2是程序，则ifcthenp1elsep2endif也是程序(其中c是条件表达式);若p是程序，则whilecdopendwhile也是程序;
终极条款(略)
数学中“数”是最基本的原始概念，在集合论创立之后，采用集合来定义自然数，使得数学建立在更为简单的概念“集合”基础之上
在算术公理化系统中，皮亚诺(Peano)的5大公理刻画了自然数概念
基础条款:∈N
归纳条款:如果x∈N，则x'=x∪{x}∈N
自然数集的列举定义:
加法的定义:
*x+0=x*x+y'=(x+y)'〉如:3+2=(3+1)'=((3+0)')'=(3')'=4'=5乘法的定义
(归纳基础)针对归纳定义的基础条款，证明基础条款中的所有元素均使P(x0)真
(归纳推理)证明归纳条款是“保持性质P的”
即在假设归纳条款中已确定元素x使P(x)真的前提下，证明用归纳条款中的操作g所生成的g(x)依然有性质P，即P(g(x))为真
L[(A)]=L[A]+1=R[A]+1=R[(A)]L[(A→B)]=L[A]+L[B]+1=R[A]+R[B]+1=R[(A→B)]
所以对于一切命题公式，左括号数量等于右括号数量
归纳基础:证明P(0)为真
归纳过程:对于任意k≥0假设P(k)为真时，推出P(k+1)也为真
结论:所有自然数n都使P(n)为真
证明对任意自然数有(0+1+2+…+n)2=03+13+23+…+n3归纳基础:当n=0，02=03
归纳过程:
设当n=k时，(0+1+2+...+k)2=03+13+23+...+k3成立，当n=k+1时，(0+1+2+...+k+(k+1))2=03+13+23+...+k3+(k+1)2+2(0+1+2+...+k)(k+1)=03+13+23+...+k3+(k+1)2+k(k+1)2=03+13+23+...+k3+(k+1)3归纳完成，命题得证※数学归纳法的变种起始于任意自然数n0的数学归纳法证明所有大于等于n0的自然数都具有性质P
起始于多个自然数的数学归纳法
允许有参变量的数学归纳法对于二元谓词P(m,n)，证明对于一切自然数m,n都为真，可以视情况只对一个变量进行归纳，另一个变量作为参数
证明:3分币和5分币可以组成8分以上任何币值
证明:8=3+5;9=3+3+3;10=5+5
假设k可以用3分和5分币组成，需要证明k+3时命题真，这是显然的，只要再加一个3分币即可
假设我们已经完成下面的推理:
归纳基础:P(0)真;归纳推理:k(P(k)→P(k+1))但是还并非所有自然数都有性质P将这些不满足性质P的自然数构成一个非空自然数子集，这样，子集中必定有一个最小的自然数，设为m显然m>0，记做n+1，这样n一定具有性质P，即P(n)为真n(P(n)∧P(n+1))╞╡k(P(k)∨P(k+1))╞╡k(P(k)→P(k+1))假设推理结果与已经完成的归纳推理矛盾，所以假设错误即数学归纳法成立，所有自然数都有性质P