First order: the language

What propositional calculus cannot say

“All students like logic. Paul is a student. Therefore Paul likes logic.” The reasoning is correct, but propositional calculus does not see it: it can only give a variable to each sentence, $p$, $q$, $r$, and $\{p, q\} \vDash r$ is false. What makes the reasoning correct lies inside the sentences: an object (Paul), properties (being a student, liking logic), and the word “all”.

First-order logic (or predicate calculus) adds what is needed to talk about objects: names of objects, functions, properties and relations, and two quantifiers, “for all” and “there exists”.

The ingredients

The signature

We first choose the vocabulary of the domain we are talking about, the signature:

• constants: names of specific objects, such as $a$, $\mathit{paul}$, $0$;
• function symbols, each with its arity (its number of arguments): $f$ of arity 1, $+$ of arity 2, $\textit{mère}$ (“mother of”) of arity 1;
• predicate symbols, with their arity: $\mathit{Etud}$ of arity 1 (“is a student”), $\mathit{Aime}$ of arity 2 (“likes”), $<$ of arity 2.

In addition, we have infinitely many variables: $x$, $y$, $z$, $x_1$…

Terms

Terms denote objects:

1. a variable or a constant is a term;
2. if $f$ is a function symbol of arity $n$ and $t_1, \ldots, t_n$ are terms, $f(t_1, \ldots, t_n)$ is a term.

Examples: $x$, $\mathit{paul}$, $\textit{mère}(\mathit{paul})$, $f(x, g(a))$. A term is neither true nor false: it denotes something.

Formulas

1. If $P$ is a predicate symbol of arity $n$ and $t_1, \ldots, t_n$ are terms, $P(t_1, \ldots, t_n)$ is a formula, called atomic. Equality $t_1 = t_2$ is often allowed as well.
2. If $A$ and $B$ are formulas, so are $\lnot A$, $A \land B$, $A \lor B$, $A \to B$ and $A \leftrightarrow B$.
3. If $A$ is a formula and $x$ a variable, $\forall x\, A$ (“for all $x$, $A$”) and $\exists x\, A$ (“there exists $x$ such that $A$”) are formulas.

Example: $\forall x\, (\mathit{Etud}(x) \to \mathit{Aime}(x, \mathit{log}))$ says “every student likes logic”.

The scope of a quantifier

A quantifier, like $\lnot$, applies to the shortest formula that follows it. So $\forall x\, P(x) \to Q(x)$ reads $(\forall x\, P(x)) \to Q(x)$, and the last $x$ is not affected by the $\forall$. For it to be, we write $\forall x\, (P(x) \to Q(x))$.

Free and bound variables

Definition

In $\forall x\, A$ or $\exists x\, A$, the formula $A$ is the scope of the quantifier. An occurrence of a variable $x$ is bound if it lies within the scope of a quantifier on $x$; it is then bound by the nearest one. Otherwise, it is free.

A variable is free in a formula if it has at least one free occurrence in it. A formula with no free variable is closed (a sentence): it is a statement that will be true or false. A formula with free variables is rather a property of those variables: $\exists y\, (x = 2 \times y)$ says “$x$ is even”, and is neither true nor false as long as $x$ is not fixed.

Renaming

The name of a bound variable does not matter: $\forall x\, P(x)$ and $\forall y\, P(y)$ say the same thing, just like $\sum_{i=1}^n i$ and $\sum_{j=1}^n j$. So we can rename a bound variable, with a fresh name (one that does not occur in the scope), without changing the meaning.

We use this so that no variable is both free and bound, or bound by two quantifiers: in the example, $\forall u\, (P(u) \to \exists y\, R(u, y)) \land Q(x, z)$. Each name now has only one role.

Substitution

Definition

$A[x := t]$ denotes the formula obtained by replacing, in $A$, all the free occurrences of $x$ by the term $t$. Bound occurrences do not move: they denote another $x$.

Capture

Substitution has a pitfall. Let $A = \exists y\, (y > x)$, “there exists a number greater than $x$”, true for every $x$ in the integers. Let us replace $x$ by $y$:

The $y$ we wanted to bring in has been captured by $\exists y$: the formula now says “some number is greater than itself”, which is false. The meaning has changed.

The rule: before substituting, rename the bound variables of $A$ that occur in $t$. Here, we first rename $y$ to $z$: $\exists z\, (z > x)$, then substitute: $\exists z\, (z > y)$. We say that $t$ is free for $x$ in $A$ when no variable of $t$ would be captured.