最近在网上看了几位大牛的博客,对集合论逐渐产生兴趣。进而去维基上翻了翻,对集合论有了个初步的了解。这里做点笔记。
集合论是一个目标统一全宇宙的超级理论。当然也有可能他统一不了了,但透过集合论,去理解人类逻辑的固有定式,去理解数学如何解释世界,是很有意思的事情。
朴素集合论是很容易理解的事情。首先有元素这个概念。然后元素可以属于集合。两个集合相等完全由其元素一一相等来判定(外延公理)。然后集合的元素也可以是集合,集合可以为空(空集公理)。
这就是高中课本上的集合定义了吧。但这样的定义存在巨大的问题。
例如著名的罗素悖论:设存在集合R, 它包含的元素由对“所有集合”应用的一个函数(谓词)来确定,即“不包含自身的集合”(固有前提,该元素是一个集合)。这个谓词是合理的,因为在”所有集合”这个范围内确实存在不包含自身的集合。那么,将所有这样的集合作为元素,放到这个集合R里,理论上似乎可行。那么我们看这样的集合R有什么特性呢? 他或许不包含自身(R不属于R),如果是这样,那么他就应该包含R(因为R是所有不包含自己的集合嘛)。但是如果他包含了自己,他立刻就不应该包含自己了(包含自己的集合不应该属于R)。
为了阻止这种情况发生,严谨的集合论不得不增加一些公理和概念来回避这个问题。首先,使用一个谓词确定的集合不再确保构成一个集合。他们只是属于一类(内涵公理,替代公理)。因此“类”这个概念比集合更广泛。如果一个类不是一个集合(例如“不包含自身的所有集合”),那么他就是一个“真类”。
另外,在一个集合上使用一个谓词仍然可以得到所有符合这个谓词的元素的集合。这称之为分类公理。
之后引入“正则性公理”来确保集合的合理性。这个公理描述起来有点费力。首先,公理化集合论一般认为所有集合都是集合的集合,不存在集合之外的概念。集合的元素也是集合(有可能是空集,所以这个定义是可以终止的)。然后正则性公理是说,任意非空集合,总存在一个元素,这个元素(同时也是集合)与这个集合的交集为空。这样理解很困难,我们反过来理解。任意非空集合,不可能发生这种情况:他的所有元素都与其相交。这仍然很难想象,我们举个例子来观察这样的集合的特性。
假设R符合这个条件,假设他包含一个元素。则 R = {A}
这里A和R相交非空,则A交R = B
B是A和R的交集,则B是R的子集。同时B非空。则B只能是{A}。也就是说,B = R。
所以A交R = B。A = {A, …}
而R = {A}, 所以R = {{A, …}} = {{{A, …}, …}} = {{{{A, …}, …}, …}}
这样的A是无穷递归定义的。或者说,在有限时间内无法写出R的定义。这和无穷集合并不相同。无穷集合只是在有限时间内无法写出这个集合中的元素而已。如果一个集合无法被定义,我们应该认为他就是不存在的吧。
R包含更多元素的情况比较复杂,不过归结到最后都是如这样形式的无穷递归。可以说这个公理防止了这样的不良定义的集合出现。所以“禁止自包含”就是正则公理的内涵之一。
以上几个公理定义了集合的内涵和外延,以及一个操作(分类)。接下来还需定义集合的并(并集公理)这个操作。这个操作的定义与朴素集合论中的定义略有不同。
这个定义的形式描述有点绕,这里形象的说明就是:一个形如R = {{A},{B},{C}, …}的集合,他的并U R = {A, B, C, …}。
所以,{A, B, C}U{D} = U{{A, B, C},{D}} = {A, B, C, D}
相信读到这里很多lisp玩家已经感到似曾相识了。确实函数式语言、图灵机等等计算机科学基本概念都可以说是自集合论派生出来。这也是我会忽然跳这个大坑的原因。
定义了并之后,集合操作基本定义完全。至于说交集这个定义呢,因为存在分类公理,交集其实是分类公理使用“属于某个集合”这个谓词的一种特化形式。因此无需使用公理定义出来。
还有几个公理,我这里配合描述集合论构造自然数的定义来描述。因为这一段似乎是集合论中最容易懂的一部分了
这里直接给出定义的形式,他比描述还容易懂。之后根据这个形式中出现的几个特征,引出几个定义。
0 = {} (空集)
1 = {0} = { {} }
2 = {0,1} = { {}, { {} } }
3 = {0,1,2} = {{}, { {} }, { {}, { {} } }}
4 = {0,1,2,3} = { {}, { {} }, { {}, { {} } }, {{}, { {} }, { {}, { {} } }} }
由于自然数是无穷的,必须使用归纳法定义全体自然数。前面集合的并集的定义是一个铺垫:
首先 0 = {} 是自然数。
然后 假设x是自然数,则x的下一个自然数x’ = x U {x}
由是自然推出了元素的“后继”这个概念。x’是x的后继,则x’ = x U {x}。并依据后继这个概念定义归纳法(无穷公理):
存在集合A,首先,空集属于A,并且对于任意的元素x属于A,则x的后继x’ = x U {x}也属于A。
这不破坏正则公理,因为空集属于A。因此A中存在一个元素,{},他与A的交集是空。
这并不是文字游戏。要求空集包含于A是非常重要的。这相当于是数学归纳法中的初始条件。否则归纳法无法成立。
此外还引出了集合中元素的顺序问题。称x’是x的后继,就是说,x和x’之间存在顺序关系。并且这个顺序关系可以传导。也就是说,x1是x0的后继,x2是x1的后继,则x0和x2也存在x0在前, x2在后这样的关系。 通过这个关系,可以得出集合的序的概念。
首先定义良序集合。所谓良序集合,通俗地说,需要符合两个条件。其一,首先给定一个判定关系的运算符,任意举出这个集合中的两个元素,在这个运算符上能够判定顺序关系(因此这是一个线性的顺序关系,每个元素如果有,都仅有一个后继和一个前驱);其二,任意给定这个集合的子集,能够找出该子集的最小元素(无需保证最大元素)。符合这个条件的集合和这个关系一起就称作良序集。因此自然数在<=这个关系上是良序的。但是整数在<=这个关系上就不是良序。因为不存在这个集合的最小元素。但是如果用其他的顺序关系运算,仍然可以给出一个良序的整数集。例如0, -1, -2, ..., 1, 2, ... 这个顺序,0最小,然后负数比整数小,然后绝对值小的数更小,则得到一个良序集。为何一定要确保最小值,其实就是为了使归纳法成立。后续的大量论证将会建立在良序集的归纳法之上(超限归纳法)。
好了,对于良序集,既然后继是唯一确定的,就可以不停地向后列举下一个后继。如果这个集合是有限集,则最后一个后继的序号(序数)就是一个自然数。如果是可数无穷集合,则这个最大的序数无法在有限时间内获取到。我们设这个数为ω (自然数的序数)。仍然存在序数比ω还大的可数无限集合。例如整数,假如按照上述排序方式,则其序数相当于是ω+ω。又比如,自然数如果采取另一种排序方式0, 3, 6, 9, …, 1, 4, 7, …, 2, 5, 8, …则自然数的序数是ω+ω+ω。我们看到,序作为衡量集合大小的指标有一个不足,就是序是由一个人为确定的关系运算符来确定的。关系不同,就有可能改变序大小。因此还需要更通用的,仅与集合本身相关的指标来衡量集合的大小。
接下来应该引入基数的概念。但由于这一块我还没有完全理解,所以暂且写到这里了。
后续会写一篇文章记录读到目前为止我的各种疑问。作为思考题,推动自己接下来继续去学习~
引用:
维基百科:公理化集合论
刘未鹏:永恒的金色对角线
Matrix67:对角线方法之后的故事