书名:皇帝新脑(第一推动丛书·综合系列)
作者:罗杰·彭罗斯
译者:许明贤,吴忠超
出版社:湖南科学技术出版社
出版时间:2018-01-01
ISBN:9787535794444
第4章 真理、证明和洞察
- 数学的希尔伯特计划
- 形式数学系统
- 哥德尔定理
- 数学洞察
- 柏拉图主义或直觉主义
- 从图灵结果到类哥德尔定理
- 递归可列集
- 芒德布罗集是递归的吗
- 一些非递归数学的例子
- 芒德布罗集像非递归数学吗
- 复杂性理论
- 物理事物中的复杂性和可计算性
六、从图灵结果到类哥德尔定理
1、形式数学系统的主要性质
- 一个形式数学系统的主要性质是,决定某一给定的符号串是否构成该系统中给定的数学论断的证明应是可计算的事体。
表达数学证明的全部要点毕竟在于对于什么是有效推理、什么是无效推理不必做进一步的裁决。
以完全机械的和原先预定的办法来检查一个想象的证明是否确实是一个证明应是可能的;也就是说必须有检查证明的算法。
另一方面,为提出的数学陈述去找证明(或证伪),我们并不要求它必须是算法的事。
七、递归可列集
一个可用某种算法以这种方式产生的集合,譬如P,叫作递归可数的。
递归可数集的简单例子是偶数{0,2,4,6,8, …},
和平方的集合{0,1,4,9,16, …},
以及素数的集合{2,3,5,7,11, …}。集合的补集——也就是不在该集中的自然数的集为递归可数的。
哥德尔定理的结论:形式论证只是得到数学真理的部分手段。
存在一定的真的算术命题的简单的族,却的的确确能形成递归可数集。
例如,不难看出,具有如下形式的真的命题∃w, x…, z[f(w, x…, z)=0]组成递归可数集(我把它记作A)
然而,人们发现集合A不是递归的。
这样,我们并没有任何算法手段,哪怕在原则上决定“费马大定理”的真假!