数学吧 关注:869,649贴子:8,665,302

关于哥德尔不完备定理的疑问

只看楼主收藏回复

最近看了关于哥德尔不完备定理的的视频(就是毕导的视频),感觉其中所讲的证明过程充满了bug,来数吧看看有没有懂的吧友指教一下。
2l细说


IP属地:安徽来自Android客户端1楼2024-01-04 16:01回复
    首先讲一下视频中说的证明过程,过程中我会提出我的问题:
    1.定义哥德尔数:将一个数因数分解,取各质数的指数得到一个数串,每个指数按事先定义的对应表(类似asc2码)对应一个符号,于是每个哥德尔数对应一个符号串。每个命题首先是一个符号串,所以都对应一个哥德尔数。
    但这里有一个问题(a):虽然每个命题对应一个哥德尔数,但是并非每个字符串都是命题。所以说哥德尔数到命题只是满射不是双射,那么给每个哥德尔数贴上一个真/假的做法是否合理?
    举几个例子:a1“x+++*//-0”;a2“y=0”(前方没有对y进行∃或∀的限制);a3“sub(yy17)”
    这些符号串要么语法不通要么逻辑不通,我个人的看法看法是这些哥德尔数not even wrong. 因此说哥德尔数真假之前先判定其是不是命题是必要的,不通过判定的哥德尔数非真非假,因此不可对其使用排中律。


    青铜拳手
    贴吧拳王争霸赛中累计获取30场胜利,去领取
    活动截止:2100-01-01
    去徽章馆》
    IP属地:安徽来自Android客户端2楼2024-01-04 16:02
    收起回复
      2.定义sub(xyz),指将哥德尔数x中所有等于z的指数换成y。
      定义“可以证”。
      如何定义不重要,可以将其当做最初的符号集的一员。


      青铜拳手
      贴吧拳王争霸赛中累计获取30场胜利,去领取
      活动截止:2100-01-01
      去徽章馆》
      IP属地:安徽来自Android客户端3楼2024-01-04 16:03
      收起回复
        3.记命题“sub(yy17)不可证明“的哥德尔数是n(17是y的哥德尔数)。那么sub(nn17)对应的符号串就是“sub(nn17)不可证明”。如果subnn17是真命题那么其不可证明,如果假,那么假命题当然不可证明,所以又是真命题,矛盾。最终得到其不可证明。
        问题b:这特么就是在罗素悖论里夹带私货,我可以按照这个做法证明任何“命题”!
        首先拆解一下subnn17
        “这个命题不可证明”=“这个命题是假命题或这个命题不可证”。所以它的结构就是罗素悖论或上另一个命题。
        构造“sub(yy17)是假命题或命题a”的哥德尔数是f(a)。
        那么sub(f(a),f(a),17)≡h(a)对应的“命题”就是“这个命题是假命题或命题a”
        如果h(a)为真那么得到“假或a=真”所以a是真。
        如果h(a)是假那么得到“真或a=假”矛盾舍去。
        所以得到任意命题a是真命题。
        选a为这个命题不可证就是哥德尔证明用的哥德尔数;选a为“假”直接得出“假=真”的矛盾;选a为“哥德尔的证明是错误的”直接推翻其证明。
        我个人的看法:sub(yy17)就是个病句,在其基础上构造出来的h(a)更是个病句,应该属于问题a里提到的not even wrong的“不是命题”。


        青铜拳手
        贴吧拳王争霸赛中累计获取30场胜利,去领取
        活动截止:2100-01-01
        去徽章馆》
        IP属地:安徽来自Android客户端4楼2024-01-04 16:03
        收起回复
          问题c:
          就像正则公理之于罗素悖论,如果我在问题ab中的看法正确,那么可能又需要一个xx公理来排除h(a)的一众命题。既如此,为什么不一劳永逸禁用自指,规定所有命题/集合或是什么什么都不能在定义完之前引用自身?1阶哥德尔数可以指向所有不包含哥德尔数这个概念的命题;n阶哥德尔数可以指向包含0~n-1阶哥德尔数的命题,不可以指向包含≥n阶哥德尔数的命题。如此h(a)就会被排除在语法正确的命题之外,从而不对完备性一致性造成影响。能否一致且完备仍然未可知。


          青铜拳手
          贴吧拳王争霸赛中累计获取30场胜利,去领取
          活动截止:2100-01-01
          去徽章馆》
          IP属地:安徽来自Android客户端5楼2024-01-04 16:03
          收起回复
            顶顶


            青铜拳手
            贴吧拳王争霸赛中累计获取30场胜利,去领取
            活动截止:2100-01-01
            去徽章馆》
            IP属地:安徽来自Android客户端6楼2024-01-04 16:50
            回复
              我工科生你问我


              IP属地:江苏来自Android客户端7楼2024-01-04 17:03
              收起回复
                h(a)是啥?


                IP属地:北京来自Android客户端8楼2024-01-04 19:21
                收起回复
                  它的魅力就是本身没有使用自指,却先含义中实际上带有自指,也就是说明自指是本征存在的,无法通过额外定义来去除。


                  IP属地:浙江来自Android客户端9楼2024-01-04 23:31
                  收起回复
                    因为你无法在公理系统内构造类似“sub(y,y,17)对应的命题是假命题”这样的formula,但可以构造“sub(y,y,17)对应的命题是可证明的”这样的formula(当然这一点也并不trivial,一般网上搜到的证明都省略了这一步)。


                    IP属地:北京来自Android客户端10楼2024-01-05 00:59
                    收起回复
                      接9楼回答。
                      “合理不合理”也只是主观判断,不同符号系统可能就含义不一样了。
                      我觉得哥德尔第一不完备性定理,不只是毕导视频里面提到的找到一个“真的却无法证明的命题”。
                      第一不完备性定理应该是说,如果是完备的,总是可以构造出这样的一个反例,从而推翻完备性。完备性是说,如果是真命题,一定可以证明。当然你也可以寻找别的反例。而你举的例子更像是在推翻一致性。
                      另外,哥德尔的思想我觉得主要就是这种“自指”的幽灵会出现在任意这样的符号系统,无法禁止,从而导致那些自指的悖论总是会出现。


                      IP属地:浙江来自Android客户端11楼2024-01-06 23:42
                      收起回复
                        对你的问题c而言,哥德尔第一不完备性定理只对公理集递归可枚举的算术系统成立,像真算数系统(true arithmetic)就是一致且完备的


                        IP属地:北京来自Android客户端12楼2024-01-07 03:09
                        回复
                          由Tarski不可定义定理,“哥德尔数为Q的命题是假命题”这个命题不能在Peano算术系统里表达出来(把“假命题”换为“不可证”是可以表达的),所以“命题为假或不可证”并不是一个Peano算术系统内的命题


                          IP属地:北京来自Android客户端14楼2024-01-07 03:37
                          收起回复
                            最后一个问题就是毕导视频标题里“这些都是真的”其实并不正确,像评论区里说的,毕导视频证的是“如果Peano公理系统一致,那么sub(n,n,17)为真”


                            IP属地:北京来自Android客户端15楼2024-01-07 08:10
                            回复
                              【【挑战毕导】停机悖论三句话就能证明不完备性定理?-哔哩哔哩】 网页链接
                              看了最近另一个不完备定理的视频感觉好像弄懂了。这里用图灵机停机问题的方法来构造“subnn17”,感觉方法比毕导那里像字符串游戏一样好得多,更容易接受。也没法像上面那样构造submm17了。
                              我现在的理解就是可证=图灵机停机,是要优先于真假=图灵机输出的,先停机了才能输出,所以只能构造“这个命题不可证”=“这个图灵机会停机”,不能构造“这个命题是假命题”=“这个图灵机输出假”。
                              ———————————————————
                              不过这个视频有个问题就是那些图灵机的输入都没有标清楚(好像还想为此再水一期视频),比如Q会停机这里就没说输入是啥,搞得我很困扰,想半天才理清楚,在这里记录一下。
                              第一处不可判定性的证明:
                              M(p,q):当p(q)停机是输出T否则输出F
                              M'(p):当M(p,p)停机是输出T时死循环否则停机
                              于是M'(M')出现矛盾
                              第二处不完备性的证明:
                              K(p):命题p可证明时输出T否则(假或不可证明)时输出F
                              Q(p):K(命题“图灵机p(p)会停机”)为真时死循环否则停机
                              于是Q(Q)出现矛盾
                              “p(p)会停机”就是sub(yy17)
                              Q(Q)则是sub(nn17)


                              青铜拳手
                              贴吧拳王争霸赛中累计获取30场胜利,去领取
                              活动截止:2100-01-01
                              去徽章馆》
                              IP属地:安徽来自Android客户端16楼2024-02-06 21:25
                              收起回复