models constructed from constants

The definition of a structureMathworldPlanetmath 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, L is a fixed first-order language.

Let C be a set of constant symbols of L, and T be a theory in L. Then we say C is a set of witnesses for T if and only if for every formula φ with at most one free variableMathworldPlanetmathPlanetmath x, we have Tx(φ)φ(c) for some cC.

Lemma. Let T is any consistent set of sentencesMathworldPlanetmath of L, and C is a set of new symbols such that |C|=|L|. Let L=LC. Then there is a consistent set TL extending T and which has C as set of witnesses.

Lemma. If T is a consistentPlanetmathPlanetmath theory in L, and C is a set of witnesses for T in L, then T has a model whose elements are the constants in C.

Proof: Let Σ be the signaturePlanetmathPlanetmathPlanetmath for L. If T is a consistent set of sentences of L, then there is a maximal consistent TT. Note that T and T have the same sets of witnesses. As every model of T is also a model of T, we may assume T is maximal consistent.

We let the universePlanetmathPlanetmath of 𝔐 be the set of equivalence classesMathworldPlanetmathPlanetmath C/, where ab if and only if a=bT. As T is maximal consistent, this is an equivalence relation. We interpret the non-logical symbols as follows :

  1. 1.

    [a]=𝔐[b] if and only if ab;

  2. 2.

    Constant symbols are interpreted in the obvious way, i.e. if cΣ is a constant symbol, then c𝔐=[c];

  3. 3.

    If RΣ is an n-ary relation symbol, then ([a1],,[an])R𝔐 if and only if R(a1,,an)T;

  4. 4.

    If FΣ is an n-any function symbol, then F𝔐([a0],,[an])=[b] if and only if F(a1,,an)=bT.

From the fact that T is maximal consistent, and is an equivalence relation, we get that the operationsMathworldPlanetmath are well-defined (it is not so simple, i’ll write it out later). The proof that 𝔐T is a straightforward inductionMathworldPlanetmath on the complexity of the formulas of T.

Corollary. (The extended completeness theorem) A set T of formulas of L is consistent if and only if it has a model (regardless of whether or not L has witnesses for T).

Proof: First add a set C of new constants to L, and expand T to T in such a way that C is a set of witnesses for T. Then expand T to a maximal consistent set T′′. This set has a model 𝔐 consisting of the constants in C, and 𝔐 is also a model of T.

Corollary. (Compactness theorem) A set T of sentences of L has a model if and only if every finite subset of T has a model.

Proof: Replace “has a model” by “is consistent”, and apply the syntactic compactness theorem.

Corollary. (Gödel’s completeness theorem) Let T be a consistent set of formulas of L. Then A sentence φ is a theorem of T if and only if it is true in every model of T.

Proof: If φ is not a theorem of T, then ¬φ is consistent with T, so T{¬φ} has a model 𝔐, in which φ cannot be true.

Corollary. (Downward Löwenheim-Skolem theorem) If TL has a model, then it has a model of power at most |L|.

Proof: If T has a model, then it is consistent. The model constructed from constants has power at most |L| (because we must add at most |L| many new constants).

Most of the treatment found in this entry can be read in more details in Chang and Keisler’s book Model TheoryMathworldPlanetmath.

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