哥德尔完备性定理

✍ dations ◷ 2025-06-27 13:08:39 #哥德尔完备性定理
哥德尔完备性定理是数理逻辑中重要的定理,在1929年由库尔特·哥德尔首先证明。它的最熟知的形式声称在一阶谓词演算中所有逻辑上有效的公式都是可以证明的。上述词语“可证明的”意味着有着这个公式的形式演绎。这种形式演绎是步骤的有限列表,其中每个步骤要么涉及公理要么通过基本推理规则从前面的步骤获得。给定这样一种演绎,它的每个步骤的正确性可以在算法上检验(比如通过计算机或手工)。如果一个公式在这个公式的语言的所有模型中都为真,它就被称为“逻辑上有效”的。为了形式的陈述哥德尔完备性定理,你必须定义这个上下文中词语“模型”的意义。这是模型论的基本定义。在另一个方向上,哥德尔完备性定理声称一阶谓词演算的推理规则是“完备的”,在不需要额外的推理规则来证明所有逻辑上有效的公式的意义上。完备性的逆命题是“可靠性”。一阶谓词演算的实情是可靠的,就是说,只有逻辑上有效的陈述可以在一阶逻辑中证明,这是可靠性定理断言的。处理在不同的模型中什么为真的数理逻辑分支叫做模型论。研究在特定形式系统中什么为可以形式证明的分支叫做证明论。完备性定理建立了在这两个分支之间的基本联系。给出了在语义和语形之间的连接。但完备性定理不应当被误解为消除了在这两个概念之间的区别;事实上另一个著名的结果哥德尔不完备定理,证实了对“在数学中什么是形式证明可以完成的”有着固有的限制。不完备定理的名声与另一种意义的“完备”有关,参见模型论。更一般版本的哥德尔完备性定理成立。它声称对于任何一阶理论T和在这个理论中的任何句子S,有一个S的自T的形式演绎,当且仅当S被T的所有模型满足。这个更一般的定理被隐含使用,例如,在一个句子被证实可以用群论的公理证明的时候,通过考虑一个任意的群并证实这个句子被这个群所满足。完备性定理是一阶逻辑的中心性质,不在所有逻辑中成立。比如二阶逻辑就没有完备性定理。完备性定理等价于超滤子引理,它是弱形式的选择公理,在不带有选择公理的策梅洛-弗兰克尔集合论中有着等价的可证明性。对定理的最初证明的解释请参见哥德尔完备性定理的最初证明。在现代逻辑课本中,哥德尔完备性定理通常使用Leon Henkin的证明而不是哥德尔最初的证明。

相关

  • 金属金属是一种具有光泽(对可见光强烈反射)、富有延展性、容易导电、传热等性质的物质。金属的上述特质都跟金属晶体内含有自由电子有关。由于金属的电子倾向脱离,因此具有良好的导
  • 离岸流离岸流(英语:Rip current),又称裂流,是一种向外海方向快速移动的强劲海流。这些水流的纵向长度可达61~762米,但宽度一般不会超过9米。离岸流的速度非常快,流速可高达每秒2米以上。离
  • 恐慌症恐慌症,是一种焦虑症,特征为没有预兆地一再恐慌发作。恐慌发作是突然的短期强烈恐惧,可能包含心悸、流汗、手颤抖、呼吸困难、麻痹感、或是有非常严重的事即将发生的感觉。症状
  • 角质软化剂角质软化剂是一种用来降低皮肤角质层的密度,以便医生进行后续的治疗的物质,主要用来消除因为疣或其他病变而引起皮肤上过度生产的表皮细胞。角质软化剂包括诸如水杨酸、煤焦油
  • 基督教化基督教化,也称基督化(英语:Christianization或Christianisation)指个人改宗(英语:Conversion to Christianity)或集体改宗至基督教。从古典时代晚期直到中世纪,人们使用过各种各样不
  • 间皮细胞间皮细胞是指构成间皮的细胞,间皮由一层细胞组成,位在胸膜或腹膜,心包腔内和器官相接之面上。间皮的功用是提供润滑,使器官与器官、器官与胸膜与腹膜间都能得到良好的保护,不会互
  • 镰状细胞镰刀型红血球疾病(英语:Sickle-cell disease, SCD)是一组通常由双亲遗传而来的血液疾病。其中最常见的一种类型,叫做镰状红血球贫血症(Sickle-cell anemia, SCA)。该疾病会引起红
  • 表现主义表现主义(法语:Expressionnisme)是20世纪初流行于法国、德国、奥地利、北欧和俄罗斯的文学和艺术流派。1901年法国画家 朱利安·奥古斯特·埃尔韦为表明自己绘画有别于印象派而
  • 狄俄尼索斯·特拉克斯狄俄尼索斯·特拉克斯(希腊语:Διονύσιος ὁ Θρᾷξ,前170年-前90年),是生活于希腊化时期的一位语法学家,被一些人认为曾经在亚历山大里亚生活过,之后到罗得岛生活。西方
  • 逻辑联结词在形式逻辑中,逻辑运算符或逻辑联结词把语句连接成更复杂的复杂语句。例如,假设有两个逻辑命题,分别是“正在下雨”和“我在屋里”,我们可以将它们组成复杂命题“正在下雨,并且我