“量词消去定理。 $T {\mathrm{DLO}}$ 有有效的量词消去。其中最主要的一步是:$\Gamma$ 不含 $x$,而所有 $l i,u j,e k$ 都是不同于 $x$ 的参数变量…”
形式陈述
固定一阶语言
这是一项相对于
本页允许逻辑真值常量
定义只断言等价式存在。有效量词消去程序进一步要求一个算法:输入公式后有限步输出这样的无量词式。两者都依赖指定的语言和理论;扩充语言后得到的无量词表达式,不能直接算作原语言中的消去结果。
直觉
存在量词把“选哪一个见证”隐藏起来,只留下“是否有合适见证”。例如
把带参数公式看成一个集合的定义,
例子与边界
从一个存在量词推广到全部公式
证明量词消去时,只需解决
其中每个
每支
参数条件必须一路保留。若某支是
Presburger 算术给出离散情形的另一种实现:整数见证须满足线性上下界和固定模数的余数条件,统一系数后只需在最大下界之后检查一个共同周期。原来的加法、序语言不能无量词地定义偶数;加入同余谓词后才有这里的消去。因此“整数也能消去”同时改变了见证构造方法和所用语言。
量词消去不自动决定全部句子
取语言
即使已有有效消去,也要能决定消去后无量词句的后承,才能决定一般句子的后承。尤其对不完备理论,不能把“检查每个原子句是否被蕴涵”直接当作任意布尔组合的判定器:理论不蕴涵
推论与应用
若
量词消去还给出检查初等嵌入的捷径。设
参考资料
- Philipp Schlicht,Introduction to Mathematical Logic,2022-02-01 讲义,§5.1,Definition 5.1.1、Lemma 5.1.3、Definition 5.1.5:固定语言、基本存在合取的归纳归约及真值常量。
- James Worrell,Logic and Proof — Decidable Theories (I),Hilary 2026,§1,pp.1–2:语义消去与有效程序的区分、由内向外消去。
- Anand Pillay,Lecture Notes — Model Theory (Math 411),2002,§2,Definition 2.2、Remarks 2.3–2.5:参数可定义集合与语言扩充。