First order: semantics and modelling

Structures

Definition

In propositional calculus, it was enough to give each variable a value. Here, we must say what we are talking about. A structure $\mathcal{M}$ for a signature gives:

• a domain $D$, a non-empty set of objects;
• for each constant $c$, an object $c^{\mathcal{M}}$ of $D$;
• for each function symbol $f$ of arity $n$, a function $f^{\mathcal{M}} : D^n \to D$;
• for each predicate symbol $P$ of arity $n$, the set $P^{\mathcal{M}} \subseteq D^n$ of the $n$-tuples for which $P$ is true.

The value of a formula

To evaluate a formula that has free variables, we also fix an assignment $\sigma$: an object of $D$ for each variable. Terms are then computed bottom-up, and we define “$A$ is true in $\mathcal{M}$ under $\sigma$”, written $\mathcal{M}, \sigma \vDash A$:

• $P(t_1, \ldots, t_n)$ is true if the $n$-tuple of the values of the $t_i$ is in $P^{\mathcal{M}}$;
• the connectives follow their tables, as in chapter 2;
• $\forall x\, A$ is true if $A$ is true for every value of $x$ in $D$ (the other variables keeping their value);
• $\exists x\, A$ is true if $A$ is true for at least one value of $x$ in $D$.

A closed formula does not depend on $\sigma$: it is true or false in $\mathcal{M}$, and we write $\mathcal{M} \vDash A$.

The same words as in chapter 2

We take up the definitions again, replacing “interpretation” with “structure”:

• $\mathcal{M}$ is a model of a closed formula $A$ if $\mathcal{M} \vDash A$;
• $A$ is valid if it is true in every structure, satisfiable if it has a model, unsatisfiable otherwise;
• $\Sigma \vDash A$ if every model of $\Sigma$ is a model of $A$.

A major difference: there are infinitely many structures, and infinite domains. No more truth table to check everything. To show that $\Sigma \not\vDash A$, we exhibit a structure (a countermodel) that makes $\Sigma$ true and $A$ false, often on a small domain. To show that $\Sigma \vDash A$, we reason about an arbitrary structure, or we prove it (chapters 6 and 10).

Quantifiers and connectives

Useful equivalences

“It is not true that all swans are white” does indeed mean “there exists a swan that is not white”.

What does not work

• $\forall x\, (A \lor B) \not\equiv \forall x\, A \lor \forall x\, B$. Every integer is even or odd; but it is not true that every integer is even, nor that every integer is odd.
• $\exists x\, (A \land B) \not\equiv \exists x\, A \land \exists x\, B$. There exists an even integer and there exists an odd integer; there is no integer that is both even and odd.
• $\forall x\, \exists y\, A \not\equiv \exists y\, \forall x\, A$. “Everyone has a mother” is not “someone is everybody's mother”. We only have $\exists y\, \forall x\, A \vDash \forall x\, \exists y\, A$: if one and the same $y$ works for everyone, then each one has a $y$ that works for them.

Translating natural language

The four standard sentences

The order of quantifiers and the scope of negation

Natural language often leaves the order of quantifiers implicit, and lets negation float. “All the students did not pass” can mean “none passed” or “not all passed”. The formula, however, has to choose. When a sentence is ambiguous, we write down the possible readings, and say which one we adopt.

Syllogisms and non-empty domains

“All A are B; all C are A; therefore all C are B” is a valid argument:

Let $\mathcal{M}$ be a model of both hypotheses and $d$ an object of $D$ such that $C(d)$. By the second, $A(d)$; by the first, $B(d)$.

A valid argument does not say that its conclusions are true, only that they are if the hypotheses are. And some syllogisms of Aristotle's logic are no longer valid in first order: those that conclude “there exists” from “all” sentences. “All A are B” does not assert that there are A's: $\forall x\, (A(x) \to B(x))$ is true in a structure where no object is A.