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.
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.
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.
if and only if ;
Constant symbols are interpreted in the obvious way, i.e. if is a constant symbol, then ;
If is an -ary relation symbol, then if and only if ;
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|
|Date of creation||2013-03-22 12:44:42|
|Last modified on||2013-03-22 12:44:42|
|Last modified by||ratboy (4018)|
|Synonym||Gödel completeness theorem|
|Defines||set of witnesses|