Section 2.6: Models of Theories

Finite Models

• 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 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

• 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{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}}$ .

• 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.

• According to the LST, $\Sigma$ is (first-order) categorical iff $\Sigma$ does not have an infinite model.

• $(\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$ .

• 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.

• 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