跳转至

一阶语言的语法和语义(Syntax and Semantics of First-order Languages)

翻译须知

在这一节当中,出现的新名词的翻译对照表如下:

名词 翻译
expression 表达式
term
formula 公式

语法部分

数学结构

对于一个数学结构,我们常常能将其抽象为:非空集 \(A\) 以及其直积 \(R\subseteq A^k\) ,它们之间还可能有关系(可以表为集合直积),同时也会有一些确定的函数:\(F:A^k\to A\) ,常量与元素 \(a\in A\) 等等......
我们写为:

\[ \mathfrak{A} = \left\lbrace A,R,S,\cdots,F,G,\cdots,a,b,\cdots \right\rbrace \]

其中 \(\mathfrak{A}\) 为哥特体的 \(A\)\(\LaTeX\) 代码为 \mathfrak{A} .

我们不妨举例:

数学结构的例子

  1. 最简单的结构是简单的集合 \(A\) ,没有关系、函数和不同的元素.
  2. 最常见的关系往往是二元关系 \(R\subseteq A\times A\) ,例如,\((\omega,<_{\omega})\) 就是自然数集的自然排列关系.

对于二元关系,这里将偏序关系和全序关系阐述一下. 注意在其他的教材中,\(a\)\(b\) 有关系 \(R\) 可能写为 \(aRb\) ,但是这里我们写为序对的形式 \((a,b)\) .

定义:偏序 (Partial Order)

给定一个集合 \(X\) ,考虑该集合上一个关系(Relation) \(R\) ,如果满足以下条件:

  1. 对于任意的 \(x\in X\) ,都有 \((x,x)\in R\) (自反性);
  2. 对任意的 \(x,x'\in X\) ,如果 \((x,x')\in R, (x',x)\in R\) ,那么 \(x= x'\) (反对称性).
  3. 对任意的 \(a,b,c\in X\) ,如果 \((a,b)\in R, (b,c)\in R\) ,那么 \((a,c)\in R\) (传递性).

那么就称 \(R\)偏序关系.

对于任意的数学结构 \(\mathfrak{A} = (A,R)\) ,如果 \(R\) 是偏序关系,则 \(\mathfrak{A}\) 称为偏序的 (Partial Ordering) .

定义:全序集 (Chain/Totally Ordered Set)

