“典范模态模型以最大 K 一致集为世界,并把方框公式决定的义务变成可达关系。典范模型定理由此证明 K 的强完备性和紧致性。”
形式陈述
设
其中左侧使用标准模态满足关系。定理对任意嵌套深度的公式都成立,证明依赖最大一致集的布尔闭包、典范关系的定义以及菱形存在引理。
证明对
- 若
,则对每个 都有 ;归纳假设给出 ,所以 。 - 若
,最大一致性先给出 。K 可证 ,正规性进而给出 ,所以 。存在引理构造 ,使 且 ;归纳假设给出一个不满足 的后继,因此 不满足 。
第二向的关键是构造后继。典范关系规定:凡是
直觉
典范模型把最大一致的公式集当作世界,真值引理把“公式属于集合”与“公式在这个世界为真”联系起来。最大一致性保证布尔联结词的行为,典范关系和存在引理保证模态算子的行为;结构归纳把这条对应推广到任意复杂的公式。
于是,要为一个不可证公式
例子与边界
K 不证明 T 公理
所以典范模型内部已经含有 T 的反例。这里的单点模型只用于借 K 的可靠性确认一致性;最终反例由典范构造统一提供。
若
边界在于证明系统。把 K 换成一致的正规扩展
推论与应用
强完备性给出
因为形式证明只使用有限多个前提,强完备性还导出语义紧致性:若
要从完备性走向可判定性,还需过滤法或其他有限模型构造。典范模型保证反模型存在,过滤法只保留目标公式的有限观察类型;有限模型性质由后一步而非真值引理单独推出。
典范法也为插值与复杂度研究提供起点:插值证明进一步分析前提与结论如何共享语言,复杂度分析则需要能有效构造和搜索反模型的方法。
参考资料
- 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。