数学吧 关注:933,236贴子:8,931,442
  • 6回复贴,共1

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

取消只看楼主收藏回复

最近看了关于哥德尔不完备定理的的视频(就是毕导的视频),感觉其中所讲的证明过程充满了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
    收起回复
      2026-01-10 22:52:31
      广告
      不感兴趣
      开通SVIP免广告
      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
            回复
              【【挑战毕导】停机悖论三句话就能证明不完备性定理?-哔哩哔哩】 网页链接
              看了最近另一个不完备定理的视频感觉好像弄懂了。这里用图灵机停机问题的方法来构造“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
              收起回复