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–SkolemTarski) 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 onetoone 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 (firstorder) 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 quantifierfree.
(Prenex Normal Form Theorem) For every wff
there exists a logically equivalent prenex formula.