l*3
发帖数: 2279 | 1 注意你的逻辑, 请明确你的发言.
你这么说的意思就是:
"a是素数 <=> a是大于1的自然数, 且a不被任何小于a的素数整除", 这句话是错的.
是吗?
回复前请仔细阅读引号内的每个字, 注意 "素数" 和 "数" 的区别.
.. |
|
l*3
发帖数: 2279 | 2 我这么问你吧:
你的意思就是:
"a是素数 <=> a是大于1的自然数, 且a不被任何小于a的素数整除" 这句话, 在 "素数
只有有限个" 的前提条件下不对.
是不是? |
|
f**w
发帖数: 377 | 3 帖子太长，不知道讨论到什么程度了。
我也感觉楼主证明有问题：
p_1,p_2,...,p_k 不能整除N, 不能直接推出所有小于N的素数都不能整除N吧？p_k 和N
之间还可以有很多很多素数。
即使事实上p_k和N之间所有的素数的确不能整除N,那也应该给出证明吧。这个证明应该
不容易吧。
个人浅见，如有不对，请见谅。 |
|
l*3
发帖数: 2279 | 4 你以后回答问题可以先清楚直白一些.
我就当你的回答是 "不对", 可以吧?
继续往下:
那么你的意思就是:
"a是素数 <=> a是大于1的自然数, 且a不被任何小于a的素数整除" 成立的前提, 是 "
素数必须有无穷个".
是这个意思吗? |
|
d*****u
发帖数: 17243 | 5 唉，这么说吧
你怎么假设都可以
但是假设了就不能随便说素数就是不能被其他所有素数整除的数
因为你只考虑比p_n小的素数 |
|
l*3
发帖数: 2279 | 6 "a是素数 <=> a是大于1的自然数, 且a不被任何小于a的素数整除"
这句话的正确性, 与假设是什么, 无关.
以上两行能懂不?
-----------
"定义就一个！"
你还加个感叹号, 呵呵. 我请问你, 是素数的定义只有一个, 还是说所有数学对象的定
义都只有一个? |
|
b*********z
发帖数: 26 | 7 如果你要用反正法，就一定要回到原始定义，因为你要证明你的假设是错的。
而你用到的所谓”定义“，都有可能在你的假设下不成立（它本来就是错的嘛）。任何
所谓的其他”定义“的引用，一定要说明它在你的假设下是成立的才能使用。
a是素数 <=> a是大于1的自然数, 且a不被任何小于a的素数整除
在你说”素数就这些“的前提下，显然是不成立的，怎么能当作推论步骤最后去归谬呢
？ |
|
l*3
发帖数: 2279 | 8 我看你是不敢回答.
如果你想让我指出这个和我们讨论的关系, 我告诉你,
A就是 "a是素数 <=> a是大于1的自然数, 且a不被任何小于a的素数整除"
B就是 "素数只有有限个"
------
你要么脑子缺根筋, 要么已经意识到自己的错误, 但是怯懦到不敢面对错误, 懦夫一个
.
结论就是: 你要么是蠢货, 要么是懦夫. |
|
l*3
发帖数: 2279 | 9 我的意思就是, 这是素数的一个等价定义:
"a是素数 <=> a是大于1的自然数, 且a不被任何小于a的素数整除"
只要承认主流数学公理,定义,逻辑都正确, 那这个定义就是对的.
所以你的问题不单单是看错字了, 可能你还有其他的逻辑错误 (或者我不说的这么绝对
, 换一种说法: 你的观点和我的观点矛盾). |
|
|
s******k
发帖数: 168 | 11 如果我把上面post定义的素数改个名字，比如叫“吵架数”。那么上面的证明过程和结
论对如此定义的“吵架数”应该是全对的吧。剩下的问题就是确定这么定义的“吵架数
”和原始定义的“素数”是不是完全定价的。我觉得是的。
当然如果楼主使用原始定义，在加上最后那句“如果性质一为假则N不一定是素数”（
楼主没说这句但是确实也没有必要说）就没有这么多争论了。 |
|
l*3
发帖数: 2279 | 12 我问你, 你看以下这个命题对不对:
命题一: 如果素数只有有限个, 那么 "a是素数 <=> a是大于1的自然数, 且a不被任何
小于a的素数整除"
请直接回答: 对 or 不对. |
|
l*3
发帖数: 2279 | 13 这里的素数, 就是 "通常意义下的" 素数, 如果你真的非常喜欢用这种奇怪的方式来给
素数加一些区分的话. |
|
n******h
发帖数: 97 | 14 看着坑大，忍不住跳一个。
就像前面一个人说的，光是 "a是素数 <=> a是大于1的自然数, 且a不被任何不等于a的
素数整除" 是正确的命题不够把。你需要说明这个正确性并不建立在素数无穷的基础上
。虽然你后来证明了，但是你需要把这样的证明加到1楼里面才能完备。加进去之后看
上去并不比欧几里得的要简洁了。 |
|
t*******r
发帖数: 22634 | 15 我去查了一下，发现素数这个 recursive definition 是正确的。
谢谢。
只是素数这个 recursive definition 确实不如素数非 recursive
definition 用得广泛，外加 recursive definition 的正确性
常常不是那么显而易见，俺半夜三更的就先有罪假定了一把。。。 |
|
t*******r
发帖数: 22634 | 16 我后面看到那个素数的 recursive definition。
如果用素数的 recursive definition，你的比欧几里德的简单，因为
你可以直接上 recursive definition。
但是素数的 非recursive definition 更流行，如果是 非recursive
definition，应该是欧几里德的更简单明了。 |
|
l*3
发帖数: 2279 | 17 嗨呀....你说的高深了, 我无力理解.
我想先讨论讨论这个:
"a是素数 <=> a是大于1的自然数, 且a不被任何不等于a的素数整除" 其实也是可以作
为素数定义的, 没有问题.
你说是不是? |
|
t*******r
发帖数: 22634 | 18 不需要从小到大，刚才用从小到大只是说起来直观而已，并不是严格的说法。
关键的问题是在 recursive definition 里的 definition 的概念。
严格的说法，在这个 recursive definition 里，被定义的 “素数”（定义符号
左边），同时也出现在用来定义“素数”（定义符右边）。不要求从小到大，但要求
存在一个 context，在该 context 里面，定义符号右边的 “素数” 都已经被定义。
而且最终能够 recursive down，否则就是无法 recur。
recursive definition 广泛存在于计算机文法中。。。 |
|
n*****n
发帖数: 1029 | 19 lz说的是“所有的”素数相乘加一。注意是所有的！你那个N是6个素数乘出来的，
不是所有的素数！怎么就这么点事，争了一天一夜了还有人不明白呢？唉。 |
|
d*****n
发帖数: 3033 | 20 发信人: l63 (l63), 信区: WaterWorld
标 题: 关于使用反证法证明 "素数有无穷多个"
发信站: BBS 未名空间站 (Thu May 23 00:34:22 2013, 美东)
假设素数只有有限个, 记为 p_1,p_2,...,p_k
考察 N = p_1*p_2*...*p_k + 1
。。。。。
可知: N是素数
--------------------------------------------------
k=1的时候，就一个质数2，
k=2的时候，就两个质数2和3，
k=3的时候，就三个质数2，3，5，
k=4的时候，就4个质数2 3 5 7
k=5的时候，就5个质数2 3 5 7 11
k=6的时候，就6个质数2 3 5 7 11 13
所有的质数都在这儿了，一个没有漏。
p1=2
p2=3
p3=5
p4=7
p5=11
p6=13
N=p1*p2*p3*p4*p5*p6+1=30031=59*509 不是质数。 |
|
l****e
发帖数: 57 | 21 你到是先证明N是素数啊。你以为随便有限个素数相乘再加个1就是素数了。谁告诉你这
个结论是成立的。 |
|
l*3
发帖数: 2279 | 22 请问我说过 "N是素数" 吗?
我只说过 "在假设下, N是素数", 相当于 "如果假设成立, 那么N是素数".
这么说懂了没? 区别在哪能理解不? |
|
c****n
发帖数: 1646 | 23 文科生，你需要一个独立于你假设之外的公理来证明N是素数.
欧选择了大于1的自然数或是素数，或是合数这个与原假设毫无关系的公理推理得出原
假设矛盾。
你用你的素数定义如何证明N,
说明白点，这个证明需要是从你的定义出发，而不是同时利用用你的假设，
这个是你需要证实或正否的东西，
你用个需要证实或正否的假设得到个结论，反回去说假设错了，算什么反证？ |
|
l*3
发帖数: 2279 | 24 我觉得我声称 "大于a的素数构成了一个集合" 就是naive set theory里的东西, 被罗
素悖论敲扁了.
因为罗素悖论告诉我们, 你不能随便拿一个命题函数P(x) 来定义集合 {x|P(x)}, 这可
能会导致有问题.
你说的 axiomatic set theory 我是不懂的, 于是我不知道怎么用formal language来
写. 不过我根据你的意思, 大致明白了, 你应该就是说, 在你那个更高级更严谨的set
theory下, 我这个 "大于a的素数构成的" 东西确实不是集合, 不符合集合的定义.
如果承认 "大于a的素数构成了一个集合", 那我觉得定义是没问题的. |
|
k******a
发帖数: 2436 | 25 好吧，既然对反证法有这么多误解，我老给尔等解释一下。LOL
我也不是学数学的。但是学过逻辑
证明 "素数有无穷多个"
定义1：质数
n 是质数:= n是大于1的自然数，而且n不能被除了1和n之外的自然数整除
命题a: 素数有无穷多个
命题b: 素数有有限多个, 用p1, p2, p3, ... pk 表示 （其中k是大于等于1的自然数）
denote M = p1*p2*...*pk+1
显然命题b和命题a互为反命题
命题c: M是质数
命题d: b => M不是质数
命题e: M是质数 => b 不成立
命题d和命题e互为逆反命题
第一步，根据定义1证明命题c，细节略去
第二步，证明命题d，细节略去
第三步，证明命题e, 因为第二步已经证明了e的逆反命题，所以e是真命题
第四步，从第一步和第三步的结果（命题c和命题e都成立）得到最终结果：b 不成立
好像不对。让我再改改 |
|
t*******r
发帖数: 22634 | 26 其实就有点像罗素悖论，你俩看同一个自然语言，结果看到是不同的意思。
这不奇怪，我一开始看楼主的，也没看明白。也争了一大通。不过后来发现
那是古典数学语言。码工多用现代数学集合论图论正则语言，或者类似正则
语言写法的东东，导致看古典数学转不过弯来。
楼主的证明其实没错，但是用到了素数的递归定义，实际上我认为是个
trivial 的证明。（由素数递归定义可以容易直接证明无限性，不需要
反证或归谬）。
老实说素数的递归定义并不显而易见，我觉得非码工用自然语言理解，很可能是
似懂非懂。说实话我一开始其实也理解有偏差，导致一开始写的那个 yacc/c
伪码里，把 if and only if 里的 only if 判断条件写错了。其实那个
不是笔误，是理解错误。但写正则语法就是有这个好处，写出来，testcase
跑对，也就基本理解对了。 |
|
d*****u
发帖数: 17243 | 27 你的问题已经好多人重复指出了
就是在推出N是素数的时候，没有遵守素数的定义
你以为你遵守了，因为用的是等价推论
但是你的反证假设实际包含了“质因数最大只能检查到p_n”
这样就破坏了等价性，所以不能再用那个等价推论还判断N是否素数 |
|
d*****u
发帖数: 17243 | 28 你别管我是码工还是什么
你为什么死都听不进去别人的话
你反驳一下说说的有什么不对吧
你不知道那个推论实际已经隐含了素数可以任意大的条件了吗？
那你还证明什么？
如果我给你一个arbitrarily big的自然数
你怎么判断它是不是素数，按照你的假设？
按照素数的原始定义是可以判断的哦
,p |
|
l*3
发帖数: 2279 | 29 你的意思是不是:
我要证明 "a是素数 <=> a是大于1的自然数, 且a不被任何小于a的素数整除" 这个命题
的话, 必须要用到 "素数有无穷多个"?
回答 "是", 或者 "不是". |
|
l*3
发帖数: 2279 | 30 错, 你那不是更准确的说法, 你那是自我意淫出来的说法. 我不认同你意淫出来的说法
.
我就问你, 你是不是认为: 我在没有素数无穷多的前提下, 证明不了 "a是素数 <=> a
是大于1的自然数, 且a不被任何小于a的素数整除" 这个命题?
请回答 是 or 不是.
请简单回答, 不要做其他补充. |
|
l*3
发帖数: 2279 | 31 我觉得你那个 formal system 局限性太大了.
请问你那个 formal system 如何根据以下这个素数的主流定义来判断素数?
"a是素数 <=> a是大于1的自然数, 且不被任何非1和非a的自然数整除"
请问, 你的 formal system 如何扔掉比a大的那一部分? (在主流数学逻辑中, 我们可
以根据 "比a大的自然数不会整除a" 来做这个 "筛选" )
这个定义本身, 在数学上来看应该是 "没有问题" 的, 用了几千年了.... |
|
l*3
发帖数: 2279 | 32 没懂...
所以其实你的意思是 "a是素数 <=> a是大于1的自然数, 且a不被其他非a的素数整除"
这个定义, 违背了你那个system?
我疑惑的就是, 如果上面的定义违背了你那个system, 那你是如何论证清楚 "a是素数
<=> a是大于1的自然数, 且a不被非1和a的任何自然数整除" 这个定义是不违背你那个
system的? |
|
l*3
发帖数: 2279 | 33 什么叫 "已定义的自然数" ? 如果你说 "已定义的自然数" 就是 "递归到a的自然数"
的话.
那你第一个完全可以改成 "已定义的素数" , 也就是 "递归到a-1的自然数子集中的所
有素数"
至于为什么我要说 "只用到a-1", 那很简单, 我是根据定义表述来判断的, 就好像你根
据定义和一些 "预处理" 之后, 根本不在程序中考虑 "比a大的自然数" 这种情况一样.
如果你这么做 (即在程序中只考虑 "递归到a且非a的自然数") 是 "有道理的", 那我不
觉得根据第一个定义, 只考虑 "递归到a-1的自然数子集中的所有素数" 有什么 "没道
理" 的地方.
-----
另备注: 以上说 "递归到a的自然数子集" 是指0, 1, 2,..., a 这些自然数构成的集合
.
在朴素集合论中, a本身是一个自然数的子集, 是指 {0,1,2,...,a-1}, 所以我不知道
上下文中的 "递归到a的自然数子集" 是指 {0,1,2,...,a} 还是指a本身 (也就是{0,1,
2,...,a-1} ), 故特别声明规定一下, 这里的表意是前一种, 即 {0,1,2,...,a}. |
|
l*3
发帖数: 2279 | 34 噢, 是这样, 我的问题就是, 你现在好像在说这么一件事情:
首先我们只考虑 "边界内的自然数", 然后由此我们可以根据朴素定义来判定 "边界内
的素数", 至于 "边界外的" 为什么不用考虑, system内给出的理由是 "有一个整除算
子可以排除边界外的情况".
那我的疑问就是: 既然整除算子能够 "排除边界外的自然数 (因为他们肯定大于a)",
那为什么不能排除 "边界外的素数"? 尤其是你已经默认system有能力知道 "素数都是
自然数" 这一回事. |
|
f*******i
发帖数: 1049 | 35 是的
我们能推出N既是素数又是合数..有问题吗,
我们还能推出N能被某p1,p2,...pn,之外的某素数整除,尽管p1,p2,...,pn是所有的素数 |
|
g******y
发帖数: 126 | 36 我看了一下英文版，原来欧几里德原版是证明如果给定素数集是有限个，那么必然可以
再增加一个素数。
英文wiki 上说经常有错误报道说欧几里德是假设所有的素数集，然后推出自相矛盾的
结果。但是我认为这样证明也是对的啊，只是它不是欧几里德的原版。 |
|
l***o
发帖数: 7937 | 37 发信人: luobo (菠萝), 信区: Mathematics 标 题: Re: 素数有无穷多个, 你会证吗?
给大家奉上几篇欢乐的帖子. 发信站: BBS 未名空间站 (Thu May 23 03:55:43 2013,
美东)
你这个证明有点绕，感觉不够严密。这样证会更好一些 (给你改进了一下)。
假设：素数只有有限个, 记为 p_1, p_2, ..., p_k
考察 N = p_1*p_2*...*p_k + 1
显然 N 不能被所有 p_i 整除。（1）
但根据假设，N必为合数，必为已有素数之积，即必可被某些 p_i 整除。（2）
（1）（2）矛盾，假设不成立。
D |
|
l*3
发帖数: 2279 | 38 不用再来一次反证法. 你为什么要认为再来一次反证法? 麻烦跟帖说明.
-------
我的证明本身确实没有归结到最基本的 "公理" 的情形, 但是没有必要, 我目的只是让
大多数人理解其中的逻辑. (事实证明有一些人还不能理解, 还在纠结于所谓 "p_1,p_2
,...,p_k之外的素数" 一类的问题.)
如果要做一些吹毛求疵的补充的话, 可以是这样的:
"N是素数" 并不显然矛盾于 "素数只有p_1,p_2,...,p_k"
需要说明N不是p_i中的任何一个.
这是因为每个p_i都整除它自身, 但是不整除N, 所以N不是p_i中的任何一个. |
|
m**x
发帖数: 8454 | 39 不带像lz这样煽自己耳光的好不好
发信人: xiongyp (dreamrain), 信区: WaterWorld
标 题: Re: 关于使用反证法证明 "素数有无穷多个"
发信站: BBS 未名空间站 (Thu May 23 17:23:27 2013, 美东)
我承认，但这个等价不明显，需要有完备性的证明。我同样给出的另一个类似的递归定
义，就不完备。对于一个不明显的递归定义，有必要进行说明或者证明。楼主在这个问
题上一笔跳过，是不严谨的。
发信人: xiongyp (dreamrain), 信区: WaterWorld
标 题: Re: 有人认为反证法的证明过程中不能用某些定理,某些等价定义,我问
发信站: BBS 未名空间站 (Fri May 24 09:02:54 2013, 美东)
等价定义可以，但I63对素数的递归定义，与素数本身的定义不等价。
,. |
|
f*******i
发帖数: 1049 | 40 a是素数 <=> a是大于1的自然数, 且a不被任何小于a的素数整除
已经"硬性"规定了1不是素数
你认为这个跟一般的定义不等价? |
|
x*****p
发帖数: 1707 | 41 如果这样的定义也可以成立，我们可以简单的如下定义素数
a是素数当且仅当a是素数集合的一个元素。
那你认为我上面的命题对不对？ |
|
t*******r
发帖数: 22634 | 42 不用争论啦，看我在另一楼里面用 yacc/c伪码 写的正则语法（formal language）
的素数递归定义，这下就可以对罗素笑而不语啦。。。
link 在下面：
http://www.mitbbs.com/article/WaterWorld/2034385_0.html
我把全文 copy & paste 过来：
=============================================
// yacc 段落 (大致):
list_of_primes : list_of_primes one_natural_number
{ if (! if_and_only_if_divisor($2, $1))
弹出语法错误 ; }
| "2"
{ printf("Reduce 成功！"); }
| "1"
... 阅读全帖 |
|
g***s
发帖数: 3811 | 43 你认为"a是大于1的自然数, 且a不被任何小于a的素数整除"是素数的定义？
这只能算素数定义以后可以推导出来的一个定理。 |
|
d*****u
发帖数: 17243 | 44 作为反证的假设，当然可以限定大小
但你在定义素数的时候就不能再用这个限定
否则你的素数到底是啥子？你怎么推出N是素数的？ |
|
x*****p
发帖数: 1707 | 45 大家做个题吧。素数除了2以外全是奇素数，那就可分成两种类型。一种是4k+1型的，
如5, 13, 17, 29；一种是4k+3型的，如3, 7, 11, 19。请证明这两种类型的素数都有
无穷多个。 |
|
x*****p
发帖数: 1707 | 46 文科生吧。
当素数很大的时候，可能只剩下4k+1类型的无穷个素数，不再发现新的4k+3类型的素数
了。 |
|
d******k
发帖数: 4295 | 47 不需要复杂的技巧，和证明素数无穷差不多。
假设4k+3的素数是有限个，
P_1，P_2,...P_K,
N=P_1*P_2*...*P_K
N+1,N+3都是素数，必有一个是4k+3. |
|
m**x
发帖数: 8454 | 48 先证明4k+1无限：
假设4k+1有限，为K个。则N=P_1*P_2*...*P_K+4
N是4k+1类型的素数，因为：
1) N除以4余1
2）4k+3的素数不能整除N因为 1)
3）4k+1的素数不能整除N因为4不能被4k+1整除而P_1*P_2*...*P_K能 |
|
m**x
发帖数: 8454 | 49 再证明4k+3无限：
假设4k+3有限，为K个。如K为奇数则N=P_1*P_2*...*P_K+4，若K为偶数则N=7*P_1*P_2*
...*P_K+4
N是4k+3类型的素数，因为：
1) N除以4余3 (至于为什么，不和文科生讨论）
2）4k+1的素数不能整除N因为 1)
3）4k+3的素数不能整除N因为4不能被4k+3整除而N－4能 |
|
c****n
发帖数: 1646 | 50 我想我明白你的意思，有一类素数可能无限，不能用那个素数有限的假设。
不过我们跳一步说，
这是一个证明素数无限的反证法，你觉得对否？ |
|
