北京大学：离散数学（一）：4

《集合论与图论》第10讲1 第10讲自然数 内容提要 ? 1. Peano系统 ? 2. 后继, 归纳集, 自然数, 自然数集 ? 3. 数学归纳法原理 ? 4. 传递集 ? 5. 自然数的运算 ? 6. 自然数上的序关系 《集合论与图论》第10讲2 封闭 ?封闭: 设f是函数, A?domf, 若 ?x( x∈A → f(x)∈A ) 则称A在f下是封闭的(closed) ?等价条件: f(A)?A ?例: f:N→N, f(x)=x+1, A={0,2,4,6,…}在f下不是封闭的 B={2,3,4,…}在f下是封闭的 《集合论与图论》第10讲3 Peano系统 ?Peano系统: <M,F,e>, F:M→M (1) e∈M (2) M在F下封闭 (3) e?ranF (4) F是单射的 (5) (极小性公理) A?M ∧ e∈A ∧ A在F下封闭? A=M eF(e)F 2 (e) F 3 (e) 《集合论与图论》第10讲4 为何如此定义? 《集合论与图论》第10讲5 如何实现? ?如何利用集合来构造Peano系统? ?----借助于下面两个概念 ?后继 ?归纳集 《集合论与图论》第10讲6 后继(successor) ?后继(successor): 设A是集合, A + = A∪{A} 称为A的后继. ?特征: A?A + ∧ A∈A + ?在公理集合论中, 无序对公理({a,b})和并 集公理(UA)保证了后继的存在 《集合论与图论》第10讲7 后继(举例) ?A=? A + = ? + = ?∪{?} = {?} A ++ = {?} + = {?}∪{{?}} = {?,{?}} A +++ ={?,{?}} + ={?,{?}}∪{{?,{?}}} = {?,{?},{?,{?}}} ?A={a,b} A + = {a,b}∪{A} = {a,b,A} = {a,b,{a,b}} 《集合论与图论》第10讲8 归纳集 ?归纳集: 若A满足 (1) ?∈A (2) ?x( x∈A → x + ∈A ) 则称A为归纳集. ?A是归纳集? A含有?且对后继封闭 ?在公理集合论中, 无穷公理(无穷集存在) 保证了归纳集的存在 《集合论与图论》第10讲9 归纳集(举例) ?A={?,? + ,? ++ ,? +++ ,…} ?A={?,? + ,? ++ ,? +++ ,…,a,a + ,a ++ ,a +++ ,…} ?A={? + ,? ++ ,? +++ }, 少? ?A={?,? + ,? ++ ,? +++ ,…,a}, 少a + ,a ++ ,a +++ ,… 《集合论与图论》第10讲10 自然数 ?自然数: 自然数是属于每个归纳集的集合 ?例: ?, ? + = {?}, ? ++ ={ ?,{?} }, ? +++ = { ?,{?},{?,{?}} }, ? ++++ = { ?,{?},{?,{?}},{?,{?},{?,{?}}} }, …… 《集合论与图论》第10讲11 0,1, 2, …,n,… ?0 = ? ?1 = ? + = {?} = {0} ?2 = ? ++ = {?,{?}} = { 0,1} ?3 = ? +++ ={ 0,1,2 } ?…… ?n = { 0,1,2,…,n-1 } 《集合论与图论》第10讲12 0,1,2,…作为集合 ?2∩3=2=min(2,3), 2∪3=3=max(2,3) ?3-2={2},2-3=0 (-是集合运算) ?Un = U{ 0,1,2,…,n-1 } = n-1 =max(0,1,…,n-1), ?∩n = ∩{ 0,1,2,…,n-1 } = 0 =min(0,1,…,n-1), ?0∈1∈2∈3∈… ∧ 0?1?2?3?… 《集合论与图论》第10讲13 自然数集 ?自然数集N: 设D = { v | v是归纳集}, N=∩D ?D 不是集合, 否则导致悖论! ?在公理集合论中, 由无穷公理保证N 存 在(即保证N 是集合). 《集合论与图论》第10讲14 定理1 ?定理1: N是归纳集. ?证明: N =∩D=∩{ v | v是归纳集} = { x | ?v( v是归纳集→x∈v) }. (1) ?∈N: ?v, v是归纳集??∈v. 《集合论与图论》第10讲15 定理1(续): ?证明(续): (2) ?n( n∈N → n + ∈N ). 利用x∈N ??v( v是归纳集→x∈v)以及 ?v( v是归纳集→?n( n∈v → n + ∈v ) ): ?n, n∈N ??v( v是归纳集→n∈v) ??v( v是归纳集→n + ∈v ) ? n + ∈N. # 《集合论与图论》第10讲16 N = ? ?N是最小的归纳集 ?v( v是归纳集) ? N?v ?N = { 0, 1, 2, 3, … } ?对比: ?自然数是属于每个归纳集的集合 ?自然数集是包含于每个归纳集的归纳集 《集合论与图论》第10讲17 后继函数 ?后继函数σ: σ:N→N, ?n∈N, σ(n)=n + ?例: σ(0) = 0 + = 1, σ(1) = 1 + = 2 = 0 ++ , σ(2) = 2 + = 3 = 1 ++ = 0 +++ , …… # 《集合论与图论》第10讲18 N是否Peano系统? ?定理2: <N,σ,0>是Peano系统. ?证明: (1) ?∈N: 定理1. (2)?n(n∈N→n + ∈N): 定理1. (3) ??ranσ: σ(n)=n + =n∪{n}≠? (4) σ是单射的: 下面定理3 (5) S?N∧?∈S∧?n∈S(n + ∈S) ? S=N : ?∈S∧?n∈S(n + ∈S)?S是归纳集?N?S.# ?称(5)为数学归纳法原理. ?证(5)时没有利用(4), 故可用(5)证(4). 《集合论与图论》第10讲19 数学归纳法原理 ?数学归纳法分两个步骤: 1. 令S = { n | n∈N ∧ P(n) } 2. 证明 (1) ?∈S; (2) ?n( n∈S → n + ∈S ). 《集合论与图论》第10讲20 定理3 ?定理3: 任何自然数的元素均为它的子集. ?证明: 1.令S={ n | n∈N ∧?x(x∈n→x?n) }. 2. (1) ?∈S: ?∈N ∧?x(x∈?→x??) (2) 设n∈S, 要证n + ∈S, 即要证 n + ∈N ∧?x( x∈n + → x?n + ). ?x, 设x∈n + =n∪{n}, 分两种情况: (a) x=n ? x=n?n + , (n + =n∪{n}) (b) x∈n ? x?n?n + , (归纳假设) ∴ S=N. # 《集合论与图论》第10讲21 定理4 ?定理4: ?m,n∈N, m + ∈n + ? m∈n. ?证明: (?) 定理3 (?) 归纳法. # 《集合论与图论》第10讲22 定理5: ?定理5: 任何自然数都不是自己的元素. ?证明: S={ n | n∈N ∧ n?n }. # 《集合论与图论》第10讲23 定理6 ?定理6: ?属于除0外的任何自然数. ?证明: S={0}∪S’, S’={ n | n∈N ∧ n≠0 ∧?∈n }. (1) ?∈S, (2) n∈S ? n + ∈S. # 《集合论与图论》第10讲24 定理7(三歧性) ?定理7(三歧性): ?m,n∈N, 下面三式成立 且仅成立一式. m∈n, m=n, n∈m ?证明: (1). 至多成立一式: 定理5. (2). 至少成立一式: S={n|n∈N∧?m(m∈N→m∈n∨m=n∨n∈m)}. # 《集合论与图论》第10讲25 传递集 ?传递集: A为传递集? ?x?y( x∈y ∧ y∈A → x∈A) ?定理10: A为传递集 ? UA?A ??x( x∈A → x?A ) ? A ? P(A). # ?自然数及自然数集都是传递集. 《集合论与图论》第10讲26 自然数的运算 ?加法:+:N×N→N, +(<2,3>)=5, 2+3=5 ?乘法: ?:N×N→N, ?(<2,3>)=6, 2?3=6 《集合论与图论》第10讲27 N上的递归定理 ?N上的递归定理: 设A为集合, a∈A, F:A→A, 则存在唯一函数h:N→A, 使得 h(0)=a, 且?n∈N, h(n + )=F(h(n)). # F(a)=F(h(0))=h(1)=h(0 + ) a=h(0) F 2 (a)=F(F(a))=F(h(1))=h(2)=h(1 + ) F 3 (a)=F(F 2 (a))=F(h(2))=h(3)=h(2 + ) F 4 (a)=F(F 3 (a))=F(h(3))=h(4) =h(3 + ) 1 0 2 3 4 《集合论与图论》第10讲28 一元函数加法: “加m” ?“加m”: m固定, A m :N→N, A m (0)=m, A m (n + )=(A m (n)) + . ?例: A 2 (3)=A 2 (2 + )=A 2 (2) + =A 2 (1 + ) + =A 2 (1) ++ =A 2 (0 + ) ++ =A 2 (0) +++ =2 +++ =3 ++ =4 + =5. ? m m m A σσσσ σ == 4434421 οΛοο 个 《集合论与图论》第10讲29 二元函数加法 ?加法: +:N×N→N, m+n=A m (n) ?例: 3+3 = A 3 (3) = A 3 (2 + )= A 3 (2) + = A 3 (1 + ) + = A 3 (1) ++ = A 3 (0 + ) ++ = A 3 (0) +++ = 3 +++ = 4 ++ =5 + = 6. # ?递归定理保证如此定义是有意义的 《集合论与图论》第10讲30 加法单位元0 ??m∈N, 0+m=m, m+0=m ?证明: (1) 0+m = A 0 (m) (+定义) = σ 0 (m) (A m 定义) = I N (m), (R 0 定义) = m (2) m+0=A m (0)=m. # 《集合论与图论》第10讲31 ?m,n∈N, m+n + = (m+n) + ??m,n∈N, m+n + = (m+n) + ?证明: m+n + = A m (n + ) (+定义) = (A m (n)) + (A m 定义) = (m+n) + (+定义) . # 《集合论与图论》第10讲32 ?m,n∈N, m + +n = (m+n) + ?证明: (数学归纳法). 对任意m∈N, 令S = { n | n∈N ∧ m + +n=(m+n) + }. (1) 0∈S: m + +0=m + =(m+0) + . (2) ?n(n∈S→n + ∈S): 设n∈S,下证n + ∈S. m + +n + = A m+ (n + ) = A m+ (n) + (+与A m 定义) =(m + +n) + = (m+n) ++ (归纳假设) =(m+n + ) + (定理: m+n + = (m+n) + ) ∴ S = N. # 《集合论与图论》第10讲33 加法交换律 ?加法交换律: ?m,n∈N, m+n=n+m. ?证明: 对任意m∈N, 令S={ n | n∈N ∧ m+n=n+m }. (1) 0∈S: m+0=m=0+m. (0是加法单位元) (2) ?n(n∈S→n + ∈S): 设n∈S,下证n + ∈S. m+n + =A m (n + )=A m (n) + =(m+n) + =(n+m) + (归纳假设) = n + +m (性质: m + +n = (m+n) + ) ∴ S = N. # 《集合论与图论》第10讲34 加法性质 ?加法单位元0: 0+n=n+0=n ?交换律: n+m = m+n ?结合律: (m+n)+k = m+(n+k) 《集合论与图论》第10讲35 乘法 ?“乘m”: m固定, M m :N→N, M m (0) = 0, M m (n + ) = M m (n)+m. ?例: M 2 (3)=M 2 (2 + )=M 2 (2)+2=M 2 (1 + )+2 = M 2 (1)+2+2=M 2 (0)+2+2+2=0+2+2+2=6. ?乘法: ?:N×N→N, m?n=M m (n) ?例: 3?2=M 3 (2)=M 3 (1)+3=M 3 (0)+3+3 =0+3+3=3 +++ =6. # 《集合论与图论》第10讲36 乘法性质 ?1是乘法单位元: 1?n=n?1=n ?交换律: n?m = m?n ?结合律: (m?n)?k = m?(n?k) ?分配律: m?(n+k) = (m?n)+(m?k) 《集合论与图论》第10讲37 自然数的序 ? “属于等于”: m∈n ? m∈n ∨ m=n ? “小于等于”: m≤n ? m<n ∨ m=n ? m<n ? m∈n ? m>n ? n∈m ? m≤n ? m∈n ? m≥n ? n∈m 《集合论与图论》第10讲38 总结 ? 1. Peano系统 ? 2. 后继, 归纳集, 自然数, 自然数集 ? 3. 数学归纳法原理 ? 4. 传递集 ? 5. 自然数的运算 ? 6. 自然数上的序关系 《集合论与图论》第10讲39 作业讲解(#1) ? p25, 习题一,3, 7, 10, 16 ?3. TF,FT,TT,FT,TFF ?7. ?10. TT,FT,TF ?16. { {3},{4},3,4 }, ?, {?,{?}} A B C A BC A B C A B C 《集合论与图论》第10讲40 作业讲解(#2) ?p27,习题一,11,13,14,20 ?11. A-B=A?A∩B=? 证一: 利用A=(A-B)∪(A∩B), (A-B)∩(A∩B)=? 证二: A?~B ??x(x∈A→x?B) ???x(x∈A∧x∈B) ? A∩B=? AB 《集合论与图论》第10讲41 作业讲解(#2) ?13. (1) 证一: 直接证. 证二: 利用X∩Y=Y? X?Y (2) A∩C=? (利用文氏图) ?14. 利用X=(X-Y)∪(X∩Y) ?20. 类似14题. 《集合论与图论》第10讲42 习题讲解(#3) ? p80, 习题二, 6, 7,11,12 ?6.(1)(2) 7.(1)(2) ----------- OK 《集合论与图论》第10讲43 习题讲解(#3) ?11.(1) R 1 ∪R 2 ={<a,b>,<b,d>,<c,c>,<c,d>, <a,c>,<d,b>,<d,d>} R 1 ∩R 2 ={<b,d>} R 1 ⊕R 2 ={<a,b>, <c,c>,<c,d>, <a,c>,<d,b>,<d,d>} (2) domR 1 ={a,b,c} domR 2 ={a,b,d} dom(R 1 ∪R 2 )={a,b,c,d} 《集合论与图论》第10讲44 习题讲解(#3) ?11. (3) ranR 1 ={b,c,d} ranR 2 ={b,c,d} ranR 1 ∩ranR 2 ={b,c,d} (4) R 1 ↑A={<a,b>,<c,c>,<c,d>} R 1 ↑{c}={<c,c>,<c,d>} (R 1 ∪R 2 )↑A={<a,b>,<c,c>,<c,d>,<a,c>} R 2 ↑A={<a,c>} 《集合论与图论》第10讲45 习题讲解(#3) ?11.(5) R 1 [A]={b,c,d} R 2 [A]={c} (R 1 ∩R 2 )[A]=? (6) R 1 ○R 2 ={<a,c>,<a,d>,<d,d>} R 2 ○R 1 ={<a,d>,<b,b>,<b,d>,<c,d>,<c,b>} R 1 ○R 1 ={<a,d>,<c,c>,<c,d>}. # 《集合论与图论》第10讲46 习题讲解(#3) ? p80, 习题二, 12. (1) R -1 ={<{?,{?}},?>,<?,{?}>,<?,?>} (2) R○R={<{?},{?,{?}}>, <{?},?>, <?,{?,{?}}>,<?,?>} (3) R↑[?]=? R↑{?}={<?,{?,{?}}>,<?,?>} R↑{{?}}={<{?},?>} R↑{?,{?}}={<?,{?,{?}}>,<?,?>, <{?},?>} 《集合论与图论》第10讲47 习题讲解(#3) ?12. (4) R[?]=? R[{?}]={ {?,{?}}, ? } R[{{?}}]={?} R[{?,{?}}]={ {?,{?}}, ? } (5) domR={ ?, {?} } ranR={ {?,{?}}, ? } fldR= { {?,{?}}, {?}, ? } # 《集合论与图论》第10讲48 习题讲解(#4) ?p81, 习题二, 15, 16, 17, 22, 23 ?15. R: 反自反, 反对称, 传递 S: 对称T: 对称 (严格说, 应按|A|分情形讨论) ?16. |R|=11, 对称 |S|=5, 反对称 《集合论与图论》第10讲49 习题讲解(#4) ?17. 自反, 对称 0 1 2 3 ? ? ? ? ? ? ? ? ? ? ? ? 1001 0111 0111 1111 《集合论与图论》第10讲50 习题讲解(#4) ?22.利用R传递? R○R?R R自反? I A ?R. 反例: ?, (R○R=R?R传递, 反例只能破坏自反性) ?23. 利用(R○S) -1 = S -1 ○R -1 , R对称? R -1 =R. 《集合论与图论》第10讲51 作业(#8) ? p125, 习题四, 3, 7 ?今天交作业#5,#6,#7