Section 2.6: Problem 1 Solution »

# Section 2.6: Models of Theories

A theory $T$ is a set of sentences closed under logical implication: $T\vDash\sigma\Rightarrow\sigma\in T$ .
The theory of a structure $\mathfrak{A}$ , $\mbox{Th}\mathfrak{A}$ , is the set of sentences true in $\mathfrak{A}$ .
The theory of a class of structures $\mathcal{K}$ , $\mbox{Th}\mathcal{K}$ , is the set of sentences true in every structure of $\mathcal{K}$ .

## Finite Models

A sentence is finitely valid iff it is true in every finite model.
• The negation of a finitely valid sentence is true in (some) infinite models only, and vice versa, if a sentence is true only in (some) infinite models, then its negation is finitely valid.
If a set of sentences has arbitrary large finite models, then it has an infinite model.
• If a sentence is true in all infinite models of a theory $T$ , then it is true in all models of $T$ of size $\ge n$ for some $n\in\mathbb{N}$ .
• The class of all finite models is not $EC_{\Delta}$ . The class of all infinite models is $EC_{\Delta}$ but not $EC$ .

## Size of Models

Assume the language has cardinality $\lambda$ .
(Löwenheim–Skolem, 1915, 1920) If $\Gamma$ is satisfiable, then $\Gamma$ is satisfiable in some structure of cardinality $\le\lambda$ . If $\Sigma$ has a model, then $\Sigma$ has a model of cardinality $\le\lambda$ .
(LST, i.e. Löwenheim–Skolem-Tarski) If $\Gamma$ is satisfiable in an infinite structure, then $\Gamma$ is satisfiable in some structure of cardinality $\kappa$ for every $\kappa\ge\lambda$ . If $\Sigma$ has an infinite model, then $\Sigma$ has a model of cardinality $\kappa$ for every $\kappa\ge\lambda$ .
• For a language of cardinality $\lambda$ , for any structure $\mathfrak{A}$ , there is an elementarily equivalent structure $\mathfrak{B}$ of cardinality $\le\lambda$ . If $\mathfrak{A}$ is infinite, then there is an elementarily equivalent structure $\mathfrak{B}$ of cardinality $\kappa$ for every $\kappa\ge\lambda$ .
• For example, the set of algebraic real numbers is elementarily equivalent to $(\mathbb{R};0,1,+,\cdot)$ .
• $\mathfrak{B}$ does not have to be isomorphic to $\mathfrak{A}$ even if they have the same cardinality: for example, for $(\mathbb{N};0,S,<,+,\cdot)$ there is an elementarily equivalent countable structure in which there is an “infinite” number.
• Skolem’s Paradox. For the set $A_{\mbox{ST}}$ of axioms for set theory, there is a countable model $\mathfrak{G}$ . In particular, $\mathfrak{G}$ is a model of the sentence that asserts that there are uncountably many sets. The paradox is resolved as follows: within $\mathfrak{G}$ there is no one-to-one function from $\mathbb{N}$ onto the universe $|\mathfrak{G}|$ , which does not mean there is no such function outside of $\mathfrak{G}$ .

## Theories

