一阶理论¶

定义：一阶理论 (first-order theory)

一阶理论 \(T = (\Sigma, \mathcal A)\),

• 非逻辑符号集 \(\Sigma\) (签名 signature)
  • 有限的非逻辑符号, 比一阶逻辑更强的限定
• 闭公式 [ 没有自由变元 ] 集合 \(\mathcal A\) (公理集 axioms)
  • 规定非逻辑符号的含义

\(\Sigma\)-公式: 只由逻辑符号(变元, 联结词, 量词) 和 \(\Sigma\) 中非逻辑符号组成的一阶逻辑公式

定义: 等式理论 \(\mathcal T_E\)

• 签名 \(\Sigma_E: \{=, a,b,c, \dots, f,g,h, \dots, p, q, r, \dots\}\)
  • 引入了 \(=\)
• 公理集 \(\mathcal A_E\), 定义 \(=\) 的含义
  • 自反/对称/传递/函数同余/谓词同余

定义: Peano 算术 (\(\mathcal T_{PA}\))

• 签名 \(\Sigma_{PA}: \{0,1,+, \times, =\}\)
  • \(0, 1\) 为常元
  • \(+, \times\) 为二元函数, \(=\) 为二元谓词
• 公理集 \(\mathcal A_{PA}\):
  1. 等式
  2. 零元
  3. 后继
  4. 加 0
  5. 加法后继
  6. 乘 0
  7. 乘法后继
  8. 归纳公理

!!!tip \(\mathcal T_{PA}\) 的语法糖 * 任意自然数可以表示为多个 1 相加 * 关系式转换为等式: 用一个额外的自然数变量转换 * 严格关系式:上面的额外的自然数变量不为 0

定义: Presburger 算术 \(\mathcal T_\mathbb N\)

• 签名 \(\Sigma_{\mathbb N} : \{ 0,1, +, =\}\)
• 公理集 \(\mathcal A_N\):
  1. 等式的公理: 自反/对称/传递/同余
  2. 零元
  3. 后继
  4. 与 0 加法
  5. 加法后继
  6. 归纳