Chapter 2 First-Order Logic

#mathematical_logic #first_order_logic

First-Order Language

Logical symbols:

• $()\to \mathrm{\neg }$
• $v_1,v_2,\cdots$
• $=$（optional）

Parameteres:

• Quantifier $\mathrm{\forall }$
• Predicate symbols
• Constant symbols
• Function symbols

一阶逻辑并不是只有一套语言，基于函数符号、常量符号（再组合变量决定可以形成的 Term 集合），谓词符号（决定了原子表达式可能施加于 term 之上的陈述断言）的选择可以有多套语言。如集合论（$=;\in ;\varnothing ;$），初等数论（$=;<;\mathbf{0};\mathbf{S},\mathbf{+},\cdot ,\mathbf{E}$），纯一阶逻辑（$;A_i^n;a_i;$）。

将 $=$ 作为 logical symbols 而不是参数是因为其常见性，把描述其性质的公理直接内化到语言中可以简化分析。

terms 递归定义
atomic formulas
wff 递归定义
occur free 的递归定义

$\wedge \vee \leftrightarrow \mathrm{\exists }$ 均定义为符号组合的 alias，二元谓词放在中间 $a<b$ 为 $<ab$ 的 alias，按照 $\mathrm{\forall }\mathrm{\neg }\wedge \vee \to \leftrightarrow$ 的优先级和 $\to$ 的右结合所进行的各种括号省略也是 alias

这一节完全地确定了我们所使用的表达式语法规范（如唯一分解）。这仅仅是符号上的，尚未涉及语义；也仅仅是对单体表达式的分析，尚未涉及表达式之间语法上的推导。

Truth and Models

在 Sentential Logic 中有 truth assignment（决定 sentence symbol 的真假）来确定一个表达式的语义。在 First-Order Logic 中我们有 variable symbol，predicate symbol、function symbol、constant symbol，这些符号代表的是更底层的对象，是用来形成类似 "sentence symbol" 的概念的。首先我们需要确定这些符号的含义，然后再根据这些符号组成的子句的含义以及全称量词、逻辑连接词来决定整个表达式的含义。

structure 和 assignment 在两个不同的自由维度上共同确定了一个一阶逻辑句子的含义。

structure $\mathfrak{A}$ 定义为元组 $|\mathfrak{A}|$ 和一组映射，其决定了 predicate symbol、function symbol、constant symbol 的解释方式。

• 全集 $|\mathfrak{A}|$，用于表示 $\mathrm{\forall }$ 中考虑的所有对象
• 对于任意 $n$ 元谓词符号 $P$，$\mathfrak{A}$ 将其映射到 $n$ 元关系 $P^{\mathfrak{A}}\subseteq |\mathfrak{A}{|}^n$。
• 对于任意常量符号 $c$，$\mathfrak{A}$ 将其映射到元素 $c^{\mathfrak{A}}\subseteq |\mathfrak{A}|$。
• 对于任意 $n$ 元函数符号 $f$，$\mathfrak{A}$ 将其映射到 $n$ 元函数 $f^{\mathfrak{A}}:|\mathfrak{A}{|}^n\to |\mathfrak{A}|$。

assigment $s$ 定义为函数 $s:V\to |\mathfrak{A}|$，其决定了 variable symbol 的赋值（解释方式）。

term 的含义：拓展 $s:V\to |\mathfrak{A}|$ 为 $\overline{s}:T\to |\mathfrak{A}|$ 用于表示所有 term 的含义，注意 $s$ 和 $\overline{s}$ 都是基于 $|\mathfrak{A}|$ 的存在才能定义的。递归定义：

• 对于 variable symbol $x$，有 $\overline{s}(x)=s(x)$
• 对于 constant symbol $c$，有 $\overline{s}(c)=c^{\mathfrak{A}}$
• 对于 term $t_1,t_2,\cdots ,t_n$ 和 n-place function symbol $f$，有 $\overline{s}(f{t}_1{t}_2\cdots t_n)=f^{\mathfrak{A}}(\overline{s}(t_1),\overline{s}(t_2),\cdots ,\overline{s}(t_n))$

对于 wff $\phi$ ， $\mathfrak{A}$ satisfy $\phi$ with $s$（$\phi$ 在 structure $\mathfrak{A}$ 和 assignment $s$ 下语义为真），记为 ${\models }_{\mathfrak{A}}\phi [s]$，定义采用如下递归定义

atomic formulas 的语义为真：直接定义：

• ${\models }_{\mathfrak{A}}=t_1{t}_2[s]$ 当且仅当 $\overline{s}(t_1)=\overline{s}(t_2)$
• 对于 n-place predicate symbol $P$，${\models }_{\mathfrak{A}}P{t}_1{t}_2\cdots t_n[s]$ 当且仅当 $⟨\overline{s}(t_1),\overline{s}(t_2),\cdots ,\overline{s}(t_n)⟩\in P^{\mathfrak{A}}$

other wffs 的语义为真：递归定义：

• ${\models }_{\mathfrak{A}}\mathrm{\neg }\phi [s]$ 当且仅当 ${⊭}_{\mathfrak{A}}\phi [s]$。这样的定义默许了排中律，即要么语义真，要么语义假，二者完全对立。
• ${\models }_{\mathfrak{A}}(\phi \to \psi )[s]$ 当且仅当 ${⊭}_{\mathfrak{A}}\phi [s]$ 或者 ${\models }_{\mathfrak{A}}\psi [s]$
• ${\models }_{\mathfrak{A}}\mathrm{\forall }x\phi [s]$ 当且仅当任意 $d\in |\mathfrak{A}|$ 都有 ${\models }_{\mathfrak{A}}\phi [s(x|d)]$

