证明：所有的自然数都相等

定理：所有的自然数都相等。

证明：
先证引理：令 x, y 为自然数。如果 max(x, y) = k, 则 x = y。

引理证明（强归纳法）：当 k = 1，命题显然：如果 max(x, y) = 1，则必然有 x=1 和 y=1；由自然数的唯一最小元素公理，必得 x = y。
    假设对于所有 k < N，引理皆成立。如果 max(x, y) = N, 则 max(x-1, y-1) = N-1 。因 N -1 < N，由归纳假设，可知 x-1 = y-1。等式两边加１得 x = y。引理证毕。

对于任何两个自然数 x, y，必然存在一个 k，使得 max (x, y) = k。由引理，可知 x = y。由 x, y 的一般性，任意两个自然数必然相等。定理证毕。

[quote]原帖由 [i]天宫公主[/i] 于 2007-8-15 20:20 发表
定理：所有的自然数都相等。

证明：
先证引理：令 x, y 为自然数。如果 max(x, y) = k, 则 x = y。

引理证明（强归纳法）：当 k = 1，命题显然：如果 max(x, y) = 1，则必然有 x=1 和 y=1；由自然数的唯 ... [/quote]

证明错在没有保证x-1和y-1仍然是自然数

[quote]原帖由 [i]lazykid[/i] 于 2007-8-15 20:28 发表


证明错在没有保证x-1和y-1仍然是自然数 [/quote]
:ohmy:

一眼就看出问题的关键，赞一个！

P.S. 今天有个投行的工作面式，我被问了这个问题，而且限定１分钟之内找出证明错误。虽然还是做出来了，但感觉满有意思的，而且对非专业人士也应该有一定难度吧。

:ph34r:结论肯定是错的
:mellow:仔细看看证明里面哪部分错了:mellow:

回复 #2 lazykid 的帖子

:mellow:嗯
证明引理的归纳法的第一步，max(1,1)=1
[quote]假设对于所有 k < N，引理皆成立。[/quote]
这里的N如果等于1，N-1已经不是自然数了。后面的推导步骤的前提已经错了:mellow:

如果 max(x, y) = k, 则 x = y。

不是学数学的，恕我愚钝，这条是什么理由？:qoo+

这是一个引理，也就是说是需要证明的。这个引理应该这样理解，如果"statement P" 则 "statement Q"，也就是说条件 P 成立，则结论 Q 必然。这里，P = "max(x, y) = k", Q = "x=y"。

[quote]原帖由 [i]djgan[/i] 于 2007-8-15 20:46 发表
:mellow:嗯
证明引理的归纳法的第一步，max(1,1)=1

这里的N如果等于1，N-1已经不是自然数了。后面的推导步骤的前提已经错了:mellow: [/quote]
自然数当然不可能都相等

N=1,N-1不是自然数
那我能否说,对所有大于等于2的自然数都相等???

不可以。因为 k=2 时，引理已经不能成立。

想起我初中见过的一个证明“任意一个三角形都是等腰三角形”，感觉这类假证明都有异曲同工之妙

那么换一种证明方法：

先证引理：令 x, y 为自然数。如果 max(x, y) = k, 则 x = y。

k=1时，引理显然成立。

假设当k=n时，引理成立，则max(x,y)=n时，x=y

则max(x+1,y+1)=n+1

则x+1=y+1，即x=y

因此当k=n+1时，引理也成立？

max(x+1,y+1)=n+1 =>x+1=y+1

怎么来的?

max(x,y)=n =>x=y
和
max(x+1,y+1)=n+1 =>x+1=y+1

是等价的

因为max(x,y)=n 等价于 max(x+1,y+1)=n+1

x=y等价于x+1=y+1

现在已经搞明白自己的“证明”在哪里偷换概念了~

数学归纳法的起点与推导错位。