第2节可定义性 第5章一阶语言的结构和真值理论 前面我们提到过“群”这个概念。我们想说明所有的群组成一个初等类,并说明我们 可以选择不同的语言。在第??章第??节中,我们选的语言为Lo=(e,+)。现在我们选取 L1={≈,o,1,e},其中。和-1分别是一个二元和一元函数符号,e是一个常数符号。在 L1上,所有群的类可以被下列闭语句描述,因而是一个初等类 VarvyVz (ao(yo z)a(aoy)oz) vx(xoe≈eox≈x); r(xox1≈r-lor≈e) 我们也可以选取L2={≈,o},其中。是一个二元函数符号。在L2上,所有群的类仍 是一个初等类,因为它可以被下列闭语句描述(见习题) VarvyVz(o(yo)a(oy)ox); vrvy3z(xoz≈y) vry3z(zox≈y)o 注:选取不同的语言对本课程关系不大,但如果我们对句法复杂性感兴趣的话,我们 会注意到在L1上,我们只用到了全称量词,而在L2中我们需要两种不同的量词。这样 的细微差别有时会产生一些影响。 如果语言中有等词的话,我们有闭语句彐表示“结构中至少有n个不同的元素”,例 如,丑2和彐3分别为 丑x3y(x米y) x3y32(x米y∧y关2∧x2) 这样所有的无限群组成的类就是一个广义初等类,因为它是由所有满足群的公理并且满 足{2,3,…}的结构组成的。后面我们会证明它不是一个初等类。 我们再来讨论结构内的可定义性。这种可定义性在数理逻辑是很普遍的,比如,在哥 德尔可构成集的类L中可定义性是最重要的概念。此外,模型论学家也经常研究可定义 的集合或关系,因为同没有限制的任意集合相比,人们更愿意讨论自然的集合,而可定义 的集合可以说是自然的。至少退一步说,不可定义的集合是不太自然的。熟悉集合论公理 的同学可以比较分离公理和选择公理,由分离公理得到的集合是由某个公式定义出来的, 而由选择公理得到的集合往往是不可定义的,因而分离公理比选择公理显得自然。 固定一个语言L和L上面的一个结构。我们先引进一个写法来避免s之类的 繁琐(该写法在练习?中已经出现过)。假定φ(v1,2,…,k)为L的一个公式,并且 t1,2,…,tk包括了中的所有自由变元。对于||中的元素a1,a2,…,ak,我们想说第 2 节 可定义性 第 5 章 一阶语言的结构和真值理论 前面我们提到过“群”这个概念。我们想说明所有的群组成一个初等类，并说明我们 可以选择不同的语言。在第 ?? 章第 ?? 节中，我们选的语言为 L0 = (e, +)。现在我们选取 L1 = {≈, ◦, −1 , e}，其中 ◦ 和 −1 分别是一个二元和一元函数符号，e 是一个常数符号。在 L1 上，所有群的类可以被下列闭语句描述，因而是一个初等类： ∀x∀y∀z (x ◦ (y ◦ z) ≈ (x ◦ y) ◦ z); ∀x (x ◦ e ≈ e ◦ x ≈ x); ∀x (x ◦ x −1 ≈ x −1 ◦ x ≈ e)。 我们也可以选取 L2 = {≈, ◦}，其中 ◦ 是一个二元函数符号。在 L2 上，所有群的类仍 是一个初等类，因为它可以被下列闭语句描述（见习题）： ∀x∀y∀z (x ◦ (y ◦ z) ≈ (x ◦ y) ◦ z); ∀x∀y∃z (x ◦ z ≈ y); ∀x∀y∃z (z ◦ x ≈ y)。 注：选取不同的语言对本课程关系不大，但如果我们对句法复杂性感兴趣的话，我们 会注意到在 L1 上，我们只用到了全称量词，而在 L2 中我们需要两种不同的量词。这样 的细微差别有时会产生一些影响。 如果语言中有等词的话，我们有闭语句 ∃n 表示“结构中至少有 n 个不同的元素”，例 如，∃2 和 ∃3 分别为： ∃x∃y(x ̸≈ y), ∃x∃y∃z(x ̸≈ y ∧ y ̸≈ z ∧ x ̸≈ z)。 这样所有的无限群组成的类就是一个广义初等类，因为它是由所有满足群的公理并且满 足 {∃2, ∃3, · · · } 的结构组成的。后面我们会证明它不是一个初等类。 我们再来讨论结构内的可定义性。这种可定义性在数理逻辑是很普遍的，比如，在哥 德尔可构成集的类 L 中可定义性是最重要的概念。此外，模型论学家也经常研究可定义 的集合或关系，因为同没有限制的任意集合相比，人们更愿意讨论自然的集合，而可定义 的集合可以说是自然的。至少退一步说，不可定义的集合是不太自然的。熟悉集合论公理 的同学可以比较分离公理和选择公理，由分离公理得到的集合是由某个公式定义出来的， 而由选择公理得到的集合往往是不可定义的，因而分离公理比选择公理显得自然。 固定一个语言 L 和 L 上面的一个结构 A。我们先引进一个写法来避免 s x d 之类的 繁琐（该写法在练习 ?? 中已经出现过）。假定 φ(v1, v2, · · · , vk) 为 L 的一个公式，并且 v1, v2, · · · , vk 包括了 φ 中的所有自由变元。对于 | A | 中的元素 a1, a2, · · · , ak，我们想说 6