北京大学：《离散数学》系列课程之一《集合论与图论》第10讲 自然数

第10讲自然数 内容提要 1. Peano系统 2.后继,归纳集,自然数,自然数集 癱3.数学归纳法原理 颦4.传递集 5.自然数的运算 癱6.自然数上的序关系 《集合论与图论》第10讲

《集合论与图论》第10讲 1 第10讲 自然数 内容提要 1. Peano系统 2. 后继, 归纳集, 自然数, 自然数集 3. 数学归纳法原理 4. 传递集 5. 自然数的运算 6. 自然数上的序关系

封闭 封闭:设f是函数, Acdomf,若 X(X∈A→f(×)∈A) 则称A在f下是封闭的( closed) 等价条件:f(A)A 秦例:fN→)N,fx=x+1, A={0,24,6,}在f下不是封闭的 B=234…}在f是封闭的 《集合论与图论》第10讲

《集合论与图论》第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下是封闭的

Peano系统。 婚 Peano系统:,F:M→M (1eEM 2)M在F下封闭 (3)egranF e F(e) Fl(e) F3( (4)F是单射的 (5)(极小性公理) AcMe∈A∧A在F下封闭→A=M 《集合论与图论》第10讲

《集合论与图论》第10讲 3 Peano系统 Peano系统: , F:M→M (1) e∈M (2) M在F下封闭 (3) e∉ranF (4) F是单射的 (5) (极小性公理) A⊆M ∧ e∈A ∧ A在F下封闭 ⇒ A=M e F(e) F2(e) F3(e)

为何如此定义? 《集合论与图论》第10讲

《集合论与图论》第10讲 4 为何如此定义?

如何实现? 婚如何利用集合来构造 Peano系统? 借助于下面两个概念 后继 归纳集 《集合论与图论》第10讲

《集合论与图论》第10讲 5 如何实现? 如何利用集合来构造Peano系统? ----借助于下面两个概念 后继 归纳集

后继( successor) 后继( success:设A是集合, A*= AUAN 称为A的后继 婚特征:AcA+∧A∈A+ 在公理集合论中,无序对公理(ab和并 集公理(U)保证了后继的存在 《集合论与图论》第10讲

《集合论与图论》第10讲 6 后继(successor) 后继(successor): 设A是集合, A+ = A∪{A} 称为A的后继. 特征: A⊆A+ ∧ A∈A+ 在公理集合论中, 无序对公理({a,b})和并 集公理(UA)保证了后继的存在

后继(举例) A=O A+==0}=团 A+={}={{}={{ A++={2{}={{{②( ={{②2 馨A={ab A*=a, bUa=f a, b, A=a,b,a, b 31 《集合论与图论》第10讲

《集合论与图论》第10讲 7 后继(举例) A=∅ A+ = ∅+ = ∅∪{∅} = {∅} A++ = {∅}+ = {∅}∪{{∅}} = {∅,{∅}} A+++ ={∅,{∅}}+ ={∅,{∅}}∪{{∅,{∅}}} = {∅,{∅},{∅,{∅}}} A={a,b} A+ = {a,b}∪{A} = {a,b,A} = {a,b,{a,b}}

归纳集 婚归纳集:若A满足 (1)∈A 2)X(X∈A→X+∈A) 则称A为归纳集 秦A是归纳集◇→A含有必且对后继封闭 在公理集合论中,无穷公理(无穷集存在) 保证了归纳集的存在 《集合论与图论》第10讲

《集合论与图论》第10讲 8 归纳集 归纳集: 若A满足 (1) ∅∈A (2) ∀x( x∈A → x+∈A ) 则称A为归纳集. A是归纳集 ⇔ A含有∅且对后继封闭 在公理集合论中, 无穷公理(无穷集存在) 保证了归纳集的存在

归纳集(举例) A={②,0+,⑦+,+… A={,+,0+ +十十 a.a. a. a 十 1■■ A={8,++号,少 A={,+,,处2,少a,a,a+, 《集合论与图论》第10讲

《集合论与图论》第10讲 9 归纳集(举例) A={∅,∅+,∅++,∅+++,…} A={∅,∅+,∅++,∅+++,…,a,a+,a++,a+++,…} A={∅+,∅++,∅+++}, 少∅ A={∅,∅+,∅++,∅+++,…,a}, 少a+,a++,a+++,…

自然数 自然数:自然数是属于每个归纳集的集合 { +-{{}, +={{∞}{} 《集合论与图论》第10讲

《集合论与图论》第10讲 10 自然数 自然数: 自然数是属于每个归纳集的集合 例: ∅, ∅+ = {∅}, ∅++ ={ ∅,{∅} }, ∅+++ = { ∅,{∅},{∅,{∅}} }, ∅++++ = { ∅,{∅},{∅,{∅}},{∅,{∅},{∅,{∅}}} }, ……