跳至内容
Topos Uranos
中文 (中国)

语言：总结与挑战

摘要

本课结束专讲命题逻辑语言的单元。它重建一条演绎之链：从有效性与真的区分以及对悖论的分析出发，通往公式的唯一可读性以及陈述句和论证的形式化，并在每一环指出用到哪条原理、它在哪一课中证明；把已取得的成果放回课程计划中衡量，并解释为什么已经建成的语言会提出下一单元的问题，下一单元专讲演绎。它在结业测评中重复入门测评的各项技能，最后给出六道挑战题，难度高于各课的习题，要求综合运用其中几课的工具。

学习目标

  1. 重建本单元各结果的逻辑顺序，指出每个结果所依据的原理以及证明它的那一课。
  2. 解释封闭原理、分解为词、权重引理与唯一可读性如何环环相扣，以及为什么递归定义和形式化之间的比较都依赖于唯一可读性。
  3. 区分本单元证明了的东西、作为假设接受的东西（二值原则、真理模式、归纳原理以及或非的读法）和留给后续单元的东西。
  4. 解决综合运用对角线引理、符号串计数、对公式的归纳、权重论证和缩写展开的问题。

本单元的收获

本单元的目标是：从一个只有两个符号的字母表出发，构造一种每个公式都只有一种读法的语言，严格证明这种语言的性质，并在它与我们用来推理的语言之间架起一座桥。这个目标已经达成，只有少数几处保留，每一处都在相应的地方声明过：二值原则和真理模式，第一课不是把它们当作真理，而是当作明确的假设来接受，以考察二者同时成立时会发生什么；自然数上的归纳原理，它作为皮亚诺第五公理被接受；或非的非形式读法，它是约定的，语义单元将把它变成定义；以及集合论中不可或缺的部分（属于、包含与并集），在需要的地方讲授。有了这些保留，走过的路可以读成由四段组成的一条演绎之链。

推理与谈论语言

关于什么是数理逻辑的一课确定了课程的对象：不是陈述句的真，那属于各门科学，而是真的传递。一个论证是有效的，当且仅当它的形式不容许任何前提为真而结论为假的实例；由这个定义推出了有效性所保证的唯一的东西：如果前提为真，那么结论为真；由此，一个结论为假的有效论证必有某个前提为假，而一个形式无效，恰好当它有反例。同一个结果把对悖论的分析变成了一种程序：如果一个以矛盾告终的推理的各步都有效，那么某个假设为假，解决悖论就是找出是哪一个。说谎者就是这样处理的：对一个宣称自身为假的语句，二值原则与真理模式不能同时成立；贝里悖论和形容词“他谓的”也是这样处理的。从理发师中提炼出一个一般的引理，即对角线引理，它证明这样的理发师不存在，并证明不加限制的概括原则是矛盾的。最后，这一课确立了对象语言与元语言的区分，以及一个表达式的使用与提及的区分，这一区分支配着此后的一切：本单元关于公式的结果不是公式，而是元定理。

圆圈与圆盘的语言

关于命题逻辑的语言的一课引入了集合与符号串，数出了每种长度的符号串（共有 2n2^{n} 个长为 nn 的，以及 2N+1−22^{N + 1} - 2 个长为 11 到 NN 的），并构造了基础语言：变元 vn=∘n∙v_n = \sigO^{n}\sigI，以及唯一的一条规则，它由两个公式 φ\varphi 和 ψ\psi 构成 ∙φψ\sigI\varphi\psi。“除此之外没有别的公式”这一条，通过把公式定义为属于所有封闭集的符号串而变得精确；由这个定义推出了封闭原理，并用它证明了：每个公式要么是变元，要么是 ∙φψ\sigI\varphi\psi，而不会两者都是；每个公式都以圆盘结尾；每个公式含有奇数个圆盘。变元和单独的圆盘构成前缀码，这一观察给出了分解为词的唯一性，并随之给出了权重的概念。这一课还构造了此后使用的元语言：元变元、写作 (φ↓ψ)(\varphi \downarrow \psi) 的或非，以及六个正式缩写，每个都只用前面的缩写定义一次，因此每个缩写表达式都只指称一个符号串。

归纳法与唯一可读性

