Section 2.2: Truth and Models

Structures and Models

A structure $\mathfrak{A}$ for a given first-order language is a function on the set of parameters that assigns

to $\forall$ a nonempty set $|\mathfrak{A}|$ called the universe or domain of $\mathfrak{A}$ .
to every $n$ -place predicate symbol $P$ an $n$ -ary relation $P^{\mathfrak{A}}$ on $|\mathfrak{A}|$ .
to every constant symbol $c$ a member $c^{\mathfrak{A}}$ of $|\mathfrak{A}|$ .
to every $n$ -place function symbol $f$ an $n$ -ary operation $f^{\mathfrak{A}}$ on $|\mathfrak{A}|$ .

Let $\phi$ be a wff, and $s:V\rightarrow\mathfrak{A}$ , where $V$ is the set of all variables. Then, $\mathfrak{A}$ is said to satisfy $\phi$ with $s$ , $\vDash_{\mathfrak{A}}\phi[s]$ , iff

First, we extend $s$ to $\overline{s}$ defined for all terms as follows: a) for variables, $\overline{s}(x)=s(x)$ , b) for constants, $\overline{s}(c)=c^{\mathfrak{A}}$ , c) for functions of terms, $\overline{s}(ft_{1}\ldots t_{n})=f^{\mathfrak{A}}(\overline{s}(t_{1}),\ldots,\overline{s}(t_{n}))$ .
Second, we define satisfaction for all atomic formulas: a) $\vDash_{\mathfrak{A}}=t_{1}t_{2}[s]$ iff $\overline{s}(t_{1})=\overline{s}(t_{2})$ , b) $\vDash_{\mathfrak{A}}Pt_{1}\ldots t_{n}[s]$ iff $<\overline{s}(t_{1}),\ldots,\overline{s}(t_{n})>\in P^{\mathfrak{A}}$ .
Third, we extend the notion of satisfaction to all wffs: a) $\vDash_{\mathfrak{A}}\neg\phi[s]$ iff $\not\vDash_{\mathfrak{A}}\phi[s]$ , b) $\vDash_{\mathfrak{A}}(\phi\rightarrow\psi)[s]$ iff $\not\vDash_{\mathfrak{A}}\phi[s]$ or $\vDash_{\mathfrak{A}}\psi[s]$ , c) $\vDash_{\mathfrak{A}}\forall x\phi[s]$ iff for every $d\in|\mathfrak{A}|$ , $\vDash_{\mathfrak{A}}\phi[s(x|d)]$ where $s(x|d)$ is $s$ everywhere except for $x$ and $s(x|d)(x)=d$ .
- Another way is, given $\mathfrak{A}$ , to define recursively the function $\overline{h}(\phi)$ as the set of functions $s$ such that $\mathfrak{A}$ satisfies $\phi$ with $s$ .

Assume that $s$ and $s'$ agree at all variables that occur free in $\phi$ , then $\vDash_{\mathfrak{A}}\phi[s]$ iff $\vDash_{\mathfrak{A}}\phi[s']$ .

Similarly, if structures $\mathfrak{A}$ and $\mathfrak{B}$ agree at all the parameters that occur in $\phi$ , then $\vDash_{\mathfrak{A}}\phi[s]$ iff $\vDash_{\mathfrak{B}}\phi[s]$ for any $s$ .
The theorem justifies the following notation: $\vDash_{\mathfrak{A}}\phi[[a_{1},\ldots,a_{k}]]=\vDash_{\mathfrak{A}}\phi[s(v_{i}|a_{i})_{i=1}^{k}]$ where all free variables of $\phi$ are among $v_{1},\ldots,v_{k}$ .
For a sentence $\sigma$ either $\vDash_{\mathfrak{A}}\sigma[s]$ for every $s$ , or $\not\vDash_{\mathfrak{A}}\sigma[s]$ for every $s$ .