$\mbox{Th}\mathcal{K}$ is indeed a theory.
Proof 1. If $\mbox{Th}\mathcal{K}\vDash\sigma$ , then $\sigma$ is true in all models of $\mbox{Th}\mathcal{K}$ , but every structure $\mathfrak{A}\in\mbox{Th}\mathcal{K}$ is a model of $\mbox{Th}\mathcal{K}$ .
Proof 2. We can think of $\mbox{Th}\mathcal{K}$ as $\cap_{\mathfrak{A}\in\mathcal{K}}\mbox{Th}\mathfrak{A}$ . $\mathfrak{A}$ is a model of $\mbox{Th}\mathfrak{A}$ , hence, $\mathfrak{A}$ is a model of $\mbox{Th}\mathcal{K}$ , hence, if $\mbox{Th}\mathcal{K}\vDash\sigma$ , then $\sigma$ is true in $\mathfrak{A}$ (for all $\mathfrak{A}\in\mathcal{K}$ ).
• $\mbox{Cn}\Sigma=\mbox{Th}\mbox{Mod}\mbox{\Sigma}=\{\sigma|\Sigma\vDash\sigma\}$ is called the set of consequences of $\Sigma$ .
• $\Sigma\subseteq\mbox{Th}\mbox{Mod}\Sigma$ , $\mathcal{K}\subseteq\mbox{Mod}\mbox{Th}\mbox{\mathcal{K}}$ .
• $\mbox{Mod}\Sigma=\mbox{Mod}\mbox{Th}\mbox{Mod}\Sigma$ , $\mbox{Th}\mathcal{K}=\mbox{Th}\mbox{Mod}\mbox{Th}\mbox{\mathcal{K}}$ .
A theory $T$ is complete iff for every sentence $\sigma$ , either $T\vDash\sigma$ or $T\vDash\neg\sigma$ , or, equivalently, either $\sigma\in T$ or $\neg\sigma\in T$ .
• For every structure $\mathfrak{A}$ , $\mbox{Th}\mathfrak{A}$ is complete.
• For every class of structures $\mathcal{K}$ , $\mbox{Th}\mathcal{K}$ is complete iff for every $\mathfrak{A},\mathfrak{B}\in\mathcal{K}$ , $\mathfrak{A}\equiv\mathfrak{B}$ .
• A theory $T$ is complete iff any two models of $T$ are elementarily equivalent.
• If a theory $T$ is complete and satisfiable, then every strictly larger theory is not satisfiable, and every strictly smaller theory is not complete.
• Examples:
• The theory of fields is not complete: $1+1=0$ is true in some fields but not others.
• The theory of algebraically closed fields of characteristic $0$ is complete.
• The theory of the complex field $(\mathbb{C};0,1,+,\cdot)$ is complete.
A set of sentences $\Sigma$ is called categorical iff any two models of $\Sigma$ are isomorphic. A theory $T$ is $\lambda$ -categorical iff all the infinite models of cardinality $\lambda$ of $T$ are isomorphic.
• According to the LST, $\Sigma$ is (first-order) categorical iff $\Sigma$ does not have an infinite model.
(Łoś–Vaught Test for Completeness, 1954) If $T$ is a theory in a language of cardinality $\lambda$ , and $T$ does not have a finite model, then if $T$ is $\kappa$ -categorical ($\kappa\ge\lambda$ ), $T$ is complete.
• $(\mathbb{Q};<_{\mathbb{Q}})\equiv(\mathbb{R};<_{\mathbb{R}})$ as, due to Cantor, the theory of dense linear orderings without endpoints is $\aleph_{0}$ -categorical.
• The theory of algebraically closed fields of characteristic $0$ is $\lambda$ -categorical for any $\lambda\ge\aleph_{0}$ .
• The theory of the real field $(\mathbb{R};0,1,+,\cdot)$ is not $\lambda$ -categorical for any $\lambda$ .
A theory $T$ is axiomatizable iff there is a decidable set $\Sigma$ of sentences (axioms) such that $T=\mbox{Cn}\Sigma=\mbox{Th}\mbox{Mod}\Sigma$ . A theory $T$ is finitely axiomatizable iff there is a finite set $\Sigma$ of sentences (axioms) such that $T=\mbox{Cn}\Sigma=\mbox{Th}\mbox{Mod}\Sigma$ .
If $\mbox{Cn}\Sigma$ is finitely axiomatizable, then there is a finite subset $\Sigma_{0}\subseteq\Sigma$ such that $\mbox{Cn}\Sigma_{0}=\mbox{Cn}\Sigma$ .
• Examples:
• The theory of fields is (finitely) axiomatizable: if $\Phi$ is the (finite) set of field axioms, then the class of fields is $\mbox{Mod}\Phi$ , and the theory of fields is $\mbox{Th}\mbox{Mod}\Phi$ .
• The theory of fields of characteristic $0$ is axiomatizable: its axioms $\Phi_{0}$ consist of $\Phi$ and $\underbrace{1+\ldots+1}_{n}\neq0$ for every $n$ .
• The theory of algebraically closed fields of characteristic $0$ is axiomatizable: its axioms consist of $\Phi_{0}$ and $\forall x_{0}\ldots\forall x_{n}x_{n}\neq0\rightarrow\exists xx_{n}\cdot\underbrace{x\cdot\ldots\cdot x}_{n}+\ldots+x_{1}\cdot x+x_{0}=0$ for every $n$ .

## Decidability

• For a finite language, if $\mathfrak{A}$ is finite, $\mbox{Th}\mathfrak{A}$ is decidable.
• For a finite language, $\{\sigma|\sigma\mbox{ has a finite model}\}$ is effectively enumerable.
• For a finite language, let $\Phi$ be the set of sentences true in every finite model. Then $\Phi$ is not effectively enumerable (Trakhtenbrot’s Theorem, 1950), but $\overline{\Phi}$ is effectively enumerable.
• Therefore, the analogue of the enumerability theorem for finite structures is false: the set of finitely valid sentences is not effectively enumerable.
• For a finite language, if $\Sigma$ has the finite model property (every sentence is either true in a finite model, or not satisfiable), then whether a sentence $\sigma\in\Sigma$ is satisfiable is decidable.
• The set of satisfiable $\exists_{2}$ sentences is decidable. The set of valid $\forall_{2}$ sentences is decidable.
Decidability facts from the previous Section restated:
• If $\Gamma$ is decidable and the language is reasonable, then $\mbox{Th}\Gamma$ and $\{\phi|\Gamma\vDash\phi\}$ are effectively enumerable.
• An axiomatizable theory in a reasonable language is effectively enumerable.
• In fact, the converse holds as well. An effectively enumerable theory in a reasonable language is axiomatizable.
• If $\Gamma$ is decidable, the language is reasonable, and for every sentence $\sigma$ , $\Gamma\vDash\sigma$ or $\Gamma\vDash\neg\sigma$ , then $\{\sigma|\Gamma\vDash\sigma\}$ is decidable.
• A complete axiomatizable theory in a reasonable language is decidable.
• Examples:
• Set theory (if consistent) is not decidable, hence, not complete.
• Number theory is complete, but not decidable (not even effectively enumerable), hence, not axiomatizable.
• The theory of algebraically closed fields of characteristic $0$ is decidable.
• The theory of the complex field $(\mathbb{C};0,1,+,\cdot)$ is decidable.
• The theory of the real field $(\mathbb{R};0,1,+,\cdot)$ is also decidable, though it is not $\lambda$ -categorical for any $\lambda$ .
• The theory of dense linear orderings without endpoints is decidable.

## Prenex Normal Form

A prenex formula is one of the form $Q_{1}x_{1}\ldots Q_{n}x_{n}\alpha$ where $Q_{i}\in\{\forall,\exists\}$ and $\alpha$ is quantifier-free.
(Prenex Normal Form Theorem) For every wff $\phi$ there exists a logically equivalent prenex formula.