也可以等价地利用 Recursion Thoerem 定义：由于 wff 是可以唯一分解地（freely generated），所以在 wff 上可以建立映射 $\overline{h}:U\to (V\to |\mathfrak{A}|)$：

• 对于 atomic formulas $\phi =P{t}_1{t}_2\cdots t_n$，有 $\overline{h}(\phi )=\{s:V\to |\mathfrak{A}|\mid ⟨\overline{s}(t_1),\overline{s}(t_2),\cdots ,\overline{s}(t_n)\in P^{\mathfrak{A}}⟩\}$
• 对于 other wffs $\phi =\mathrm{\neg }\psi$，有 $\overline{h}(\phi )=\{s:V\to |\mathfrak{A}|\mid s\notin \overline{h}(\psi )\}$
• 对于 other wffs $\phi =\psi \to \varphi$，有 $\overline{h}(\phi )=\{s:V\to |\mathfrak{A}|\mid \overline{h}(\psi )\}$
• 对于 other wffs $\phi =\mathrm{\forall }x\psi$，有 $\overline{h}=\{s:V\to |\mathfrak{A}|\mid \text{for all }d\in |\mathfrak{A}|\text{, }s(x\mid d)\in \overline{h}(\psi )\}$

定义 ${\models }_{\mathfrak{A}}\phi [s]$ 当且仅当 $s\in \overline{h}(\phi )$。依 Recursion Theorem 可以直接得到 $\overline{h}$ 的存在性和唯一性，从而我们的定义是递归良构的（recursive well-formed）。

需要注意，一阶逻辑中 wff 的语义并不像在 sentential logic 中简单地决定于子句在相同的 structure 和 assigment 下的语义。由于量词的存在，$\mathrm{\forall }x\phi$ 在 $s$ 下的语义与 $\overline{s}(x)$ 是形式上无关的，$\phi$ 在 $s$ 下的语义通常是与 $\overline{s}(x)$ 是形式上有关的（如果 $x$ 是 $\phi$ 的自由变量）。$\mathrm{\forall }x\phi$ 在 $s$ 下的语义取决于 $\phi$ 在 $s(x|d)$ 下的语义而不是 $s$ 下的语义。

直觉上 $\overline{s}$ 只有在出现在 $\phi$ 中自由变量上的赋值才会会对 $\phi$ 的语义真造成影响。这可以简单地递归证明。在定义时不直接限制 $\overline{s}$ 的定义域为 $\phi$ 中出现的自由变量的原因是，可以一定程度上对所有公式进行统一地描述。

sentence 定义为不含有自由变量的 wff。对于 sentence $\phi$，此时要么任意 $s$ 都有 ${\models }_{\mathfrak{A}}\phi [s]$，要么任意 $s$ 都有 ${⊭}_{\mathfrak{A}}\phi [s]$，即 $\phi$ 的语义与 assigment $s$ 无关。

所以我们可以进行记号的简化，对于 sentence $\phi$，其语义真可以直接记为 ${\models }_{\mathfrak{A}}\phi$，称为 $\phi$ 在 $\mathfrak{A}$ 中语义为真，或者 $\mathfrak{A}$ 是 $\phi$ 的一个模型（Model）。

对于 sentence set $\mathrm{\Sigma }$，定义 $\mathfrak{A}$ 为 $\mathrm{\Sigma }$ 的一个模型（Model），当且仅当 $\mathfrak{A}$ 是每一个 $\phi \in \mathrm{\Sigma }$ 的模型

Logical Implication

wff set $\mathrm{\Sigma }$ 逻辑蕴含（Logical Implies） formula $\phi$（$\mathrm{\Sigma }\models \phi$ ），当且仅当任意该语言的 structure $\mathfrak{A}$ 以及任意该 structure 的 assignment $s$ 满足：如果任意 $\sigma \in \mathrm{\Sigma }$ 都有 ${\models }_{\mathfrak{A}}\sigma [s]$，那么 ${\models }_{\mathfrak{A}}\phi [s]$。特别地，对于 sentence set $\mathrm{\Sigma }$ 和 sentence $\phi$ ，$\mathrm{\Sigma }\models \phi$ 当且仅当如果 $\mathfrak{A}$ 是 $\mathrm{\Sigma }$ 的模型，那么 $\mathfrak{A}$ 也是 $\phi$ 的模型。

wff $\phi$ 是 valid wff 当且仅当 $\models \phi$。即 valid wff 是任意 strucutre 和任意 assignment 都满足的 wff。特别地，sentence $\phi$ 是 valid wff 当且仅当任意模型都满足 $\phi$。

valid wff 在 first-order logic 中的地位和 tautology 在 sentential logic 中的地位是相同的。

可满足性：$\mathrm{\Sigma }$ 是可满足的定义为存在一个模型 $\mathfrak{A}$ 和一组赋值 $s$ 使得任意 $\phi \in \mathrm{\Sigma }$ 都有 ${\models }_{\mathfrak{A}}\phi [s]$
逻辑蕴含：$\mathrm{\Sigma }$ 逻辑蕴含 $\phi$（$\mathrm{\Sigma }\models \phi$）定义为任意模型 $\mathfrak{A}$ 和一组赋值 $s$，若其满足了 $\mathrm{\Sigma }$

Definability in a Structure