Tips无名氏No.9999999

2099-01-01 00:00:01 ID: Tips

( ｣ﾟДﾟ)｣＜X岛微信公众号已开放：【矛盾苇草】 官方微博：【X岛揭示板】

无标题无名氏No.63267984

2024-07-30(二)13:28:06 ID: 22b93o1 (PO主)

>哥德尔数与哥德尔编码（上）
接下来我们会讲到哥德尔不完备定理的证明。虽然这是二十世纪最重要的定理之一，但它的证明并不难，只需要从另一个角度（语言的角度！）来看待数学。

假设一数学系统符号集，其中每一个符号都代表数学论证中所要用到的符号，例如0，=，+，*，（，）x，y等。虽然数字是无限的，但这个符号集是有限的，因为其中含有一个符号s叫做“后继”，定义为对于数字n，ns=n+1。0s=1，0ss=2，用诸如此类的方式可以构建所有自然数。

这个数学符号集中符号构成的语言就是数学命题。例如语言“0=0s”的含义就是“提出一个命题，该命题为：0是等于1的”。自然，这个命题是假命题。

可判定性问题就是想要知道是否所有的命题都可以被证明是真命题或者假命题。而哥德尔接下来就要证明有些命题不能被证明成真命题或者假命题。

###假设这个涵盖所有论证所需的数学符号集里的每个符号都被给予了一个不一样的独特正整数编号。例如符号“=”的编号可以是5，符号“0”的编号可以是6，符号“s”的编号可以是7。编号到底是什么无所谓，只要不同的符号不一样即可。为了简便，我们定义一个函数g(x)，输入符号x，输出该符号的哥德尔数。例如g(s)=7。

###给定一个数学命题，即数学符号集中符号e的排列组合l=e1e2e3...，其中en指第n位的符号 例如语言0=0s中e1为符号0，e2为符号=，e3为符号0，e4位符号s。

###有了函数g，我们可以为这个数学命题定义一个独特的哥德尔编码，定义给予编码的函数为G。G(l)=2^g(e1) * 3^g(e2) * 5^g(e3) * 7^g(e4) * ...。即，给定l，G每次按顺序从左向右依次拿取l的i个元素，并向结果乘第i个素数的g(ei)次方。

###例如，G(0=0s)=2^g(0) * 3^g(=) * 5^g(0) * 7^g(s)=2^6 * 3^5 * 5•6 * 7^7=200,120,949,000,000。通过这种方法，对于所有数学命题l，我们都能找到对应的独特哥德尔编码G(l)。用同样的方式，对于所有符号集，我们都可以设计这样的函数G，使得符号集中的每一个语言都可以有与该符号集中其他语言不同的哥德尔编码。

###我们也可以反过来从哥德尔编码倒推出其对应的语言。200,120,949,000,000除以2可以整除6次，结果为3,126,889,828,125，所以对应语言中第一位的哥德尔数是6，对应符号0。3,126,889,828,125除以3可以整除5次，结果是12,867,859,375，所以对于语言中第二位的哥德尔数是5，对应符号=...

###G是一个单射函数：对于所有语言，G都可以推导出自然数。如果一个语言符号集中有无限多个符号，那么这个语言的G函数是满射的（这也代表它是双射的），对于所有自然数，都有一个对应的语言l使得G(l)等于这个自然数，自然数和语言一一对应。

###如果你看不懂这一段，没有关系，你只要知道语言与数字本质相同。这是哥德尔给我们的启发。

无标题无名氏No.63783174

2024-09-15(日)19:23:37 ID: 22b93o1 (PO主)

https://y.music.163.com/m/song/666448

>哥德尔数与哥德尔编码（下）

接下来就是哥德尔不完备定理证明的重头戏：

定义函数sub(a, b, c)，这个函数输入的a代表一个数学命题l所对应的哥德尔编码G(l)，b代表一个符号b，c代表某符号x的哥德尔数，c=g(x)。这个函数的效果是输出一个新的命题，这个新的命题是将旧命题l中所有符号x替换成符号b所产生的。

例如，假设根据某哥德尔数排列方案，g(x)=10。sub(G(x=y), 0, 10)的输出是G(0=y)，我们将命题中哥德尔数为10的符号“x”替换成了符号“0”。

这个函数是可以通过因式分解很简单实现的。如何实现呢？各位可以自己思考一下如何输出更改后的哥德尔编码。

有了这个函数，我们定义一个数学命题：“哥德尔编码为sub(x, x, 10)的数学命题无法被证明”。也就是说，给定一哥德尔编码为某未知数x的数学命题，将这个数学命题中哥德尔数为10的符号（即“x”）替换为符号“x”（实际上，在此时，这毫无作用）后得到的命题无法被证明。

毫无疑问，在一个成熟的数学系统中，上面所述的数学命题是可以被表示成哥德尔编码的。我们不需要知道这个哥德尔编码是多少，只需要知道其存在就可以了，我们假设这个哥德尔编码是n。

根据n，我们再定义另外一个（也是最后一个）数学命题：“哥德尔编码为sub(n, n, 10)的数学命题无法被证明”。定义这个数学命题的哥德尔编码为m。

sub(n, n, 10)将哥德尔编码n对应的命题中所有出现的，哥德尔数为10的符号x变成了n。

哥德尔编码n对应的命题为“哥德尔编码为sub(x, x, 10)的数学命题无法被证明”。将这个命题中的x替换为n之后，输出的对应命题为“哥德尔编码为sub(n, n, 10)的数学命题无法被证明”。我们仅仅是把x这个符号替换成了n。

“哥德尔编码为sub(n, n, 10)的数学命题无法被证明”这个命题是不是有点眼熟？没错，这个命题是我们定义为哥德尔编码为m的命题。也就是说，m=sub(n, n, 10)，同时，m对应的命题等价于“哥德尔编码为m的命题无法被证明”。

请问，m可以被证明？如果m可以被证明，那么我们证明了m无法被证明，显然，如果m可以被证明，那么一个悖论产生了：我们证明了一个东西无法被证明。

所以，m无法被证明。然而，m存在，因为我们可以构建出m。也就是说，在任何成熟到足以产生m对应命题的数学系统中，存在无法被证明的命题。

这就是哥德尔不完备定理：所有可以构建m，换言之，足够成熟的数学系统都存在无法被证明的命题。换言之，不是所有的数学命题都能被证明。换言之，数学家证明某些命题的行为可能是无用功。

In other words, please be true. 这句期望虽然很美好，却无法实现。

无标题无名氏No.63783434

2024-09-15(日)19:51:03 ID: 22b93o1 (PO主)

>>No.63670885
没有，搜了一下应该是类似的证明