First-Order Languages

Mort Yao

Symbols. We take these following symbols to construct our first-order language \(\mathcal{L}\):

  1. Logical symbols.
    1. Parentheses: \((\), \()\).
    2. Sentential connective symbols: \(\to\), \(\lnot\).
    3. Variables: \(x, y, z, v_1, v_2,\) …
    4. Equality symbol (special 2-place predicate symbol; optional): \(=\).
  2. Parameters.
    1. Universal quantifier symbol: \(\forall\).
    2. (\(n\)-place) Predicate symbols (a.k.a. relation symbols): \(P_1, P_2,\) …
    3. Constant symbols (0-place function symbols): \(c_1, c_2,\) …
    4. (\(n\)-place) Function symbols: \(f_1, f_2,\) …

Example 1. The Language of Set Theory (LOST) contains: (1) the equality symbol \(=\); (2) \(\in\) as a 2-place predicate symbol.

Example 2. The Language of Elementary Number Theory contains: (1) the equality symbol \(=\); (2) \(<\) as a 2-place predicate symbol; (3) \(\mathbf{0}\) (zero) as a constant symbol; (4) \(\mathbf{S}\) (successor) as a 1-place function symbol; (5) \(+\) (addition), \(\cdot\) (multiplication) and \(\mathbf{E}\) (exponentiation) as 2-place function symbols.

Remark 3. For sentential connective symbols, we choose \(\to\) and \(\lnot\) as a complete set. Other common connectives are seen as abbreviations of them: \[\begin{align*} (\alpha \land \beta) &\quad\text{ is equivalent to }\quad (\lnot (\alpha \to (\lnot \beta))) \\ (\alpha \lor \beta) &\quad\text{ is equivalent to }\quad ((\lnot \alpha) \to \beta) \\ (\alpha \leftrightarrow \beta) &\quad\text{ is equivalent to }\quad (\lnot((\alpha \to \beta) \to (\lnot (\beta \to \alpha)))) \end{align*}\] The existential quantifier \(\exists\) is also seen as an abbreviation: \[\exists x \alpha \quad\text{ is equivalent to }\quad (\lnot \forall x (\lnot \alpha))\] For 2-place predicate and function symbols, it is conventional to use infix notations instead, e.g., \(u = t\) abbreviates \(= u\ t\), \(u \in t\) abbreviates \(\in u\ t\). Moreover, \(u \neq t\) abbreviates \((\lnot = u\ t)\); similarly, \(u \notin t\) abbreviates \((\lnot \in u\ t)\).

An expression is any finite sequence of symbols. Among all possible expressions, terms and formulas are of our interest.

Terms. Let \(\mathcal{L}\) be a first-order language. We define \[\text{Term}^\mathcal{L}_0 = \{ \langle a \rangle : a \text{ is a variable or constant symbol} \}\] \[\text{Term}^\mathcal{L}_{n+1} = \{ f t_1 \cdots t_m : f \text{ is a }m\text{-place function symbol}, t_1,\dots,t_m \in \bigcup_{0 \leq i \leq n}\text{Term}^\mathcal{L}_i \}\] Furthermore, we define \[\text{Term}(\mathcal{L}) = \bigcup_{n \in \mathbb{N}} \text{Term}^\mathcal{L}_n\] thus, \(t\) is a term in \(\mathcal{L}\) if and only if \(t \in \text{Term}(\mathcal{L})\).

The complexity of a term \(t\) is an integer \(n\) such that \(t \in \text{Term}^\mathcal{L}_n\), and for every \(k < n\), \(t \notin \text{Term}^\mathcal{L}_k\).

Proposition 4. (Induction principle for terms) If \(\Pi\) is a set of terms such that

  1. \(\text{Term}^\mathcal{L}_0 \subseteq \Pi\);
  2. If \(f\) is an \(m\)-place function symbol and \(t_1,\dots,t_m \in \Pi\) then \(f t_1 \cdots t_m \in \Pi\);