$\mathfrak{A}$ is a model of the sentence $\sigma$ iff $\sigma$ is true in $\mathfrak{A}$ , $\vDash_{\mathfrak{A}}\sigma$ , meaning $\vDash_{\mathfrak{A}}\sigma[s]$ for any $s$ . Otherwise, $\sigma$ is false in $\mathfrak{A}$ . $\mathfrak{A}$ is a model of a set of sentences iff it is a model of every sentence in the set.

Logical Implication

A set of wffs $\Gamma$ logically implies a wff $\phi$ , $\Gamma\vDash\phi$ , iff $\vDash_{\mathfrak{A}}\Gamma[s]$ implies $\vDash_{\mathfrak{A}}\phi[s]$ , for every structure $\mathfrak{A}$ for the language and every $s:V\rightarrow|\mathfrak{A}|$ .

Wffs $\phi$ and $\psi$ are logically equivalent iff $\phi\vDash\psi$ and $\psi\vDash\phi$ .
- $\Gamma;\phi\vDash\psi$ iff $\Gamma\vDash(\phi\rightarrow\psi)$ .
A wff $\phi$ is called valid, $\vDash\phi$ , iff $\emptyset\vDash\phi$ .
- $\phi$ and $\psi$ are logically equivalent iff $(\phi\leftrightarrow\psi)$ is valid.
- $\phi$ is valid iff $\forall x\phi$ is valid.
Sentences: $\Sigma\vDash\tau$ iff every model of $\Sigma$ is also a model of $\tau$ . $\tau$ is valid iff it is true in every structure.

Homomorphisms

$h:|\mathfrak{A}|\rightarrow|\mathfrak{B}|$ is a homomorphism of $\mathfrak{A}$ into $\mathfrak{B}$ iff it preserves predicates and functions (including constants) both ways (that is iff).

$h$ is an isomorphism (isomorphic embedding) of $\mathfrak{A}$ into $\mathfrak{B}$ iff it is a one-to-one homomorphism.
$\mathfrak{A}$ and $\mathfrak{B}$ are said to be isomorphic, $\mathfrak{A}\cong\mathfrak{B}$ , iff there is an isomorphism of $\mathfrak{A}$ onto $\mathfrak{B}$ .

Homomorphism Theorem. If $h$ is a homomorphism of $\mathfrak{A}$ into $\mathfrak{B}$ , and $s:V\rightarrow|\mathfrak{A}|$ , then

(a) For any term $t$ , $\overline{h\circ s}(t)=h(\overline{s}(t))$ .

(b) For any quantifier- and equality- free formula $\alpha$ , $\vDash_{\mathfrak{A}}\alpha[s]$ iff $\vDash_{\mathfrak{B}}\alpha[h\circ s]$ .

(c) In (b), $\alpha$ may contain the equality symbol if $h$ is one-to-one (isomorphism), and/or quantifier symbols if $h$ is onto.

$\mathfrak{A}$ is a substructure of $\mathfrak{B}$ , or, alternatively, $\mathfrak{B}$ is an extension of $\mathfrak{A}$ , iff $|\mathfrak{A}|\subseteq|\mathfrak{B}|$ and the identity map from $|\mathfrak{A}|$ into $|\mathfrak{B}|$ is an isomorphism.

The identity map in this case is an isomorphism iff a) for every predicate $P$ , $P^{\mathfrak{A}}$ is the restriction of $P^{\mathfrak{B}}$ to $|\mathfrak{A}|$ , b) for every constant $c$ , $c^{\mathfrak{A}}=c^{\mathfrak{B}}$ , and c) for every function $f$ , $f^{\mathfrak{A}}$ is the restriction of $f^{\mathfrak{B}}$ to $|\mathfrak{A}|$ .
For every structure $\mathfrak{A}$ and function $h$ such that $\mbox{ran}h=|\mathfrak{A}|$ , there is a structure $\mathfrak{B}$ such that $h$ is a homomorphism of $\mathfrak{B}$ onto $\mathfrak{A}$ .
For every structure $\mathfrak{A}$ and one-to-one function $h$ such that $\mbox{dom}h=|\mathfrak{A}|$ , there is a unique structure $\mathfrak{B}$ such that $h$ is an isomorphism of $\mathfrak{A}$ onto $\mathfrak{B}$ .
If $h$ is an isomorphic embedding of $\mathfrak{A}$ into $\mathfrak{B}$ , there is a structure $\mathfrak{C}$ such that $\mathfrak{A}$ is a substructure of $\mathfrak{C}$ , and $\mathfrak{C}$ is isomorphic to $\mathfrak{B}$ .