对于一个偏序集 \((X,\leqslant)\) ,我们称其为全序集,如果对于任意两个元素 \(x,x'\) 必有 \(x\leqslant x'\)\(x'\leqslant x\) 成立.

如果 \(\mathfrak{A} = (A,R)\)\(R\) 为全序关系,则 \(\mathfrak{A}\) 称为线序全序的 (Linear Ordering or Total)

仅在传递性的基础上,如果对于任意的 \(a\in A\)\((a,a)\not\in R\) ,则称 \(\mathfrak{A}\)严格线序的.

但是现在,我们还没有对 \(\mathfrak{A}\) ,也就是数学结构作一个明确的定义,我们需要借助以前的一些内容进行定义.

一阶逻辑语言

定义:一阶逻辑语言

一个一阶语言 \(L\) 通常由如下的符号表示

  1. 集合 \(\mathrm{Rs}_L\) ,表示 \(L\)-关系 符号 (\(\mathrm{Rs}\) 即为 Relation Symbol);
  2. 集合 \(\mathrm{Fs}_L\) ,表示 \(L\)-函数 符号(\(\mathrm{Fs}\) 即为 Function Symbol);
  3. 集合 \(\mathrm{Cs}_L\) ,表示 \(L\)-常值 符号 (\(\mathrm{Cs}\) 即为 Constant Symbol).
  4. 元数 (Arity) 函数:\(\nu: \mathcal{R}\cup \mathcal{F}\to \mathbb{N}^*\) ,它指定了所有关系符号和函数符号的元数.

上述符号称为非逻辑符号,\(\mathrm{Rs}_L,\mathrm{Fs}_L,\mathrm{Cs}_L\) 是两两不交的,除上述非逻辑符号(或称 initial symbol ,初始符号)外,我们还需要逻辑的符号.

  1. 变元符号(可数集合): \(\mathrm{Vb} = \left\lbrace v_n: n\in \omega \right\rbrace\) ( Variable ).
  2. 等值符号 \(=\) .
  3. 连接词 \(\neg\)\(\lor\) .
  4. 存在量词:\(\exists\) .

连接词我们选择之前我们证明完备的两个连接词. 量词实际上选择任意 \(\forall\) 和存在 \(\exists\) 都是 OK 的,只不过这里我们选择了存在 \(\exists\) .

我们熟悉的一些符号实际上能通过这些符号导出:

\[ \begin{aligned} (x\neq y ) &:= \neg(x =y ) \\ \forall x \varphi &:=\neg \exists x (\neg \varphi) \\ (x\land y) &:= \neg (\neg x\lor \neg y) \\ (x\to y ) &:= \neg x\lor y \end{aligned} \]

同时,等值符号在教材上采用

\[ \dot{=} \]

这个符号,但是为了简化表达,在不混淆的情况下(在之后的定义当中出现基本表达等值符号的含义)还是采用 \(=\) 符号.

实际上,在中文教材当中,有时也能学到如下的两个定义:

一阶逻辑语言定义补充

逻辑符号添加如下两种:

  1. 语法逗号: ,
  2. 语法括号:( 和 )

这两个定义补充的出现是中缀表达式固有问题的体现,因为它无法避免括号的使用.

我们在今后,为简洁起见,我们不认为这两个在定义当中,但是在书写中缀表达式的时候,为了表达的简洁,还是会写上述两个符号.

一阶逻辑语言示例

  1. 语言 \(L_=\)\(\mathrm{Rs}_{L_=}=\mathrm{Fs}_{L_=} = \mathrm{Cs}_{L_=} = \varnothing\)\(L_=\) 没有非逻辑符号. 因此在后续书写公式的时候只能使用变量符号.
  2. 群论自然语言的符号是 \(L_G\) ,它有非逻辑符号 \(\dot{*}\)\(\dot{^{-1}}\)\(\dot{e}\) , 其中 \(\dot{*}\) 是群论中的二元运算符,是二元函数,\(\dot{^{-1}}\) 是逆元函数,是一元函数. 而 \(\dot{e}\) 是幺元符号. 环论类似,符号为 \(L_R\) .
  3. 一阶算数理论当中,对应的逻辑语言是 \(L_\Omega\) ,它有如下的部分:\(\mathrm{Rs}_{L_{\Omega}} = \left\lbrace \dot{<} \right\rbrace; \mathrm{Fs}_{L_\Omega} = \left\lbrace \dot{+},\dot{\times},\dot{\mathrm{S}} \right\rbrace; \mathrm{Cs}_{L_{\Omega}} = \left\lbrace \dot{0} \right\rbrace\) 其中,\(\dot{\mathrm{S}}\) 为后继函数. 例如,在自然数当中,\(\dot{\mathrm{S}}(n) = n+1\) ,也可以在其他的集合中定义,例如 \(\mathbb{Z}_5\) 当中,可以规定 \(\dot{\mathrm{S}}(\overline{4}) = \overline{0}\) . 这主要看全域规定为什么

\(L\)-项

首先定义 \(L\)-原子项 (atomic term) ,它是一个包含了一个符号的表达式且这个符号要么是常量,要么是变量.

也就是说,称 \(\varphi\) 为一个 \(L\)-原子项当且仅当其唯一符号满足:

\[ \varphi\in \mathrm{Cs}_L\cup \mathrm{Vb}_L \]

定义:\(L\)-项

\(L\)-项的集合 \(\mathrm{Te}_L\) 是满足如下条件的最小 \(L\)-表达式集合:

  1. 每一个 \(L\)-原子项都是 \(L\)-项.
  2. 对于任意 \(L\)-函数符号 \(f\) 和任意 \(L\)-项 \(t_0,\cdots,t_{\nu_L(f)-1}\) ,都有 \(ft_0\cdots t_{\nu_L(f)-1}\) 是一个 \(L\)-项. (也就是 \(f\) 作用于这 \(\nu_L(f)\) 个变量生成 \(L\)-项)

此时定义好了之后我们已经能明白 \(L\)-项的构成了,它是常量和变量在函数的作用下生成的公式. 以前我们学到的种种运算都可以理解为函数.

\(L\)-项的唯一可读性

和以前的 \(L\)-语句一样,\(L\)-项也应该有唯一可读性,否则将会出现歧义.

命题:\(L\)-项的唯一可读性

对于每一个 \(L\)-项 \(t\) ,一定满足如下性质中的其中一个:

  1. \(t\)\(L\)-原子项.
  2. 存在 \(L\)-函数符号 \(f\)\(L\)-项 \(u_0,\cdots,u_{\nu_L(f)-1}\) ,有 \(t\)\(fu_0\cdots u_{\nu_L(f)-1}\).

更进一步,第二个性质当中,\(f\)\(u_k\) 都是唯一确定的.

(此处在教材上留作习题,在此挖坑). \(\square\)

我们对唯一可读性再举几个例子,在群论当中,二元运算符记为 \(\dot{*}\) ,对群 \(G\) 中的元素 \(x,y\)

\[ (x\dot{*}y)^{-1} \]

不会产生歧义,它是 \(x\)\(y\) 进行二元运算作用之后取逆元. 写为前缀表达式为 \(\dot{^{-1}}\dot{*}xy\) . 一般地,\(L_G\) 中的 \(L\)-项总能写为:

\[ x_0^{\pm 1}\dot{*} \cdots \dot{*} x_k^{\pm 1} \]

这就是唯一可读性的一个体现.

\(L\)-公式

\(L\)-原子公式

我们在定义 \(L\)-项的时候,实际上只有变量、常量以及函数,那么原来的关系符号和逻辑符号去哪了?我们需要把这些也纳入到体系当中.

我们来谈公式 (formula) 的概念,自小到大,我们学到的公式都形如:

\[ \cdots \overset{?}\sim \cdots \]

这里面 \(\sim\) 代表一种关系,大部分学到的公式都是等号,表示出一个运算的相等关系,也有类似群同态基本定理这样的公式:

\[ G / \mathrm{Ker}(G) \simeq \mathrm{Im}(G) \]

没有关系的公式实际上就是草稿纸上的运算过程而已,给不了我们什么信息,所以公式的存在必须要有关系符号.

定义:\(L\)-原子公式 (\(L\)-atomic formulas)

\(L\)-原子公式的集合 \(\mathrm{AtFm}_L\) 是所有满足如下条件的 \(L\)-表达式的集合(其中的表达式是如下的某种形式):

  1. \(=tu\) ,其中 \(t\)\(u\)\(L\)-项.
  2. \(pt_0\cdots t_{\nu_L(p)-1}\) ,其中 \(p\in \mathrm{Rs}_L\)\(t_0,\cdots,t_{\nu_L(p)-1}\)\(L\)-项.

其中的 \(=tu\) 是前缀表达式. 而 \(p\) 在为二元关系符时,由于偏序关系等特殊关系的存在,我们不写 \(< tu\) 而写 \(t<u\) .

举例:

  1. \(L_=\) 中的 \(L\)-原子公式只有 \(x=y\) 的形式,其中 \(x,y\) 为变量.
  2. 在一阶算数语言 \(L_\Omega\) 中,公式的形式为 \(t=u\)\(t\dot{<}u\) ,例如公式:\(\dot{\mathrm{S}}x\dot{+}y=\dot{\mathrm{S}}(x\dot{+}y)\) . 它表现了后继函数和加法之间的关系.

\(L\)-公式与其唯一可读性

定义:\(L\)-公式 (\(L\)-formula)

\(L\)-公式的集合 \(\mathrm{Fm}_L\) 是满足以下条件的最小的 \(L\)-表达式集合:

  1. 每一个 \(L\)-原子公式都是 \(L\)-公式;
  2. 如果 \(\varphi\)\(\psi\)\(L\)-公式,那么 \(\neg \varphi\)\(\lor \varphi \psi\) 都是 \(L\)-公式;
  3. 如果 \(\varphi\)\(L\)-公式且 \(x\) 为变量,那么 \(\exists x \varphi\)\(L\)-公式.

这个概念的范围非常广,我们几乎可以处处找到例子.

在数学分析当中,集合为 \(\mathbb{R}\) ,定义两个关系符号为实数相等 \(=\) ,实数的小于关系 \(<\) (大于记为 \(>\) ,由于仅有记录的顺序问题,无需再次定义),函数符号 \(-\) 为两个实数的相减,绝对值 \(|\cdot|\) 为一元函数符号.

那么我们有如下的例子:

数列极限 \(\lim\limits_{n\to \infty}x_n=a\)\(\varepsilon-N\) 语言:
$$ \forall \varepsilon>0, \exists N> 0, \forall n>N, |x_n-a|<\varepsilon $$
是否为 \(L\)-公式?

在中缀表达式的表达下,这显然是公式,我们一个个提取它的成分:
\(\varepsilon,N,n,x_n\) 均为变元符号,\(a\) 为常值符号,\(|\cdot|\)\(-\) 为二元函数符号,\(<,>\) 是关系符号. \(\square\)

唯一可读性已经基本和之前的一致了:

定义:\(L\)-公式的唯一可读性

对于每个 \(L\)-公式 \(\theta\) ,总有以下一个结论成立:

  1. \(\theta\)\(L\)-原子公式;
  2. 存在 \(L\)-公式 \(\varphi\) 使得 \(\theta\)\(\neg \varphi\)
  3. 存在 \(L\)-公式 \(\varphi,\psi\) 使得 \(\theta\)\(\lor\varphi\psi\)
  4. 存在 \(L\)-公式 \(\varphi\) 和 变元 \(x\) 使得 \(\theta\)\(\exists x \varphi\)

更近一步,在 2~4 当中,\(\varphi\)\(\psi\) 还有 \(x\) 是唯一确定的.

例:外延公理

请写出 \(L\)-公式表述集合论中的外延公理:给定任意的集合 \(A,B\)\(A\) 等于 \(B\) 当且仅当给定任意 \(x\)\(x\in A\) 当且仅当 \(x\in B\) .

写为如下形式:

\[ [\neg \exists z (z\in x \land z\in y) \land \neg \exists z (z\in y \land \neg z \in x)] \to x=y \]

其中 \(\in\) 为二元关系符号. \(\square\)

由于我们没有作者那样想要把一切定义写为递归定义的执念,因此项递归定理 (Term Recursion Theorem) 和公式递归定理 (Formula Recursion Theorem) 就不阐述了.

\(L\) - 结构

经过了如此漫长的前置准备,我们终于可以严格定义一个数学结构了.

定义:\(L\)-结构

一个 \(L\)-结构 \(\mathfrak{A}\) 可以由以下的内容组成:

  1. 一个非空集合 \(A\) ,作为 \(\mathfrak{A}\)全域,记为 \(|\mathfrak{A}|\) .
  2. 关系集 \(\mathrm{Rs}_L\) 中的符号 \(p\) ,对应 \(\mathfrak{A}\) 中的一个关系 \(p^\mathfrak{A}\subseteq A^{\nu_L(p)}\).
  3. 函数集 \(\mathrm{Fs}_L\) 中的符号 \(f\),对应一个函数 \(f^{\mathfrak{A}}: A^{\nu_L(f)}\to A\) .
  4. 互异元素 \(\mathrm{Cs}_L\) 中的符号 \(c\) ,对应一个元素 \(c^\mathfrak{A}\in A\) .

我们利用一阶算数理论来说明这个定义:

\[ \Omega := (\omega,<,+,\times , \mathrm{Sc},0) \]

这里面,我们有:

  • 全域: \(\omega\)
  • 关系符号:\(<\)
  • 函数:
  • 二元:\(+,\times\)
  • 一元:\(\mathrm{Sc}:m\to m+1\) (后继函数)
  • 常量元素:\(0\)

需要注意的是,\(p^\mathfrak{A}\) 是一个集合,我们通常把满足关系 \(p\) 的序对称为属于 \(p^\mathfrak{A}\) . 例如 \(\mathbb{R}\) 中的小于关系:\(<\) ,有

\[ (1,2)\in p^\mathfrak{A}, (2,1)\notin p^{\mathfrak{A}} \]

语义部分

在定义了语法层面上的数学结构后,我们需要赋予这些对象意义,因此我们采用和命题逻辑相似的方法进行研究.

\(\mathfrak{A}\)-真值指派

定义:\(\mathfrak{A}\)-真值指派

对于任意的 \(L\)-结构 \(\mathfrak{A}\) ,一个 \(\mathfrak{A}\)-真值指派就是指一个函数 \(\alpha: \mathrm{Vb}\to A\) .

为什么要这么定义真值指派?这是由于在结构当中,只有变元所代表的东西是不确定的,例如在一阶算数语言 \(L_\Omega\) 当中,\(\dot{\mathrm{S}}0\) 是确定的,但是

\[ x+\dot{\mathrm{S}}0 \]

是不确定的,只有给定了 \(x\) 才能知道是什么含义.

为了解决这个的取值问题,首先我们需要给变元 \(x\) 赋值,这是 \(\alpha\) 做的事情,例如 \(\alpha(x)= 0\) .

然后,我们需要给项一个整体的指派,形式上可以写为

\[ V_{\mathfrak{A},\alpha}: \mathrm{Te}_L \to A \]

但是我们亲爱的作者 🤯 这个时候不喜欢这个符号,他要在后续的公式里面使用这个符号,因此他给出了一个这样的符号:我们记

\[ t = x+\dot{\mathrm{S}}0 \]

在给定了 \(\alpha\) 时,对项的真值指派写为 \(t^{\mathfrak{A}}[\alpha]\) ,表示结构 \(\mathfrak{A}\) 中的项 \(t\)\(\mathfrak{A}\)-真值指派 \(\alpha\) 下的取值.

当然,这也仅仅是符号上的一个新约定,我们还并没有解决项的取值的定义问题,因此我们需要下面的定义:

定义:\(L\)-项的取值

对于任意的 \(L\)-结构 \(\mathfrak{A}\) 和任意的 \(\mathfrak{A}\)-指派 \(\alpha\)

  1. 对于每个变元 \(x\)\(x^{\mathfrak{A}}[\alpha] = \alpha(x)\)
  2. 对于每个 \(c\in \mathrm{Cs}_L\)\(c^\mathfrak{A}[\alpha]=c^\mathfrak{A}\)
  3. 对于每个 \(f\in \mathrm{Fs}_L\)\(t_0,\cdots,t_{\nu_L(f)-1}\in \mathrm{Te}_L\),有
\[ (ft*0\cdots t*{\nu*L(f)-1})^\mathfrak{A}[\alpha] = f^{\mathfrak{A}}(t_0^\mathfrak{A}[\alpha],\cdots,t^{\mathfrak{A}}*{\nu_L(f)-1}[\alpha]). \]

简而言之,就是变元的取值由 \(\mathfrak{A}\)-指派 \(\alpha\) 决定,常值和真值指派无关,函数的取值等于它作用的这些 \(L\)-原子项的取值后 \(f\) 作用下的取值.

我们来看一个实例:

一阶算数语言的计算

给定 \(\alpha(x)=3\)\(\alpha(y)=7\) ,计算:
$$ (\dot{\mathrm{S}}x\times \dot{\mathrm{S}}\dot{\mathrm{S}}y)^\Omega [\alpha] $$

首先拆分函数,然后在分部计算即可:

\[ \begin{aligned} (\dot{\mathrm{S}}x\times \dot{\mathrm{S}}\dot{\mathrm{S}}y)^\Omega [\alpha] &= (\dot{\mathrm{S}}x)^\Omega [\alpha] \times (\dot{\mathrm{S}}\dot{\mathrm{S}}y)^\Omega [\alpha] \\ &=\mathrm{Sc}(\alpha(x))\times \mathrm{Sc}(\mathrm{Sc}(\alpha(y))) \\ &= \mathrm{Sc(3)}\times \mathrm{Sc}(\mathrm{Sc}(7)) = 4\times 9 = 36 \end{aligned} \]

\(\square\)

\(L\)-公式的取值

我们接下来讨论公式的取值时,我们使用的是真值指派 \(V_{\mathfrak{A},\alpha}\) ,因为在讨论一个公式的时候,我们常说的是某个公式是正确的还是错误的,所以取值也就是真假值.

定义:\(L\)-原子公式的取值

对于任意的 \(\mathfrak{A}\)\(\alpha\)

  1. 任意的 \(L\)-项 \(t\)\(u\) ,有 $$ V_{\mathfrak{A},\alpha}(t = u) = \begin{cases}\mathrm{T}, &\text{if }t^{\mathfrak{A}}[\alpha]=u^{\mathfrak{A}}[\alpha], \\ \mathrm{F}, &\text{otherwise}.\end{cases} $$
  2. 对任意的关系 \(p\in \mathrm{Rs}_L\)\(t_0,\cdots,t_{\nu_L(p)-1}\in \mathrm{Te}_L\)
\[ V*{\mathfrak{A},\alpha}(pt_0\dots t*{\nu*L(p)-1})= \begin{cases}\mathrm{T},&\text{if } (t_0^\mathfrak{A}[\alpha],\cdots,t^\mathfrak{A}*{\nu_L(p)-1}[\alpha])\in p^\mathfrak{A} \\ \mathrm{F},&\text{otherwise}.\end{cases} \]

最后就只剩下 \(L\)-公式了,这实际上也就是照搬命题逻辑部分的内容了,其中 \(\neg\)\(\lor\) 我们直接略去不表,仅说明一下存在量词即可.

再进行一个符号上的约定:约定 \(\alpha_{x\to a}\) 代表一个指派 \(\beta\) ,满足:

  • 变元为 \(x\) 时,\(\beta(x)=a\)
  • 变元不为 \(x\) ,而为其他任意变元 \(y\) ,都有 \(\beta(y) = \alpha(y)\) .

定义:\(L\)-公式的定义(部分)

对任意的结构 \(\mathfrak{A}\)\(\mathfrak{A}\)-指派 \(\alpha\) ,所有的 \(L\)-公式 \(\varphi\)\(\psi\) 和变元 \(x\) 有:

\[ V*{\mathfrak{A},\alpha}({\exists x \varphi}) := \begin{cases}\mathrm{T},&\text{if for some }a\in A, V*{\mathfrak{A},\alpha\_{x\to a}}(\varphi)=\mathrm{T} \\ \mathrm{F}, &\text{otherwise}.\end{cases} \]

在命题逻辑当中,我们曾经使用过符号 \(\mid\!\equiv\) ,我们在一阶语言当中也使用类似的记号 \(\models\) . 我们使用如下的记号:

\[ \underset{\mathfrak{A}}{\models}\varphi[\alpha] \]

下面给出定义:

定义:\(\mathfrak{A}\)-指派满足 (satisfies) 语句

对于任意的 \(\mathfrak{A}\), \(\alpha\)\(\varphi\)

  1. \(\underset{\mathfrak{A}}{\models}\varphi[\alpha]\) 当且仅当 \(V_{\mathfrak{A},\alpha}(\varphi)=\mathrm{T}\) ,称 \(\alpha\) 满足 (satisfies) \(\mathfrak{A}\) 中的 \(\varphi\).
  2. \(\underset{\mathfrak{A}}{|\!\!\!\neq}\ \varphi[\alpha]\) 当且仅当 \(V_{\mathfrak{A},\alpha}(\varphi)=\mathrm{F}\) .

然后就是简单的一些命题:

  • \(\underset{\mathfrak{A}}{|\!\!\!\neq}\ \varphi[\alpha] \iff \underset{\mathfrak{A}}{|\!\!\!=}\neg\ \varphi[\alpha]\)
  • \(\underset{\mathfrak{A}}{|\!\!\!=}\ (\varphi\lor \psi)[\alpha]\iff \underset{\mathfrak{A}}{|\!\!\!=}\ \varphi[\alpha]\) 或者 \(\underset{\mathfrak{A}}{|\!\!\!=}\ \psi[\alpha]\) .
  • \(\underset{\mathfrak{A}}{|\!\!\!=}\ (\exists x\varphi)[\alpha]\iff\) 对于一些 \(a\in A\) ,有 \(\underset{\mathfrak{A}}{|\!\!\!=}\ \varphi[\alpha_{x\to a}]\) . 我们将 \(a\) 称为 witness (不知道怎么翻译了,或许叫见证常量?)

之后的 Proposition 2.1.25 比较显然,就不在这里写了.

还是利用一阶算数语言举例,对于任意的 \(\Omega\)-指派 \(\alpha\) ,有

\[ \underset{\Omega}{|\!\!\!=}\ x< \dot{\mathrm{S}}y \to (x< y\lor x=y)[\alpha]; \]

这里实际上就是说,对于自然数,如果一个数小于另一个数的后继,即 \(m<n+1\) ,要么 \(m=n\) 要么 \(m<n\) .

一阶语言的大小、基数

定义:有限一阶语言、基数

一个语言 \(L\) 称为有限的 (可数的),当且仅当其非逻辑符号集合都是有限集(可数集).

对于任意的无限集合基数 \(\kappa\) (\kappa),称 \(L\) 为基数 \(\kappa\) 的语言当且仅当非逻辑符号集合的基数为 \(\kappa\) .

注意:即使是有限的语言也会有无限多的项和公式.

下面是简单推论:

推论

对于任意语言 \(L\)

  1. 如果 \(L\) 是可数的,那么 \(\mathrm{Te}_L,\mathrm{AtFm}_L\)\(\mathrm{Fm}_L\) 都是可数集.
  2. 对于任意无限基数 \(\kappa\) ,如果 \(L\) 有基数 \(\kappa\) ,那么 \(\mathrm{AtFm}_L\)\(\mathrm{Fm}_L\) 是基数为 \(\kappa\) 的集合.

证明需要使用初等的集合论,感兴趣的话看英文原文. \(\square\)

教材上剩余的部分是讨论有效性 (effectiveness) 的问题,我们自此打住日后再来看. (反正老师也没有再说,何必逼自己 😫)

评论