《北大集合论与图论10资料》由会员分享，可在线阅读，更多相关《北大集合论与图论10资料（51页珍藏版）》请在金锄头文库上搜索。
1、2019/9/20,集合论与图论第10讲,1,第10讲 自然数 北京大学,内容提要 1. Peano系统 2. 后继, 归纳集, 自然数, 自然数集 3. 数学归纳法原理 4. 传递集 5. 自然数的运算 6. 自然数上的序关系,2019/9/20,集合论与图论第10讲,2,封闭,封闭: 设f是函数, Adomf, 若 x( xA f(x)A ) 则称A在f下是封闭的(closed) 等价条件: f(A)A 例: f:NN, f(x)=x+1, A=0,2,4,6,在f下不是封闭的 B=2,3,4,在f下是封闭的,2019/9/20,集合论与图论第10讲,3,Peano系统,Peano系统:
2、, F:MM (1) eM (2) M在F下封闭 (3) eranF (4) F是单射的 (5) (极小性公理) AM eA A在F下封闭 A=M,e,F(e),F2(e),F3(e),2019/9/20,集合论与图论第10讲,4,为何如此定义?,2019/9/20,集合论与图论第10讲,5,如何实现?,如何利用集合来构造Peano系统? -借助于下面两个概念 后继 归纳集,2019/9/20,集合论与图论第10讲,6,后继(successor),后继(successor): 设A是集合, A+ = AA 称为A的后继. 特征: AA+ AA+ 在公理集合论中, 无序对公理(a,b)和并集公理
3、(UA)保证了后继的存在,2019/9/20,集合论与图论第10讲,7,后继(举例),A= A+ = + = = A+ = + = = , A+ =,+ =, = , A=a,b A+ = a,bA = a,b,A = a,b,a,b,2019/9/20,集合论与图论第10讲,8,归纳集,归纳集: 若A满足 (1) A (2) x( xA x+A ) 则称A为归纳集. A是归纳集 A含有且对后继封闭 在公理集合论中, 无穷公理(无穷集存在)保证了归纳集的存在,2019/9/20,集合论与图论第10讲,9,归纳集(举例),A=,+,+,+, A=,+,+,+,a,a+,a+,a+, A=+,+,
4、+, 少 A=,+,+,+,a, 少a+,a+,a+,2019/9/20,集合论与图论第10讲,10,自然数,自然数: 自然数是属于每个归纳集的集合 例: , + = , + = , , + = , , + = , , ,2019/9/20,集合论与图论第10讲,11,0,1, 2, ,n,0 = 1 = + = = 0 2 = + = , = 0,1 3 = + = 0,1,2 n = 0,1,2,n-1 ,2019/9/20,集合论与图论第10讲,12,0,1,2,作为集合,23=2=min(2,3), 23=3=max(2,3) 3-2=2,2-3=0 (-是集合运算) Un = U 0
5、,1,2,n-1 = n-1 =max(0,1,n-1), n = 0,1,2,n-1 = 0 =min(0,1,n-1), 0123 0123,2019/9/20,集合论与图论第10讲,13,自然数集,自然数集N: 设D = v | v是归纳集 , N=D D 不是集合, 否则导致悖论! 在公理集合论中, 由无穷公理保证 N 存在(即保证 N 是集合).,2019/9/20,集合论与图论第10讲,14,定理1,定理1: N是归纳集. 证明: N =D= v | v是归纳集 = x | v( v是归纳集xv) . (1) N: v, v是归纳集 v.,2019/9/20,集合论与图论第10讲,
6、15,定理1(续):,证明(续): (2) n( nN n+N ). 利用 xN v( v是归纳集xv)以及 v( v是归纳集 n( nv n+v ) ): n, nN v( v是归纳集nv) v( v是归纳集n+v ) n+N. #,2019/9/20,集合论与图论第10讲,16,N = ?,N是最小的归纳集 v( v是归纳集 ) Nv N = 0, 1, 2, 3, 对比: 自然数 是 属于每个归纳集的集合 自然数集是包含于每个归纳集的归纳集,2019/9/20,集合论与图论第10讲,17,后继函数,后继函数: :NN, nN, (n)=n+ 例: (0) = 0+ = 1, (1) =
7、1+ = 2 = 0+, (2) = 2+ = 3 = 1+ = 0+, #,2019/9/20,集合论与图论第10讲,18,N是否Peano系统?,定理2: 是Peano系统. 证明: (1) N: 定理1. (2)n(nNn+N): 定理1. (3) ran: (n)=n+=nn (4) 是单射的: 下面定理3 (5) SNSnS(n+S) S=N : SnS(n+S)S是归纳集NS.# 称(5)为数学归纳法原理. 证(5)时没有利用(4), 故可用(5)证(4).,2019/9/20,集合论与图论第10讲,19,数学归纳法原理,数学归纳法分两个步骤: 1. 令 S = n | nN P(
8、n) 2. 证明 (1) S; (2) n( nS n+S ).,2019/9/20,集合论与图论第10讲,20,定理3,定理3: 任何自然数的元素均为它的子集. 证明: 1.令S= n | nN x(xnxn) . 2. (1) S: N x(xx) (2) 设nS, 要证n+S, 即要证 n+N x( xn+ xn+ ). x, 设xn+=nn, 分两种情况: (a) x=n x=nn+, (n+=nn) (b) xn xnn+, (归纳假设) S=N. #,2019/9/20,集合论与图论第10讲,21,定理4,定理4: m,nN, m+n+ mn. 证明: () 定理3 () 归纳法.
9、 #,2019/9/20,集合论与图论第10讲,22,定理5:,定理5: 任何自然数都不是自己的元素. 证明: S= n | nN nn . #,2019/9/20,集合论与图论第10讲,23,定理6,定理6: 属于除0外的任何自然数. 证明: S=0S, S= n | nN n0 n . (1) S, (2) nS n+S. #,2019/9/20,集合论与图论第10讲,24,定理7(三歧性),定理7(三歧性): m,nN, 下面三式成立且仅成立一式. mn, m=n, nm 证明: (1). 至多成立一式: 定理5. (2). 至少成立一式: S=n|nNm(mNmnm=nnm). #,2
10、019/9/20,集合论与图论第10讲,25,传递集,传递集: A为传递集 xy( xy yA xA) 定理10: A为传递集 UAA x( xA xA ) A P(A). # 自然数及自然数集都是传递集.,2019/9/20,集合论与图论第10讲,26,自然数的运算,加法: +:NNN, +()=5, 2+3=5 乘法: :NNN, ()=6, 23=6,2019/9/20,集合论与图论第10讲,27,N上的递归定理,N上的递归定理: 设A为集合, aA, F:AA, 则存在唯一函数h:NA, 使得h(0)=a, 且nN, h(n+)=F(h(n). #,F(a)=F(h(0)=h(1)=h
11、(0+),a=h(0),F2(a)=F(F(a)=F(h(1)=h(2)=h(1+),F3(a)=F(F2(a)=F(h(2)=h(3)=h(2+),F4(a)=F(F3(a)=F(h(3)=h(4) =h(3+),1,0,2,3,4,2019/9/20,集合论与图论第10讲,28,一元函数加法: “加m”,“加m”: m固定, Am:NN, Am(0)=m, Am(n+)=(Am(n)+. 例: A2(3)=A2(2+)=A2(2)+ =A2(1+)+ =A2(1)+ =A2(0+)+ =A2(0)+ =2+ =3+ =4+ =5.,2019/9/20,集合论与图论第10讲,29,二元函数加
12、法,加法: +:NNN, m+n=Am(n) 例: 3+3 = A3(3) = A3(2+) = A3(2)+ = A3(1+)+ = A3(1)+ = A3(0+)+ = A3(0)+ = 3+ = 4+ =5+ = 6. # 递归定理保证如此定义是有意义的,2019/9/20,集合论与图论第10讲,30,加法单位元0,mN, 0+m=m, m+0=m 证明: (1) 0+m = A0(m) (+定义) = 0(m) (Am定义) = IN(m), (R0定义) = m (2) m+0=Am(0)=m. #,2019/9/20,集合论与图论第10讲,31,m,nN, m+n+ = (m+n)
13、+,m,nN, m+n+ = (m+n)+ 证明: m+n+ = Am(n+) (+定义) = (Am(n)+ (Am定义) = (m+n)+ (+定义) . #,2019/9/20,集合论与图论第10讲,32,m,nN, m+n = (m+n)+,证明: (数学归纳法). 对任意mN, 令 S = n | nN m+n=(m+n)+ . (1) 0S: m+0=m+=(m+0)+. (2) n(nSn+S): 设nS,下证n+S. m+n+ = Am+(n+) = Am+(n)+ (+与Am定义) =(m+n)+ = (m+n)+ (归纳假设) =(m+n+)+ (定理: m+n+ = (m+n)+ ) S = N. #,2019/9/20,集合论与图论第10讲,33,加法交换律,加法交换律: m,nN, m+n=n+m. 证明: 对任意mN, 令S= n | nN m+n=n+m . (1) 0S: m+0=m=0+m. (0是加法单位元) (2) n(nSn+S): 设nS,下证n+S. m+n+=Am(