A universal ( $\forall_{1}$ ) formula is of the form $\forall v_{1}\ldots\forall v_{n}\theta$ where $\theta$ is quantifier-free. An existential ( $\exists_{1}$ ) formula is of the form $\exists v_{1}\ldots\exists v_{n}\theta$ where $\theta$ is quantifier-free. In general, a $\forall_{n}$ formula is of the form $\forall v_{1}\ldots\forall v_{n}\theta$ where $\theta$ is an $\exists_{n-1}$ formula. An $\exists_{n}$ formula is of the form $\exists v_{1}\ldots\exists v_{n}\theta$ where $\theta$ is a $\forall_{n-1}$ formula.

If $\mathfrak{A}$ is a substructure of $\mathfrak{B}$ , $s:V\rightarrow|\mathfrak{A}|$ , then if $\phi$ is $\exists_{1}$ then $\vDash_{\mathfrak{A}}\phi[s]$ implies $\vDash_{\mathfrak{B}}\phi[s]$ , and if $\phi$ is $\forall_{1}$ then $\vDash_{\mathfrak{B}}\phi[s]$ implies $\vDash_{\mathfrak{A}}\phi[s]$ .
If $\mathfrak{A}$ is a model of an $\exists_{2}$ sentence $\sigma$ , and the language does not have any function or constant symbols, then there is a finite substructure of $\mathfrak{A}$ that is a model of $\sigma$ .

An isomorphism of $\mathfrak{A}$ onto $\mathfrak{A}$ is called an automorphism.

The identity map is an automorphism. If there are other automorphisms, $\mathfrak{A}$ is called rigid.
If $R$ is an $n$ -ary relation on $|\mathfrak{A}|$ definable in $\mathfrak{A}$ , then an automorphism preserves it.
- This can be used to show that some relations are not definable (see Definability in a Structure below): $\mathbb{N}$ is not definable in $(\mathbb{R},<)$ , $h(x)=x/2$ ; the length is not definable in a vector space via addition and scalar multiplication, $h(v)=2v$ .

Elementarily equivalent structures

$\mathfrak{A}$ and $\mathfrak{B}$ are elementarily equivalent, $\mathfrak{A}\equiv\mathfrak{B}$ , iff for any sentence $\sigma$ , $\vDash{}_{\mathfrak{A}}\sigma$ iff $\vDash_{\mathfrak{B}}\sigma$ .

Isomorphic structures are elementarily equivalent: $\mathfrak{A}\cong\mathfrak{B}$ implies $\mathfrak{A}\equiv\mathfrak{B}$ .
- If $\mathfrak{A}$ is finite, $\mathfrak{A}\equiv\mathfrak{B}$ implies $\mathfrak{A}\cong\mathfrak{B}$ .
$(\mathbb{R};<_{R})$ and $(\mathbb{Q};<_{Q})$ are elementarily equivalent but not isomorphic.
$(\mathbb{N};<_{N})$ and $(\mathbb{R};<_{R})$ are not elementarily equivalent, but every $\exists_{2}$ sentence true in $(\mathbb{R};<_{R})$ is true in $(\mathbb{N};<_{N})$ .

An elementary type of a structure $\mathfrak{A}$ is the class of all structures elementarily equivalent to $\mathfrak{A}$ .

