9. Syntax of First-Order Logic
We now begin the second part of the course on First-Order Logic (which we will regularly shorten to FOL) with some discussion and a formal definition of FOL formulas.
Motivation
To see why we need to go beyond propositional logic in the study of mathematics, consider the following basic argument:
\[\begin{align*} 3+2 &= 5 \\ 5 &> 1 \\ \hline \therefore~~ 3+2 &> 1 \end{align*}\]We can analyze this argument with propositional logic. The three statements “\(3+2=5\)”, “\(5 > 1\)”, and “\(3+2 > 1\)” are each propositions. And all three of these propositions are atomic since we can’t break them up into simpler propositions with our logical connectives \(\wedge\), \(\vee\), \(\neg\), \(\to\), and \(\leftrightarrow\). So the only formalization of this argument we can make is by assigning each of these propositions their own variable:
\[\begin{align*} p: & ~~ 3+2 = 5\\ q: & ~~ 5 > 1 \\ r: & ~~ 3+2 > 1. \end{align*}\]The original argument can be analyzed using these propositional variables. Its premises form the set \(\{p, q\}\) and its conclusion is \(r.\) But \(\{p,q\} \not\vDash r,\) so we cannot verify the validity of the argument using propositional logic.
What went wrong here?
The problem is that we have to “break up” the atomic propositions above to properly analyze the argument. We have to use the fact that “\(3 + 2 = 5\)” and “\(5 > 1\)” are not just generic and completely independent statements but rather statements about numbers that involve specific constants (here, 2, 3, 5, and 1) from some domain, functions (like addition) applied to the numbers, and predicates (like equality or greater than) about the numbers that are either true or false.
This is exactly what first-order logic will let us do.
Symbols and Signatures
Just like in propositional logic, the formulas that we analyze in first-order logic are strings from a formal first-order language. Unlike in propositional logic, however, we do not define a single first-order language but rather a whole class of languages. The strings in first-order languages contain two types of symbols. The logical symbols are common to all first-order languages. They consist of:
- the logical connective symbols \(\wedge\), \(\vee\), \(\neg\), \(\to\), and \(\leftrightarrow\);
- the logical quantifier symbols \(\forall\) and \(\exists\);
- the punctuation symbols “\((\)”, “\()\)”, and “\(,\)”;
- the variable symbols \(x_1,x_2,x_3,\ldots\); and
- the equality predicate symbol “\(=\)”.
The non-logical symbols vary from language to language. They include three types of symbols:
- a set of constant symbols;
- a set of function symbols; and
- a set of predicate symbols.
In addition, each function and predicate symbol in a first-order language is associated with a positive integer \(k\) which we call its arity. Functions and predicates of arity 1 are called unary; those of arity 2 are called binary.
The signature of a first-order language defines the constant, function, and predicate symbols of the language as well as the arity of each function and predicate symbol.
The basic object of study in a first-order language is a set of elements. (These elements might be numbers, graphs, sets, or other types of objects, depending on the language and its interpretation; we will discuss this topic in more detail in the next lecture when we formally define the notioin of domain.) The constants in a first-order language represent specific elements. Functions of arity \(n\) map each \(n\)-tuple of elements to a single element. And predicates of arity \(n\) are statements about \(n\)-tuples of elements that areeither True or False.
Examples of Signatures:
Number theory. One signature for number theory is \(\{0, S, +, \times\}\) where $0$ is a constant, $S$ is a unary function (that represents the successor function), and \(+\) and \(\times\) are binary functions. This signature does not contain any predicate symbols.
Number theory (2). An alternative signature for number theory is \(\{0,1, S,+, \times, E, <\}\) with two constants \(0\) and \(1\), the unary function \(S\), the binary functions \(+, \times, E\) and the binary predicate \(<\).
Set theory. The standard signature for set theory is \(\{\in\}\), with a single binary predicate \(\in\) but no constant or function symbols.
Graph theory. A signature for graph theory is \(\{E\}\) with a single binary predicate \(E\).
As we saw in the case of number theory, different signatures can be used to encode the same theory in first-order logic. And different signatures can also have overlapping symbols. This was the case above with \(E\), which represents exponentiation in number theory and edges in graph theory. Typically, we choose the symbols in the signature of a first-order language to best represent its meaning. But it’s worth pointing out that at this stage we do not associate any fixed meaning to constants, functions, or predicates. We will see how to do this when we discuss the semantics of first-order languages in the next lecture.
Terms and Formulas
The terms of a first-order language are the strings that represent elements of the language. The set of strings that form terms is defined recursively.
Definition. A string \(s\) is a term if and only if:
- \(s\) consists of a single variable or constant symbol;
- \(s = f(t_1,\ldots,t_n)\) where \(f\) is an \(n\)-ary function symbol and \(t_1,\ldots,t_n\) are all terms; or
- \(s = (t_1 \,\circ\, t_2)\) where \(\circ\) is a binary function symbol and \(t_1\), \(t_2\) are both terms.
Examples of Terms:
- $(3+2)$
- $S(S(S(S(0))))$
- $(x_1 + (x_2 \times 0))$
- $+(x_1,\times(x_2,0))$
- $x_{23}$
The formulas of a first-order language are also defined recursively.
Definition. A string \(s\) is a formula if and only if:
\(s = P(t_1,\ldots,t_n)\) for some \(n\)-ary predicate \(P\) and \(n\) terms \(t_1,\ldots,t_n\); or
\(s = (t_1 \circ t_2)\) for some binary predicate \(\circ\) and terms \(t_1\), \(t_2\); or
\(s\) is a string of the form
\[(\phi \wedge \psi), \quad (\phi \vee \psi), \quad \neg \phi, \quad (\phi \to \psi), \quad (\phi \leftrightarrow \psi)\]for some formulas \(\phi\) and \(\psi\); or
\(s = \forall x \,\phi\) or \(s = \exists x \, \phi\) for some variable \(x\) and formula \(\phi\).
Examples of Formulas:
- $((((3+2) = 5) \wedge (5 > 1)) \to ((3+2) > 1))$
- $(x_1 \in x_1)$
- $(S(x_1) = 0)$
- $\forall x_1 \exists x_2\, (\neg(x_1=x_2) \wedge E(x_1,x_2))$
Unique Parsing Theorem
The definitions of formulas and terms ensures that the Unique Parsing property we established for propositional logic also holds for first-order languages.
Theorem. (Unique Parsing Theorem for First-Order Logic) Every formula \(\phi\) in a first-order language \(L(\sigma)\) has a unique decomposition in exactly one of the following forms:
- \(\phi = P(t_1,\ldots,t_n)\) for some \(n\)-ary predicate \(P\) and \(n\) terms \(t_1,\ldots,t_n\).
- \(\phi = (t_1 \circ t_2)\) for some binary predicate \(\circ\) and terms \(t_1,t_2.\)
- \(\phi = \neg \psi\) for some formula \(\psi\).
- \(\phi = (\psi \,\square\, \theta)\) for some formulas \(\psi,\theta\) and some binary logical connective \(\square \in \{\wedge, \vee, \to, \leftrightarrow\}.\)
- \(\phi = \exists v \, \psi\) or \(\phi = \forall v \, \psi\) for some variable \(v\) and formula \(\phi\).
Moreover, every term \(t\) has a unique decomposition in exactly one of the following forms:
- \(t = x\) for some variable symbol \(x\).
- \(t = c\) for some constant symbol \(c\).
- \(t = f(t_1,\ldots,t_n)\) for some \(n\)-ary function symbol \(f\) and \(n\) terms \(t_1,\ldots,t_n\).
- \(t = (t_1 \circ t_2)\) for some binary function symbol \(\circ\) and terms \(t_1, t_2.\)
The proof of this theorem proceeds by induction on the length of the string representing the formula or the term, as in the proof of the Unique Parsing Theorem for Propositional Logic. This theorem guarantees that each formula in a first-order language has a unique parse tree representation. For example, the parse tree for the formula
\[(( P(0) \wedge \forall x (P(x) \to P(S(x)))) \to \forall y P(y))\]with the unary predicate \(P\) and unary function \(S\) is
A formula is atomic when it is of the form \(P(t_1,\ldots,t_n)\) for some predicate \(P\) and terms \(t_1,\ldots,t_n\). It is a compound formula otherwise.
Variable symbols can (and often do) appear multiple times in a formula. Each instance of a variable symbol appears in a leaf of the parse tree for the formula. An instance of the variable \(v\) is bound when it is below a node labelled \(\forall v \, \phi\) or \(\exists v \, \phi\) for some formula \(\phi\). It is free otherwise.
A formula is closed when it contains no instance of a free variable. Closed formulas are also called sentences.
Examples:
- \((( P(0) \wedge \forall x_1 (P(x_1) \to P(S(x_1)))) \to \forall x_2 P(x_2))\) is a closed formula because both instances of \(x_1\) and the single instance of \(x_2\) are all bound.
- \(((1+0) = 1)\) is also a closed formula since it does not contain any free variables.
- In the formula \(\forall x_1 E(x_1,x_2)\), the single instance of \(x_1\) is bound but the instance of \(x_2\) is free. Therefore, this formula is not closed.
- The formula \(((x_1=x_1) \wedge \exists x_1 \, \neg(x_1 = 0))\) constains three instances of the variable \(x_1\). The first two are free and the last one is bound. The formula is not closed.
Sentences will be the main object of our study, as we will see starting in the next lecture when we describe how to interpret first-order languages and evaluate sentences to determine when they are True and when they are False.