2.3 Structures and Interpretations

In first order logic, formulas do not have meaning by themselves, and meaning is provided by specifying a structure in which the symbols of the language are interpreted as actual objects, functions, and relations.

Structures

A structure consists of a domain together with interpretations of all symbols in the signature, and it serves as the semantic environment in which formulas are evaluated.

Definition 2.19 (Structure)

A structure $\mathcal{M}$ for a given signature consists of the following data.

A non empty set:

M

called the domain of the structure.

For each constant symbol $c$ , an element:

c^{\mathcal{M}} \in M

For each function symbol $f$ of arity $n$ , a function:

f^{\mathcal{M}} : M^n \to M

For each predicate symbol $P$ of arity $n$ , a relation:

P^{\mathcal{M}} \subseteq M^n

Thus every symbol in the language is assigned a concrete meaning inside the structure.

Example 2.20

Let $\mathcal{M}$ be a structure with domain:

M = \mathbb{N}

Suppose the signature contains a constant symbol $0$ , a unary function symbol $s$ , and a binary predicate symbol $<$ .

We may interpret these symbols as follows:

0^{\mathcal{M}} = 0

s^{\mathcal{M}}(x) = x + 1

<^{\mathcal{M}} = \{(x, y) \in \mathbb{N}^2 : x < y\}

This structure represents the natural numbers with their usual operations and relations.

Assignments

Formulas may contain free variables, and to interpret such formulas we need to assign elements of the domain to these variables.

Definition 2.21 (Assignment)

An assignment in a structure $\mathcal{M}$ is a function:

s : \mathrm{Var} \to M

which assigns to each variable an element of the domain.

Thus an assignment tells us which object each variable refers to.

Interpretation of Terms

Terms denote elements of the domain once a structure and an assignment have been fixed.

Definition 2.22 (Value of a Term)

Let $\mathcal{M}$ be a structure and $s$ an assignment.

The value of a term $t$ in $\mathcal{M}$ under $s$ , written:

t^{\mathcal{M}, s}

is defined inductively.

If $t$ is a variable $x$ , then:

t^{\mathcal{M}, s} = s(x)

If $t$ is a constant symbol $c$ , then:

t^{\mathcal{M}, s} = c^{\mathcal{M}}

If $t = f(t_1, \dots, t_n)$ , then:

t^{\mathcal{M}, s} = f^{\mathcal{M}}(t_1^{\mathcal{M}, s}, \dots, t_n^{\mathcal{M}, s})

This definition assigns a unique element of the domain to every term.

Example 2.23

In the structure of natural numbers described above, let the assignment $s$ be given by:

s(x) = 2

Then:

x^{\mathcal{M}, s} = 2

and:

s(x)^{\mathcal{M}, s} = 3

if $s$ denotes the successor function.

Interpretation of Atomic Formulas

Atomic formulas express basic relations between terms.

Definition 2.24 (Truth of Atomic Formulas)

Let $\mathcal{M}$ be a structure and $s$ an assignment.

If $A$ is an atomic formula of the form:

P(t_1, \dots, t_n)

then:

\mathcal{M}, s \models A

if and only if:

(t_1^{\mathcal{M}, s}, \dots, t_n^{\mathcal{M}, s}) \in P^{\mathcal{M}}

If $A$ is of the form:

t_1 = t_2

then:

\mathcal{M}, s \models A

if and only if:

t_1^{\mathcal{M}, s} = t_2^{\mathcal{M}, s}

Thus atomic formulas are evaluated by checking whether the corresponding relation holds in the structure.

Extension to All Formulas

The truth of general formulas is defined recursively.

Definition 2.25 (Satisfaction)

Let $\mathcal{M}$ be a structure and $s$ an assignment.

The relation:

\mathcal{M}, s \models A

is defined inductively.

For atomic formulas, the definition is as above.

For negation:

\mathcal{M}, s \models ¬A

if and only if:

\mathcal{M}, s \not\models A

For conjunction:

\mathcal{M}, s \models A \land B

if and only if:

\mathcal{M}, s \models A \quad \text{and} \quad \mathcal{M}, s \models B

The other connectives are defined similarly.

For the universal quantifier:

\mathcal{M}, s \models \forall x \, A

if and only if for every element $a \in M$ , we have:

\mathcal{M}, s[x \mapsto a] \models A

For the existential quantifier:

\mathcal{M}, s \models \exists x \, A

if and only if there exists an element $a \in M$ such that:

\mathcal{M}, s[x \mapsto a] \models A

Here $s[x \mapsto a]$ denotes the assignment that agrees with $s$ except that it assigns $a$ to $x$ .

Example 2.26

Let $\mathcal{M}$ be the structure of natural numbers, and let $s$ be any assignment.

Then:

\mathcal{M}, s \models \forall x \, (x = x)

because for every element $a \in \mathbb{N}$ :

a = a

holds.

However:

\mathcal{M}, s \models \exists x \, (x < 0)

is false, because there is no natural number less than $0$ .

Lemma 2.27 (Uniqueness of Evaluation)

For every structure $\mathcal{M}$ , assignment $s$ , and formula $A$ , the truth value of $A$ is uniquely determined.

Proof

The proof is by structural induction on formulas.

The value of atomic formulas is uniquely determined by the interpretation of symbols and the values of terms.

The logical connectives define truth values uniquely from the truth values of their components.

The quantifiers define truth uniquely by ranging over all elements of the domain.

Thus every formula has a well defined truth value in a given structure under a given assignment.

Closed Formulas

If a formula has no free variables, then its truth does not depend on the assignment.

In this case we write:

\mathcal{M} \models A

to mean that $A$ is true in the structure $\mathcal{M}$ .

Such formulas are called sentences, and they express properties of the structure itself rather than properties of particular elements.

Example 2.28

In the structure of natural numbers:

\mathcal{M} \models \forall x \, (x = x)

but:

\mathcal{M} \models \exists x \, (x < 0)

does not hold.

Thus sentences describe global properties of the domain and its operations.