then \(\Pi = \text{Term}(\mathcal{L})\).

Formulas. Let \(\mathcal{L}\) be a first-order language. We define the set of atomic formulas as \[\text{Formula}^\mathcal{L}_0 = \{ P t_1 \cdots t_k : P \text{ is a }k\text{-place predicate symbol or }=, t_1,\dots,t_k \in \text{Term}(\mathcal{L}) \}\] We say that \(\varphi \in \text{Formula}^\mathcal{L}_{n+1}\) if and only if one of the following holds:

  1. \(\varphi = (\lnot \psi)\) for some \(\psi \in \bigcup_{m \leq n} \text{Formula}^\mathcal{L}_m\);
  2. \(\varphi = (\psi \to \theta)\) for some \(\psi, \theta \in \bigcup_{m \leq n} \text{Formula}^\mathcal{L}_m\);
  3. \(\varphi = \forall v_i \psi\) for some \(v_i \in V\) and \(\psi \in \bigcup_{m \leq n} \text{Formula}^\mathcal{L}_m\).

Furthermore, we define \[\text{Formula}(\mathcal{L}) = \bigcup_{n \in \mathbb{N}} \text{Formula}^\mathcal{L}_n\] thus, \(\varphi\) is a formula (or well-formed formula, wff) in \(\mathcal{L}\) if and only if \(\varphi \in \text{Formula}(\mathcal{L})\).

The complexity of a formula \(\varphi\) is an integer \(n\) such that \(\varphi \in \text{Formula}^\mathcal{L}_n\), and for every \(k < n\), \(\varphi \notin \text{Formula}^\mathcal{L}_k\).

Proposition 5. (Induction principle for formulas) If \(\Phi \subseteq \text{Formula}(\mathcal{L})\) is a set of formulas such that

  1. \(\text{Formula}^\mathcal{L}_0 \subseteq \Phi\);
  2. If \(\varphi \in \Phi\) then \((\lnot \varphi) \in \Phi\);
  3. If \(\varphi, \psi \in \Phi\) then \((\varphi \to \psi) \in \Phi\);
  4. If \(\varphi \in \Phi\) then for any \(v_i \in V\), \(\forall v_i \varphi \in \Phi\);

then \(\Phi = \text{Formula}(\mathcal{L})\).

Free variables. For any wff \(\varphi\), we define that a variable \(x\) occurs free in \(\varphi\) (or \(x\) is a free variable of \(\varphi\)) by recursion:

  1. For atomic \(\psi\), \(x\) occurs free in \(\psi\) iff \(x\) is a symbol in \(\psi\);
  2. \(x\) occurs free in \((\lnot \psi)\) iff \(x\) occurs free in \(\psi\);
  3. \(x\) occurs free in \((\psi \to \theta)\) iff \(x\) occurs free in \(\psi\) or in \(\theta\);
  4. \(x\) occurs free in \(\forall v_i \psi\) iff \(x\) occurs free in \(\psi\) and \(x \neq v_i\).

Alternatively, we can define \(h(\alpha)\) as the set of all variables in the atomic formula \(\alpha\). And we extend \(h\) to a function \(\bar{h}\) on all wffs such that \[\begin{align*} \bar{h}((\lnot \psi)) &= \bar{h}(\psi) \\ \bar{h}((\psi \to \theta)) &= \bar{h}(\psi) \cup \bar{h}(\theta) \\ \bar{h}(\forall v_i \psi) &= \bar{h}(\psi) \text{ after removing }v_i\text{ if present} \end{align*}\] then we say that a variable \(x\) occurs free in \(\varphi\) iff \(x \in \bar{h}(\varphi)\). The existence of a unique such \(\bar{h}\) follows from the recursion theorem and the fact that each wff has a unique decomposition.

If no variable occurs free in the wff \(\varphi\), i.e., \(\bar{h}(\varphi) = \emptyset\), then \(\varphi\) is called a sentence.