Currently I am reading Enderton's A Mathematical Introduction to Logic. In page $154,$ he stated the following:

Lowenheim-Skolem Tarski Theorem Let $\Gamma$ be a set of formulas in a language of cardinality $\lambda,$ and assume that $\Gamma$ satisfies in some infinite structure. Then for every cardinal $\kappa\geq \lambda,$ there is a structure of cardinality $\kappa$ in which $\Gamma$ is satisfiable.

The proof is as follows:

Proof: Let $\mathfrak{A}$ be the infinite structure in which $\Gamma$ is satisfiable. Expand the language by adding a set $C$ of $\kappa$ new constant symbols. Let $$\Sigma=\{c_1\neq c_2|c_1,c_2 \text{ distinct members of }C\}.$$ Then every finite subset of $\Sigma\cup\Gamma$ is satisfiable in the structure $\mathfrak{A},$ expanded to assign distinct objects to the finitely many new constant symbols in the subset. (Since $\mathfrak{A}$ is infinite, there is room to accommodate any finite number of these.) So by Compactness $\Sigma\cup\Gamma$ is satisfiable, and by the Downward Lowenheim-Skolem Theorem it is satisfiable in a structure $\mathfrak{B}$ of cardinality $\leq \kappa.$ (The expanded language has cardinality $\lambda+\kappa=\kappa.$) But any model of $\Sigma$ clearly has cardinality $\geq \kappa.$ So $\mathfrak{B}$ has cardinality $\kappa;$ restrict $\mathfrak{B}$ to the original language.

I have two questions:

Questions $(1):$ Why is every finite subset of $\Sigma\cup\Gamma$ satisfiable in the structure $\mathfrak{A}?$ If the finite subset is in $\Gamma$ only, then by assumption, the finite subset is satisfiable in $\mathfrak{A}.$ However, when the finite subset contains some elements from $\Sigma,$ I fail to understand why it is satisfiable in $\mathfrak{A}.$

$(2):$ Why is every model of $\Sigma$ has cardinality $\geq \kappa?$

Any hint would be appreciated.

  • $\begingroup$ (2) Because $\Sigma$ has $\kappa$ many new distinct constants. $\endgroup$ – Mauro ALLEGRANZA Mar 10 '18 at 11:42
  • $\begingroup$ @MauroALLEGRANZA: So whenever we add $\kappa$ new symbols, we are assuming that those symbols are all distinct? $\endgroup$ – Idonknow Mar 10 '18 at 11:43
  • 1
    $\begingroup$ The constants $c_i, c_j$ are distinct and the corresponding "axiom" $c_i \ne c_j$ of $\Sigma$ forces us to interpret them with distict objects. $\endgroup$ – Mauro ALLEGRANZA Mar 10 '18 at 11:52
  • $\begingroup$ So the theory $\Sigma$ is satisfied by an interpretation whose domain has $\kappa$ many objects. $\endgroup$ – Mauro ALLEGRANZA Mar 10 '18 at 12:09
  • 3
    $\begingroup$ No; $\mathfrak A$ is what it is. It has a domain with infinite many elements. We "expand" the language adding constants (symbols) to it and we "expand" the theory $\Gamma$ adding the "axioms" of $\Sigma$. $\endgroup$ – Mauro ALLEGRANZA Mar 10 '18 at 14:01

We start from a theory $\Gamma$ in a language $\mathcal L$.

Then we expand the language adding infinite many new individual constant $c_i \in C$, where $C$ has cardinalty $\kappa$.

Then we consider the set of sentence $\Sigma = \{ c_1 \ne c_2 \mid c_1, c2 \text { distinct elements of } C \}$.

Then we consider the set of sentences: $\Gamma \cup \Sigma$ in the expanded language.

Lastly, we assume that $\Gamma$ has an infinite model $\mathfrak A$.

(2) Due to the fact that the expanded language has $\kappa$ many distinct constants, the "axiom" $c_i \ne c_j$ of $Σ$ forces us to interpret them with distict objects.

And (1) due to the fact that $\mathfrak A$ has an infinite domain, it has enough objects to satisfy a finite number of new "axioms" from $\Sigma$.

Thus, by compactness, there is model of $Γ \cup Σ$ and by Downward L-S there is a model $\mathfrak B$ (different from $\mathfrak A$) with the required cardinality.

Obviously, being a model of $Γ \cup Σ$, $\mathfrak B$ is also a model of $Γ$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.