一阶语言与一阶逻辑 [一阶语言]

教程 : 一阶语言与一阶逻辑

定义

定义. 一个 (一阶) 符号表 $\Sigma$ 由如下资料构成:

  • 一族类型 (type/sort),
  • 一些函数符号 (function symbols), 每一个函数符号 $f$ 具有固定的 “输入类型” $A_1,\cdots,A_n$, “输出类型” $B$, 记作 $f \colon (A_1\times \cdots \times A_n) \to B$, 非负整数 $n$ 称为 $f$ 的元数 (arity); (当 $n=0$ 时, 函数符号 $f$ 是 “零元函数”, 也即类型 $B$ 的常数 $f : B$.)
  • 一些关系符号 (relation symbols), 又叫谓词 (predicates), 每一个关系符号 $R$ 具有固定的类型 $A_1,\cdots,A_n$, 记作 $R \hookrightarrow A_1\times \cdots\times A_n$, 非负整数 $n$ 称为 $R$ 的元数. (当 $n=0$ 时, 关系符号是 “零元关系”, 也即原子命题 (atomic proposition).)

在指定的符号表 $\Sigma$ 上, 归纳定义公式 (formula) 与项 (term) 如下:

  • 每个类型 $A$ 的变量 $x\colon A$ 是 $A$ 的项;
  • 对于函数 $f\colon (A_1\times \cdots \times A_n) \to B$ 与项 $x_1\colon A_1,\cdots,x_n\colon A_n$, $f(x_1,\cdots,x_n)$ 是类型 $B$ 的项;
  • 对于关系 $R\hookrightarrow A_1\times \cdots\times A_n$ 与项 $x_1\colon A_1,\cdots,x_n\colon A_n$, $R(x_1,\cdots,x_n)$ 是公式;
  • 公式可用逻辑符号 $\land,\lor,\bigvee,\bigwedge,\forall,\exists,\neg,\Rightarrow$ 等组合得到新的公式.

每条公式都有相适应的语境, 语境中包含其所需的变量.

在指定的符号表 $\Sigma$ 上, 一个一阶理论由若干条公理构成. 每条公理形如 $$ \psi \vdash_\Gamma \varphi, $$ 其中 $\Gamma$ 是语境, $\psi$ 和 $\varphi$ 是该语境所适应的公式.

有些一阶逻辑的片段会限制公式中可以使用的逻辑符号.

例

初等算术

群

范畴

小范畴的语言的符号表包括

  • 类型 $O$ (对象), $M$ (态射);
  • 一元函数符号 $s,t\colon M\to O$ (态射的起点与终点), 一元函数符号 $\operatorname{id}\colon O\to M$ (对象的恒等态射);
  • 三元关系符号 $C\hookrightarrow M^3$, $C(f,g,h)$ 表达 “$h$ 是 $f$ 与 $g$ 的复合”.

注. 范畴中并非任意两个态射都能复合, 故此处表达复合关系使用了三元关系, 而不是二元函数.

注. 这里的范畴指的是严格 $1$-范畴.