关于自然数上与公式上的归纳法的一课为前一课用“依此类推”完成的计数提供了依据，由简单归纳推出了强归纳，并把强归纳用于长度，得到了结构归纳，而结构归纳原来就是移到公式上的自然数归纳。借助这一工具，它证明了权重引理：每个公式的权重为 +1+1，每个非空的真按词前缀的权重至多为 00。由此依次推出：没有一个公式是另一个公式的真前缀，以及每个复合公式只有唯一的读法。唯一可读性是本单元其余部分所系的一环：它为判定程序提供依据，这个程序在关于语言的一课中被描述为偿还一笔债务；它也使递归定义（长度、变元与联结圆盘的个数、子公式、深度和代入）合法，没有它，这些定义就可能给同一个公式指派两个不同的值。

从汉语到公式

关于自然语言的形式化的一课架起了通往我们所说的语言的桥。它确立了字母的约定，把 pp、qq、rr、ss、tt 作为五个确定变元的名字，要求每个形式化都声明自己的词典，并仅从约定的或非读法推出了每个缩写的读法。借助唯一可读性，它证明了同样一些联结词的两种不同组合是不同的公式；借助长度的递归定义，它算出了展开后的缩写有多长，这提供了区分形式化的一个快速判据。它表明，实质蕴涵只在前件为真而后件为假时为假，而且这是唯一只依赖于各部分之真、又能使数学中的条件定理为真的读法；它指出了形式化所丢失的东西（量词、时间、因果、模态），最后把完整的论证形式化为一个前提集 Γ\Gamma 和一个结论。

下图把四段汇成一条链。中间一列的每个节点是一个定义或一个结果，按逻辑顺序编号，并用弧线连到其证明所用到的前面的环节；四周浮动的是支柱，即这条链一再求助的原理，每个支柱用实线连到依靠它的环节，用虚线连到确立它的环节，不加证明而接受的支柱则画成圆环。点击一个支柱，会突出显示所有用到它的环节；每个环节都链接到证明它的那一课。请注意，判定程序虽然在关于语言的一课中讲述，但它的逻辑位置在唯一可读性之后，因为它依靠唯一可读性。

