跳转至
\[ \newcommand{\bs}{\boldsymbol} \newcommand{\bsX}{\boldsymbol{X}} \newcommand{\bf}{\mathbf} \newcommand{\msc}{\mathscr} \newcommand{\mca}{\mathcal} \newcommand{\msf}{\mathsf} \newcommand{\T}{\text{T}} \newcommand{\tb}{\text{b}} \newcommand{\rest}{\text{rest}} \newcommand{\rme}{\mathrm{e}} \newcommand{\rmi}{\mathrm{i}} \newcommand{\rmj}{\mathrm{j}} \newcommand{\rmd}{\mathrm{d}} \newcommand{\rmm}{\mathrm{m}} \newcommand{\rmb}{\mathrm{b}} \newcommand{\and}{\land} \newcommand{\or}{\lor} \newcommand{\exist}{\exists} \newcommand{\sube}{\subseteq} \newcommand{\lr}[3]{\left#1 #2 \right#3} \newcommand{\intfy}{\int_{-\infty}^{+\infty}} \newcommand{\sumfy}[1]{\sum_{#1=-\infty}^{+\infty}} \newcommand{\vt}{\vartheta} \newcommand{\ve}{\varepsilon} \newcommand{\vp}{\varphi} \newcommand{\Var}{\text{Var}} \newcommand{\Cov}{\text{Cov}} \newcommand{\edef}{\xlongequal{\text{def}}} \newcommand{\prob}{\text{P}} \newcommand{\Exp}{\text{E}} \newcommand{\t}{\text} \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\A}{\mathbb{A}} \newcommand{\true}{\mathtt{true}} \newcommand{\false}{\mathtt{false}} \newcommand{\fatsemi}{⨟} \newcommand{\versionofnewcommand}{\text{260202}} \]

1. Syntax of First-Order Languages

1.1 Alphabets

我们首先需要一个 字母表 (Alphabets) 存储将要用到的符号. 于是定义 alphabet 及其相关概念如下:

Definition 1.1.1 (Alphabets)

我们称一个非空的, 由各种符号构成的集合为一个 alphabet \(\mathbb{A}\). 由 \(\mathbb{A}\) 中有限个符号构成的序列, 构成 \(\A\) 上的一个 string 或者 word. 接着, 我们记 \(\A^*\) 为 \(\A\) 上所有 strings 构成的集合; 并称一个 string \(\zeta \in \A^*\) 的 length 为 \(\zeta\) 中符号的数目, 重复的也计数. String 可以是空的, length 为 0 的, 并且同样属于 \(\A^*\), 一般以 \(\square\) 标记. 对于 \(\A\) 通常还有一个附加要求: \(\A\) 上的任意 string 只有唯一的读法.

Example 1.1.2

来举几个合法的 alphabets 的例子. \(\A_1 = \{ 0,1,2, \cdots, 9\}\), \(\A_2 = \{a, b, c, \cdots, z\}\), \(\A_3 = \{\circ, \int, a, \rmd, x, f,),(\}\), \(\A_4 = \{c_0, c_1, c_2, \cdots \}\). 注意, 我们使用单个拉丁字母构成 alphabet (如 \(\A_2\)) 时, 习惯上使用小写. 大写字母另有所指.

以下为上述 alphabets 上的 strings 例:

\[ 114514 \in {\A_1}^*, \quad math \in {\A_2}^*, \quad \int f(x)\rmd x \in {\A_3}^*, \quad c_3c_6c_5 \in {\A_4}^* \]

注意, 集合 \(\A_5 = \{0,1,2,\cdots,9,10,11\}\) 不是一个合法的 alphabet. 因为 114514 的 "11" 在 \(\A_5\) 上有两种读法: "11" 和 "1""1".

Definition 1.1.3 (Countability)

\(M\) 为一个集合. 若 \(M\) 为无限集且存在一个从自然数集 \(\N\) 到 \(M\) 的满射 \(\alpha\), 我们称 \(M\) 是 可数的 (countable). 于是可以将 \(M\) 表示为 \(\{\alpha(n) \mid n\in\N\}\) 或者 \(\{\alpha_n \mid n \in \N\}\). 另有一概念为 at most countable 用以表示有限的或是可数的集合.

Lemma 1.1.4

对于非空集合 \(M\), 有如下的等价命题:

  1. \(M\) is at most countable.
  2. 存在一个满射 \(\alpha : \N \to M\).
  3. 存在一个单射 \(\beta : M \to \N\).

(证明略.)

Corollary 1.1.5

以下命题为 Lemma 1.1.4 的推论:

  1. A subset of an at most countable set is at most countable.
  2. If sets \(M_1\) and \(M_2\) are at most countable, then \(M_1 \cup M2\) is at most countable.

Remark 1.1.6

后面将会证明, 对于目前的数学命题, 有限的 alphabet 已经足够. 另外, 接下来, 可数 alphabet \(\A_\text{N} = \{c_0, c_1, c_2, \cdots \}\) 和不可数 alphabet \(\A_\text{R} = \{c_r \mid r \in R\}\) 会很有用.

Lemma 1.1.7

If \(\A\) is an at most alphabet