形式陈述
固定经典一阶语言 、-结构 与参数集 。在语言 中为每个 添加常元 ,并在 中把它解释成 ;记这个带名字结构的完整一阶理论公理库一阶理论First-order theory同一一阶语言中一组句子及其模型类所构成的理论。为 。以下公式的自由变量至多为 ,写 时, 可以是来自 的有限元组。
上的部分类型是一个 -公式集 ,使得对不在 中的新常元 ,句子集
可满足。等价地, 的每个有限子集 都能在 中被同一个元素同时满足:
这称为在 中有限可满足。这里只要求各个有限片段分别有见证,不要求这些见证相同。
称 为完全类型,若它还是一致的上述部分类型,并且对每个 -公式 ,恰好包含 、 中的一个。若 是初等扩张公理库初等嵌入Elementary embedding保持所有一阶公式真值的结构间单射。, 满足 的所有公式,则称 在 中实现 ;没有这样的元素时,称 省略 。元素自身的完全类型记为
同一类型可以由多个元素实现;“完全”指它决定每一个允许的公式,不表示它唯一指定一个元素。
直觉
类型把一个尚未找到的元素写成一份相容的条件清单。参数决定这份清单能点名哪些已有元素:在纯序中,可以要求新元素位于两个指定点之间,也可以要求它同时位于无穷多对上下界之间。有限公式只能使用有限多个参数,而整个类型可以汇集无穷多公式。正是这个差别,使得每次有限检查都有见证,整份清单却可能在当前结构中无人满足。
部分类型允许留下尚未回答的问题;完全类型则对每一个带参数的一阶问题给出答案。补全不能任意填写“真”或“假”:全部答案仍须相容。例如要求 与 时,两条各自可能有见证,合在一起却没有。因此定义中的“有限可满足”检查的是有限组条件的联合满足,而不是逐条检查。
形式陈述中的等价性也体现这一点。若某个有限合取在 中无见证,那么它的存在量化的否定属于 ,会与 冲突。反过来,若每个有限合取在 中有见证,就可用这个见证解释 ;由一阶逻辑紧致性定理公理库一阶逻辑紧致性定理First-order compactness theorem · Compactness theorem一阶理论可满足,当且仅当它的每个有限子理论都可满足。,整个句子集有模型。接下来的初等图表构造将进一步保证:实现类型时,能够完整保留原结构及其参数。
例子与边界
有理数上的一个无理割
取 、。在语言之外选定实数 ,据此分开有理数,并写出条件集
式中的 是命名有理数的参数常元的简写。语言没有乘法,也没有命名 的常元; 只在语言之外帮助选取哪些有理数作为上下界。这不是把 写进纯序语言。
任取 的有限片段。若两侧约束都有,取其中最大下界 与最小上界 ,便有 ;有理数的稠密性给出某个 满足 ,从而同时满足片段中全部条件。若只有一侧界,无端点性提供见证;若片段为空,任意有理数都可以。因此 是 上的部分类型。
例如有限片段
确实来自这个割,因为 ,且两端均为正数。取 ,两项比较分别化为
这些平方与乘法只是我们在语言之外核验所选有理数的计算,不是类型中的公式。
从生成条件到完全类型
本身只列了若干不等式,尚未列出所有公式的答案。令
稠密线性序的量词消去公理库稠密线性序的量词消去Quantifier elimination for dense linear orders · DLO 量词消去在无端点稠密线性序中,以所有下界小于所有上界消去存在量词,并构造避开有限禁点的见证。已经给出 ,因此 是相对于 的完全类型,且包含 。量词消去还说明它是 的唯一完全扩展:每个带有理数参数的公式,都等价于原子比较的布尔组合; 决定 与每个有理数的大小和不等关系, 决定参数彼此的比较。于是所有这些布尔组合的真值都已确定。
这也能直接验证完全类型 的有限可满足性。有限多个公式经消去后只出现有限多个有理数参数。若没有参数,任取一个有理数即可;否则, 不等于其中任何一个,故处在这些参数划分出的某个开区间或外侧射线内。在同一区域选一个有理数 ,它与所有出现的参数具有相同的大小关系,因而同时满足所取公式。这里验证的是完全类型的任意有限片段,比只检查 中的不等式更强。
谁实现,谁省略
省略 ,甚至已经省略 。对任意 ,若 ,则 中的条件 在 时失败;若 ,则其中的 失败。由于 无理,这两种情形覆盖全部有理数。另一方面, 中的 满足 ,也按定义实现 。
这不与初等包含矛盾。一个有限合取可以装进一条存在公式,初等性保证它在 中也有见证;“存在一个元素同时满足整个无限类型”通常不是一条一阶公式。 为整份清单补上了见证,却没有改变任何以有理数为参数的一阶公式的真值。
推论与应用
用初等图表实现任意参数类型
设 是 上的部分类型。在 中命名 的每一个元素,令
这称为 的初等图表。它记录全部带参数句子的真值,包含有量词的句子;只记录原子式及其否定的图表不足以确保初等性。
再添加新常元 ,考虑
任何有限片段只使用 的有限子集 。在 中选取同时满足 的元素来解释 ,而每个名字 仍解释成 ;这样既满足所取图表句子,也满足所取类型条件。紧致性给出整个句子集的一个模型 。
去掉新常元得到 -结构 ,定义 。对任意 -公式 与 ,图表中包含 或其否定,且恰好反映 中的真值,所以
特别地,不同元素的名字满足不等式,故 单射;上式正是初等嵌入条件。把 重命名为 ,即可视为 ,而 实现 。只加入无参数的 不能完成这一步:它没有把原来的每个元素及其参数关系固定在新模型中。
这个证明不要求语言或参数集可数,也不保证见证已经在 内。它还说明任何部分类型都能扩展为完全类型:在得到的初等扩张中,取实现元素的完整类型即可。
参数集大小决定饱和性要求
一个结构是否已经拥有足够的类型见证,要同时说明允许多大的参数集。对无限基数 ,称 为 -饱和,若对每个 、,每个 上的完全一变量类型都在 中实现;等价地,可以要求所有有限元组的类型都实现。
上述无理割使用了可数参数集 ,所以它证明 不是 -饱和,却不能据此否定 -饱和。事实上,纯序结构 是 -饱和的。对有限非空参数集,量词消去把完全一变量类型分成“等于某个参数”“位于相邻参数之间”及“位于两侧射线”几类;相等点本身、稠密性和无端点性分别提供有理数见证。空参数集则只有一个完全一变量类型,任意有理数都实现它。对有限元组,同样只需在这些区域中按指定次序安排有限多个相等类,仍能完成。有限参数与可数参数之间的这一变化,正是本例显示的边界。
参考资料