Structures

Structure. A structure (or interpretation) $$\mathfrak{A}$$ for a first-order language $$\mathcal{L}$$ is a function whose domain is the set of parameters and such that

1. $$\mathfrak{A}$$ assigns to the quantifier symbol $$\forall$$ a nonempty set $$|\mathfrak{A}|$$ called the universe (or domain) of $$\mathfrak{A}$$.
2. $$\mathfrak{A}$$ assigns to each $$n$$-place predicate symbol $$P$$ an $$n$$-ary relation $$P^\mathfrak{A} \subseteq |\mathfrak{A}|^n$$, i.e., $$P^\mathfrak{A}$$ is a set of $$n$$-tuples of members of the universe.
3. $$\mathfrak{A}$$ assigns to each constant symbol $$c$$ a member $$c^\mathfrak{A}$$ of the universe $$|\mathfrak{A}|$$.
4. $$\mathfrak{A}$$ assigns to each $$n$$-place function symbol $$f$$ an $$n$$-ary operation $$f^\mathfrak{A}$$ on $$|\mathfrak{A}|$$, i.e., $$f^\mathfrak{A} : |\mathfrak{A}|^n \to |\mathfrak{A}|$$.

Let $$\varphi$$ be a wff of the language $$\mathcal{L}$$, $$\mathfrak{A}$$ be a structure for the language $$\mathcal{L}$$, $$s : V \to |\mathfrak{A}|$$ be a function from the set $$V$$ of all variables into the universe $$|\mathfrak{A}|$$. We say that $$\mathfrak{A}$$ satisfies $$\varphi$$ with $$s$$, if and only if the translation of $$\varphi$$ determined by $$\mathfrak{A}$$, where the variable $$x$$ is translated as $$s(x)$$ wherever it occurs free, is true, written as $\models_\mathfrak{A} \varphi[s]$ Formally, we define the extension function from the set $$T$$ of all terms into the universe of $$\mathfrak{A}$$: $\bar{s} : T \to |\mathfrak{A}|$ such that

1. For each variable $$x$$, $$\bar{s}(x) = s(x)$$.
2. For each constant symbol $$c$$, $$\bar{s}(c) = c^\mathfrak{A}$$.
3. If $$t_1, \dots, t_n$$ are terms and $$f$$ is a $$n$$-place function symbol, then $\bar{s}(f t_1 \cdots t_n) = f^\mathfrak{A}(\bar{s}(t_1), \dots, \bar{s}(t_n))$

For atomic formulas,

1. $$\models_\mathfrak{A} = t_1 t_2 [s]$$ iff $$\bar{s}(t_1) = \bar{s}(t_2)$$.
2. $$\models_\mathfrak{A} P t_1 \cdots t_n [s]$$ iff $$\langle \bar{s}(t_1), \dots, \bar{s}(t_n) \rangle \in P^\mathfrak{A}$$.

For other wffs,

1. $$\models_\mathfrak{A} (\lnot \varphi) [s]$$ iff $$\not\models_\mathfrak{A} \varphi[s]$$.
2. $$\models_\mathfrak{A} (\varphi \to \psi) [s]$$ iff either $$\not\models_\mathfrak{A} \varphi[s]$$ or $$\models_\mathfrak{A} \psi[s]$$ or both.
3. $$\models_\mathfrak{A} \forall x \varphi[s]$$ iff for every $$d \in |\mathfrak{A}|$$, we have $$\models_\mathfrak{A} \varphi[s(x|d)]$$, where $$s(x|d)$$ is defined as $s(x|d)(y) = \begin{cases} s(y) & \text{if } y \neq x \\ d & \text{if } y = x \end{cases}$

Example 1. $$\mathfrak{A} = (\mathbb{N}; \leq, S, 0)$$ is a structure for a first-order language:

• $$|\mathfrak{A}| = \mathbb{N}$$, the set of all natural numbers,
• $$P^\mathfrak{A} =$$ the set of pairs $$\langle m, n \rangle$$ such that $$m \leq n$$,
• $$f^\mathfrak{A} =$$ the successor function $$S$$: $$f^\mathfrak{A}(n) = n + 1$$,
• $$c^\mathfrak{A} = 0$$.

Theorem 2. Assume that $$s_1$$ and $$s_2$$ are functions from $$V$$ into $$|\mathfrak{A}|$$ which agree at all variables that occur free in the wff $$\varphi$$. Then $\models_\mathfrak{A} \varphi[s_1] \iff \models_\mathfrak{A} \varphi[s_2]$

Proof. (By induction on $$\varphi$$.)

Theorem 3. If two structures $$\mathfrak{A}$$ and $$\mathfrak{B}$$ agree at all parameters that occur in $$\varphi$$, then $\models_\mathfrak{A} \varphi[s] \iff \models_\mathfrak{B} \varphi[s]$

Corollary 4. For a sentence $$\sigma$$, either

1. $$\mathfrak{A}$$ satisfies $$\sigma$$ with every function $$s : V \to |\mathfrak{A}|$$, or
2. $$\mathfrak{A}$$ does not satisfy $$\sigma$$ with any such function.

Model and truth. If a structure $$\mathfrak{A}$$ satisfies the sentence $$\sigma$$ with every function $$s : V \to |\mathfrak{A}|$$, we say that $$\sigma$$ is true in $$\mathfrak{A}$$ or that $$\mathfrak{A}$$ is a model of $$\sigma$$, written as $$\models_\mathfrak{A} \sigma$$. Otherwise $$\sigma$$ is false in $$\mathfrak{A}$$. For a set $$\Sigma$$ of sentences, $$\mathfrak{A}$$ is a model of $$\Sigma$$ iff it is a model of every $$\sigma \in \Sigma$$.

Logical implication and validity. Let $$\Gamma$$ be a set of wffs, $$\varphi$$ be a wff. $$\Gamma$$ logically implies $$\varphi$$, written as $$\Gamma \models \varphi$$, iff for every structure $$\mathfrak{A}$$ for the language and every function $$s : V \to |\mathfrak{A}|$$ such that $$\mathfrak{A}$$ satisfies every member of $$\Gamma$$ with $$s$$, $$\mathfrak{A}$$ also satisfies $$\varphi$$ with $$s$$.

We say that $$\varphi$$ and $$\psi$$ are logically equivalent iff $$\varphi \models \psi$$ and $$\psi \models \varphi$$.

A wff $$\varphi$$ is valid iff $$\emptyset \models \varphi$$, written simply as $$\models \varphi$$. That is, $$\varphi$$ is valid iff for every $$\mathfrak{A}$$ and every $$s : V \to |\mathfrak{A}|$$, $$\mathfrak{A}$$ satisfies $$\varphi$$ with $$s$$.

The concept of validity is the first-order analogue of the concept of tautology in sentential logic.

Corollary 5. For a set $$\Sigma; \tau$$ of sentences, $$\Sigma \models \tau$$ iff every model of $$\Sigma$$ is also a model of $$\tau$$. A sentence $$\tau$$ is valid iff it is true in every structure.