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.