Skip to content

定理Theorem

模态逻辑典范模型定理

施工中 · 内容逐步修订

Canonical model theorem for modal logic · Truth lemma for modal K

K 的典范模型中公式在世界为真,当且仅当公式属于对应的最大一致集。

形式陈述 ​

设 Mc=(Wc,Rc,Vc) 是K 的典范模型。典范模型定理,又称真值引理,断言对每个模态公式 A 与每个最大 K-一致集 Γ,

Mc,Γ⊩A⟺A∈Γ,

其中左侧使用标准模态满足关系。定理对任意嵌套深度的公式都成立,证明依赖最大一致集的布尔闭包、典范关系的定义以及菱形存在引理。

证明对 A 的结构归纳。原子情形由 Vc(p) 的定义成立;合取、否定和蕴涵情形由最大一致集的经典闭包性质完成。方框情形分两向:

  • 若 ◻B∈Γ,则对每个 ΓRcΔ 都有 B∈Δ;归纳假设给出 Mc,Δ⊩B,所以 Mc,Γ⊩◻B。
  • 若 ◻B∉Γ,最大一致性先给出 ¬◻B∈Γ。K 可证 B↔¬¬B,正规性进而给出 ◻B↔◻¬¬B,所以 ⋄¬B=¬◻¬¬B∈Γ。存在引理构造 Δ,使 ΓRcΔ 且 ¬B∈Δ;归纳假设给出一个不满足 B 的后继,因此 Γ 不满足 □B。

第二向的关键是构造后继。典范关系规定:凡是 Γ 已承诺必然成立的公式,都要在后继中成立。存在引理进一步证明,这些要求可以与 ¬B 同时放入某个最大一致集,从而得到缺失方框的反例。

直觉

典范模型把最大一致的公式集当作世界,真值引理把“公式属于集合”与“公式在这个世界为真”联系起来。最大一致性保证布尔联结词的行为,典范关系和存在引理保证模态算子的行为;结构归纳把这条对应推广到任意复杂的公式。

于是,要为一个不可证公式 A 找反例,可以先构造含 ¬A 的最大一致集,再把它看作典范世界。构造阶段处理的是公式能否一致地放在一起,真值引理则保证这个集合确实成为使 A 为假的语义模型。

例子与边界

K 不证明 T 公理 □p→p。可先用一个无后继、且 p 为假的单点模型验证公式集 {◻p,¬p} 与 K 相容,再把它扩张为最大一致集 Γ。真值引理立即给出

Mc,Γ⊩◻p,Mc,Γ⊮p,

所以典范模型内部已经含有 T 的反例。这里的单点模型只用于借 K 的可靠性确认一致性;最终反例由典范构造统一提供。

若 Γ⊬KA,则 Γ∪{¬A} 一致:否则一个只用有限多个前提的矛盾证明会给出 Γ⊢KA。把它扩张为最大一致集后,真值引理让全部 Γ 为真而 A 为假。这给出强完备性。若只从“A 不是定理”开始,则取 Γ=∅,得到普通完备性。

边界在于证明系统。把 K 换成一致的正规扩展 L 后,仍可建立 L-最大一致集和真值引理,但若要相对于某个受限框架类完备,还需证明 L 的典范框架属于该类。某些正常逻辑不是典范逻辑;真值引理本身成立,不代表目标关系性质会在典范框架中出现。

推论与应用

强完备性给出

Γ⊩allA⟹Γ⊢KA.

因为形式证明只使用有限多个前提,强完备性还导出语义紧致性:若 Γ 的每个有限子集都有 Kripke 模型,则 Γ 整体有模型。这个结论不提供有限模型,典范世界集通常仍然无限。

要从完备性走向可判定性,还需过滤法或其他有限模型构造。典范模型保证反模型存在,过滤法只保留目标公式的有限观察类型;有限模型性质由后一步而非真值引理单独推出。

典范法也为插值与复杂度研究提供起点:插值证明进一步分析前提与结论如何共享语言,复杂度分析则需要能有效构造和搜索反模型的方法。

参考资料
  • Patrick Blackburn, Maarten de Rijke, and Yde Venema, Modal Logic, Cambridge University Press, 2001, Chapter 4, Truth Lemma and completeness。
  • George E. Hughes and Max J. Cresswell, A New Introduction to Modal Logic, Routledge, 1996, Chapter 6, completeness of K。
  • Alexander Chagrov and Michael Zakharyaschev, Modal Logic, Oxford University Press, 1997, Chapter 5, canonical models and filtration。
关系图谱7 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
类型化关系