轩辕春秋文化论坛 - Powered by Discuz! Board

标题: 证明：所有的自然数都相等 [打印本页]

作者: 天宫公主 时间: 2007-8-15 20:20 标题: 证明：所有的自然数都相等

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

证明：
先证引理：令 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 的一般性，任意两个自然数必然相等。定理证毕。

作者: lazykid 时间: 2007-8-15 20:28

QUOTE:

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

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

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

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

作者: 天宫公主 时间: 2007-8-15 20:32

QUOTE:

原帖由 lazykid 于 2007-8-15 20:28 发表

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

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

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

作者: djgan 时间: 2007-8-15 20:34

结论肯定是错的

仔细看看证明里面哪部分错了

作者: djgan 时间: 2007-8-15 20:46 标题: 回复 #2 lazykid 的帖子

嗯
证明引理的归纳法的第一步，max(1,1)=1

QUOTE:

假设对于所有 k < N，引理皆成立。

这里的N如果等于1，N-1已经不是自然数了。后面的推导步骤的前提已经错了

作者: sincery 时间: 2007-8-15 22:55

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

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

作者: 天宫公主 时间: 2007-8-16 00:36

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

作者: KYOKO 时间: 2007-8-16 01:45

QUOTE:

原帖由 djgan 于 2007-8-15 20:46 发表

嗯
证明引理的归纳法的第一步，max(1,1)=1

这里的N如果等于1，N-1已经不是自然数了。后面的推导步骤的前提已经错了

自然数当然不可能都相等

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

作者: 天宫公主 时间: 2007-8-16 01:50

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

作者: edyswghe 时间: 2007-8-16 02:22

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

作者: 武骧金星 时间: 2008-7-15 11:57

那么换一种证明方法：

先证引理：令 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时，引理也成立？

作者: sky_force 时间: 2008-7-16 16:58

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

怎么来的?

作者: 武骧金星 时间: 2008-7-17 22:41

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

作者: 武骧金星 时间: 2008-7-17 22:45

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

作者: sunnybill 时间: 2008-9-19 15:20

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

欢迎光临轩辕春秋文化论坛 (http://www.xycq.org.cn/forum/)