无穷逻辑 infinitary (John L. Bell)
首次发表于 2000 年 1 月 23 日;实质性修订于 2023 年 9 月 6 日。
传统上,形式系统中的表达式被认为是表示有限的铭文,至少在原则上,能够以原始符号写出来。然而,(一阶)公式可以通过“哥德尔编号”与自然数(从而与有限集合)等同起来,这使得不再需要将公式视为铭文,并且暗示着可以构建一些“语言”,其中一些公式可以自然地被认为是无穷集合。这种语言被称为无穷语言:在本文中,我讨论了那些可以通过允许无穷长的合取、析取和可能的量词序列从一阶语言中直接获得的无穷语言。在讨论过程中,将会看到,尽管这些语言的表达能力远远超过有限(一阶)语言的表达能力,但很少有它们具备后者的“吸引人”的特点(例如,紧致性和完备性)。因此,实际上具备这些特点的无穷语言值得特别关注。
在第 1 节中,介绍了无穷语言的基本语法和语义;然后通过示例展示了它们的表达能力。第 2 节专门讨论了那些只允许有限量词序列的无穷语言:这些语言被证明相对行为良好。第 3 节讨论了无穷语言的紧致性问题及其与纯粹集合论问题中的“大”基数的关系。第 4 节概述了一个论证,表明大多数“无限量词”语言具有二阶性质,并且因此高度不完备。第 5 节简要介绍了一类特殊的无穷语言子语言,可以证明紧致性定理的一个令人满意的推广。本节还包括关于可接受集合定义的一个子节。第 6 节提供了历史和文献注释。
1. 无穷语言的定义和基本属性
给定一对无穷基数 κ, λ,其中 λ ≤ κ,我们定义了一类无穷语言,其中我们可以形成基数 < κ 的公式集合的合取和析取,并对长度 < λ 的变量序列进行量化。
设 L 为(有限的)基础语言,它是一个任意但固定的一阶语言,具有任意数量的非逻辑符号。无穷语言 L(κ,λ) 具有以下基本符号:
L 的所有符号
一个个体变量集合 Var,其中 Var 的基数(写作:|Var|)为 κ
一个逻辑运算符 ∧(无穷合取)
L(κ,λ)的前公式类被递归地定义如下:
每个 L 的公式都是一个前公式;
如果 φ 和 ψ 是前公式,那么 φ∧ψ 和 ¬φ 也是前公式;
如果 Φ 是一组前公式,使得|Φ| < κ,则 ∧Φ 是一个前公式;
如果 φ 是一个前公式,并且 X ⊆ Var 是这样的集合,使得|X| < λ,则 ∃Xφ 是一个前公式;
所有的前公式都由上述子句定义。
如果 Φ 是由集合 I 索引的一组前公式,记作 Φ = {φi : i ∈ I},那么我们约定写成 ∧Φ 表示:
∧ i ∈ I φ
或者,如果 I 是自然数集合,我们写成 ∧Φ 表示:
φ0 ∧ φ1 ∧ …
如果 X 是由序数 α 索引的一组个体变量,即 X = {xξ : ξ < α},我们同意写成(∃xξ)ξ<αφ 来表示 ∃Xφ。
逻辑运算符 ∨、→、↔ 按照惯例进行定义。我们还引入了运算符 ∨(无穷析取)和 ∀(全称量化)。
∨Φ =df ¬∧{ ¬φ : φ ∈ Φ}
∀Xφ =df ¬∃X¬φ,
并采用与 ∧、∃ 类似的约定。
因此,L(κ,λ)是从 L 中获得的无穷语言,允许长度小于 κ 的合取和析取以及长度小于 λ 的量化[1]。L(κ,ω)语言称为有限量词语言,其余为无限量词语言。注意到 L(ω,ω)就是 L 本身。
注意以下在无穷语言中可能出现但有限语言中不会出现的异常情况。在语言 L(ω1,ω)中,允许可数无穷的合取,但只允许有限的量化,存在一些前公式具有如此多的自由变量,以至于无法通过前缀量词将其“封闭”为 L(ω1,ω)的句子。例如,对于 L(ω1,ω)-前公式而言,情况就是如此。
_x_0 < _x_1 ∧ _x_1 < _x_2 ∧ … ∧ xn < x**n+1 …,
其中 L 包含二元关系符号<。因此,我们做以下定义。
L(κ,λ)的一个公式是一个包含< λ 个自由变量的前公式。L(κ,λ)的所有公式的集合将被表示为 Form(L(κ,λ))或简称为 Form(κ,λ),所有句子的集合将被表示为 Sent(L(κ,λ))或简称为 Sent(κ,λ)。
在这种联系中,需要注意的是,一般情况下,考虑 λ > κ 的“语言”L(κ,λ)不会有任何收益。例如,在“语言”L(ω,ω1)中,公式只会有有限个自由变量,而会有大量“无用”的量词能够绑定无穷多个自由变量。[2]
在定义了 L(κ,λ)的语法之后,我们接下来勾勒其语义。由于 L(κ,λ)的非逻辑符号只是 L 的非逻辑符号,而正是这些符号决定了给定的一阶语言要被解释的结构的形式,因此自然地将 L(κ,λ)-结构定义为简单的 L-结构。L(κ,λ)中的公式在 L-结构 A 中是否满足(通过 A 的一个元素序列)的概念以与 L 的公式相同的归纳方式定义,只是我们必须添加两个额外的子句,对应于 preformula 的 ∧Φ 和 ∃Xφ 的子句。在这两种情况下,我们自然地定义:
对于给定的序列,∧Φ 在 A 中满足 ⇔ 对于所有的 φ ∈ Φ,φ 在 A 中满足(通过该序列);
∃Xφ 在 A 中满足 ⇔ 存在一个与 X 具有双射对应关系的来自 A 的元素序列,在 A 中满足 φ。
这些非正式的定义需要在严格的发展中加以细化,但它们的意义应该对读者来说是清楚的。现在,通常的真理、有效性、可满足性和 L(κ,λ)公式和句子的模型的概念变得可用。特别地,如果 A 是一个 L-结构,σ ∈ Sent(κ,λ),我们将写作 A ⊨ σ 表示 A 是 σ 的一个模型,⊨ σ 表示 σ 是有效的,即对于所有的 A,A ⊨ σ。如果 Δ ⊆ Sent(κ,λ),我们将写作 Δ ⊨ σ 表示 σ 是 Δ 的逻辑推论,即每个 Δ 的模型都是 σ 的模型。
现在我们给出一些例子,旨在展示无穷语言 L(κ,λ)的表达能力,其中 κ ≥ ω1。在每种情况下,众所周知,所讨论的概念无法用任何一阶语言来表达。
L(ω1,ω)中算术标准模型的特征化。这里,算术的标准模型是结构 N = ⟨N, +, ·, s, 0⟩,其中 N 是自然数集,+、·和 0 具有它们的通常含义,s 是后继操作。让 L 是适用于 N 的一阶语言。那么,与 N 同构的 L-结构的类与以下 L(ω1,ω)句子的模型类重合(其中 0 是 0 的一个名称):
∧ m ∈ω ∧ n ∈ω s_ m _0** + s_**n* _0** = * s**m +_n_ 0
∧ m ∈ω ∧ n ∈ω s_ m _0** · s_**n* _0** = * s**m ·_n_ 0
∧ m ∈ω ∧ n ∈ω−{m} s_ m _0** ≠ s_n_0**
∀ x ∨ m ∈ω x = s_ m_0**
术语 snx 通过递归定义
s_0_x | = | x |
s**n+1_x_ | = | s(snx) |
L(ω1,ω)中所有有限集合的特征化。在这里,基本语言没有额外的逻辑符号。所有有限集合的类与 L(ω1,ω)-句子的模型类重合。
∨ n ∈ω ∃_v_0 … ∃ vn ∀ x(x = _v_0 ∨ … ∨ x = vn).
在一个可数的基础语言 L(ω1,ω)中的真理定义。让 L 是一个可数的一阶语言(例如,算术或集合论的语言),其中包含每个自然数 n 的名称 n,并且让 σ0,σ1,…是其句子的枚举。那么 L(ω1,ω)-公式
Tr(x) =df ∨ n ∈ω (x = n ∧ σ_n_)
是 L 的一个真理谓词,因为句子
Tr(n) ↔ σ_n_
对每个 n 都是有效的。
在 L(ω1,ω1)中对良序的表征。这里的基本语言 L 包括一个二元谓词符号 ≤。让 σ1 是表征线性序的通常 L 句子。那么,解释 ≤ 为良序的 L-结构的类与 L(ω1,ω1)句子 σ = σ1 ∧ σ2 的模型类相一致,其中
σ2 =df (∀vn)n∈ω ∃x [∨n∈ω (x = vn) ∧ ∧n∈ω (x ≤ vn)]。
注意,句子 σ2 包含一个无穷量词:它表达了本质上是二阶断言的每个可数子集都有一个最小成员。事实上,可以证明这个无穷量词的存在是必要的:良序结构的类不能用任何有限量词语言来表征。这个例子表明,无穷量词语言(如 L(ω1,ω1))的行为与二阶语言相当相似;我们将看到它们共享后者的缺陷(不完备性)以及一些优点(强表达能力)。
许多一阶语言的扩展可以被翻译成无穷语言。例如,考虑从 L 中添加一个新的量词符号 Q0 并将 Q0xφ(x)解释为存在无穷多个 x 使得 φ(x)的广义量词语言 L(Q0)。很容易看出,句子 Q0xφ(x)与 L(ω1,ω)-句子 ¬∨n∈ω ∃v0…∃vn∀ x[φ(x) → (x = v0 ∨ … ∨ x = vn)]具有相同的模型。
因此,从自然意义上讲,L(Q0)可以被翻译成 L(ω1,ω)。另一个可以按照这种意义翻译成 L(ω1,ω)的语言是通过向 L 添加一个可数集合的单调谓词变量,并将其解释为范围在所有有限个体集上的弱二阶语言。
Thus L(_Q_0) is, in a natural sense, translatable into L(ω1,ω). Another language translatable into L(ω1,ω) in this sense is the weak second-order language obtained by adding a countable set of monadic predicate variables to L which are then interpreted as ranging over all finite sets of individuals.
可以引入具有任意长的合取、析取和(可能的)量化的语言。对于固定的无穷基数 λ,语言 L(∞,λ)通过指定其公式类 Form(∞,λ)为所有 κ ≥ λ 的集合 Form(κ,λ)的并集来定义。因此,L(∞,λ)允许任意长的合取和析取,即如果 Φ 是 Form(∞,λ)的任意子集,则 ∧Φ 和 ∨Φ 都是 Form(∞,λ)的成员。但是,L(∞,λ)只允许长度< λ 的量化:它的所有公式都有< λ 个自由变量。语言 L(∞,∞)则通过指定其公式类 Form(∞,∞)为所有无穷基数 λ 的类 Form(∞,λ)的并集来定义。因此,L(∞,∞)除了允许任意长的合取和析取外,还允许任意长的量化。请注意,根据哥德尔-伯内斯集合论的观点,Form(∞,λ)和 Form(∞,∞)都是适当的类。在结构中满足 L(∞,λ)和 L(∞,∞)的公式可以通过对 L(κ,λ)的相应概念的明显扩展来定义。
2. 有限量词语言
我们已经指出,像 L(ω1,ω1)这样的无穷量词语言在某种程度上类似于二阶语言,因为它们允许对无穷个体集合进行量化。有限量词语言不允许这样做,这表明在某些方面,它们可能比首阶语言更接近它们的首阶对应物。我们将看到,这确实是这种情况,特别是在 L(ω1,ω)的情况下。
语言 L(ω1,ω)在无穷语言中占据着特殊的地位,因为它像一阶语言一样,具有有效的演绎学工具。实际上,让我们在通常的一阶公理和推理规则的基础上添加新的公理方案
∧Φ → φ
对于任意可数集合 Φ ⊆ Form(ω1,ω)和任意 φ ∈ Φ,以及新的推理规则
φ0, φ1, …, φ_n_, … |
---|
∧ n ∈ω φ_n_ |
并且允许推导具有可数长度。在这个意义上,我们用 ⊢*表示可推导性,然后我们有
L(ω1,ω)-完备性定理。对于任意的 σ ∈ Sent(ω1,ω),⊨ σ ⇔ ⊢*σ
作为一个直接的推论,我们推断出这个演绎装置对于 L(ω1,ω)中可数前提集的推导是足够的。也就是说,通过显然的符号扩展,对于任意可数集合 Δ ⊆ Sent(ω1,ω),我们有
(2.1) Δ ⊨ σ ⇔ Δ⊢*σ
这个完备性定理可以通过修改一阶逻辑的通常 Henkin 完备性证明,或者使用布尔代数方法来证明。类似的论证,应用于适当的公理和推理规则的进一步增强,可以得到许多其他有限量词语言的类似完备性定理。
如果只允许有限长度的推导,那么就无法建立一个对任意前提集合都适用的 L(ω1,ω)的演绎设备,即对于每个集合 Δ ⊆ Sent(ω1,ω),无论其基数如何,都满足(2.1)。这是因为简单观察可知,存在一个一阶语言 L 和一个 L(ω1,ω)-句子的不可数集合 Γ,使得 Γ 没有模型,但 Γ 的每个可数子集都有模型。为了看到这一点,让 L 是算术的语言,增加 ω1 个新的常量符号{cξ : ξ < ω1},并且让 Γ 是 L(ω1,ω)-句子的集合{σ} ∪ {cξ ≠ cη : ξ ≠ η},其中 σ 是描述算术标准模型的 L(ω1,ω)-句子。这个例子还表明,紧致性定理对于 L(ω1,ω)以及任何满足 κ ≥ ω1 的 L(κ,λ)也不成立。
在一阶情况下成立但对于满足 κ ≥ ω1 的 L(κ,ω)(以及 L(ω1,ω1),尽管这更难证明)不成立的另一个结果是前束范式定理。如果一个句子的量词都出现在前面,那么它就是前束的;我们举一个 L(ω1,ω)-句子的例子,它不等价于前束句子的合取。让 L 是没有额外逻辑符号的一阶语言,让 σ 是描述有限集合类的 L(ω1,ω)-句子。假设 σ 等价于一个合取式
∧ i ∈ I σ_i_
针对前束 L(ω1,ω)-句子 σi 的源头。然后每个 σi 的形式为
Q_1_x_1 … * Q_n_xn * φ_i(_x_1 ,…, xn),
其中每个 Qk 是 ∀ 或 ∃,而 φi 是一个(可能是无穷的)合取或析取,其由形如 xk = xl 或 xk ≠ xl 的公式组成。由于每个 σi 都是一个句子,因此每个 φi 中只有有限数量的变量,并且很容易看出每个 φi 等价于一个一阶公式。因此,每个 σi 可以被视为一个一阶句子。由于假设 σ 等价于 σi 的合取,因此可以得出 σ 和集合 Δ = {σi : i ∈ I}具有相同的模型。但显然 σ,以及 Δ,具有所有有限基数的模型;现在,一阶句子集的紧致性定理暗示 Δ,以及 σ,具有一个无穷模型,这与 σ 的定义相矛盾。
转向 Löwenheim-Skolem 定理,我们发现向下版本对 L(ω1,ω)(实际上对所有无穷语言)有足够的概括。事实上,可以以与一阶句子集相同的方式证明,如果 Δ ⊆ Sent(ω1,ω)具有基数 ≥ |Δ|的无穷模型,则它具有基数为 ℵ0 和|Δ|中较大的模型。特别地,具有无穷模型的任何 L(ω1,ω)-句子都有可数模型。
另一方面,通常形式的向上 Löwenheim-Skolem 定理对所有无穷语言都不成立。例如,描述算术标准模型的 L(ω1,ω)-句子具有基数 ℵ0 的模型,但没有其他基数的模型。然而,在这里并非一无所获,我们将会看到。
我们将语言 L 的 Hanf 数 h(L)定义为最小基数 κ,使得如果一个 L-句子具有基数 κ 的模型,则它具有任意大基数的模型。h(L)的存在很容易证明。对于不具有任意大基数模型的每个 L-句子 σ,令 κ(σ)为最小基数 κ,使得 σ 没有基数为 κ 的模型。如果 λ 是所有 κ(σ)的上确界,则如果一个 L 的句子具有基数 λ 的模型,则它具有任意大基数的模型。
通过递归方式定义基数 μ(α)
μ(0) | = | ℵ0 |
---|---|---|
μ(α+1) | = | 2μ(α) |
μ(λ) | = | ∑α<λ μ(α),对于极限 λ |
然后可以证明
h(L(ω1,ω)) = μ(ω1),
对于其他有限量词语言也成立类似的结果。无穷量词语言如 L(ω1,ω1)的 Hanf 数值对于大基数的存在与否非常敏感,但无论如何都远远超过 L(ω1,ω)的数值。
适用于 L 的一个结果可以推广到 L(ω1,ω),但对于其他无穷语言则不成立。
克雷格插值定理:如果 σ,τ ∈ Sent(ω1,ω)满足 ⊨ σ → τ,则存在 θ ∈ Sent(ω1,ω)满足 ⊨ σ → θ 和 ⊨ θ → τ,并且 θ 中出现的每个非逻辑符号都出现在 σ 和 τ 中。
证明是对一阶情况的合理直接扩展。
最后,我们提到一个进一步推广到 L(ω1,ω)但不适用于其他无穷逻辑语言的结果。众所周知,如果 A 是任何只有有限个关系的有限 L-结构,则存在一个 L-句子 σ 表征 A 的同构。对于 L(ω1,ω),我们有以下的推广,被称为
斯科特的同构定理。如果 A 是一个只有可数多个关系的可数 L-结构,则存在一个 L(ω1,ω)-句子,其可数模型的类与与 A 同构的 L-结构的类相一致。
对可数结构的限制是必要的,因为可数性通常不能通过 L(ω1,ω)-句子来表达。
语言 L(∞,ω)也可以被视为有限量词语言。关于这种语言的结构等价的概念具有特殊的意义:我们称两个(相似的)结构 A 和 B 为(∞,ω)-等价,记作 A ≡∞ω B,如果 L(∞,ω)的相同句子在 A 和 B 中都成立。首先,可以通过部分同构的概念来表征这种关系。A 和 B 之间的部分同构是一个非空映射族 P,满足以下条件:
对于每个 p ∈ P,dom(p) 是 A 的子结构,ran(p) 是 B 的子结构,并且 p 是其定义域到其值域的同构;并且
如果 p ∈ P,a ∈ A,b ∈ B,则存在扩展 p 的 r、s ∈ P,使得 a ∈ dom(r),b ∈ ran(s)(“前后”性质)。
如果 A 和 B 之间存在部分同构,则我们称 A 和 B 部分同构,并写作 A ≅p B。我们有
Karp 的部分同构定理。 对于任意相似的结构 A、B,A ≡∞ω B ⇔ A ≅p B。
对于 L(∞,ω)也存在 Scott 同构定理的一个版本,即,
(2.2) 给定任何结构 A,存在一个 L(∞,ω)-句子 σ,对于所有的结构 B,A ≅p B ⇔ B ⊨ σ。
部分同构和(∞,ω)-等价与布尔同构的概念相关。为了定义这个概念,我们需要引入布尔值集合论模型的概念。给定一个完备的布尔代数 B,B-值集合的宇宙 V(B),也被称为集合宇宙 V 的 B-扩张,通过首先递归地定义在 α 上得到,
Vα(B) = {x: x 是一个函数 ∧ range(x) ⊆ B ∧ ∃ξ<α[domain(x) ⊆ Vξ(B)]}
然后设置
V(B) = {x: ∃α(x ∈ Vα(B))}。
V(B)的成员被称为 B-值集合。现在很容易看出,B-值集合恰好是具有 B-值集合为定义域的 B-值函数。现在让 L 成为集合论的一阶语言,L(B)是通过向 L 中添加 V(B)的每个元素的名称而得到的语言(我们将使用相同的符号表示元素和其名称)。现在可以构建一个将语言 L(B)的(句子)映射到 B 的映射:对于 L(B)的每个句子 σ,B 的元素 σ 是 σ 在 V(B)中的“布尔真值”。该映射被定义为将 Zermelo-Fraenkel 集合论的所有定理发送到 B 的顶部元素 1,即“真”;因此,V(B)可以被视为集合论的布尔值模型。一般来说,如果 σ = 1,我们说 σ 在 V(B)中是有效的,并写作 V(B) ⊨ σ。
现在,对于每个 x ∈ V,都有一个在 V(B) 中的规范代表 x,满足
x = y 当且仅当 V(B) ⊨ x = y x ∈ y 当且仅当 V(B) ⊨ x ∈ y
我们说两个相似的结构 A、B 是布尔同构的,记作 A ≅b B,如果存在一个完备的布尔代数 B,使得 V(B) ⊨ A ≅ B,也就是说,在某个集合宇宙的布尔扩展中,A 和 B 的规范代表是布尔值 1 同构的。然后可以证明:
(2.3) A ≡∞ω B ⇔ A ≅ b_ B_.
这个结果可以通过范畴论的形式化得到加强。为此,我们需要引入一个(基本)拓扑的概念。为了介绍这个概念,我们从集合和映射的熟知范畴 Set 开始。Set 具有以下关键属性:
存在一个“终端”对象 1,对于任何对象 X,存在一个唯一的映射 X → 1(对于 1,我们可以取任何一个元素的集合,特别是{0})。
任意一对对象 X,Y 都有一个笛卡尔积 X × Y。
对于任意一对对象,可以形成所有从 X → Y 的“指数”对象 Y**X。
存在一个“真值”对象 Ω,对于每个对象 X,X 的子对象(子集)与映射 X → Ω 之间存在自然对应关系。(对于 Ω,我们可以取集合 2 = {0,1};然后 X → Ω 的映射是 X 上的特征函数。)
这四个条件都可以用范畴论语言来表述——满足这些条件的范畴被称为拓扑。集合范畴是一个拓扑;同样,布尔值集合和映射的范畴 Set(B)在任何布尔扩张 V(B)的集合宇宙中也是拓扑;在拓扑空间上的所有集合层范畴也是拓扑;所有映射集的图表的范畴也是拓扑。
_X_0 → _X_1 → _X_2 → …
每个这些类别的对象可以被视为以某种方式变化的集合:在情况(i)中,是在布尔代数上;在情况(ii)中,是在拓扑空间上;在情况(iii)中,是在(离散的)时间上。一个拓扑学可以被理解为一个“可变”集合的宇宙。熟悉的集合范畴 Set 是一个拓扑学的特殊极限情况,其中对象的“变化”已经被减少到零。
正如在集合论中,可以在任何拓扑学中的真值对象上定义“逻辑运算符”。这些运算符是映射 ¬: Ω → Ω; ∧, ∨, ⇒: Ω × Ω → Ω,对应于否定、合取、析取和蕴涵的逻辑操作。通过这些运算,Ω 成为一个 Heyting 代数,从而一般地体现了直觉主义逻辑而不是经典逻辑的规律。从这个意义上说,直觉主义逻辑在一个拓扑学中被“内化”:直觉主义逻辑是可变集合的逻辑。(当然,经典逻辑在某些拓扑学中被内化,例如在集合范畴 Set 和任何完备布尔代数 B 上的 Set(B)中。)
任何拓扑学都可以被看作是可能的“话语宇宙”,在其中可以解释数学断言并进行数学构造。通过 E 的内部语言(集合论的通常语言的类型论版本)在拓扑学 E 中表达,数学断言可以被解释。类似于布尔值有效性,可以在 E 中引入关于其内部语言句子 σ 的有效性的适当概念。同样,我们写作 E ⊨ σ 表示“σ 在 E 中有效”。
如果一个拓扑空间 E 被称为是 full 的,那么对于任意集合 I,在 E 中存在它的 I-fold copower[ 3] ∐I1。∐I1 可以被看作是集合 I 在 E 中的规范代表;因此,我们简单地将其写作 I。(在 V(B)中,这与之前定义的 I 相一致。)上述所有的拓扑空间都是 full 的。
现在假设 E 是一个 full 的拓扑空间。如果 A = (A, R, …)是一个结构,我们用 A 来表示(A, R, …)。如果两个结构 A 和 B 是 topos 同构的,即 A ≅t B,那么对于一些定义在集合范畴上的拓扑空间 E,我们有 E ⊨ A ≅ B。换句话说,如果两个结构的规范代表在某个拓扑空间的内部语言中是同构的,那么它们就是 topos 同构的。然后可以证明
(2.4) A ≡∞ω B ⇔ A ≅ t_ B_.
因此,可以将(∞,ω)-等价性视为在“可变”集合的宇宙的极其一般的背景下的同构。在这方面,(∞,ω)-等价性是同构的“不变”概念。
3. 紧致性质
正如我们所见,紧致性定理在其通常形式下对所有无穷语言都不成立。然而,确定无穷语言是否满足定理的某种适当修改版本是有一定兴趣的。这个所谓的紧致性问题与纯粹的集合论问题,涉及“大”基数有自然的联系。
我们构建以下定义。设 κ 是一个无穷基数。如果对于每个 L-句子集合 Δ(或者基数 ≤κ 的 L-句子集合 Δ),并且 Δ 的每个基数小于 κ 的子集都有一个模型,那么语言 L 被称为 κ-紧致(或者弱 κ -紧致)。注意,对于 L 的通常紧致性定理正是 L 是 ω-紧致的断言。赋予 κ-紧致性质重要性的一个原因是以下。如果存在一个 L 的演绎系统 P,其演绎长度小于 κ,并且如果 Δ 是一个 P-一致[4]的 L-句子集合(或者|Δ|≤κ),那么 Δ 有一个模型,则称 L 为 L κ-完备(或者弱 κ-完备)。注意,这样的 P 将对于从任意前提集合(基数 ≤κ)进行演绎具有充分性质(根据第 2 节的意义)。很容易看出,如果 L 是 κ-完备或者弱 κ-完备,则 L 是 κ-紧致或者弱 κ-紧致。因此,如果我们能够证明给定的语言不是(弱)κ-紧致的话,则不能存在一个演绎系统,其演绎长度小于 κ,并且对于从任意前提集合(基数 ≤κ)进行演绎具有充分性质。
实际上,事实证明,大多数语言 L(κ,λ)甚至不是弱 κ-紧致的,而且对于那些是的语言,κ 必须是一个非常大的基数。我们需要一些定义。
如果一个无穷基数 κ 被称为弱不可达的话,
(a) λ < κ → λ+ < κ,(其中 λ+表示 λ 的继承基数),并且
(b) | I | < κ 且 λi < κ(对于所有 i ∈ I)⇒ ∑i∈I λi < κ。
如果此外
(c) λ < κ ⇒ 2λ < κ,
如果 κ 被称为(强)不可达,则 ℵ0 是不可达的,因此通常将注意力限制在那些超过 ℵ0 的不可达或弱不可达的基数上。因此,不可达或弱不可达的基数总是被认为是不可数的。很明显,这样的基数——如果它们存在的话——必须非常大;而且哥德尔不完备定理表明,甚至不能从集合论的常规公理中证明弱不可达基数的存在。
如果语言 L(κ,κ)是 κ-紧致(或弱 κ-紧致),则称基数 κ 是紧致的(或弱紧致的)。然后我们有以下结果:
(3.1) ℵ0 是紧致的。当然,这只是一种简洁表达一阶语言紧致性定理的方式。
(3.2) 如果 κ 是弱紧致的 ⇒L(κ,ω)是弱 κ-紧致的 ⇒κ 是弱不可达的。因此,假设没有语言 L(κ,ω)满足 κ ≥ ω1 是弱 κ-紧致的(或者更确切地说,弱 κ-完备的)是与集合论的通常公理一致的。
(3.3) 假设 κ 是不可达的。那么 κ 是弱紧致的 ⇔L(κ,ω)是弱 κ-紧致的。此外,κ 是弱紧致的 ⇒ 在 κ 之前存在一个 κ 个不可达的集合。因此,弱紧致的不可达基数非常大;特别是它不能是第一个、第二个、...第 n 个、...不可达的基数。
(3.4) κ 是紧致的 ⇒κ 是无法访问的。(但是,根据上面的结果,逆命题不成立。)
让 Constr 代表哥德尔的可构造性公理;请记住,Constr 与集合论的通常公理一致。
(3.5)如果 Constr 成立,则不存在紧致基数。
(3.6) 假设 Constr 成立,并且让 κ 是不可达的。那么 κ 是弱紧致的 ⇔ 对于所有的 L,L(ω1,ω) 都是弱 κ-紧致的。
(3.7) 如果 Constr 成立,则不存在基数 κ 使得 L(ω1,ω) 是紧致的。因此,根据集合论的通常公理,假设不存在基数 κ 使得所有语言 L(ω1,ω) 都是 κ-完备的是一致的。这个结果与所有一阶语言都是 ω-完备的事实形成对比。
这些结果的重要性在于,对于大多数满足 κ ≥ ω1 的语言 L(κ,λ),紧致性定理的失败非常严重。
这里需要一些历史性的评论。在 20 世纪 30 年代,数学家们研究了与勒贝格测度理论相关的所谓集合测度问题的各种版本。特别地,提出了以下非常简单的测度概念。如果 X 是一个集合,那么 X 上的(可数可加的二值非平凡)测度是一个映射 μ,将幂集 PX 映射到集合{0, 1},满足以下条件:
(a) μ(X) = 1,
(b) 对于所有 x ∈X,μ({x}) = μ(∅) = 0。
(c) 如果 A 是 X 的任意可数个互不相交的子集的族,则 μ(∪A) = ∑{μ(Y) : Y ∈ A}。
显然,一个给定集合是否支持这样的度量仅取决于它的基数,因此自然地定义一个基数 κ 是可测的,如果所有基数为 κ 的集合都支持这种度量。很快人们意识到可测基数必须是不可达的,但直到 20 世纪 60 年代,塔斯基才证明了可测基数是弱紧致的,他的学生汉夫证明了第一、第二等不可达基数不是弱紧致的(参见(3.3))。尽管现在通常在不经过弱紧致性和无穷语言的绕道路的情况下证明可测基数必须是巨大的,但事实仍然是这些思想被用来首次建立结果。
4. 无穷量词语言的不完备性
关于一阶语言,可能最重要的结果是哥德尔完备定理,它当然表明了任何一阶语言 L 的所有有效公式可以通过一些简单的公理和推理规则生成。这个定理的一个重要推论是,如果 L 的公式以某种可构造的方式编码为自然数,则有效句子(的编码)的集合是可递归可枚举的。因此,一阶语言的完备性意味着其有效句子的集合可以用一种特别简单的方式定义。因此,对于任意语言 L,如果 L 的有效句子集合不能以某种简单方式定义,则无法为 L 建立有意义的完备性结果,或者说 L 是不完备的。在本节中,我们将利用这个建议来概述“大多数”无穷量词语言在这个意义上是不完备的证明。
让我们首先介绍定义性的形式概念如下。如果 L 是一种语言,A 是 L-结构,X 是 A 的域的子集,我们说 X 在 A 中可以由 L 的公式 φ(x, y1,...,yn)定义,如果存在 A 的元素序列 a1,...,an,使得 X 是所有满足在 A 中 φ(x, a1,...,an)的元素 x ∈ A 的子集。
现在,我们用 Val(L)表示所有有效的 L-句子的集合,即在每个 L-结构中都成立的句子。为了给语句“Val(L)是可定义的”赋予意义,我们必须指定
一个结构 C(L) - L 的编码结构;
一个特定的一一映射 - 编码映射 - 将 L 的公式集映射到 C(L)的域中。
然后,如果我们将 Val(L)在编码映射下的图像与 Val(L)进行等同,我们将解释语句“Val(L)是可定义的”为语句“将 Val(L)视为 C(L)域中的子集,在 C(L)中可由 L 的一个公式定义”。
例如,当 L 是算术的一阶语言 L 时,哥德尔最初使用算术的标准模型 ℕ 作为编码结构,并使用从自然数的素因子分解定理得到的著名函数作为编码映射。然后,Val(L)的递归可枚举性仅意味着 Val(L)的成员的编码(“哥德尔数”)的集合在 ℕ 中可以由形如 ∃yφ(x, y)的 L-公式定义,其中 φ(x, y)是一个递归公式。
另一个等价的算术一阶语言的编码结构是具有继承有限集的结构[5]⟨H(ω), ∈ ⨡ H(ω)⟩,其中集合 x 是继承有限的,如果 x、它的成员、它的成员的成员等都是有限的。这种编码结构考虑到了一阶公式自然上被视为有限集的事实。
现在转向 L 是无穷语言 L(κ,λ)的情况,这种情况下适合的编码结构是什么?我们在开始时提到,无穷语言是通过将公式视为集合论对象的可能性而提出的,因此让我们试着通过思考我们应该将无穷公式视为什么样的集合论对象来获得我们的编码结构。鉴于对于每个 φ∈Form(κ,λ),φ 及其子公式、子子公式等都具有长度<κ 的事实,一瞬间的反思揭示了 L(κ,λ)的公式“对应”于集合 x,其继承基数<κ,即 x、它的成员、它的成员的成员等都具有基数<κ。所有这些集合的集合被写作 H(κ)。H(ω)是上面介绍的继承有限集的集合,而 H(ω1)是所有可数继承集的集合。
为简单起见,让我们假设基本语言 L 的唯一非逻辑符号是二元谓词符号 ∈(讨论很容易扩展到 L 包含其他非逻辑符号的情况)。在上述备注的指导下,作为 L(κ,λ)的编码结构,我们采用结构,
H(κ) =df ⟨H(κ), ∈ ⨡ H(κ)⟩。
现在我们可以定义 Form(κ,λ)到 H(κ)的编码映射。首先,对于 L(κ,λ)的每个基本符号 s,我们按照以下方式分配一个代码对象 ⌈s⌉∈H(κ)。让{vξ: ξ < κ}是 L(κ,λ)的个体变量的枚举。
Symbol | Code Object | Notation |
¬ | 1 | ⌈¬⌉ |
∧ | 2 | ⌈∧⌉ |
∧ | 3 | ⌈∧⌉ |
∃ | 4 | ⌈∃⌉ |
∈ | 5 | ⌈ ∈ ⌉ |
= | 6 | ⌈=⌉ |
_v_ξ | ⟨0,ξ⟩ | ⌈_v_ξ⌉ |
然后,对于每个 φ ∈ Form(κ,λ),我们递归地分配代码对象 ⌈φ⌉ 如下:
⌈vξ = vη⌉ =df ⟨⌈vξ⌉, ⌈=⌉, ⌈vη⌉⟩,
⌈vξ ∈ vη⌉ =df ⟨⌈vξ⌉, ⌈∈⌉, ⌈vη⌉⟩;
对于 φ, ψ ∈ Form(κ,λ),
⌈φ ∧ ψ⌉ =df ⟨⌈φ⌉, ⌈∧⌉, ⌈ψ⌉⟩
⌈¬φ⌉ =df ⟨⌈¬⌉, ⌈φ⌉⟩
⌈∃_X_φ⌉ =df ⟨⌈∃⌉, {⌈ x ⌉: x ∈ X}, ⌈φ⌉⟩;
最后,如果 Φ ⊆ Form(κ,λ),其中|Φ| < κ,
⌈∧Φ⌉ =df ⟨⌈∧⌉, {⌈φ⌉: φ ∈ Φ}⟩.
映射 φ ↦ ⌈φ⌉ 从 Form(κ,λ) 到 H(κ) 很容易看出是一对一的,并且是所需的编码映射。因此,我们同意在这个编码映射下将 Val(L(κ,λ)) 与其在 H(κ) 中的像等同起来。
什么时候 Val(L(κ,λ)) 是 H(κ) 的可定义子集?为了回答这个问题,我们需要以下定义。
如果一个 L-公式等价于一个所有量词都是形如 ∀x∈y 或 ∃x∈y(即,∀x(x∈y → …) 或 ∃x(x∈y ∧ …))的公式,则它被称为 Δ0-公式。如果一个 L-公式等价于一个可以由原子公式及其否定使用逻辑运算符 ∧、∨、∀x∈y、∃x 构建的公式,则它是一个 Σ1-公式。如果集合 A 的子集 X 可以由 L-结构 ⟨A, ∈ ⨡ A⟩ 中的一个 Δ0-(或 Σ1-)公式定义,则称 X 在 A 上是 Δ0(或 Σ1)的。
例如,如果我们以通常的方式将自然数集与继承有限集合 H(ω)等同起来,那么对于每个 X ⊆ H(ω),我们有:
X 在 H(ω)上是 Δ0 ⇔ X 是递归的
X 在 H(ω)上是 Σ1 ⇔ X 是可递归枚举的。
因此,Δ0-集合和 Σ1-集合的概念可以被视为递归集合和可递归集合的概念的推广。
对于 L 的完备性定理意味着 Val(L)(被视为 H(ω)的子集)是可递归的,因此在 H(ω)上是 Σ1 的。类似地,对于 L(ω1,ω)的完备性定理(见 §2)意味着 Val(L(ω1,ω))(被视为 H(ω1)的子集)在 H(ω1)上是 Σ1 的。然而,当达到 L(ω1,ω1)时,这种令人愉快的情况完全崩溃。因为可以证明
斯科特的 L(ω1,ω1)不可定义定理。Val(L(ω1,ω1))在 H(ω1)中甚至不能被 L(ω1,ω1)-公式定义;因此,更不用说 Val(L(ω1,ω1))在 H(ω1)上是 Σ1 的了。
这个定理的证明方式与众所周知的结果相同,即算术的二阶语言 L2 的有效句子(代码)集合在其编码结构 ℕ 中不是二阶可定义的。为了得到这个后一结果,首先观察到 ℕ 可以由一个单一的 L2 句子来表征,然后证明如果这个结果是假的,那么对于 L2 句子来说,“在 ℕ 中的真实性”可以由一个 L2 公式来定义,从而违反了塔斯基关于真实性不可定义性的定理。
因此,为了沿着上述思路证明斯科特的不可定义性定理,需要建立以下内容:
(4.1) 在 L(ω1,ω1)中,编码结构 H(ω1)的可表征性:存在一个 L(ω1,ω1)句子 τ0,对于所有的 L-结构 A,A ⊨ τ0 ⇔ A ≅ H(ω1)。
(4.2) 在编码结构中,L(ω1,ω1)-句子的真理无法定义:不存在 L(ω1,ω1)-公式 φ(v0),使得对于所有 L(ω1,ω1)-句子 σ,H(ω1) ⊨ σ↔φ(⌈σ⌉)。
(4.3) 存在一个 L(ω1,ω1)的项 t(v0, v1),对于 L(ω1,ω1)的每一对句子 σ、τ,H(ω1) ⊨ [t(⌈σ⌉,⌈τ⌉) = ⌈σ → τ⌉]。
(4.1) 通过分析 H(ω1)的集合论定义,并展示它可以在 L(ω1,ω1)中“内部”表述来证明。(4.2)与塔斯基关于一阶或二阶语言中真理无法定义的定理的证明方式类似。(4.3)通过形式化编码映射的定义 σ ↦ ⌈σ⌉ 在 L(ω1,ω1)中获得。
武装着这些事实,我们可以通过以下方式得到斯科特的不可定义性定理。假设它是错误的;那么将存在一个 L(ω1,ω1)-公式 θ(v0),对于所有的 L(ω1,ω1)-句子 σ,
(4.4) H(ω1) ⊨ θ(⌈σ⌉) 当且仅当 σ ∈ Val(L(ω1,ω1))。
让 τ0 是(4.1)中给出的句子。那么对于所有的 L(ω1,ω1)-句子 σ,我们有,
H(ω1) ⊨ σ 当且仅当 (τ0 → σ) ∈ Val(L(ω1,ω1)),
所以,根据 (4.4),
H(ω1) ⊨ σ 当且仅当 H(ω1) ⊨ θ(⌈τ0 → σ⌉).
如果 t 是(4.3)中给定的术语,则会得出以下结论
H(ω1) ⊨ σ↔θ(t(⌈τ0⌉, ⌈σ⌉)).
现在将 φ(v0)写为 L(ω1,ω1)-公式 θ(t(⌈τ0⌉, ⌈σ⌉)). 然后
H(ω1) ⊨ σ↔φ(⌈σ⌉),
与(4.2)相矛盾,并完成证明。
因此,Val(L(ω1,ω1))甚至不能被一个 L(ω1,ω1)-公式定义,所以 a fortiori L(ω1,ω1)是不完备的。类似的论证表明,当 ω1 被任何后继基数 κ+替换时,Scott 的不可定义定理仍然成立;因此,语言 L(κ+,κ+)都是不完备的。[7]
5. L(ω1,ω)的子语言和 Barwise 紧致性定理
鉴于我们对无穷语言的现有了解,似乎只有 L(ω1,ω)表现得相对良好。另一方面,紧致性定理在 L(ω1,ω)中无法以任何有用的方式推广,这对于应用而言是一个严重的缺点。让我们试图更详细地分析这个失败。
请回忆第 4 节中,我们可以将一阶语言 L 的公式编码为继承有限集,即作为 H(ω)的成员。在这种情况下,每个有限集合的(编码的)L-句子也是 H(ω)的成员,由此可得 L 的紧致性定理可以表述为:
(5.1) 如果 Δ ⊆ Sent(L)满足每个子集 Δ0 ⊆ Δ,Δ0 ∈ H(ω)都有一个模型,那么 Δ 也有一个模型。
现在众所周知,(5.1)是 L 的广义完备性定理的直接推论,该定理以类似于(5.1)的形式陈述,变成了如下断言:
(5.2) 如果 Δ ⊆ Sent(L)和 σ ∈ Sent(L)满足 Δ ⊨ σ,那么存在一个从 Δ 推导出 σ 的推导 D,使得 D ∈ H(ω)。[ 8]
在第 2 节中,我们指出了 L(ω1,ω)的紧致性定理非常强烈地失败了;事实上,我们构造了一个集合 Γ ⊆ Sent(ω1,ω),使得
(5.3) Γ 的每个可数子集都有一个模型,但 Γ 本身没有。
还要记住,我们引入了 L(ω1,ω)中的演绎概念;由于这样的演绎是可数长度的,根据(5.3),很快就可以得出结论。
(5.4) 存在一个句子[9] σ ∈ Sent(ω1,ω),使得 Γ ⊨ σ,但在 L(ω1,ω) 中没有 σ 的推导。
现在,L(ω1, ω) 的公式可以编码为 H(ω1) 的成员,并且很明显 H(ω1) 在可数子集和序列的形成下是封闭的。因此,(5.3) 和 (5.4) 可以写成:
(5.3 bis) 对于每个 Γ0 ⊆ Γ,使得 Γ0 ∈ H(ω1) 有一个模型,但 Γ 没有;
(5.4 bis) 存在一个句子 σ ∈ Sent(ω1,ω),使得 Γ ⊨ σ,但不存在一个推导 D ∈ H(ω1),从 Γ 推导出 σ。
由此可见,当“L”被替换为“L(ω1,ω)”,“H(ω)”被替换为“H(ω1)”时,(5.1)和(5.2)失效。此外,可以证明在(5.3 bis)和(5.4 bis)中,集合 Γ ⊆ Sent(ω1,ω) 可以取为 H(ω1) 上的 Σ1。因此,即使对于 L(ω1, ω)-句子的 Σ1-集合,紧致性和广义完备性定理也会失败。
从(5.4 bis)中我们可以看出,广义完备性定理在 L(ω1,ω) 中的 Σ1-集合上失败的原因是,粗略地说,H(ω1) 在从 H(ω1) 的 Σ1-句子集合推导出的推导形成中不是“闭合”的。因此,为了解决这个问题,似乎自然地将 H(ω1) 替换为一些在这种推导形成中是“闭合”的集合 A,然后只考虑那些代码在 A 中的公式。
现在我们简要介绍如何完成这个任务。
首先,我们将 L(ω1,ω)的符号和公式与 H(ω1)中的代码进行对应,就像第 4 节中所述。对于每个可数传递的[10]集合 A,令
L_A_ = Form(L(ω1,ω)) ∩ A.
我们说如果满足以下条件,LA 是 L(ω1,ω)的子语言:
L ⊆ L_A_
如果 φ,ψ ∈ LA,则 φ ∧ ψ ∈ LA 且 ¬φ ∈ LA
如果 φ ∈ 逻辑学 A 且 x ∈ A, 那么 ∃xφ ∈ 逻辑学 A
如果 φ(x) ∈ 逻辑学 A 且 y ∈ A, 那么 φ(y) ∈ 逻辑学 A
如果 φ ∈ 逻辑学 A, φ 的每个子公式都在 逻辑学 A 中
如果 Φ ⊆ LA 且 Φ ∈ A,则 ∧Φ ∈ LA。
在逻辑学中,推导的概念以惯例方式定义;如果 Δ 是 LA 的一组句子且 φ ∈ LA,则在逻辑学中,从 Δ 中推导出 φ 的推导是指从 L(ω1, ω)中的 Δ 中推导出 φ 的推导,其中每个公式都在 LA 中。我们说 φ 在 LA 中从 Δ 可推导出来,如果存在一个在 LA 中从 Δ 中推导出 φ 的推导 D;在这些条件下,我们写作 Δ ⊢A φ。一般来说,D 不会是 A 的成员;为了确保在 A 中可以找到这样的推导,需要对 A 施加进一步的条件。
设 A 是一个可数的传递集,使得 LA 是 L(ω1, ω)的一个子语言,并且 Δ 是 LA 的一组句子。我们说 A(或者滥用术语,LA)是 Δ-闭的,如果对于任何 LA 的公式 φ,使得 Δ ⊢A φ,存在一个从 Δ 中推导 φ 的推导 D,使得 D ∈ A。可以证明,对于任意 Δ,唯一的可数语言是 Δ-闭的,即 A = H(ω)。然而,J. Barwise 发现存在一些可数集合 A ⊆ H(ω1),其对应的语言 LA 与 L 不同,但对于所有 Σ1-句子集 Δ,它们都是 Δ-闭的。这样的集合 A 被称为可接受集;粗略地说,它们是继承有限集的扩展,其中递归论和证明论仍然可行(完整定义见下面的第 5.1 节)。
从巴尔维斯的结果中,我们立即得到了巴尔维斯紧致性定理。
设 A 是一个可数的可接受集合,Δ 是一个在 A 上为 Σ1 的 LA 句子集合。如果对于每个 Δ′ ⊆ Δ,满足 Δ′ ∈ A 的话,都有一个模型,那么 Δ 也有一个模型。
这里的“Σ1”的存在表明这个定理是对可递归可枚举句子集合的紧致性定理的推广。
另一个版本的 Barwise 紧致性定理,用于构建集合论模型,如下所示。设 ZFC 是 Zermelo-Fraenkel 集合论的通常公理集,包括选择公理。那么我们有:
5.5 定理。设 A 是一个可数的传递集,使得 A = ⟨A, ∈ ⨡ A⟩ 是 ZFC 的一个模型。如果 Δ 是 LA 中由集合论语言的公式在 A 中可定义的句子集合,并且对于每个 Δ′ ⊆ Δ,使得 Δ′ ∈ A 有一个模型,那么 Δ 也有一个模型。
最后,我们给出这个定理的一个简单应用。设 A = ⟨A, ∈ ⨡ A⟩ 是 ZFC 的一个模型。如果模型 B = ⟨B, E⟩ 是 ZFC 的一个适当的端扩展,那么满足以下条件:(i) A ⊆ B,(ii) A ≠ B,(iii) a ∈ A,b ∈ B,bEa ⇒ b∈A。因此,ZFC 模型的适当端扩展是一个适当的扩展,在这个扩展中没有“新”的元素出现在任何“旧”的元素之前。作为我们对 5.5 的应用,我们证明
5.6 定理. ZFC 的每个可数传递模型都有一个适当的无穷扩展。
证明. 设 A = ⟨A, ∈ ⨡ A⟩ 是 ZFC 的一个传递模型,L 是集合论的一阶语言,增加了每个 a ∈ A 的名字 a 和一个额外的常量 c。设 Δ 是由以下 LA 句子组成的集合:
ZFC 的所有公理;
c ≠ a,对于每个 a ∈ A;
∀x(x ∈ a → ∨b∈a x = b),对于每个 a ∈ A;
a ∈ b,对于每个 a ∈ b ∈ A。
易见,Δ 是 A 的一个子集,该子集可以通过集合论语言的一个公式在 A 中定义。此外,对于每个满足 Δ′ ∈ A 的子集 Δ′ ⊆ Δ,都存在一个模型。对于所有属于 A 的 a ∈ A 的集合 C,其中 a 出现在 Δ′中,因为 Δ′属于 A,所以如果我们将 c 解释为集合 A − C 中的任意成员,则 A 是 Δ′的一个模型。因此,(5.5)意味着 Δ 有一个模型 ⟨B,E⟩。如果我们将每个常量 a 解释为元素 a ∈ A,则 ⟨B,E⟩ 是 A 的一个适当的终结扩张。证明完成。
读者很快会发现,一阶紧致性定理无法得出这个结果。
5.1 可接受集概念的定义
当满足以下条件时,非空的传递集合 A 被称为可接受的:
如果 a,b ∈ A,则{a,b} ∈ A 且 ∪A ∈ A;
如果 a ∈ A 且 X ⊆ A 在 A 上是 Δ0 的,则 X ∩ a ∈ A;
如果 a ∈ A,X ⊆ A 在 A 上是 Δ0 的,并且 ∀x∈a∃y(< x,y> ∈ X),那么,对于某个 b ∈ A,∀x∈a∃y∈b(< x,y> ∈ X)。
条件(ii)—— Δ0-分离方案 —— 是策梅洛分离公理的一个受限版本。条件(iii)——一个类似削弱的替换公理 —— 可以称为 Δ0-替换方案。
很容易看出,如果 A 是一个传递集,使得 < A, ∈ | A> 是 ZFC 的一个模型,那么 A 是可接受的。更一般地,当从 ZFC 中省略幂集公理时,该结果仍然成立,因此 H(ω) 和 H(ω1) 都是可接受的。然而,由于后者是不可数的,巴尔维斯紧致性定理不适用于它。
6. 历史和文献评论
§§1 和 2. 无穷命题和谓词语言似乎是在 Scott 和 Tarski [1958]以及 Tarski [1958]的论文中首次明确出现在印刷物上。Karp [1964]证明了 L(ω1,ω)的完备性定理,以及其他无穷语言的完备性定理。Morley [1965]首次对 L(ω1,ω)的 Hanf 数进行了计算。Karp [1965]和 Lopez-Escobar [1966]证明了有限量词语言中无法定义良序关系。Lopez-Escobar [1965]证明了 L(ω1,ω)的插值定理,而 Scott [1965]证明了 L(ω1,ω)的同构定理。Negri [2021]将几何逻辑的思想扩展到了 L(ω1,ω)中,该思想起源于拓扑学。
Karp [1965]首次证明了 Karp 的部分同构定理;另请参阅 Barwise [1973]。结果(2.2)出现在 Chang [1968]中,结果(2.3)出现在 Ellentuck [1976]中,结果(2.4)出现在 Bell [1981]中。
§3. 结果(3.2)和(3.3)归功于 Hanf [1964],Lopez-Escobar [1966]和 Dickmann [1975]进行了一些改进,而(3.4)是由 Tarski 证明的。结果(3.5)归功于 Scott [1961],(3.6)归功于 Bell [1970]和[1972],而(3.7)归功于 Bell [1974]。可测基数首先由 Ulam [1930]和 Tarski [1939]考虑。可测基数是弱紧的事实在 Tarski [1962]中被注意到。
§4. 关于 L(ω1,ω1)的不可定义定理。Carol Karp 在 1964 年的一篇论文中指出:“在 1960 年斯坦福大学举办的逻辑、方法论和科学哲学国际大会上,Dana Scott 传播了一份关于在(γ+, γ+)语言中不存在完全可定义形式系统的证明大纲,该语言除了等号符号外还有一个二元谓词符号。”Scott 从未发表过他的结果,而详细的证明首次出现在 Karp [1964]中。本文采用的定理方法基于 Dickmann [1975]的解释。
§5. 本节中所提出的结果的最初动机来自 Kreisel;在他的[1965]中,他指出仅仅基于“长度”选择无穷公式没有令人信服的理由,并提议采用可定义性或“闭包”标准。Kreisel 的建议被 Barwise [1967]非常成功地采纳,他证明了紧致性定理。可接受集合的概念归功于 Platek [1966]。定理(5.6)取自 Keisler [1974]。
有关无穷语言的进一步阅读,请参阅 Aczel [1973],Dickmann [1975],Karp [1964],Keisler [1974]和 Makkai [1977]。关于无穷语言与大基数之间的联系的有用解释可以在 Drake [1974]的第 10 章中找到。
Bibliography
Aczel, P., 1973, “Infinitary Logic and the Barwise Compactness Theorem”, Proceedings of the 1971 Bertrand Russell Memorial Logic Conference (Uldum, Denmark), J. Bell, J. Cole, G. Priest, and A. Slomson (eds.), Leeds: Bertrand Russell Memorial Logic Conference, 234–277.
Barwise, J., 1967, Infinitary Logic and Admissible Sets. Ph.D. Thesis, Stanford University.
–––, 1973, “Back and Forth through Infinitary Logic. Studies in Model Theory”, in Studies in Mathematics (Volume 8), Buffalo: Mathematical Association of American, pp. 5–34.
–––, 1975, Admissible Sets and Structures, Berlin: Springer-Verlag.
Barwise, J. and S. Feferman (eds.), 1985, Handbook of Model-Theoretic Logics, New York: Springer-Verlag.
Baumgartner, J., 1974, “The Hanf number for complete Lω1,ω sentences (without GCH)”, Journal of Symbolic Logic, 39: 575–578.
Bell, J. L., 1970, “Weak Compactness in Restricted Second-Order Languages”, Bulletin of the Polish Academy of Sciences, 18: 111–114.
–––, 1972, “On the Relationship between Weak Compactness in Lω1, ω, Lω1, ω1, and Restricted Second-Order Languages”, Archive for Mathematical Logic, 15: 74–78.
–––, 1974, “On Compact Cardinals”, Zeitschrift für Mathematical Logik und Grundlagen der Mathematik, 20: 389–393.
–––, 1981, “Isomorphism of Structures in S-toposes”, Journal of Symbolic Logic, 43 (3): 449–459.
Chang, C.C., 1968, “Some Remarks on the Model Theory of Infinitary Languages”. in The Syntax and Semantics of Infinitary Languages (Lecture Notes in Mathematics: Volume 72), J. Barwise (ed.), Springer-Verlag, Berlin, 36-63.
Dickmann, M. A., 1975, Large Infinitary Languages, Amsterdam: North-Holland.
Drake, F.R., 1974, Set Theory: An Introduction to Large Cardinals, Amsterdam: North-Holland Publishing Company.
Ellentuck, E., 1976, “Categoricity Regained”, Journal of Symbolic Logic, 41 (3): 639–643.
Hanf, W. P., 1964, Incompactness in Languages with Infinitely Long Expressions, Amsterdam: North-Holland.
Karp, C., 1964, Languages with Expressions of Infinite Length, Amsterdam: North-Holland.
–––, 1965, “Finite-Quantifier Equivalence” in The Theory of Models, J. Addison, L. Henkin, and A. Tarski (eds.), Amsterdam: North-Holland, 407–412.
Keisler, H. J., 1974, Model Theory for Infinitary Logic, Amsterdam: North-Holland.
Keisler, H. J., and Julia F. Knight, 2004, “Barwise: Infinitary Logic And Admissible Sets”, Journal of Symbolic Logic, 10(1): 4–36
Kolaitis, P. and M. Vardi, 1992, “Fixpoint Logic vs. Infinitary Logic in Finite-Model Theory,” Proceedings of the Seventh Annual IEEE Symposium on Logic in Computer Science (LICS '92), IEEE, pp. 46-57; available online, doi:10.1109/LICS.1992.185518
Kreisel, G., 1965, “Model-Theoretic Invariants, Applications to Recursive and Hyperarithmetic Operations”, in The Theory of Models, J. Addison, L. Henkin, and A. Tarski (eds.), Amsterdam: North-Holland, 190-205.
Kueker, D., 1975, “Back-and-forth arguments in infinitary languages”, in Infinitary Logic: In Memoriam Carol Karp (Lecture Notes in Mathematics: Volume 492), D. Kueker (ed.), Berlin: Springer-Verlag.
Lopez-Escobar, E. G. K., 1965, “An Interpolation Theorem for Infinitely Long Sentences”, Fundamenta Mathematicae, 57: 253–272.
–––, 1966, “On Defining Well-Orderings”, Fundamenta Mathematicae, 59: 13–21.
Makkai, M., 1977, “Admissible Sets and Infinitary Logic”, Handbook of Mathematical Logic, J. Barwise (ed.), Amsterdam: North-Holland, 233-282.
Morley, M., 1965, “Omitting Classes of Elements”, The Theory of Models, J. Addison, L. Henkin, and A. Tarski (eds.), Amsterdam: North-Holland, 265-273.
Nadel, M., 1985, “Lω1,ω and Admissible Fragments”, in J. Barwise and S. Feferman (eds.) 1985, 271–287.
Negri, Sara, 2021, “Geometric Rules in Infinitary Logic”, in O. Arieli and A. Zamansky (eds.), Arnon Avron on Semantics and Proof Theory of Non-Classical Logics, Cham: Springer, 265–293. doi:10.1007/978-3-030-71258-7_12
Platek, R., 1966, Foundations of Recursion Theory, Ph.D. Thesis, Stanford University.
Scott, D., 1961, “Measurable Cardinals and Constructible Sets”, Bulletin of the Academy of Polish Sciences, 9: 521–524.
–––, 1965, “Logic with Denumerably Long Formulas and Finite Strings of Quantifiers”, The Theory of Models, J. Addison, L. Henkin, and A. Tarski (eds.), Amsterdam: North-Holland, 329-341.
Scott, D., and A. Tarski, 1958, “The sentential calculus with infinitely long expressions”, Colloquium Mathematicum, 16: 166–170.
Shelah, Saharon, 2012, “Nice infinitary logics”, Journal of the American Mathematical Society, 25: 395-427, available online, doi:10.1090/S0894-0347-2011-00712-1
Tarski, A., 1939, “Ideale in völlständingen Mengenkörpern I”, Fundamenta Mathematicae, 32: 140–150.
–––, 1958, “Remarks on predicate logic with infinitely long expressions”, Colloquium Mathematicum, 16: 171–176.
–––, 1962, “Some problems and results relevant to the foundations of set theory”, in E, Nagel, P. Suppes and A. Tarski (eds.), Logic, Methodology and Philosophy of Science, Stanford: Stanford University Press, 123-135.
Ulam, S., 1930, “Zur Masstheorie in der algemeinen Mengenlehre”, Fundamenta Mathematicae, 16: 140–150.
Academic Tools
Look up topics and thinkers related to this entry at the Internet Philosophy Ontology Project (InPhO). | |
Enhanced bibliography for this entry at PhilPapers, with links to its database. |
Other Internet Resources
A Primer on Infinitary Logic, by David Marker (Mathematics, Statistics, and Computer Science, University of Illinois/Chicago).
Related Entries
Boolean algebra: the mathematics of | category theory | logic: classical
最后更新于