models constructed from constants
The definition of a structure and of the satisfaction relation is
nice, but it raises the following question : how do we get models in
the first place? The most basic construction for models of
first-order theory is the construction that uses constants. Throughout
this entry, is a fixed first-order language.
Let be a set of constant symbols of , and be a theory in
. Then we say is a set of witnesses for if and only
if for every formula with at most one free variable ,
we have for some .
Lemma.
Let is any consistent
set of sentences of , and is a set of new symbols
such that . Let . Then there is a consistent
set extending and which has as set of
witnesses.
Lemma.
If is a consistent theory in , and is a set of witnesses
for in , then has a model whose elements are the constants
in .
Proof:
Let be the signature for . If is a consistent set of
sentences of , then there is a maximal consistent .
Note that and have the same sets of witnesses. As every
model of is also a model of , we may assume is maximal
consistent.
We let the universe of be the set of equivalence classes
, where if and only if . As is
maximal consistent, this is an equivalence relation. We interpret the
non-logical symbols as follows :
-
1.
if and only if ;
-
2.
Constant symbols are interpreted in the obvious way, i.e. if is a constant symbol, then ;
-
3.
If is an -ary relation symbol, then if and only if ;
-
4.
If is an -any function symbol, then if and only if .
From the fact that is maximal consistent, and is an
equivalence relation, we get that the operations are well-defined (it
is not so simple, i’ll write it out later).
The proof that is a straightforward induction
on the
complexity of the formulas of .
Corollary. (The extended completeness theorem) A set of formulas of is consistent if and only if it has a model (regardless of whether or not has witnesses for ).
Proof: First add a set of new constants to , and expand to in such a way that is a set of witnesses for . Then expand to a maximal consistent set . This set has a model consisting of the constants in , and is also a model of .
Corollary. (Compactness theorem) A set of sentences of has a model if and only if every finite subset of has a model.
Proof: Replace “has a model” by “is consistent”, and apply the syntactic compactness theorem.
Corollary. (Gödel’s completeness theorem) Let be a consistent set of formulas of . Then A sentence is a theorem of if and only if it is true in every model of .
Proof: If is not a theorem of , then is consistent with , so has a model , in which cannot be true.
Corollary. (Downward Löwenheim-Skolem theorem) If has a model, then it has a model of power at most .
Proof: If has a model, then it is consistent. The model constructed from constants has power at most (because we must add at most many new constants).
Most of the treatment found in this entry can be read in more details
in Chang and Keisler’s book Model Theory.
Title | models constructed from constants |
---|---|
Canonical name | ModelsConstructedFromConstants |
Date of creation | 2013-03-22 12:44:42 |
Last modified on | 2013-03-22 12:44:42 |
Owner | ratboy (4018) |
Last modified by | ratboy (4018) |
Numerical id | 17 |
Author | ratboy (4018) |
Entry type | Definition |
Classification | msc 03C07 |
Synonym | completeness theorem |
Synonym | Gödel completeness theorem |
Related topic | UpwardsSkolemLowenheimTheorem |
Defines | set of witnesses |