南京大学：《计算机问题求解》课程教学资源（PPT课件讲稿）数论基础

计算机问题求解一论题4-4 -数论基础 2021年03月22日

计算机问题求解 – 论题4-4 - 数论基础 2021年03月22日

问题1： 自然数有定义吗？

用集合定义自然数 设a为集合，称U{为a的后继，记为或，或s(a)。 ·设A是集合，若A满足下列条件，称A为归纳集： 口0∈A 口Va(a∈A→+∈A) 如果我们设计这个的集合：N={0,{0,{0,{0,{O, {O},{0,{O}》,…},这个集合可以在归纳集的基础上， 通过集合运算获得 自然数集合N是所有归纳集的交集

用集合定义自然数 ◼ 设a为集合, 称a{a}为a的后继, 记为或a + , 或s(a)。 ◼ 设A是集合，若A满足下列条件，称A为归纳集： ❑ ØA ❑ a(aA→a+A) ◼ 如果我们设计这个的集合：N = { Ø, {Ø}, {Ø, {Ø}}, {Ø, {Ø}, {Ø, {Ø}}}, … }，这个集合可以在归纳集的基础上， 通过集合运算获得 自然数集合N是所有归纳集的交集

用集合定义自然数 ■自然数集合N是所有归纳集的交集。 口N={0,{0,{0,{0,{0,{0},{0,{0}},.} 口N的每一个元素称为一个自然数。 口0记为0,0+记为1,1+记为2,2+记为3，余此类推 ■记号0表示：0 记号1表示0+：0U{0}={0} n 记号2表示1+：{0U{0}={0,{0} ■记号3表示2+：{0，{0U{0,{0}={0,{0},{0,{0}

用集合定义自然数 ◼ 自然数集合N是所有归纳集的交集。 ❑ N = { Ø, {Ø}, {Ø, {Ø}}, {Ø, {Ø}, {Ø, {Ø}}}, … } ❑ N的每一个元素称为一个自然数。 ❑ Ø记为0，0 +记为1，1 +记为2，2 +记为3，余此类推 ◼ 记号0表示：Ø ◼ 记号1表示0 +：Ø{Ø}={Ø} ◼ 记号2表示1 +：{Ø}{{Ø}}={Ø,{Ø}} ◼ 记号3表示2 + : {Ø,{Ø}}{{Ø,{Ø}}}={Ø,{Ø}, {Ø,{Ø}}}

再具体一点 ■3U2=?3∩2=？ ■2∈3？1∈3？ ■1s2?2s5? 自然数上的小于关系如何表达？

再具体一点 ◼ 3∪2=? 3∩2=? ◼ 23? 13? ◼ 12? 25? 自然数上的小于关系如何表达？

自然数上的运算 ·加法（递归定义) o m+0=m ▣】 m+n*=(m+n)* ·乘法（递归定义) 口m*0=0 m*n+=m+m*n 这样的序关系定义，是否准确？ a≤biff]c∈N.a+c=b

自然数上的运算 ◼ 加法（递归定义） ❑ m+0=m ❑ m+n+=(m+n) + ◼ 乘法（递归定义） ❑ m*0=0 ❑ m*n+=m + m*n 这样的序关系定义，是否准确？ ab iff cN. a+c=b

问题2： 关于自然数有“公理”吗？ 皮亚诺公理

皮亚诺公理

关于整数的公理 ■对于加法与乘法封闭： ■加法与乘法满足交换律： ■加法与乘法满足结合律； ■乘法对加法满足分配律； ■加法和乘法各自有单位元素 (0和1) ■方程十x=O有整数解（称为a的逆元素，并可由此定义“减法”） ■如果c≠0，ac=bc-→a=b（消去律) ▣（基于1,2,3…}定义“正整教”和“大于”、“小于”）对任意☑，Q>0 a=0,和a<0三者必有其一，也仅有其一； ■任一正整数的非空集合必含最小元素（良序性）

关于整数的公理 ◼ 对于加法与乘法封闭； ◼ 加法与乘法满足交换律； ◼ 加法与乘法满足结合律； ◼ 乘法对加法满足分配律； ◼ 加法和乘法各自有单位元素（0和1） ◼ 方程a+x=0有整数解（称为a的逆元素，并可由此定义“减法”） ◼ 如果c0，ac=bc → a=b（消去律） ◼ （基于{1,2,3,…}定义“正整数”和“大于”、“小于”）对任意a，a>0, a=0, 和a<0三者必有其一，也仅有其一； ◼ 任一正整数的非空集合必含最小元素（良序性）

良序性与数学归纳法原理 First Principle of Mathematical Induction.Let S(n)be a statement about integers for n E N and suppose S(no)is true for some integer no.If for all integers k with k no S(k)implies that S(k+1)is true,then S(n) is true for all integers n greater than no. Second Principle of Mathematical Induction.Let S(n)be a statement about integers for n EN and suppose S(no)is true for some integer no.If S(no),S(no+1),...,S(k)imply that S(+1)for k no,then the statement S(n)is true for all integers n greater than no. Principle of Well-Ordering.Every nonempty subset of the natural num- bers is well-ordered

良序性与数学归纳法原理

间题3： 你能说说为什么归纳法原 理与良序性质是等价的吗？