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

计算机问题求解一论题4-1 -数论基础 2017年03月20日

计算机问题求解 – 论题4-1 - 数论基础 2017年03月20日

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

Number is the basis of modern mathematics.But what is number? What does it mean to say that多+多=1，.}=，and(-1)(-l)=1? We learn in school the mechanics of handling fractions and negative numbers,but for a real understanding of the number system we must go back to simpler elements.While the Greeks chose the geometrical con- cepts of point and line as the basis of their mathematics,it has become the modern guiding principle that all mathematical statements should be reducible ultiinately to statements about the nalural numbers, 1,2,3,...."God created the natural numbers;everything else is man's handiwork."In these words Leopold Kronecker (1823-1891) pointed out the safe ground on which the structure of mathematics can be built. Fortunately,the mathematician as such need not be concerned with the philosophical nature of the transition from collections of concrete objects to the abstract number concept.We shall therefore accept the natural numbers as given,togcther with the two fundamental opera- tions,addition and multiplication,by which they may be combined. from What is Mathematics,by Courant and Robbins

from What is Mathematics, by Courant and Robbins

用集合定义自然数 设a为集合，称U{d为a的后继，记为或at,或s(a)。 ·设A是集合，若A满足下列条件，称A为归纳集： 口0∈A 口Va(a∈A→叶∈A) ■自然数集合N是所有归纳集的交集。 口因此：N={0,{0},{0,{0},{0,{0),{0,{0},…} 口N的每一个元素称为一个自然数。 口0记为0,0+记为1,1+记为2,2+记为3，余此类推

用集合定义自然数 ◼ 设a为集合, 称a{a}为a的后继, 记为或a + , 或s(a)。 ◼ 设A是集合，若A满足下列条件，称A为归纳集： ❑ ØA ❑ a(aA→a+A) ◼ 自然数集合N是所有归纳集的交集。 ❑ 因此：N = { Ø, {Ø}, {Ø, {Ø}}, {Ø, {Ø}, {Ø, {Ø}}}, … } ❑ N的每一个元素称为一个自然数。 ❑ Ø记为0，0 +记为1，1 +记为2，2 +记为3，余此类推

再具体一点 ■记号0表示：0 ■记号1表示0+：0U0}={0} ■记号2表示1+：{0狄U{0}={0,{0} ■记号3表示2*：{0，{0}U{0,{0}={0,{0,{0,{0} ■3U2=? 3∩2=？ ■2∈3？ 1∈3？ ■1c2?2c5? 自然数上的小于关系如何表达？

再具体一点 ◼ 记号0表示：Ø ◼ 记号1表示0 +： Ø{Ø}={Ø} ◼ 记号2表示1 +： {Ø}{{Ø}}={Ø,{Ø}} ◼ 记号3表示2 + : {Ø,{Ø}}{{Ø,{Ø}}}={Ø,{Ø}, {Ø,{Ø}}} ◼ 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 序关系 aa≤biff3ceN.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： 你能说说为什么归纳法原 理与良序性质是等价的吗？