Lesson 2

A vocabulary \(\Sigma = (\Phi, \Pi, r)\) consists of two disjoint countable sets: a set \(\Phi\) of function symbols, and a set \(\Pi\) of relation symbols. Here, \(r \colon \Phi \cup \Pi \to \mathbb{Z}_{\ge 0}\) tells us how many arguments each function and relation symbol takes. A function symbol \(f \in \Phi\) with \(r(f) = k\) is called a \(k\)-ary function symbol, and a relation symbol \(R \in \Pi\) with \(r(R) = k\) is also \(k\)-ary. A \(0\)-ary function symbol is called a constant. Relation symbols are never \(0\)-ary. We shall assume that \(\Pi\) always contains the binary equality relation \(=\).

There is also a fixed, countable set of variables \(V = \{x, y, z, …\}\) which, intuitively, will take values from the universe discussed by the particular expression (and are not to be confused with the Boolean variables of the previous chapter).

Now, we define inductively the terms over the vocabulary \(\Sigma\). To start off, any variable in \(V\) is a term. If \(f \in \Phi\) is a \(k\)-ary function symbol and \(t_{1}, …, t_{k}\) are terms, then the expression \(f(t_{1}, …, t_{k})\) is a term. Notice that any constant \(c\) is a term: just take \(k = 0\) in the above definition, and omit the parentheses in \(c()\). Having defined terms, we are finally in a position to start defining what an expression over the vocabulary \(\Sigma\) is. If \(R \in \Pi\) is a \(k\)-ary relation symbol and \(t_{1}, …, t_{k}\) are terms, then the expression \(R(t_{1}, …, t_{k})\) is called an atomic expression.

A first-order expression is defined inductively as follows: First, any atomic expression is a first-order expression. If \(\phi\) and \(\psi\) are expressions, then so are \(\lnot \phi\), \((\phi \lor \psi)\), and \((\phi \land \psi)\). Finally (and here is the most powerful element of this language), if \(\phi\) is a first-order expression, and \(x\) is any variable, then \((\forall x \phi)\) is a first-order expression as well.

These are all first-order expressions, or expressions for short, over \(\Sigma\). We shall use in our expressions the shorthands \(\Rightarrow\) and \(\Leftrightarrow\) as in Boolean logic. We shall also use \((\exists x \phi)\) as a shorthand for \(\lnot (\forall x \lnot \phi)\). The symbols \(\forall\) and \(\exists\) are called quantifiers. As we did in Boolean logic, we shall omit parentheses when there is no risk of ambiguity.