形式陈述
固定经典一阶语言 L 、L -结构 M 与参数集 A ⊆ M 。在语言 L ( A ) 中为每个 a ∈ A 添加常元 c a ,并在 M 中把它解释成 a ;记这个带名字结构的完整一阶理论 理路 一阶理论 First-order theory 同一一阶语言中一组句子及其模型类所构成的理论。 为 Th ( M , A ) 。以下公式的自由变量至多为 x ,写 φ ( x , a ) 时,a 可以是来自 A 的有限元组。
A 上的部分类型 是一个 L ( A ) -公式集 p ( x ) ,使得对不在 L ( A ) 中的新常元 c ,句子集
Th ( M , A ) ∪ { φ ( c ) : φ ( x ) ∈ p } 可满足。等价地,p 的每个有限子集 p 0 都能在 M 中被同一个元素同时满足 :
对 每 个 有 限 对每个有限 p 0 ⊆ p , M ⊨ ∃ x ⋀ φ ∈ p 0 φ ( x ) . 这称为在 M 中有限可满足。这里只要求各个有限片段分别有见证,不要求这些见证相同。
称 p 为完全类型 ,若它还是一致的上述部分类型,并且对每个 L ( A ) -公式 φ ( x ) ,恰好包含 φ ( x ) 、¬ φ ( x ) 中的一个。若 M ≼ N 是初等扩张 理路 初等嵌入 Elementary embedding 保持所有一阶公式真值的结构间单射。 ,b ∈ N 满足 p 的所有公式,则称 b 在 N 中实现 p ;没有这样的元素时,称 N 省略 p 。元素自身的完全类型记为
tp N ( b / A ) = { φ ( x ) ∈ L ( A ) : N ⊨ φ ( b ) } . 同一类型可以由多个元素实现;“完全”指它决定每一个允许的公式,不表示它唯一指定一个元素。
直觉
类型把一个尚未找到的元素写成一份相容的条件清单。参数决定这份清单能点名哪些已有元素:在纯序中,可以要求新元素位于两个指定点之间,也可以要求它同时位于无穷多对上下界之间。有限公式只能使用有限多个参数,而整个类型可以汇集无穷多公式。正是这个差别,使得每次有限检查都有见证,整份清单却可能在当前结构中无人满足。
部分类型允许留下尚未回答的问题;完全类型则对每一个带参数的一阶问题给出答案。补全不能任意填写“真”或“假”:全部答案仍须相容。例如要求 a < x 与 x < a 时,两条各自可能有见证,合在一起却没有。因此定义中的“有限可满足”检查的是有限组条件的联合满足,而不是逐条检查。
形式陈述中的等价性也体现这一点。若某个有限合取在 M 中无见证,那么它的存在量化的否定属于 Th ( M , A ) ,会与 p ( c ) 冲突。反过来,若每个有限合取在 M 中有见证,就可用这个见证解释 c ;由一阶逻辑紧致性定理 理路 一阶逻辑紧致性定理 First-order compactness theorem · Compactness theorem 一阶理论可满足,当且仅当它的每个有限子理论都可满足。 ,整个句子集有模型。接下来的初等图表构造将进一步保证:实现类型时,能够完整保留原结构及其参数。
例子与边界
有理数上的一个无理割
取 L = { < } 、M = A = Q 。在语言之外选定实数 α = 2 ,据此分开有理数,并写出条件集
Σ ( x ) = { q < x : q ∈ Q , q < α } ∪ { x < r : r ∈ Q , α < r } . 式中的 q , r 是命名有理数的参数常元的简写。语言没有乘法,也没有命名 2 的常元;α 只在语言之外帮助选取哪些有理数作为上下界。这不是把 x 2 = 2 写进纯序语言。
任取 Σ 的有限片段。若两侧约束都有,取其中最大下界 l 与最小上界 u ,便有 l < α < u ;有理数的稠密性给出某个 b ∈ Q 满足 l < b < u ,从而同时满足片段中全部条件。若只有一侧界,无端点性提供见证;若片段为空,任意有理数都可以。因此 Σ 是 Q 上的部分类型。
例如有限片段
7 5 < x < 10 7 确实来自这个割,因为 49 / 25 < 2 < 100 / 49 ,且两端均为正数。取 x = 17 / 12 ,两项比较分别化为
7 ⋅ 12 = 84 < 85 = 17 ⋅ 5 , 17 ⋅ 7 = 119 < 120 = 10 ⋅ 12. 这些平方与乘法只是我们在语言之外核验所选有理数的计算,不是类型中的公式。
从生成条件到完全类型
Σ 本身只列了若干不等式,尚未列出所有公式的答案。令
p ( x ) = tp ( R , < ) ( α / Q ) . 稠密线性序的量词消去 理路 稠密线性序的量词消去 Quantifier elimination for dense linear orders · DLO 量词消去 在无端点稠密线性序中,以所有下界小于所有上界消去存在量词,并构造避开有限禁点的见证。 已经给出 ( Q , < ) ≼ ( R , < ) ,因此 p 是相对于 Q 的完全类型,且包含 Σ 。量词消去还说明它是 Σ 的唯一完全扩展 :每个带有理数参数的公式,都等价于原子比较的布尔组合;Σ 决定 x 与每个有理数的大小和不等关系,Th ( Q , Q ) 决定参数彼此的比较。于是所有这些布尔组合的真值都已确定。
这也能直接验证完全类型 p 的有限可满足性。有限多个公式经消去后只出现有限多个有理数参数。若没有参数,任取一个有理数即可;否则,α 不等于其中任何一个,故处在这些参数划分出的某个开区间或外侧射线内。在同一区域选一个有理数 b ,它与所有出现的参数具有相同的大小关系,因而同时满足所取公式。这里验证的是完全类型的任意有限片段,比只检查 Σ 中的不等式更强。
谁实现,谁省略
( Q , < ) 省略 p ,甚至已经省略 Σ 。对任意 b ∈ Q ,若 b < α ,则 Σ 中的条件 b < x 在 x = b 时失败;若 α < b ,则其中的 x < b 失败。由于 α 无理,这两种情形覆盖全部有理数。另一方面,( R , < ) 中的 α 满足 Σ ,也按定义实现 p 。
这不与初等包含矛盾。一个有限合取可以装进一条存在公式,初等性保证它在 Q 中也有见证;“存在一个元素同时满足整个无限类型”通常不是一条一阶公式。R 为整份清单补上了见证,却没有改变任何以有理数为参数的一阶公式的真值。
推论与应用
用初等图表实现任意参数类型
设 p ( x ) 是 A ⊆ M 上的部分类型。在 L ( M ) 中命名 M 的每一个元素,令
是 句 子 , 且 E ( M ) = { θ : θ 是 L ( M ) -句子,且 ( M , ( m ) m ∈ M ) ⊨ θ } . 这称为 M 的初等图表 。它记录全部带参数句子的真值,包含有量词的句子;只记录原子式及其否定的图表不足以确保初等性。
再添加新常元 c ,考虑
E ( M ) ∪ { φ ( c ) : φ ( x ) ∈ p } . 任何有限片段只使用 p 的有限子集 p 0 。在 M 中选取同时满足 p 0 的元素来解释 c ,而每个名字 c m 仍解释成 m ;这样既满足所取图表句子,也满足所取类型条件。紧致性给出整个句子集的一个模型 N ∗ 。
去掉新常元得到 L -结构 N ,定义 j ( m ) = c m N ∗ 。对任意 L -公式 θ ( x ¯ ) 与 m ¯ ∈ M ,图表中包含 θ ( c ¯ m ) 或其否定,且恰好反映 M 中的真值,所以
M ⊨ θ ( m ¯ ) ⟺ N ⊨ θ ( j ( m ¯ ) ) . 特别地,不同元素的名字满足不等式,故 j 单射;上式正是初等嵌入条件。把 j ( M ) 重命名为 M ,即可视为 M ≼ N ,而 c N ∗ 实现 p 。只加入无参数的 Th ( M ) 不能完成这一步:它没有把原来的每个元素及其参数关系固定在新模型中。
这个证明不要求语言或参数集可数,也不保证见证已经在 M 内。它还说明任何部分类型都能扩展为完全类型:在得到的初等扩张中,取实现元素的完整类型即可。
参数集大小决定饱和性要求
一个结构是否已经拥有足够的类型见证,要同时说明允许多大的参数集。对无限基数 κ ,称 M 为 κ -饱和,若对每个 A ⊆ M 、| A | < κ ,每个 A 上的完全一变量类型都在 M 中实现;等价地,可以要求所有有限元组的类型都实现。
一变量与有限元组的等价可对元组长度作归纳 理路 数学归纳法 Mathematical induction · Weak induction 由基例和从 n 到 n+1 的归纳步推出性质对全部自然数成立。 。给定完全类型 p ( x 1 , … , x r ) ,先实现只含 x 1 的限制为 a 1 。把余下条件中的 x 1 替成参数 a 1 ,得到 A ∪ { a 1 } 上的一致完全类型:每个有限条件组的存在闭包已属于前述一变量限制,故在 a 1 处有见证。继续处理其余变量即可。因为 κ 无限,向 | A | < κ 的集合中加有限多个参数仍小于 κ ,归纳没有越过饱和性允许的范围。
上述无理割使用了可数 理路 可数集 Countable set · At most countable 能单射进自然数集的集合;等价地,它有限或能按自然数无重复枚举。 参数集 A = Q ,所以它证明 ( Q , < ) 不是 ℵ 1 -饱和,却不能据此否定 ω -饱和。事实上,纯序结构 ( Q , < ) 是 ω -饱和的。对有限非空参数集,量词消去把完全一变量类型分成“等于某个参数”“位于相邻参数之间”及“位于两侧射线”几类;相等点本身、稠密性和无端点性分别提供有理数见证。空参数集则只有一个完全一变量类型,任意有理数都实现它。对有限元组,同样只需在这些区域中按指定次序安排有限多个相等类,仍能完成。有限参数与可数参数之间的这一变化,正是本例显示的边界。
从实现一个类型到同时补齐所有有限参数要求,还需迭代。初等链与ω饱和扩张 理路 初等链与ω饱和扩张 Elementary chain theorem · Omega-saturated elementary extension 证明初等链的并保持一阶真值,迭代实现有限参数类型构造ω饱和扩张,并给出可数语言仍迫使不可数模型的例子。 证明一次紧致性可实现旧参数的全部有限元组类型,再沿ω链取并处理后来加入的参数;其一元谓词例子说明可数语言仍可能有连续统多个空参数类型,不能无条件要求扩张可数。
参考资料