《数理逻辑pdf截止9月1502-无限集合初步_》由会员分享，可在线阅读，更多相关《数理逻辑pdf截止9月1502-无限集合初步_（22页珍藏版）》请在金锄头文库上搜索。
1、基本约定基本约定 约定约定2.1: 以下是一些常用的集合: ? 是自然数集合 ? 是整数集合 ? 是有理数集合 ? 是实数集合是实数集合 公理集合论公理集合论 事实事实2.1(集合论公理集合论公理) 在集合论中, 一个核心概念是无限, 为纯粹数学研究提供强有 无限集合初步 N Z Q RR 力的工具, 在计算机科学中有广泛应用. 集合论的公理集合论的公理 ?外延公理 ?空集公理 ?偶对公理 ?并集公理 ?子集公理 ?幂集公理 ?无穷公理 ?替换公理 ?正规公理 ?选择公理 ZF 与 ZFC ?前 条被称为 ZF. ?全部 条被成为 ZFC. 映射映射 定义定义2.1(单射单射,满射满射,双射双
2、射) 假设 是集合 到 的函数: ? 是单射: ? 是满射: ? 是双射: 是单射且 是满射 单射与满射之间的关系单射与满射之间的关系 9 10 fAB f xyJA(f(x)=f(y) x=y) f yJB xJA(f(x)=y) fff 定理定理2.1: 假设集合 都不是空集. 若存在 到 的满射, 则存在 到 的单射. 证明证明: 假设 是满射, 则可以定义 到 的映射 : 是单射, 这是因为当 时, , 所以 定理定理2.2: 假设集合 都不是空集. 若存在 到 的单射, A,BAB BA f:A BBAg yJB f-1(y)=xJA|f(x)=y, ff-1(y) xJf-1(y)
3、yBA g gy1=y2JB/ f-1(y1)Qf-1(y2)Ig(y1)=g(y2)./ A,BAB = 则存在 到 的满射. 证明证明: 假设有以下单射: 可以如下定义 到 的映射: 其中 是 的任意一个元素, . 是一个满射. BA f: A B, x sf(x). BA g: B A, x sg(x)= i aa aa aa aa e aa aa aa aa j f-1(y), yJran(f), a 否则. aAran(f)=f(y)|yJA g 等势等势 定义定义2.2(等势等势) 给定集合 . ?若存在从 到 的单射, 则称 的势小于等于 的势. 记为 , . ?若存在从 到 的
4、双射, 则称 与 等势, 也称为有相 同的基数. 记为 . ?若 且 , 则记为 , . 性质性质2.1: 若 , 则 . 性质性质2.2: 若 是单射, 则 . 例例2.1: 假设 是自然数的平方构成的集合. A,B ABAB A;BB BA.f(A) S . / 基数基数 事实事实2.2(基数基数): 存在一类集合, 它们互不等势, 任意一个集合都 与这类集合中的某一个等势, 这些集合可以列举为: 这类集合的每一个称为基数. 若集合 与某个基数 等势, 则称 的势是 、元素个数 是 , 记为 . 假设 是自然数, 当集合 的元素个数为 时, ,1,2,l, 0,R1,R2,l,R=,R=+
5、1,l,R=2,l,RR0,l A-A- -|A|=- nAn A.n. 0R 等势关系的基本性质等势关系的基本性质 定理定理2.3(传递性传递性) 对于集合 , 若 且 , 则 . 定理定理2.4 对于集合 , 假设 且 , 则 , . Schrder-Bernstein 定理定理 定理定理2.5: 若 , 则 . A,B,CA;BB;C A;C A,B,C,DA.BC.D A#C.B#D2A.2B A;B,B;AA.B 是一个单射, 所以 . 又因为 , 根据 Schrder-Bernstein 定理, 可知 . 无限集合无限集合 定义定义2.3(有限的有限的,可数可数,可数无限可数无限,
6、不可数不可数) 给定集合 : ?若存在 到 的单射, 则称 为可数的. 是可数的当且仅当 . ?若存在 到 的双射, 则称 为可数无限的. 可数无限集合的基数记为 . ?若 与某个自然数是等势的, 则称 为有限的. ?若 不是可数的, 则称 为不可数的. 第一个不可数的基数记为 . fR;(0,1)(0,1)R (0,1).R A ANA AA;N ANA R0 AA AA R1 ; ?若 不是有限的, 则称 为无限的. 都不是有限集合. 定理定理2.7: 若 是无限的, , 则 . 证明证明: 以下递归地定义集合 : ?假设 . ?假设已定义 : 这时 , 是有限集, 所以 任取 . AA
7、N,Z,Q,R AaJAA-a.A B=an|n=0,1,2,l a=a0 Xk an|n=0,1,2,l,k-1. XkNA A-Xk=I./ akJA-Xk 由上述定义可知, 当 时, . 所以 是 的无限子 集. 以下定义的 是 到 双射: 所以 . 一些可数及不可数集合一些可数及不可数集合 定理定理2.8: 可数集合的子集是可数的. i=j/ai=aj/BA fAA-a f: A A-a, x s f(x)= i aa aa aa aa e aa aa aa aa j ak+1, x=ak,k=0,1,2l x, 其他. A-a.A 证明证明: 假设 是可数的, 则 . 当 时, 有
8、, 所以 , 因而 是可数的. 定理定理2.9: 是不可数的. 证明证明: 只需证明开区间 是不可数的. 以下用反证法证明该 事实. 假设 是可数的, 则可以将它表示为: 采用十进制表示, 可以假设 AA;NBNAB;A B;NB R (0,1) (0,1) a0,a1,a2,l. an=0$un0un1un2l 定义实数 其中 则 不同于每个 , 这是因为 与 的第 位小数不同. 上述事实与假设 是矛盾的. 所以 是不可数的. Cantor 定理定理 b=0$v 0v1v2l, vn= i aa aa aa aa aa aa aa aa e aa aa aa aa aa aa aa aa j
9、 unn+1, 若unn= , ;/ 7,若unn=8; 8, 若u nn=9. banbann (0,1)=a0,a1,a2,l (0,1) 8 9 定理定理2.10: 对任意的集合 , 都有 . 推论推论2.1: 对任意集合 , 有 因而可以得到势充分大的集合; 若 是可数集, 则上述集合中 除 之外都是不可数的. 自然数集合的一些乘积自然数集合的一些乘积 ?定理定理2.11: . 证明一证明一(构造双射构造双射): 存在 到 的双射: AA92A A A92 A922A9222A9l, A A N.N#N N NN# 证明二证明二(构造单射构造单射): 已知 , 根据 Schrder-B
10、ernstein 定理, 可知只需 证明存在 到 的单射. 以下是几种构造方式: ?以下函数 是 到 的单射. f:N#N N, s (m+n)2+3m+n 2 !. N;N#N N#NN g1:N#N N, s2m3n. N#NN ?推论推论2.2: , , ?推论推论2.3: . ?定理定理2.12: 是不可数的. ?定理定理2.13: . ?推论推论2.4: 有限个可数集合的卡氏积是可数的. ?推论推论2.5: 可数个可数集合的并集是可数的. 一些可数的字符串集合一些可数的字符串集合 ?定理定理2.14: 可数符号表上有限长字符串集合是可数的. N.N#N#NN.N#N#N#Nl N.Q
11、 N= N=.2N ?推论推论2.6: 可数的一阶语言的公式的集合是可数的. ?推论推论2.7: 自然语言的语句集合是可数的. 代数数与超越数代数数与超越数 定义定义2.4(代数数代数数,超越数超越数) ?满足整系数一元多项式方程的复数称为代数数. 一个复数若是代数数且是实数,则称它为实代数数. ?不是代数数的复数称为超越数. 一个复数若是超越数且是实数,则称它为实超越数. 例例2.2: ?有理数 是代数数. m n ! ? 是代数数. ? 是代数数. ?实数 是实超越数. ? 是实超越数. 定理定理2.15:存在实超越数. 可定义的实数可定义的实数 定义定义2.5(可定义的实数可定义的实数)
12、 假设 是一个实数, 若存在数学分析语 言之下的仅包含一个自由变元 的公式 , 使得在实数范围内 成立, 而当实数 满足 成立时, 有 , 则称 是可 定义的实数, 由 定义, 是定义 的公式. 例例2.3: 2 Y Z Z Z Z Z Z Z! i 1+ 1 101! !+ 1 102! !+ 1 103! !+l 1 r x9 9x r s9x s s=rr r99r ? 是可定义的. ? 是可定义的. ? 是可定义的. 定理定理2.16:存在不可定义的实数. 可计算函数可计算函数 定义定义2.6(可计算函数可计算函数) 假设一个程序 在一台计算机上运行, 接 收输入字符串 , 记 为相应
13、的输出. 若不停机则记输出 为 . 给定一个接收自然数输入的程序, 以下函数 2 Y Z Z Z Z Z Z Z! 1 e P xP(x) f: N NPi n sP(n) i 称为可计算的函数. 定理定理2.17:存在不可计算函数. 连续统假设与选择公理连续统假设与选择公理 ?连续统假设 CH(Continuum Hypothesis) 不存在一个集合 , 使得 且 . ?1938 年 Gdel 证明ZFC CH. ?1963 年 Cohen 证明ZFC CH. 因而 CH 独立于 ZFC. ?选择公理 AC(Axiom of Choice) AN9AA92N U/ U / 对任意的非空集合 , 都存在选择函数 使得 . ?1940 年 Gdel 证明ZF AC. ?1963 年 Cohen 证明ZF AC. 因而 AC 独立于 ZF. 总结总结: 习题习题: ?写出集合论的公理及其一阶描述. 全部 A 9: 2A-I A, xs9(x). xJ9(x) U/ U / ?证明:可数符号表上有限长字符串集合是可数的. ?证明: . RR#R.