Definability in a Structure

A wff $\phi$ defines the $k$ -ary relation $R$ in $\mathfrak{A}$ iff $R=\{<a_{1},\ldots,a_{k}>|\vDash_{\mathfrak{A}}\phi[[a_{1},\ldots,a_{k}]]\}$ where the free variables of $\phi$ are among $v_{1},\ldots,v_{k}$ .

A $k$ -ary relation on $|\mathfrak{A}|$ is definable in $\mathfrak{A}$ iff there is $\phi$ that defines it.
A $k$ -ary relation on $|\mathfrak{A}|$ is definable from points in $\mathfrak{A}$ (a more common name definable from parameters in $\mathfrak{A}$ ) iff it is definable in $\mathfrak{A}^{+}$ , where $\mathfrak{A}^{+}$ is $\mathfrak{A}$ plus a constant symbol for each element of $|\mathfrak{A}|$ .
Examples.

In $\mathfrak{N}=(\mathbb{N};<,+,\cdot)$ all decidable relations are definable, but there are many others (see Section 3.5).

In $\mathfrak{R}=(\mathbb{R};<,+,\cdot)$ a set is definable iff it is a finite union of intervals with algebraic endpoints. A set is definable from points iff it is a finite union of intervals.

In $(\mathbb{R};<)$ there are $2^{1}$ definable unary relations, $2^{3}$ definable binary relations, $2^{13}$ definable ternary relations etc. (see Exercise 14).

If $\mathfrak{A}\equiv\mathfrak{R}=(\mathbb{R};<,+,\cdot)$ , then any non-empty, bounded and definable from points subset of $|\mathfrak{A}|$ has a least upper bound in $|\mathfrak{A}|$ .

Definability of a Class of Structures

For a set of sentences $\Sigma$ let $\mbox{Mod}\Sigma$ be the class of all models of $\Sigma$ .

A class $\mathcal{K}$ of structures for the language is an elementary class ( $EC$ ) iff $\mathcal{K}=\mbox{Mod}\tau$ for some sentence $\tau$ .

A class $\mathcal{K}$ of structures for the language is an elementary class in the wider sense ( $EC{}_{\Delta}$ ) iff $\mathcal{K}=\mbox{Mod}\Sigma$ for some set of sentences $\Sigma$ .

A class $\mathcal{K}$ is elementarily closed ( $ECL$ ) iff with any structure, $\mathcal{K}$ also contains all elementarily equivalent structures.
- $\mathcal{K}$ is elementarily closed iff $\mathcal{K}$ is a union of $EC_{\Delta}$ classes.
Examples:
- Given the language $(\forall,E)$ , the class of all directed graphs is an elementary class for the axiom “ $\forall x(\neg xEx\wedge\forall y(Exy\rightarrow Eyx))$ ”, but the class of all finite graphs is not an elementary class.
- Given the language $(=,\forall,\circ)$ , the class of all groups is $EC$ , but the class of all infinite groups is $EC_{\Delta}$ but not $EC$ .
- Given the language $(=,\forall,0,1,+,\cdot)$ , the class of all fields is $EC$ , but the class of all fields of characteristic zero is $EC_{\Delta}$ but not $EC$ .

The spectrum of a sentence $\sigma$ is the set of all positive integers $n$ such that there is a model of $\sigma$ of size $n$ . A subset $A$ of positive integers in a spectrum if there is

such $A$ is the spectrum of $\sigma$ .

The set of even numbers is a spectrum, see Exercise 16. The set of powers of prime numbers is a spectrum (for the field axioms).
Whether the complement of a spectrum is a spectrum is an open question, related to the question whether co-NP=NP.

Subpages

Section 2.2: Truth and Models

Section 2.2: Truth and Models

Structures and Models

Logical Implication

Homomorphisms

Elementarily equivalent structures

Definability in a Structure

Definability of a Class of Structures