是否存在某些问题不能用有限步骤解决？ 第1页

从数理逻辑的角度上略微详细地回答一下。一段“证明”的定义是，一个由命题构成的有限列，其中的每一个命题 ，它要么是公理，要么 与 同时存在于命题列中并且编号比它小。

这个时候，对于这个命题列最后的命题 ，我们称这段证明证明了 .

虽然想举例子，但是具体的细节有点麻烦，真的很难举出个好看的例子……不那么严密地说，考虑以下的公理系统：

(1)对于任意 ，
(2)对于任意 ，
(3)对于任意 ，

这个实际上应该是推理规则……为了简便就当作是公理好了，而且“对于任意……”在这里不当作全称量词，而是当作一堆公理所构成的集合，也就是对于任意逻辑式 都有一条公理是 .

接下来，我们证明爆炸律 ，其中 是一个逻辑式（或者说是命题）.

(1) ；公理(1)，令 ，
(2) ；公理(2)，令 ，
(3) ；(1)+(2)
(4) ；公理(1)，令
(5) ；(3)+(4)
(6) ；公理(1)，令 ，
(7) ；(5)+(6)
(8) ；公理(3)，令 ，
(9) ；(7)+(8)

好了证明完了。这就是证明的运作原理。很好玩吧？上文中出现的 代表“矛盾”，但是定义中其实并没有对何为“矛盾”作出解释，只是通过公理(3)表达出了矛盾所具有的性质，并且现在我们证明了，如果一个公理系统蕴含矛盾，那么你总可以在这个系统内证明任何命题 .

有一个很重要的问题摆在面前，什么叫正确，证明又意味着什么。这个问题是由集合论解决的，集合论考虑为所有逻辑式赋予真值，使得所有公理都是真的，并且考虑到 的含义，我们要求 是真的当且仅当 是真的或者 是假的。之后，如果在任意的真值分布下一个命题的真值都为真，那么我们称它是真命题。在这个定义下，哥德尔完全性定理说明了，一个命题是真的当且仅当它是可证真的。这个只是题外话，但是反过来说，哥德尔完全性定理正是推理规则合理性的表现——能够证明为真的命题当然应当是真命题，而如果一个命题无法被证真，我们也没有理由说它是真命题。

接下来回到题目，存不存在无法用有限步证明的命题？如果了解集合论的不完备性，就可以知道在上述定义中使用的“自然数”是一个集合论中的概念，而这个概念存在一些不确定性。自然数之中除了存在有限的那些元素之外，还存在不完备性所带来的无穷的那一部分——就像暗物质，我们对它们无法触及，既不知道它们存在也不知道它们不存在，但如果我们假定它们存在并进行一些研究，则会发现它们几乎占了自然数的全部。（假定存在暗物质ν，那么ν/2的下取整必然也是暗物质，从而伴随着ν所产生的暗物质可以视为非负有理数域上的线性空间，最后结合良序性，可以将实数正半轴嵌入其中，这也就意味着暗物质如果存在，则至少是不可数无穷多的）

由于不完备性，除了有一些关于自然数本身的命题无法被证明以外，还有一些命题我们“无法证明它们能否被证明”。断言一个命题无法被证真，意味着断言“它的证明不存在”，而如果我们无法证明“一个命题无法被证真”，这也就意味着至少在有些时候，它的证明是存在的。换句话说，当暗物质足够多时，它可以被证真，而当暗物质不够多时它无法被证真。特别地，它无法在现实中被证真（现实中的证明都是真正有限的），但是我们可以在现实中构造一个包含足够多“暗物质”的自然数集，并在其中构造这个命题的证明。不严格地讲，这在某种意义上也可以说是无法用有限步骤证真的真命题。

不完备性的问题还是蛮烧脑的。

如果不是从不完备性的角度上考虑这个问题，就简单的多了，如果我们仅仅是用其它集合来代替自然数集为命题编号，那么我们会发现，在这个集合具有“良序性”时问题不会发生任何改变——因为良序集不可无穷下降，因此只需要从这个命题列中挑选出实际被使用到的命题，它们数量总是有穷的，因此它也可以被有穷长度的证明代替。

相反地，如果不要求这个集合具有良序性，那么这个推理规则就不可靠了，比方说我可以在整数集上证明哥德巴赫猜想。为了精简省略一些具体的推理过程，例如P→P显然是真命题，因此我们把它当作公理。

...
(-2k-1)哥德巴赫猜想→哥德巴赫猜想；公理
(-2k)哥德巴赫猜想；(-2k-1)+(-2k-2)
...
(-4)哥德巴赫猜想；(-5)+(-6)
(-3)哥德巴赫猜想→哥德巴赫猜想；公理
(-2)哥德巴赫猜想；(-3)+(-4)
(-1)哥德巴赫猜想→哥德巴赫猜想；公理
(0)哥德巴赫猜想；(-1)+(-2)

注意到这个证明是满足定义的（除了定义在自然数上这一条以外），每一个命题要么是公理，要么可以由它之前的命题合成得到。但是注意到这一段证明陷入了无尽的循环论证之中：为什么哥德巴赫猜想是对的？因为哥德巴赫猜想是对的。正是自然数的良序性确保了循环论证不会出现，任何一个这样的质问总会抵达问题的根本。