你好,这个从这以后几次呢, 我们要讲逻辑数学悖论,这个逻辑集合论悖论,要 好好的理解那些悖论呢,还是需要一些初步的集合论知识, 所以呢,这一讲呢我们讲一些最初步的集合论知识。 好,不难的,都可以理解。 凭借直观就可以理解。 首先,我们要有一个集合和元素的概念, 集合是什么呢?是集合论的初始概念,它是不加定义的,把一些可区分的对象 放在一起就构成一集合,额,那集合对元素的身份呢 几乎没什么要求,你比如,假设我前面,这个这个 有一块地毯,我那个地毯上摆的东西 那就构成一集合,那地毯上当然可以摆各种各样的 东西,额,那就是那个那个构成一集合, 这个构成集合的对象呢,称为集合的元素, 一个集合呢由它的元素所决定, 相同的对象呢构成相同的集合,不同的对象呢构成不同的集合。 那就是什么?你比如,如果 有,地毯上一共有五个东西, 那呢,这五个东西构成一个集合。 这个这个这个,因为就这五个东西,地毯上这五个东西 你说那就是就这一个集合, 一个集合,没有别的集合,没有别的集合,如果你呢 又给加了一个东西,这个加了一个东西, 额,把一个喝完水的瓶子 扔在上面了,那呢,那元素多啦。 那原来它是一个五个元素的集合,现在呢它是一个六个元素的集合。 相同的对象构成相同的集合,不同的对象构成不同的集合。 给出集合呢有这个呢 两个办法,一个是列举,也就是,那集合由哪些元素 这个构成呢?你一个一个把它元素列举出来。 列举出来,那个呢就叫列举法,你比如 太阳系行星的集合,那呢太阳系大行星的集合, 原来是九个元素,现在呢就八个元素了,水星,金星, 地球,火星,火星,木星,土星,天王星,海王星, 原来有一个冥王星,冥王星呢 这个2006年世界天文学家大会 这个这个把冥王星呢从太阳系大行星的集合里面 去剔除了,它认为它不属于太阳系大行星。 所以呢,现在太阳系大行星由八个元素构成。 那由 n 个元素可以构成一个集合,那这就是 n 个元素的集合。 不包含任何元素的集合呢称为 空集,写成那个,写成那个,显然 用列举法呢只能给出有穷集合。 额,甚至呢有穷集合都不能太大,你说 那个这个中国人的集合你要用列举法列举, 那个你没法列举,十三亿多人,它的确切数目究竟是多少? 都不知道,额,都不知道,那十三亿多只是一个大概的估算。 那个那个它还是有穷集,但它数目太多了。 那也没法列举,也没法列举,这个呢,所以列举法实际上 呢是非常有限的,例如,这个元素数量非常大的集合, 额,特别是对于无穷集合,就根本没办法列举, 所以列举法很有限, 因此我们要有另外的办法去定义集合,那就是刻画法。 就是通过刻画一个集合的元素必须具有的某个性质来确定该集合。 例如,一个集合啊它由这样的 x 来组成, 由这样的 x 作为元素来组成, 那 x 是什么呢?它是太阳系的大行星。 额,太阳系的大行星,它给定了一个元素条件,元素身份。 额,那例如,在另一个基础上, 它的元素是这样的 x,x 是什么呢?是上周末, 晚餐的食品或饮料,这是个有穷集嘛。 额,有穷集,你上周末呢,即使是一个多么奢华的晚宴呢, 那个那个它的食品和饮料的数量都是非常有限的。 额,最多几十种呗,额,上百种, 那个那个那个叫什么,慈禧,据说慈禧的晚宴啊 慈禧的晚餐几百多个盘,一两百个盘,实际上 到弄那么多盘,那么多种,没有意义, 额,这个这个那只是 一个人的胃呢,那个那个那个食量是非常非常有限的。 她那个两百多道菜呢,她一个里面夹一筷子她都吃不完。 它只是一种心里感觉,要的就是那派头,但实际上那个 都是 stupid 都是非常愚蠢的, 愚蠢的,所以现在即使贵族呢也不搞那样的事情了,那个那个那个 毫无意义,纯粹呢 stupid 一个非常愚蠢的做法。 好,x 自然数的集合, 自然数你没法一一列举,太多了,无穷多 所以你就说,这样,由这样的 x 组成,x 就是自然数,它就定义了自然数的集。 一般的说,一个集合呢由刻画法 刻画法可以这样来表示,x 是由这样的 x 组成的集合, 那个 x 呢具有性质 F,具有性质F,x 是 F 集合的元素呢就是由所有且只有 那些具有性质 F 的对象组成的,习惯上 我们用大写的 N 表示自然数集,用 Z 表示整数集,用 Q 表示有理数集,用 R 表示实数集, 它们都是无穷集,都是无穷集。 在给出集合的两种办法中,刻画法当然是 这个最基本的,额,这不用说了, 那 x 是集合 A 的元素,读作什么呢?x属于A, 记成那样 x∈A,为书写方便,如果 x∈A,y∈A, 那就写成 x,y∈A,集合 x 呢不是集合 A 的元素呢,就写着 x∉A,那个用那个符号,额,用这个符号, 额,用这个符号。 这个呢,对任意的 x 来说 如果对任意的 x,x 都不属于 A, 那 x 就是一个,那那那,那 A 呢就是一空集呗,它就不包含任何元素。 嗯,那集合之间呢 可以进行,有一些关系交并补, 可以进行一些运算,额,两个集合相等,当且仅当它们有相同的元素, 那就是对任意的 x,x∈A 当且仅当 x∈B, 那就记作 A=B,A 和 B 不相等 那当且仅当至少有一个元素属于一个集合而不属于另一个集合, 额,那就记作呢 A不等于B,额, 这个呢,两个集合相等,只要求它们有相同的元素, 与其元素在相应集合中的排列次序无关, 并且一个元素重复出现呢,仍记为一个元素。 而不是两个元素,你比如 (a,b,b)=(a,b)=(b,a), 额,一个元素重复出现呢,那就是同一个元素, 额,这个这个集合里面呢不管元素的次序, 哪个说在前面,哪个说在后面,没关系。 在 A、 B,如果 A、 B,设 A、 B 是两个任意的集合,如果对任一的 x, 若 x∈A 则 x∈B,则称 A是B的子集,亦称A包含于B。 或者B包含A,B包含A,A包含于 B呢就一定B包含A,记作 A这个包含于B。 这个这个包含下面一等号,它就说不排除两人相等。 不排其他相等。 若 A 是 B 的子集,但 A 和 B 不等 那就称 A 是 B 的真子集,亦称 A 真包含 于 B,或者称呢 B 真包含 A, 写成那个 呃,写成这样,写成这样 这个显然,根据定义 若 A 真包含于 B,则有元素呢 不属于 A 但属于 B。 那当然这是,例如,这个这个这个 北大学生的集合真包含于中国人的集合 那显然中国人的集合大嘛,北大学生的集合小嘛,那肯定有很多的人 他不是北大学生,但是中国人。 空集呢 是任意集的真子集。 呃 元素与集合之间的属于关系呢 这个不说了,你们自己看,时间有限啊 在集合与集合之间 也可以进行各种运算,如交、 并、 补 由集合 A 的元素和集合 B 的元素构成的集合,称为 A 和 B 的并集 记作这样,记作这样,A ∪ B A ∪ B 它是由什么组成的集合呢? 是由这样的 x 组成的集合,x 或者属于 A,或者属于 B 呃,这个呢 这个呢,又既是 A 的元素又是 B 的元素 构成的集合,称为 A 和 B 的交集 那记作这个,你看啊,这样 A ∩ B 那由这样的元素组成,x 组成,x 属于 A 并且 x 属于 B 嗯,这个呢,你比如,共产党员和北大学生的集合 交集,那就是 由他们俩重叠的那个部分构成的,就是由既是共产党员又是北大学生的人构成的 由属于 A 但不属于 B 的元素构成的集合 称为 A 与 B 的补集,或者叫 差集,记为 A—B,A—B就是什么呢?由 属于 A 但不属于 B 的那些元素组成的 呃,你比如,中国人的集合里面 呃,也包含一个北大学生的集合 那把那中国人的集合减去 北大学生的集合,那就由不是北大学生中国人组成的集合 如果我们所谈论的各个集合都是集合 D 的子集,那么 集合 A 的补集呢称为 D—A,或者就写成 —A 啦 —A 那就是由属于 D 但不属于 A 的元素构成的 那 D 呢在这个时候呢就称为论域或者叫全集 如果 A 和 B 没有共同的元素,那就是 A ∩ B =∅ 那呢,则称 A 与 B 不相交 由一个集合的所有子集构成的集合,称为 A 的幂集 呃,power set 呃,称为它的幂集,那 A 的幂集等于什么呢? A 的所有子集的集合,A 的所有子集的集合 这个,因为时间有限呢 我们不能深入各种细节。 好,我们现在讲 关系、 函数和映射。 集合之间的元素不是不区别 不区别顺序的。 为了区别两个元素的顺序呢,我们要引 进有序元组的概念。 一个有序对 那就是什么呢?呃,写成这样,你看啊,写成这样 有序对,这个由 x,y 组成的有序对 那呢,这个,这个有序对由两个元素组成 x 和 y,并且,并且 x 呢是这个有序对的第一个元素 y 是这个有序对的第二个元素。 有的时候把它叫 x 叫有序对第一个坐标 y 是有序对的第二坐标。 呃 有序对第二个坐标。 有序对不仅讲元素,而且讲元素出现的 次序,次序。 这是有序对。 如果两个有序对相等 那呢,那不仅呢就是它 们都有两个元素,并且这两个元素的出现顺序是相等的 呃,是一样的。 然后呢,第一个元素,第一个有序对第一个 元素等于第二个有序对第一个元素,第 一个有序对第二个元素等于第二个有序对第二个元素 等等等等,这是两个有序对 这个我们还可以引进有序三元组的概念 呃,1,2,3,有三个,呃,或者 n 元组 1,2,3,4,n,等等,一直到 n 这个呢,那就是,这些来说不仅 与个数有关,而且与这个元素出现的位置顺序有关 呃,一个 n 元有序组相等呢 那当且仅当,它们这两个有序对的 这个元素的个数相等,并且它们的出现位置 呃,相等,出现的次序相等。 那 有序一元组呢,那就是该元素本身 呃,就是这样。 利用有序 n 元组的概念呢,我们可以定义 n 个集合的卡氏积,笛卡尔积 这个,我们为什么要有,我们为什么要有序 n 元组啊? 那样的这样的概念啊,我们实际上是为了定义呢,就是 这个关系概念的外延,关系概念。 你比如爱 你比如大于,大于呢,我们逻辑呢要 把它外延化处理。 那什么叫大于的外延呢? 那大于的外延啊就是具有 大于关系的那些 对象的个体的有序对 构成的一个集合。 你比如啊,那我告诉你,什么叫大于啊? 什么叫大于?你看啊,我们有个有序对,这个 2 大于 1 以及这个 3 大于 2,呃,3 大于 1 呃,4 大于 3,等等等等,把这样的有序对呢这个这个集合起来 一个个写,但这写不完,它是一个无穷集。 这个呢 写不完,它是一个无穷集。 这个呢,那你把这个 有序对呢构在一起,收集起来构成一 集合。 这个集合呢就定义了,定义了 大于的外延,大于的外延 这个呢,这个为什么要有有序对。 那什么是爱?什么是爱?爱的外延 爱这个概念的外延。 爱显然是两个个体之间的,至少是两个个体之间的关系。 那 x love y,x love y,那你就把具有这种关系的有序对 爱我们一般都用到人上面吧?所以,由具有爱 这个关系定义出来的集合应该是人的集合的一个子集,那就是什么? 爱,啊,你比如,这个贾宝玉爱林妹妹 呃,这个这个等等的嘛,呃,这个这个 王刚呢爱李娜,呃,等等等等,就这样 你把这样的有序对呢集合起来,就构成一个 爱这个概念的外延,呃,就是 由爱所定义出来的一集合。 这就我们为什么需要有序对 就是这样。 它是为了定义该由关系概念 定义出来的一集合。 那你比如 这个这个这个,呃 我们就说大于吧,大于定义出来的一集合。 那就是什么啊? 这个呢,它是由 x,y 这样的有序对构成的,这个呢 这个呢,这个有序对的它必定满足的条件就是 x 大于 y,x 大于 y 等等。 好,这是有序对,可以定义关系概念 的外延,呃,由关系概念所决定的集合 利用有序元组的概念呢,我们还可以定义 n 个集合的卡氏积 设 A 和 B 是两个集合,A 和 B 的卡氏积 就是 A×B,那就是什么?在 A 里面取一个元素,在 y 里面取一个元素 那呢,就是由此定义出来的 A x B 由 A 的元素做第一个坐标, B 的元素做第二个坐标,所形成的全部有序对所组成的集合, 等等。 这个呢, 这个我们刚才说了,就是 我们为什么要有有序对呢,就是因为它可以定义呢 这个这个关系概念属于的外延, 定义呢,关系概念所决定的集合, 而大于关系的集合,[咳嗽] "大于关系"是由如下有序对组成的集合, [咳嗽] <2,1> <3,2> <3,1> <5,4> <6,3> 等等 [咳嗽] "夫妻关系", 那它是由下面的有序对定义的集合, [咳嗽] <蒋介石,宋美龄> <毛泽东,江青> <周恩来,邓颖超> [咳嗽] <钱钟书,杨绛> 等等等等。 由于关系 R 是一个集合,所以我们就可以把它写成什么呢? R 是,这个它是集 A x B 的一个子集, 呃,这个呢,那从 A 里面取第一个元素, B 里面取第二个元素,等等等等。 好,是 R 是集合 A 上的一个二元关系。 如果对任意的 x∈A,都有这个呢 <x,x>∈A,∈R,∈R 这个有序对 ∈R,则称 R 呢具有自返性。 这是 x, R, x,这对任意的 x 都成立。 这个,这个就自返,这个关系是自返关系。 你比如吧,等于、 等于,任意的 x 都等于 x, x 是 [iii] R,等于关系是自返关系。 如果对任意的 x,y ∈A,若 <x,y> 这个有序对 ∈R,这个呢,则 <y,x> ∈R,则称 R 具有对称性,换成大白话吧 就是如果 x R y, 则 y R x, 这个呢,R 就是对称的,你比如,什么叫对称? 等于关系对称,x=y,则 y=x。 呃,这个同学关系对称,如果 x 是 y 的同学,y 就是 x 的同学。 呃,这是对称。 传递,传递呢, 任意的 x,y,z∈A, 若 x R y,y R z,y R z y R z,那就得到 x R z。 那这个 R 关系是传递关系,那你比如,很多关系 都是传递的,等于、 大于、 小于等等,是传递的。 但同学关系不传递,同学关系不传递,x 是 y 的同学,y 是 z 的同学, 那 x 和 z 之间呢,不一定有同学关系。 不一定有同学关系,当然也可能有, 呃,x 和 y 是小学同学, y 和 z 是大学同学,x 和 z 呢 那可能是同学也可能不是,若 A,R 具有自反性,对称性和传递性则称 R 是集合 A 上的一个等价关系,一个等价关系。 若 R 是集合 A 上的一个等价关系,a∈A,小 a 属于 A, 则称集合,这个 R,就是这样的,R a, R, x 由满足这个条件的 R, 为 a 所在的等价内,记为这个。 呃,记为这个。 设 R 是一个二元关系, 它的所有元素,那就有序对的第一个坐标所组成的集合叫 R 的定义域。 呃,记作 dom(R),dom(R) 是由有序对的第一个元素, 呃,组成的这个这个那个集合, 它的所有元素第二个坐标所组成的集合呢, 就叫做关系 R 的值域,记作 ran(R)。 呃,就是由有序对 x,y,z,呃,x,y 这个第二个元素 y 组成的一个集合,关系 R 的定义和值域的并集叫做 R 的域。 记作 fld(R),啊 fld(R),那 fld(R) 呢,就等于 dom(R) 和 ran(R) 的并集。 如果一个二元关系满足如下面的条件, R 的定义域呢,是 A 的一个子集, 值域呢是 B 的一个子集,并且对每一个 A 的每一个元素 x,有一个并且只有一个 B 的元素 y 与它对应,那就是 <x,y> <x,y>∈R 有一个并且只有一个啊, 呃,y 呢与 x 有 R 关系,那就是与,换句话说,如果有俩, 如果 <x,y>∈R 并且 <x,z>∈R 那么 y 和 z 是同一元素,我们就称 R 呢为 一个呢从集合 A 到集合 B 的元素。 记作 f,小 f, function。 function,有时也称 f 呢是从 A 到 B 的一个映射,mapping。 呃,mapping,记作 f:A→B,当 A 是一个 n 元关系的时候 我们也称 f 为一个 n+1 元关系, 这个呢,n+1 元关系,这个你比如吧, 这个呢,这个这个,我们有一集合, 一有穷集,它第一由有序对构成, <2,10> <3,15> <4,20> <5,25>, 实际上呢,这这这,它,我们 可以把这个这个集合它定义为一个函数,那个函数就是什么呢? 函数就是什么呢? n 这个呢 乘5,n x 5。 n 就是那里面的 n,n=2,n x 5 那就二五一十,三五一十五,四五二十,五五 二十五,这个可以写成、 写成一个这个这个这个 那就是 n x 5,呃,n x 5,它是一函数, 这一函数你也可以写成一关系式啊,呃,n x 5, 等于某个东西呗, 等于某个东西,等于这个 fn,呃,fn,fn= n x 5,呃,你可以写成这样,但 3 和 4, 这个有序对啊,4 和 5,5 和 6, 6 和 1,它不是一函数,你不能抽象出一个函数来,你看啊, 那个 3 和 4 好像加 1,4 和 5 加 1,5 和 6 加 1,但 6 和 1 呢, 诶,这就又减 5 啦,呃,减 5 啦, 这个这个这个,呃, 当 f 是一个函数的时候,通常以 fx=y 来代替呢 fy 这个有序对呢属于 f, 并说 y 呢,是函数 f 在 x 的值,有时候呢称 x 为函数 f 的自变量, y 呢称函数 f 的因变量,因变量也叫作函数值,两个函数 相等是指它们的定义域相等,并且它们在定义域中的 任意元素处的值都相等, 呃,这个这个,任意元素处的值都相等。 这个呢,设有函数 f A 到 B 吧,如果 f 满足这个 若这个就是什么呢, 这个 f(x1) 或 f(x2) 等于 f(x2) 那么呢,如果两个函数运算所得到的结果相等, 那么,那俩函数的自变量呢 也应该相乘。 换句话说,如果两个函数的自变元不等 那它得,经过函数运算,得出来值也不等 这时候呢,就称f呢为 A 到 B 的单射 单射。 如果 f 满足 这个这个这个 f 的值域 f 的值域就是什么呢,就是 B。 那么呢 称 f 是从 A 到 B 的满射 把 B 呢映满了,映满了。 如果 f 既是单射又是满射 则称 f 是从 A 到 B 的双射,双射也叫一一对应 一一对应。 这个一一对应,我们前面说了,一一对应是定义无穷极的一个非常重要的 凭借和手段 换一种方式说,当f是一个函数的时候 若有对任意的 x 恰好存在一个 y 这个呢,f(x,y) 即是说,若对于任一的 x 存在一个并且只存在一个 y 使得 x 属于函数 f 的 定义域,y 属于函数 f 的值域 则称 f 是一个一对一函数 若对于任一给定的集合 A1 和 A2 有一个一对一的函数,使得 A1 等于函数 f 的 这个值域,哦不不,定义域,A2 等于函数 f 的值域 则称这两个集合之间是一一对应的,一一对应的 这个基数和序数 基数我们前面已经讲了,这个时间有限呢,我们就略过去了 就是基数呢,就是,就是元素的个数 元素的个数。 那元素呢,去掉了那个各个元素之间的 那个不同,元素,元素的那个那个那个那个不同 你这个是粉笔,那个是钢笔,等等那些玩意儿不同,这是一个元素,那是一个元素 就是把那个不同忽略了。 然后呢 那个那个,把元素之间的次序 那里是钢笔、 粉笔、 铅笔、 水瓶 这个呢,这是水瓶、 钢笔、 铅笔等等 元素不同,它只要个数相同 只要个数相同,那这俩元素呢 这俩集合就有相同的基数,这是基数的概念 基数是刻画集合大小的元,概念 也就是刻画一个集合中元素多少的概念,它有多少个元素 序数呢,也是集合论的一个基本概念,是自然数概念的推广 具体地说,如果一个集合 A 具有下面三条性质,则称集合 A 为一个序数 这个属于关系的连通,连通性 那就这样定义的。 对任意的 y,z 属于 A 都有 y 属于 z,或者 y 等于 z,或者 z 属于 y,都有 这叫属于连通。 属于传递,对于任意的 y 和 z 若有性质,若有了 这个那个 y 属于 z,y 属于 A,z 属于 y 那呢,z 也就属于这个这个这个,z 属于 A,z 属于 A 这个呢,正则性 对于任意的集合 B,B 假如真包含 A,并且 B 不空 则称 z 属于 B,使得 z 交 B 是一个空集,即 z 与 B 不相交 这时,称 z 为 B 的极小元。 关于序数呢 那就有以下定义,有以下定义。 0是一个序数 若 α 是一序数了,则 α+1 是序数;若这个 A 是序数的一个集合 则 A 的并集也是一个序数;任一序数呢,都只由上面的 这个这个这个(1)——(3)这个 获得。 那不是有以下等价定义,应该是有以下归纳定义 等等等等,递归定义,递归 等价,递归 也可能是那是拼错了,拼错了,递归定义,归纳定义 等等等等。 上面定义 α+1 呢,就是 α 并上 α 的单元集,这样构成的。 好,这个这一节呢 讲的那个集合论的初步知识,因为下面要讲 逻辑数学悖论,要涉及到其中的很多概念,也许 有同学,有同学 不太理解这些,通过我这么 讲一下,因为我是提纲挈领的,时间很有限嘛 提纲挈领地,这个概要地说了一些结论 然后有些地方没听懂,没听懂,如果你对这个愿意深入钻研 你可以看,找一本集合论的书吧,看一看 就能明白,这个实际上这些知识呢 要明白这些初步知识,找哪一本集合论的书都基本上可以 你比如我前面推荐过的,就是晏成书的《集合论》 也可以,一个小册子,就可以,也可以。 好,这一讲到这里