Section 2.6: Problem 1 Solution »

Section 2.6: Models of Theories

A theory is a set of sentences closed under logical implication: .
The theory of a structure , , is the set of sentences true in .
The theory of a class of structures , , is the set of sentences true in every structure of .

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 , then it is true in all models of of size for some .
  • The class of all finite models is not . The class of all infinite models is but not .

Size of Models

Assume the language has cardinality .
(Löwenheim–Skolem, 1915, 1920) If is satisfiable, then is satisfiable in some structure of cardinality . If has a model, then has a model of cardinality .
(LST, i.e. Löwenheim–Skolem-Tarski) If is satisfiable in an infinite structure, then is satisfiable in some structure of cardinality for every . If has an infinite model, then has a model of cardinality for every .
  • For a language of cardinality , for any structure , there is an elementarily equivalent structure of cardinality . If is infinite, then there is an elementarily equivalent structure of cardinality for every .
    • For example, the set of algebraic real numbers is elementarily equivalent to .
    • does not have to be isomorphic to even if they have the same cardinality: for example, for there is an elementarily equivalent countable structure in which there is an “infinite” number.
  • Skolem’s Paradox. For the set of axioms for set theory, there is a countable model . In particular, is a model of the sentence that asserts that there are uncountably many sets. The paradox is resolved as follows: within there is no one-to-one function from onto the universe , which does not mean there is no such function outside of .

Theories

is indeed a theory.
Proof 1. If , then is true in all models of , but every structure is a model of .
Proof 2. We can think of as . is a model of , hence, is a model of , hence, if , then is true in (for all ).
  • is called the set of consequences of .
  • , .
    • , .
A theory is complete iff for every sentence , either or , or, equivalently, either or .
  • For every structure , is complete.
  • For every class of structures , is complete iff for every , .
  • A theory is complete iff any two models of are elementarily equivalent.
  • If a theory 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: is true in some fields but not others.
    • The theory of algebraically closed fields of characteristic is complete.
      • The theory of the complex field is complete.
A set of sentences is called categorical iff any two models of are isomorphic. A theory is -categorical iff all the infinite models of cardinality of are isomorphic.
  • According to the LST, is (first-order) categorical iff does not have an infinite model.
(Łoś–Vaught Test for Completeness, 1954) If is a theory in a language of cardinality , and does not have a finite model, then if is -categorical ( ), is complete.
  • as, due to Cantor, the theory of dense linear orderings without endpoints is -categorical.
  • The theory of algebraically closed fields of characteristic is -categorical for any .
  • The theory of the real field is not -categorical for any .
A theory is axiomatizable iff there is a decidable set of sentences (axioms) such that . A theory is finitely axiomatizable iff there is a finite set of sentences (axioms) such that .
If is finitely axiomatizable, then there is a finite subset such that .
  • Examples:
    • The theory of fields is (finitely) axiomatizable: if is the (finite) set of field axioms, then the class of fields is , and the theory of fields is .
    • The theory of fields of characteristic is axiomatizable: its axioms consist of and for every .
    • The theory of algebraically closed fields of characteristic is axiomatizable: its axioms consist of and for every .

Decidability

  • For a finite language, if is finite, is decidable.
  • For a finite language, is effectively enumerable.
  • For a finite language, let be the set of sentences true in every finite model. Then is not effectively enumerable (Trakhtenbrot’s Theorem, 1950), but 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 has the finite model property (every sentence is either true in a finite model, or not satisfiable), then whether a sentence is satisfiable is decidable.
      • The set of satisfiable sentences is decidable. The set of valid sentences is decidable.
Decidability facts from the previous Section restated:
  • If is decidable and the language is reasonable, then and 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 is decidable, the language is reasonable, and for every sentence , or , then 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 is decidable.
      • The theory of the complex field is decidable.
    • The theory of the real field is also decidable, though it is not -categorical for any .
    • The theory of dense linear orderings without endpoints is decidable.

Prenex Normal Form

A prenex formula is one of the form where and is quantifier-free.
(Prenex Normal Form Theorem) For every wff there exists a logically equivalent prenex formula.