一阶语言的语法和语义(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}\) 为哥特体的 \(A\) ,\(\LaTeX\) 代码为 \mathfrak{A}
.
我们不妨举例:
数学结构的例子
- 最简单的结构是简单的集合 \(A\) ,没有关系、函数和不同的元素.
- 最常见的关系往往是二元关系 \(R\subseteq A\times A\) ,例如,\((\omega,<_{\omega})\) 就是自然数集的自然排列关系.
对于二元关系,这里将偏序关系和全序关系阐述一下. 注意在其他的教材中,\(a\) 与 \(b\) 有关系 \(R\) 可能写为 \(aRb\) ,但是这里我们写为序对的形式 \((a,b)\) .
定义:偏序 (Partial Order)
给定一个集合 \(X\) ,考虑该集合上一个关系(Relation) \(R\) ,如果满足以下条件:
- 对于任意的 \(x\in X\) ,都有 \((x,x)\in R\) (自反性);
- 对任意的 \(x,x'\in X\) ,如果 \((x,x')\in R, (x',x)\in R\) ,那么 \(x= x'\) (反对称性).
- 对任意的 \(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\) 通常由如下的符号表示
- 集合 \(\mathrm{Rs}_L\) ,表示 \(L\)-关系 符号 (\(\mathrm{Rs}\) 即为 Relation Symbol);
- 集合 \(\mathrm{Fs}_L\) ,表示 \(L\)-函数 符号(\(\mathrm{Fs}\) 即为 Function Symbol);
- 集合 \(\mathrm{Cs}_L\) ,表示 \(L\)-常值 符号 (\(\mathrm{Cs}\) 即为 Constant Symbol).
- 元数 (Arity) 函数:\(\nu: \mathcal{R}\cup \mathcal{F}\to \mathbb{N}^*\) ,它指定了所有关系符号和函数符号的元数.
上述符号称为非逻辑符号,\(\mathrm{Rs}_L,\mathrm{Fs}_L,\mathrm{Cs}_L\) 是两两不交的,除上述非逻辑符号(或称 initial symbol ,初始符号)外,我们还需要逻辑的符号.
- 变元符号(可数集合): \(\mathrm{Vb} = \left\lbrace v_n: n\in \omega \right\rbrace\) ( Variable ).
- 等值符号 \(=\) .
- 连接词 \(\neg\) 和 \(\lor\) .
- 存在量词:\(\exists\) .
连接词我们选择之前我们证明完备的两个连接词. 量词实际上选择任意 \(\forall\) 和存在 \(\exists\) 都是 OK 的,只不过这里我们选择了存在 \(\exists\) .
我们熟悉的一些符号实际上能通过这些符号导出:
同时,等值符号在教材上采用
这个符号,但是为了简化表达,在不混淆的情况下(在之后的定义当中出现基本表达等值符号的含义)还是采用 \(=\) 符号.
实际上,在中文教材当中,有时也能学到如下的两个定义:
一阶逻辑语言定义补充
逻辑符号添加如下两种:
- 语法逗号: ,
- 语法括号:( 和 )
这两个定义补充的出现是中缀表达式固有问题的体现,因为它无法避免括号的使用.
我们在今后,为简洁起见,我们不认为这两个在定义当中,但是在书写中缀表达式的时候,为了表达的简洁,还是会写上述两个符号.
一阶逻辑语言示例
- 语言 \(L_=\) 有 \(\mathrm{Rs}_{L_=}=\mathrm{Fs}_{L_=} = \mathrm{Cs}_{L_=} = \varnothing\) ,\(L_=\) 没有非逻辑符号. 因此在后续书写公式的时候只能使用变量符号.
- 群论自然语言的符号是 \(L_G\) ,它有非逻辑符号 \(\dot{*}\) 、\(\dot{^{-1}}\) 、\(\dot{e}\) , 其中 \(\dot{*}\) 是群论中的二元运算符,是二元函数,\(\dot{^{-1}}\) 是逆元函数,是一元函数. 而 \(\dot{e}\) 是幺元符号. 环论类似,符号为 \(L_R\) .
- 一阶算数理论当中,对应的逻辑语言是 \(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\)-原子项当且仅当其唯一符号满足:
定义:\(L\)-项
\(L\)-项的集合 \(\mathrm{Te}_L\) 是满足如下条件的最小 \(L\)-表达式集合:
- 每一个 \(L\)-原子项都是 \(L\)-项.
- 对于任意 \(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\) ,一定满足如下性质中的其中一个:
- \(t\) 是 \(L\)-原子项.
- 存在 \(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\) 和 \(y\) 进行二元运算作用之后取逆元. 写为前缀表达式为 \(\dot{^{-1}}\dot{*}xy\) . 一般地,\(L_G\) 中的 \(L\)-项总能写为:
这就是唯一可读性的一个体现.
\(L\)-公式
\(L\)-原子公式
我们在定义 \(L\)-项的时候,实际上只有变量、常量以及函数,那么原来的关系符号和逻辑符号去哪了?我们需要把这些也纳入到体系当中.
我们来谈公式 (formula) 的概念,自小到大,我们学到的公式都形如:
这里面 \(\sim\) 代表一种关系,大部分学到的公式都是等号,表示出一个运算的相等关系,也有类似群同态基本定理这样的公式:
没有关系的公式实际上就是草稿纸上的运算过程而已,给不了我们什么信息,所以公式的存在必须要有关系符号.
定义:\(L\)-原子公式 (\(L\)-atomic formulas)
\(L\)-原子公式的集合 \(\mathrm{AtFm}_L\) 是所有满足如下条件的 \(L\)-表达式的集合(其中的表达式是如下的某种形式):
- \(=tu\) ,其中 \(t\) 和 \(u\) 是 \(L\)-项.
- \(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\) .
举例:
- \(L_=\) 中的 \(L\)-原子公式只有 \(x=y\) 的形式,其中 \(x,y\) 为变量.
- 在一阶算数语言 \(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\)-表达式集合:
- 每一个 \(L\)-原子公式都是 \(L\)-公式;
- 如果 \(\varphi\) 和 \(\psi\) 是 \(L\)-公式,那么 \(\neg \varphi\) 和 \(\lor \varphi \psi\) 都是 \(L\)-公式;
- 如果 \(\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\) ,总有以下一个结论成立:
- \(\theta\) 为 \(L\)-原子公式;
- 存在 \(L\)-公式 \(\varphi\) 使得 \(\theta\) 为 \(\neg \varphi\) ;
- 存在 \(L\)-公式 \(\varphi,\psi\) 使得 \(\theta\) 为 \(\lor\varphi\psi\) ;
- 存在 \(L\)-公式 \(\varphi\) 和 变元 \(x\) 使得 \(\theta\) 为 \(\exists x \varphi\) ;
更近一步,在 2~4 当中,\(\varphi\) 和 \(\psi\) 还有 \(x\) 是唯一确定的.
例:外延公理
请写出 \(L\)-公式表述集合论中的外延公理:给定任意的集合 \(A,B\) ,\(A\) 等于 \(B\) 当且仅当给定任意 \(x\) ,\(x\in A\) 当且仅当 \(x\in B\) .
写为如下形式:
其中 \(\in\) 为二元关系符号. \(\square\)
由于我们没有作者那样想要把一切定义写为递归定义的执念,因此项递归定理 (Term Recursion Theorem) 和公式递归定理 (Formula Recursion Theorem) 就不阐述了.
\(L\) - 结构
经过了如此漫长的前置准备,我们终于可以严格定义一个数学结构了.
定义:\(L\)-结构
一个 \(L\)-结构 \(\mathfrak{A}\) 可以由以下的内容组成:
- 一个非空集合 \(A\) ,作为 \(\mathfrak{A}\) 的全域,记为 \(|\mathfrak{A}|\) .
- 关系集 \(\mathrm{Rs}_L\) 中的符号 \(p\) ,对应 \(\mathfrak{A}\) 中的一个关系 \(p^\mathfrak{A}\subseteq A^{\nu_L(p)}\).
- 函数集 \(\mathrm{Fs}_L\) 中的符号 \(f\),对应一个函数 \(f^{\mathfrak{A}}: A^{\nu_L(f)}\to A\) .
- 互异元素 \(\mathrm{Cs}_L\) 中的符号 \(c\) ,对应一个元素 \(c^\mathfrak{A}\in A\) .
我们利用一阶算数理论来说明这个定义:
这里面,我们有:
- 全域: \(\omega\)
- 关系符号:\(<\)
- 函数:
- 二元:\(+,\times\)
- 一元:\(\mathrm{Sc}:m\to m+1\) (后继函数)
- 常量元素:\(0\)
需要注意的是,\(p^\mathfrak{A}\) 是一个集合,我们通常把满足关系 \(p\) 的序对称为属于 \(p^\mathfrak{A}\) . 例如 \(\mathbb{R}\) 中的小于关系:\(<\) ,有
语义部分
在定义了语法层面上的数学结构后,我们需要赋予这些对象意义,因此我们采用和命题逻辑相似的方法进行研究.
\(\mathfrak{A}\)-真值指派
定义:\(\mathfrak{A}\)-真值指派
对于任意的 \(L\)-结构 \(\mathfrak{A}\) ,一个 \(\mathfrak{A}\)-真值指派就是指一个函数 \(\alpha: \mathrm{Vb}\to A\) .
为什么要这么定义真值指派?这是由于在结构当中,只有变元所代表的东西是不确定的,例如在一阶算数语言 \(L_\Omega\) 当中,\(\dot{\mathrm{S}}0\) 是确定的,但是
是不确定的,只有给定了 \(x\) 才能知道是什么含义.
为了解决这个项的取值问题,首先我们需要给变元 \(x\) 赋值,这是 \(\alpha\) 做的事情,例如 \(\alpha(x)= 0\) .
然后,我们需要给项一个整体的指派,形式上可以写为
但是我们亲爱的作者 🤯 这个时候不喜欢这个符号,他要在后续的公式里面使用这个符号,因此他给出了一个这样的符号:我们记
在给定了 \(\alpha\) 时,对项的真值指派写为 \(t^{\mathfrak{A}}[\alpha]\) ,表示结构 \(\mathfrak{A}\) 中的项 \(t\) 在 \(\mathfrak{A}\)-真值指派 \(\alpha\) 下的取值.
当然,这也仅仅是符号上的一个新约定,我们还并没有解决项的取值的定义问题,因此我们需要下面的定义:
定义:\(L\)-项的取值
对于任意的 \(L\)-结构 \(\mathfrak{A}\) 和任意的 \(\mathfrak{A}\)-指派 \(\alpha\) :
- 对于每个变元 \(x\) ,\(x^{\mathfrak{A}}[\alpha] = \alpha(x)\) ;
- 对于每个 \(c\in \mathrm{Cs}_L\) ,\(c^\mathfrak{A}[\alpha]=c^\mathfrak{A}\) ;
- 对于每个 \(f\in \mathrm{Fs}_L\) 和 \(t_0,\cdots,t_{\nu_L(f)-1}\in \mathrm{Te}_L\),有
简而言之,就是变元的取值由 \(\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] $$
首先拆分函数,然后在分部计算即可:
\(\square\)
\(L\)-公式的取值
我们接下来讨论公式的取值时,我们使用的是真值指派 \(V_{\mathfrak{A},\alpha}\) ,因为在讨论一个公式的时候,我们常说的是某个公式是正确的还是错误的,所以取值也就是真假值.
定义:\(L\)-原子公式的取值
对于任意的 \(\mathfrak{A}\) 和 \(\alpha\) :
- 任意的 \(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} $$
- 对任意的关系 \(p\in \mathrm{Rs}_L\) 和 \(t_0,\cdots,t_{\nu_L(p)-1}\in \mathrm{Te}_L\) ,
最后就只剩下 \(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\) 有:
在命题逻辑当中,我们曾经使用过符号 \(\mid\!\equiv\) ,我们在一阶语言当中也使用类似的记号 \(\models\) . 我们使用如下的记号:
下面给出定义:
定义:\(\mathfrak{A}\)-指派满足 (satisfies) 语句
对于任意的 \(\mathfrak{A}\), \(\alpha\) 和 \(\varphi\) :
- \(\underset{\mathfrak{A}}{\models}\varphi[\alpha]\) 当且仅当 \(V_{\mathfrak{A},\alpha}(\varphi)=\mathrm{T}\) ,称 \(\alpha\) 满足 (satisfies) \(\mathfrak{A}\) 中的 \(\varphi\).
- \(\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\) ,有
这里实际上就是说,对于自然数,如果一个数小于另一个数的后继,即 \(m<n+1\) ,要么 \(m=n\) 要么 \(m<n\) .
一阶语言的大小、基数
定义:有限一阶语言、基数
一个语言 \(L\) 称为有限的 (可数的),当且仅当其非逻辑符号集合都是有限集(可数集).
对于任意的无限集合基数 \(\kappa\) (\kappa
),称 \(L\) 为基数 \(\kappa\) 的语言当且仅当非逻辑符号集合的基数为 \(\kappa\) .
注意:即使是有限的语言也会有无限多的项和公式.
下面是简单推论:
推论
对于任意语言 \(L\) :
- 如果 \(L\) 是可数的,那么 \(\mathrm{Te}_L,\mathrm{AtFm}_L\) 和 \(\mathrm{Fm}_L\) 都是可数集.
- 对于任意无限基数 \(\kappa\) ,如果 \(L\) 有基数 \(\kappa\) ,那么 \(\mathrm{AtFm}_L\) 和 \(\mathrm{Fm}_L\) 是基数为 \(\kappa\) 的集合.
证明需要使用初等的集合论,感兴趣的话看英文原文. \(\square\)
教材上剩余的部分是讨论有效性 (effectiveness) 的问题,我们自此打住日后再来看. (反正老师也没有再说,何必逼自己 😫)