关于“哥德尔的不完全性定理”的讨论 - 2022/4/30 - 5/2

CloClo：

啊，我的笑话架子上的一个礼物：

————

L指逻辑学家；A指算术学家。

L：哥德尔证明PA是不完备的。

A突然大笑起来，说：“是的，你可以这么说”。

L：你为什么这样说？

A：哥德尔证明了算术不能被逻辑地理论化。

C：逻辑失败了，并不意味着没有推理可以说明问题。

————

每读一次这个笑话，都让我笑得泪崩。

2Casa：

谁是 "C"？第三方？

juannessy：

我猜 "C"指“结论”。

柳渝：

你的笑话我有些感觉，但很难用语言表达，所以我引用了Mélika Ouelbani的《维特根斯坦的哲学--Repère》一书中的一段话（第155页），我假设维特根斯坦扮演的是第三方（C）的角色。

– La question du fondement logique des mathématiques revient souvent car pour lui, la logique comme les mathématiques sont deux langages différents régis de manière autonome par leurs propres règles. C’est ainsi que pour Wittgenstein, dans les Principia, Russell ne fait que traduire un langage dans un autre : «  Que Russell ait relié les procédures mathématiques à la logique pourrait vouloir dire qu’il les a tout simplement traduits dans un nouveau langage. Mais c’est une source de confusion de croire que c’est une explication, comme si, en venant aux prédicats et aux fonctions prédicatives, nus voyions ce sur quoi les mathématiques portent vraiment » ( (Cours sur les fondements des mathématiques de Wittgenstein, trad. fr. E. Rigal, XXVII, 286)

- 数学的逻辑基础问题经常出现，因为对他来说，逻辑和数学是两种不同的语言，由它们自己的规则自主支配。因此，对维特根斯坦来说，在《数学原理》中，罗素只是把一种语言翻译成另一种语言： “罗素把数学程序与逻辑联系起来，可能意味着他只是把它们翻译成一种新的语言。但是，如果认为这是一种解释，好像有了谓语和谓语函数，我们就看到了数学的真正含义，这就是混乱的根源”（《维特根斯坦的数学基础课程》，译者注）。E. Rigal, XXVII, 286)

关于不可判定的命题（为真但不可证明），我们已经讨论很多了。这里，我想介绍著名的考拉兹猜想（conjecture de Collatz），或许对我们的讨论有启发。

1. 考拉兹猜想

数学中的考拉兹猜想是问，重复两个简单的算术运算是否会最终将所有正整数转化为1。

它涉及整数序列，其中每一项都是由前一项获得的，方法如下：如果前一项是偶数，下一项就是前一项的一半。如果前一届是奇数，下一届就是前一项的3倍加1。猜想是这些序列总是达到1，不管选择什么正整数来开始序列。

定义递归函数fCollatz(n,i)来表示Collatz序列：

fCollatz(n, i) = 1 (n=1)
fCollatz(n, i) = fCollatz(n/2, i+1) (是偶数)
fCollatz(n, i) = fCollatz(3n+1, i+1) (是奇数)

比如 :
fCollatz(5, 1) : 5, 16, 8, 4, 2, 1
fCollatz(27, 1) : 112项，在达到1之前上下波动，最大值为9232。
fCollatz(40, 1) : 40, 20, 10, 5, 16, 8, 4, 2, 1

到目前为止，计算机验证了达近3000亿亿个自然数，每个数最终都达到了1。

大多数研究人员认为这一猜想为真，它吸引了众多的数学家和非数学家，但没有人证明它。20世纪80年代初，匈牙利数学家Paul Erdős说："数学还没有准备好应对这种问题"。

2. 我写了一个C语言的程序，可以用在线编译器来测试运行：

https://www.onlinegdb.com/online_c_compiler

#include

int fCollatz(int n , int i) {
printf(« %d « ,n);
if(n<=1) {
printf("\nThe number takes %d steps to converge to 1 \n",i);
return 1;
}
else if(n%2==0) {
i++;
return fCollatz(n/2,i);
}
else {
i++;
return fCollatz(n*3+1,i);
}
}

int main() {
int n;
scanf("%d",&n);
fCollatz(n,1);
return 0;
}

Reference :
[1]https://fr.wikipedia.org/wiki/Conjecture_de_Syracuse
[2] https://www.technologyreview.com/2021/07/02/1027475/computers-ready-solve-this-notorious-math-problem/

BasicRabbit：

@柳渝，当我在互联网上查找关于你的信息以了解你的科学关注点，我找到了链接(1)，它在与哥德尔不同的意义上谈论判定问题（哥德尔谈论的是可判定性）。我认为我们应该坚持研究悖论这个迷人的问题，我也希望看到我们的讨论集中在说谎者悖论（中心议题），在你文章中提到的阿基里斯和乌龟的悖论，在中国的 "白马非马 "的悖论（PJ在 "真相如何...... "的第一章谈到的悖论）。

对我来说，判定问题（problèmes de décision）不是可判定性问题（problèmes de décidabilité）：在法语中，这两个词之间有明确的区别，可判定性指的是 "权力"，而判定是 "行动"。

在我看来，在判定中，要区分可判定理论中的P与NP问题，最简单的是承认消除量词的理论：代数封闭体、封闭实数体等(2)。 考拉兹猜想和孪生素数猜想一样，都是也许有一天会在佩阿诺算术中得到判定的猜想，这个算术 "我们 "知道（"我们 "不完全是所有人......）是一个不可判定的理论；我不认为在未来很长一段时间内可以从中得出什么概括。

1: https://home.mis.u-picardie.fr/~yli/docs/DdR-4/chap3.pdf

柳渝：

@BasicRabbit 谢谢你的关注!

你说：我认为我们应该坚持研究解决悖论这个迷人的问题。

我完全同意，这正是哥德尔不完全性定理所引发的争论和意义所在！

对于科拉茨猜想这个看似简单的例子，可能有比人们想象的更丰富的内容，匈牙利数学家保罗-厄尔多斯的说法值得注意："数学还没有准备好应对这样的问题"， ...