教学单元-4.2自然数性质

内容提要2传递集传递集的等价条件递归定理、递归定义加m函数、加法乘m函数、乘法加法和乘法的运算律自然数集上的序3传递集A为传递集A的元素的元素还是A的元素

xy(

xy

yA

xA)4定理4.10•(1)

A为传递集

(2)

A

A

(3)

x(

xA

xA)

(4)

A

P(A)5例4.2下列集合是否传递集?A={,{},{{}}}B={0,1,2}C={{a}}D=<0,1>6例4.2：是否传递集?A={,{},{{}}}

是B={0,1,2}

是C={{a}}

不是D=<0,1>={{0},{0,1}}

不是自然数自然数集??7定理4.11定理4.11A为传递集

P(A)为传递证明

A为集传递集

A

P(A)

P(A)

P(A)

P(A)是传递集(

定理4.10

)(

A=P(A)

)(

定理4.10

)#8定理4.12定理4.12A为传递集

(A+)=A证明

(A+)=

(A{A})=(A)({A})=

(A)A=

A(A+定义)(

(AB)=(A)(B))(因为AA

)

#9定理4.13定理4.13

每个自然数都是传递集证明令S={n

|

nN

n是传递集}(1)0S:

显然.

nN,

nS

n+S:

nS

n是传递集

(n+)=nn+(定理4.12)

n+是传递集(定理4.10)

n+S.

S=N

#10定理4.14定理4.14

自然数集N是传递集证明

令S

=

{

n

|

nN

nN

}(1)0S:

显然.

nN,

nS

n+S:

nN

n{n}=n+NnS(

{n}N

)

n+S.

S=N,

即n(nNnN).由定理4.10,

N是传递集.

#11自然数集上的二元运算加法:+:NNN,+(<2,3>)=5,

2+3=5乘法::

NNN,(<2,3>)=6,

23=612N上的递归定理设A为集合,

aA,

F:AA,

则存在唯一函数h:NA,

使得h(0)=a,

且nN,h(n+)=F(h(n)).

#当F是单射时a=h(0)F(a)=F(h(0))=h(1)=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+)1301234递归定义aA,

F:AAh(0)=a

h(n+1)=F(h(n)),

nN递归定理说:

h:

NA

存在唯一14一元函数“加m”m固定, Am:

NN,Am(0)=m,Am(n+)=(Am(n))+.m15A

mm个一元函数“加m”举例Am(n)=m+n

Am(0)=mAm(n+)=Am(n)+=(m+n)+=(m+n)+1=m+(n+1)=m+n+A2(3)=A2(2+)=A2(2)+=A2(1+)+=A2(1)++

=A2(0+)++

=A2(0)+++=2+++

=3++

=4+

=5.1617二元函数加法•

+

:

NNN,

m+n=Am(n)3+3

=

A3(3)=

A3(2+)

=

A3(2)+=A3(1+)+

=A3(1)++=

A3(0+)++

=

A3(0)+++=3+++

=4++

=5+

=618定理4.15定理4.15

m,nN,m+0=

mm+n+

=

(m+n)+证明

m+0=Am(0)=m.m+n+

=

Am(n+)(+定义)=(Am(n))+=(m+n)+(Am定义)(+定义)

.

#19定理m,nN,0+n

=

nm++n

=

(m+n)+用归纳法证明20加法交换律定理m,nN,m+n=n+m.证明

mN,

令S={n|nNm+n=n+m}0S: m+0

=

m

=

0+m.nS

n+S:m+n+=Am(n+)=Am(n)+=(m+n)+=(n+m)+=

n++m(归纳假设)(前一个定理)

S

=

N.

#21加法性质总结单位元:交换律:结合律:消去律:0+n

=

n+0

=

nn+m

=

m+n(m+n)+k

=

m+(n+k)m+k=n+k

m=n用归纳法证明乘法“乘m”:

m固定,

Mm:NN,Mm(0)

=

0,Mm(n+)

=

Mm(n)+m.乘法::NNN,mn=Mm(n)2223乘法性质总结单位元: 1n

=

n1

=

n交换律: nm

=

mn结合律: (mn)k

=

m(nk)消去律:

mk=nk

m=n(k0)分配律: m(n+k)

=

(mn)+(mk)用归纳法证明24自然数的序“属于等于”: mn

mn

m=n(线序,

良序)m<n

mnm>n