链的支柱

  • A二值原则. 每个命题或真或假，且不同时既真又假；为假等价于不为真。在分析悖论时作为明确的假设接受。 本单元中不加证明而采用。
  • B真理模式. 一个语句为真，当且仅当它所说的情况成立。作为明确的假设接受；塔斯基的解决方案保留了它，但只用于不含自身真谓词的语言中的语句。 本单元中不加证明而采用。
  • C归纳原理. 如果一个性质对 11 成立，并且每当它对一个自然数 kk 成立时，它也对 k+1k + 1 成立，那么它对所有自然数成立。这是皮亚诺第五公理，予以接受。 本单元中不加证明而采用。
  • D对角线引理. 在一个对象的汇集中，没有任何对象 bb 能使 R(b,x)⇔¬R(x,x)R(b, x) \Leftrightarrow \neg R(x, x) 对该汇集中的每个 xx 都成立。 确立于: 3. 对角线引理.
  • E封闭原理. 一个性质，如果所有变元都具有它，并且它能从 φ\varphi 和 ψ\psi 传到 ∙φψ\sigI\varphi\psi，那么所有公式都具有它。 确立于: 5. 封闭原理.
  • F结构归纳. 对公式复杂度的归纳，由对长度的强归纳推出：它的基始是变元，它的归纳步骤是唯一的形成规则。 确立于: 9. 结构归纳.
  • G唯一可读性. 若 ∙φψ=∙φ′ψ′\sigI\varphi\psi = \sigI\varphi'\psi'，且四个符号串都是公式，则 φ=φ′\varphi = \varphi' 且 ψ=ψ′\psi = \psi'。 确立于: 11. 唯一可读性.
  • H或非的读法. 公式 (φ↓ψ)(\varphi \downarrow \psi) 恰在 φ\varphi 和 ψ\psi 都为假时为真。这是唯一约定的读法；其余读法都由它推出，语义单元将使它精确化。 本单元中不加证明而采用。

  1. 第 1 段 推理与谈论语言

    • 区分有效性与真，并用反例驳倒无效的形式。
    • 认出自然语言的歧义，并把一个陈述句的不同读法分开。
    • 区分对象语言与元语言，以及一个表达式的使用与提及。
    • 分析悖论：分离出它的假设，并判定应当放弃哪一个。

    1. 有效性保证什么. 如果一个论证有效且它的所有前提为真，那么它的结论为真；由此，一个结论为假的有效论证必有某个前提为假，而一个形式无效，恰好当它有反例。

      证明于: 什么是数理逻辑.

    2. 说谎者悖论. 对语句 mm，即“语句 mm 是假的”，应用二值原则和真理模式，得到 V(m)⇔¬V(m)V(m) \Leftrightarrow \neg V(m)；对于含有 mm 的语言，两个假设必须放弃一个，而塔斯基的出路是：任何语言都不含自身的真谓词，因此 mm 无法构成。

      使用: 1. 有效性保证什么. 依据: A (二值原则), B (真理模式). 证明于: 什么是数理逻辑.

    3. 对角线引理. 若 RR 是汇集 DD 的对象之间的关系，使得每个 R(x,y)R(x, y) 或真或假，则没有任何 bb（属于 DD）能使 R(b,x)⇔¬R(x,x)R(b, x) \Leftrightarrow \neg R(x, x) 对每个 xx（属于 DD）都成立。

      依据: A (二值原则). 证明于: 什么是数理逻辑.

    4. 理发师与罗素. 村里不存在这样一个男人，他恰好给村里所有不给自己刮脸的男人刮脸；不加限制的概括原则是矛盾的，因为它断言集合 Z={x:x∉x}Z = \{ x : x \notin x \} 存在。

      依据: D (对角线引理). 证明于: 什么是数理逻辑.

  2. 第 2 段 圆圈与圆盘的语言

    • 描述符号串的集合，并对每种长度的符号串计数。
    • 把公式定义为最小的封闭集，并由此推出封闭原理。
    • 证明所有公式都具有的性质，并用它们排除符号串。
    • 把符号串分解为词，并把缩写展开到基础语言。

    1. 封闭原理. 公式的集合 F\mathcal{F} 是这样的最小的符号串集合：它含有变元 vn=∘n∙v_n = \sigO^{n}\sigI，并且含有 φ\varphi 和 ψ\psi 时也含有 ∙φψ\sigI\varphi\psi；因此，一个性质，如果变元都具有它，并且它能从 φ\varphi 和 ψ\psi 传到 ∙φψ\sigI\varphi\psi，那么所有公式都具有它。

      证明于: 命题逻辑的语言.

    2. 公式的形式. 每个公式要么是变元，要么是 ∙φψ\sigI\varphi\psi，其中 φ\varphi 和 ψ\psi 是公式，而不会两者都是：每个变元以 ∘\sigO 开头，每个复合公式以 ∙\sigI 开头。

      依据: E (封闭原理). 证明于: 命题逻辑的语言.

    3. 末尾符号与圆盘个数. 每个公式都以圆盘结尾，并含有奇数个圆盘；由此，两个公式的连接和符号串 ∙φ\sigI\varphi 都不是公式。

      依据: E (封闭原理). 证明于: 命题逻辑的语言.

    4. 分解为词. 每个以圆盘结尾的符号串都唯一地分解为词，即分解为变元 ∘n∙\sigO^{n}\sigI 和单独的圆盘，因为每个词都以它唯一的圆盘结尾，并且没有一个词是另一个词的真前缀。

      证明于: 命题逻辑的语言.

  3. 第 3 段 归纳法与唯一可读性

    • 用简单归纳和强归纳进行证明，并由它们推出对公式复杂度的归纳。
    • 证明权重引理，并推出唯一可读性。
    • 判定一个符号串是否为公式，并重建它的构成过程。
    • 用递归定义公式上的函数，并证明它们之间的关系。

    1. 结构归纳. 强归纳由简单归纳推出；把它用于长度，就得到对复杂度的归纳原理：如果变元具有一个性质，并且该性质能从 φ\varphi 和 ψ\psi 传到 ∙φψ\sigI\varphi\psi，那么所有公式都具有它。

      使用: 6. 公式的形式. 依据: C (归纳原理). 证明于: 自然数上与公式上的归纳法.

    2. 权重引理. 如果每个变元出现的权重为 +1+1，每个联结圆盘的权重为 −1-1，那么每个公式的权重为 +1+1，公式的每个非空的真按词前缀的权重至多为 00；特别地，每个公式中变元出现的次数比联结圆盘多一个。

      使用: 8. 分解为词. 依据: F (结构归纳). 证明于: 自然数上与公式上的归纳法.

    3. 唯一可读性. 没有一个公式是另一个公式的真前缀；由此，若 ∙φψ=∙φ′ψ′\sigI\varphi\psi = \sigI\varphi'\psi'，且四个符号串都是公式，则 φ=φ′\varphi = \varphi' 且 ψ=ψ′\psi = \psi'。

      使用: 7. 末尾符号与圆盘个数, 8. 分解为词, 10. 权重引理. 证明于: 自然数上与公式上的归纳法.

    4. 判定程序. 以 ∘\sigO 结尾的符号串不是公式；若以 ∙\sigI 结尾，就把它分解为词。若第一个词是变元，则该符号串是公式当且仅当这个变元是它唯一的词。若第一个词是圆盘，就在它之后记录债务：若债务始终不变为零，该符号串就不是公式；若变为零，φ\varphi 与 ψ\psi 之间的切分点就在债务第一次变为零的地方，每一部分都用同样的方法检查，而空符号串不是公式。

      使用: 6. 公式的形式, 7. 末尾符号与圆盘个数, 8. 分解为词. 依据: G (唯一可读性). 证明于: 命题逻辑的语言.

    5. 递归定义. 给定每个变元的一个值，以及一条规则，它计算 ∙φψ\sigI\varphi\psi 的值，所依据的是 φ\varphi、ψ\psi 以及它们的值，那么恰好存在一个遵守它们的公式上的函数；长度、子公式、深度和代入都是这样定义的，而代入总是产生公式。

      使用: 6. 公式的形式. 依据: C (归纳原理), F (结构归纳), G (唯一可读性). 证明于: 自然数上与公式上的归纳法.

  4. 第 4 段 从汉语到公式

    • 用明确的词典形式化陈述句，并确定每个联结词的辖域。
    • 展开缩写，以判定两个形式化是否为同一个公式。
    • 区分实质蕴涵与语言中的“如果……那么”，并指出形式化所丢失的东西。
    • 把完整的论证形式化为一个前提集和一个结论。

    1. 缩写的长度. 若 L(φ)=aL(\varphi) = a 且 L(ψ)=bL(\psi) = b，则 ¬φ\neg\varphi、(φ∨ψ)(\varphi \vee \psi)、(φ→ψ)(\varphi \rightarrow \psi) 和 (φ∧ψ)(\varphi \wedge \psi) 的符号串长度分别为 2a+12a + 1、2a+2b+32a + 2b + 3、4a+2b+54a + 2b + 5 和 8a+8b+158a + 8b + 15；长度不同的两个形式化是不同的公式。

      使用: 13. 递归定义. 证明于: 自然语言的形式化.

    2. 辖域与不同的公式. 组合 ((p∧q)∨r)((p \wedge q) \vee r) 与 (p∧(q∨r))(p \wedge (q \vee r)) 是不同的符号串：如果它们相同，两次应用唯一可读性就会迫使变元 rr 等于复合公式 (p∧q)(p \wedge q)。

      使用: 6. 公式的形式. 依据: G (唯一可读性). 证明于: 自然语言的形式化.

    3. 实质蕴涵. 蕴涵 (φ→ψ)(\varphi \rightarrow \psi) 是 (¬φ∨ψ)(\neg\varphi \vee \psi) 的缩写，只在 φ\varphi 为真而 ψ\psi 为假时为假；这是唯一只依赖于各部分之真、又能使数学中的条件定理为真的读法。

      依据: H (或非的读法). 证明于: 自然语言的形式化.

走向演绎. 这条链停在语言已经建成、论证已被形式化为一个前提集和一个结论之处。还有待判定的是：一个公式何时由其他公式得出；先在下一单元中按规则操作符号，然后再考虑它们的真。