502 – The Löwenheim-Skølem theorem

In this note I sketch the proof of the Löwenheim-Skølem (or Löwenheim-Skølem-Tarski) theorem for first order theories. This basic result of model theory is really a consequence of a set theoretic combinatorial lemma, as the proof will demonstrate.

Let ${{\mathcal L}}$ be a first order language, understood as a set of constant, function, and relation symbols. Let

$\displaystyle \kappa_{\mathcal L}=|{\mathcal L}|+\aleph_0,$

so ${\kappa_{\mathcal L}}$ is ${|{\mathcal L}|,}$ unless ${{\mathcal L}}$ is finite, in which case we take ${\kappa_{\mathcal L}=\omega.}$ Talking about ${\kappa_{\mathcal L}}$ rather than ${|{\mathcal L}|}$ simplifies the presentation slightly.

The Löwenheim-Skølem theorem is concerned with the possible infinite sizes of models of first order theories. Of course, a theory ${T}$ could only have finite models; the result does not say anything about ${T}$ if that is the case.

Theorem 1 If ${T}$ is a first order theory in a language ${{\mathcal L},}$ and there is at least one infinite model of ${T,}$ then there are models of ${T}$ of size ${\lambda,}$ for all ${\lambda\ge\kappa_{\mathcal L}.}$

We will prove a more precise statement. Before stating it, note that it is possible to have a theory ${T}$ in some uncountable language ${{\mathcal L}}$ such that ${T}$ has models of certain infinite sizes, but not all. Theorem 1 does not say anything about infinite models of ${T}$ of size ${<\kappa_{\mathcal L}.}$ What cardinals in this range are the possible sizes of models of ${T}$ is actually a rather difficult problem, and we will not address it.

To state the more precise version that we will prove, we need to review the notion of elementary substructure. Thoughout the note we use the notational convention that if ${{\mathcal M}}$ is a ${{\mathcal L}}$ -structure, its underlying universe is ${M.}$

Recall that if ${{\mathcal M}}$ and ${{\mathcal N}}$ are ${{\mathcal L}}$ -structures, we say that

$\displaystyle {\mathcal M}\subseteq{\mathcal N}$

( ${{\mathcal M}}$ is a substructure of ${{\mathcal N}}$ ) iff:

${M\subseteq N}$ .
${R^{\mathcal M}=R^{\mathcal N}\cap M^j}$ for any ${j<\omega}$ and any ${j}$ -ary relation symbol ${R}$ in ${{\mathcal L}.}$
${c^{\mathcal M}=c^{\mathcal N}}$ for all constant symbols ${c}$ in ${{\mathcal L}.}$
${f^{\mathcal M}=f^{\mathcal N}\upharpoonright M^j:M^j\rightarrow M}$ for any ${j<\omega}$ and any ${j}$ -ary function symbol ${f}$ in ${{\mathcal L}.}$

For example, a subgroup of a group ${(G,*,e)}$ is simply a subset ${H\subseteq G}$ such that ${e\in H}$ and ${H}$ is closed under ${*.}$ A subgroup may have significantly different properties than the group it comes from. Consider, for example, ${{\mathbb Z}\subseteq{\mathbb Q}.}$

A substructure ${{\mathcal M}}$ of ${{\mathcal N}}$ is elementary, in symbols

$\displaystyle {\mathcal M}\preceq{\mathcal N},$

iff for any ${{\mathcal L}}$ -formula ${\varphi(x_1,\dots,x_n)}$ and any ${a_1,\dots,a_n\in M,}$ we have that

$\displaystyle {\mathcal M}\models\varphi(a_1,\dots,a_n)$

iff

$\displaystyle {\mathcal N}\models\varphi(a_1,\dots,a_n).$

This is a much more strict notion than simply being a substructure. It is easy to check that ${{\mathbb Z}}$ is not elementary in ${{\mathbb Q},}$ for example.

Note that if ${{\mathcal M}\preceq{\mathcal N}}$ then, for any ${{\mathcal L}}$ -theory ${T,}$ we have that ${{\mathcal M}\models T}$ iff ${{\mathcal N}\models T.}$ (Simply consider sentences ${\varphi}$ in the definition above.)

Here is a natural example of how to obtain elementary extensions of a given model ${{\mathcal M}:}$ Expand the language ${{\mathcal L}}$ into a larger language ${{\mathcal L}'}$ by adding to ${{\mathcal L}}$ a set of ${|M|}$ many new constant symbols ${c_m}$ for ${m\in M.}$ We can expand ${{\mathcal M}}$ to an ${{\mathcal L}'}$ -structure simply by setting ${c_m^{\mathcal M}=m.}$ Let ${{\mathcal M}'}$ denote this expanded structure. Consider the theory ${T={\rm Th}({\mathcal M}'),}$ where the theory is of course considered in the language ${{\mathcal L}'.}$ Let ${{\mathcal N}}$ be any model of ${T.}$ Then there is a natural way of identifying ${{\mathcal N}}$ with an elementary extension of ${{\mathcal M}.}$ More precisely, the map ${j:{\mathcal M}\rightarrow{\mathcal N}}$ given by ${j(m)=c_m^{\mathcal N}}$ is elementary, meaning that

$\displaystyle {\mathcal M}'\models\varphi(a_1,\dots,a_n)$

iff

$\displaystyle {\mathcal N}\models\varphi(j(a_1),\dots,j(a_n))$

for any ${{\mathcal L}'}$ -formula ${\varphi(x_1,\dots,x_n)}$ and any ${a_1,\dots,a_n\in M.}$

It easily follows that the pointwise image ${j[M]}$ is the universe of an elementary substructure of ${{\mathcal N}}$ that is isomorphic to ${{\mathcal M}',}$ so we might as well assume that ${j}$ is the identity. By considering the restriction of ${{\mathcal N}'}$ to language ${{\mathcal L}}$ (i.e., by “forgetting” about the new constant symbols), we obtain this way an elementary extension of ${{\mathcal M}.}$

In fact, it is easy to check that if ${{\mathcal M}\preceq{\mathcal N},}$ then there is a natural expansion of ${{\mathcal N}}$ to an ${{\mathcal L}'}$ -structure that models ${{\rm Th}({\mathcal M}'),}$ so all elementary extensions of ${{\mathcal M}}$ arise in this fashion. From the observations above, Theorem 1 then follows from the following more precise version, where we write ${|{\mathcal M}|}$ for ${|M|,}$ and say that ${{\mathcal M}}$ is infinite iff ${M}$ is.

Theorem 2 Let ${{\mathcal M}}$ be an infinite ${{\mathcal L}}$ -structure.

For any cardinal ${\lambda\ge\kappa_{\mathcal L}+|{\mathcal M}|,}$ there is ${{\mathcal N}\succeq{\mathcal M}}$ with ${|{\mathcal N}|=\lambda.}$

For any cardinal ${\lambda\in[\kappa_{\mathcal L},|{\mathcal M}|]}$ and any ${X\subseteq M}$ with ${|X|\le\lambda,}$ there is ${{\mathcal N}\preceq{\mathcal M}}$ such that ${|{\mathcal N}|=|\lambda|,}$ and ${X\subseteq N.}$

We note first that item 1 follows from item 2 and compactness: Consider the language ${{\mathcal L}'}$ obtained by adding to ${{\mathcal L}}$ a set of ${\lambda}$ many new constant symbols ${c_\alpha,}$ ${\alpha<\lambda,}$ and ${|M|}$ many new constant symbols ${c_m,}$ ${m\in M.}$ In this language, consider the theory ${T}$ obtained by adding to ${{\rm Th}({\mathcal M}')}$ the axioms ${c_\alpha\ne c_\beta}$ for all ${\alpha<\beta<\lambda,}$ where ${{\mathcal M}'}$ is as above. This theory is consistent, by compactness (using that ${M}$ is infinite), so it has models. But any model ${{\mathcal A}}$ of ${T}$ can be naturally identified with an elementary extension of ${{\mathcal M},}$ and has size at least ${\lambda.}$ By item 2, there is an elementary substructure of ${{\mathcal A}}$ that contains ${M}$ and has size precisely ${\lambda.}$ Since ${{\mathcal A}\models{\rm Th}({\mathcal M}'),}$ it follows that the reduct of ${{\mathcal A}}$ to language ${{\mathcal L}}$ is indeed an elementary extension of ${{\mathcal M}}$ of size ${\lambda.}$

To prove item 2, we expand the language ${{\mathcal L}}$ in a different manner.

For this, we need the notion of Skølem functions. Syntactically, a Skølem function for a formula ${\varphi(x,y_1,\dots,y_n)}$ is simply a new function symbol ${f_\varphi}$ for an ${n}$ -ary function. Semantically: Given a structure ${{\mathcal M}}$ in a language containing ${\varphi}$ and ${f_\varphi,}$ we call the interpretaion ${f_\varphi^{\mathcal M}}$ a Skølem function iff, whenever ${a_1,\dots,a_n\in M,}$ and

$\displaystyle {\mathcal M}\models\exists x\,\varphi(x,a_1,\dots,a_n),$

then in fact

$\displaystyle {\mathcal M}\models\varphi(f_\varphi^{\mathcal M}(a_1,\dots,a_n),a_1,\dots,a_n).$

We say that a language ${{\mathcal L}}$ is closed under Skølem functions if a function symbol ${f_\varphi}$ is in the language for each ${\varphi}$ in the language. We say that a structure ${{\mathcal M}}$ in this language has Skølem functions if it satisfies all axioms of the form

$\displaystyle \forall x_1\dots\forall x\bigl(\exists x\,\varphi(x,x_1,\dots,x_n)\quad\rightarrow\quad\varphi(f_\varphi(x_1,\dots,x_n),x_1,\dots,x_n)).$

Note that using the axiom of choice it is straightforward to define interpretations of all the function symbols ${f_\varphi}$ so that these axioms are satisfied: Simply fix a well-ordering of ${M,}$ and take ${f_\varphi(\vec a)}$ as the least ${b}$ (in the sense of the well-ordering) that witnesses ${{\mathcal M}\models\exists x\,\varphi(x,\vec a),}$ if such is the case, or as the least element of ${M}$ otherwise.

It is straightforward to expand a language to one closed under Skølem functions: Given ${{\mathcal L},}$ let ${{\mathcal L}_0={\mathcal L},}$ and set ${{\mathcal L}_{n+1}={\mathcal L}_n\cup\{f_\varphi\mid\varphi}$ is an ${{\mathcal L}_n}$ -formula ${\}}$ for all ${n<\omega.}$ Finally, set ${{\mathcal L}_\omega=\bigcup_n{\mathcal L}_n,}$ and note that ${{\mathcal L}_\omega}$ is as wanted.

Moreover, ${\kappa_{{\mathcal L}_\omega}=\kappa_{\mathcal L},}$ as is easily verified by induction on ${n.}$ This means that to prove item 2, we may as well assume that ${{\mathcal L}}$ is closed under Skølem functions and ${{\mathcal M}}$ has Skølem functions to begin with.

The point of all this is that if ${{\mathcal M}}$ has Skølem functions and ${{\mathcal N}\subseteq{\mathcal M}}$ , then automatically ${{\mathcal N}\preceq{\mathcal M}.}$ This follows from the following test for elementarity:

Lemma 3 (Tarski-Vaught criterion) Suppose ${{\mathcal N}\subseteq{\mathcal M}}$ and that whenever ${a_1,\dots,a_n\in N}$ and

$\displaystyle {\mathcal M}\models\exists x\,\varphi(x,\vec a),$

then there exists ${b\in N}$ such that

$\displaystyle {\mathcal M}\models\varphi(b,\vec a).$

Then ${{\mathcal N}\preceq{\mathcal M}.}$

Proof: By induction in the complexity of ${\varphi.}$ $\Box$

The usefulness of the test derives from the fact that it only mentions satisfaction in ${{\mathcal M}}$ rather than in both ${{\mathcal M}}$ and ${{\mathcal N}.}$

To see how Lemma 3 allows us to conclude the claim made above, suppose that ${{\mathcal M}}$ has Skølem functions, and that ${{\mathcal N}}$ is a substructure of ${{\mathcal M}.}$ Then, automatically, the hypothesis of Lemma 3 is satisfied, since ${{\mathcal N}}$ must be closed under the restrictions of all the functions ${f_\varphi^{\mathcal M},}$ being a substructure, meaning that ${f_\varphi^{\mathcal M}(\vec a)\in N}$ whenever ${\vec a\in N.}$ It then follows that ${{\mathcal N}\preceq{\mathcal M},}$ as claimed.

Moreover, note that if ${N\subseteq M}$ and ${N}$ is (nonempty and) closed under all the Skølem functions from ${{\mathcal M},}$ then ${N}$ is the universe of a (necessarily elementary) substructure of ${{\mathcal M}.}$ To see this, note that from the definition of substructure given above, all that we require is that ${c^{\mathcal M}\in N}$ for all constant symbols ${c}$ in ${{\mathcal L},}$ and that ${f^{\mathcal M}(\vec a)\in N}$ whenever ${\vec a\in N,}$ for all function symbols ${f}$ in ${{\mathcal M}.}$

But consider ${\varphi(x,y)\equiv y=y\land x=c.}$ Then ${f_varphi^{\mathcal M}(y_0)=c^{\mathcal M}}$ for any ${y_0\in M,}$ so if ${N}$ is nonempty and as above, then ${N}$ contains the interpretaions of all the constant symbols from the language. (The only reason we added ${y}$ to the formula ${\varphi}$ rather than just taking ${\varphi(x)\equiv x=c}$ is to avoid having ${f_\varphi}$ to be ${0}$ -ary, since our official definition of function symbols requires this not to be the case. Similarly, consider ${\varphi(x,y_1,\dots,y_n)\equiv x=f(y_1,\dots,y_n).}$ Then ${f_\varphi^{\mathcal M}=f^{\mathcal M}.}$

We have finally arrived at the combinatorial core of Theorem 2. Some notation is useful (we follow Kunen Set theory. An introduction to independence proofs in the remainder of this note).

For ${n<\omega}$ say that ${f}$ is an ${n}$ -ary function on a set ${A}$ iff ${n>0}$ and, as usual, ${f:A^n\rightarrow A,}$ or ${n=0}$ and ${f\in A.}$ (This is a natural extension of the notion for ${n>0:}$ Note that ${A^0=1}$ and any ${f:1\rightarrow A}$ is simply picking an element of ${A;}$ here we are just identifying ${f}$ and this element.) Say that ${f}$ is a finitary function on ${A}$ iff ${f}$ is ${n}$ -ary on ${A}$ for some ${n<\omega.}$

Say that ${B\subseteq A}$ is closed under a finitary function ${f}$ iff ${f\cdot B\subseteq B,}$ where ${f\cdot B=\{f\}}$ if ${f}$ is ${0}$ -ary, and ${f\cdot B=f[B^n]}$ if ${f}$ is ${n}$ -ary, ${n>0.}$ If ${S}$ is a set of finitary functions on ${A,}$ we say that ${B}$ is closed under ${S}$ iff ${f\cdot B\subseteq B}$ for all ${f\in S.}$ The closure of ${B}$ under ${S}$ is the ${\subseteq}$ -smallest ${C\subseteq A}$ such that ${B\subseteq C}$ and ${C}$ is closed under ${S.}$

From the preliminaries above, it is clear that the following completes the proof of Theorem 2, since we can take as ${B}$ the set ${X}$ in item 2 (or rather, a superset of ${X}$ of size exactly ${\lambda}$ ), as ${\kappa}$ the cardinal ${\lambda,}$ as ${A}$ the set ${M}$ and as ${S}$ the set of (interpretations of) Skølem functions on ${{\mathcal M}.}$

Lemma 4 Suppose that ${\kappa}$ is infinite, that ${B\subseteq A,}$ ${|B|\le\kappa,}$ and that ${S}$ is a set of at most ${\kappa}$ many finitary functions on ${A.}$ Then the closure of ${B}$ under ${S}$ exists and has size at most ${\kappa.}$

Proof: Given ${C\subseteq A,}$ write ${S\cdot C}$ for ${\bigcup\{f\cdot C\mid f\in S\}.}$ Set ${B_0=B}$ and ${B_{n+1}=B_n\cup S\cdot B_n}$ for all ${n<\omega.}$ Finally, set ${B_\omega=\bigcup_n B_n.}$ Then, by induction on ${n,}$ each ${B_n}$ is contained in any subset of ${A}$ closed under ${S}$ that contains ${B.}$ Since ${B_\omega}$ itself is closed under ${S,}$ it follows that ${B_\omega}$ is the closure of ${B.}$ By induction, ${|B_n|\le\kappa}$ for all ${n,}$ and so the same holds for ${B.}$ $\Box$

Typeset using LaTeX2WP. Here is a printable version of this post.

This entry was posted on Sunday, November 8th, 2009 at 3:24 pm and is filed under 502: Logic and set theory. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

2 Responses to 502 – The Löwenheim-Skølem theorem

502 – The constructible universe « Teaching blog says:

December 9, 2009 at 12:23 pm

[…] This can be established by an argument very similar to the one we used in the notes on the Löwenheim-Sko lem theorem. Namely, for and each of its subformulas consider Sko lem functions from Let be the set of […]

Reply
502 – The constructible universe « A kind of library says:

August 26, 2012 at 10:30 pm

[…] This can be established by an argument very similar to the one we used in the notes on the Löwenheim-Sko lem theorem. Namely, for and each of its subformulas consider Sko lem functions from Let be the set of […]

Reply

	ปั่นสล็อต on 414/514 The theorems of Rieman…
	Richard Kimberly Hec… on Woodin’s proof of the se…
	Is there a Borel-mea… on 414/514 Examples of Baire clas…
	Simple bijectiveness… on 580 -Some choiceless results…
	Schur’s theore… on 580 -III. Partition calcu…
	Uncountable linearly… on 403/503 – Homework …
	What is a non-constr… on On strong measure zero se…
	function from Nmathb… on Hindsight
	Cauchy Schwarz Inequ… on 275 -Positive polynomials
	What is a Cantor-sty… on 580 -Some choiceless results…
	Question about Gener… on 580 -Some choiceless results…
	Set has Measure Zero… on On strong measure zero se…
	Non-measurable subse… on 580 -Cardinal arithmetic …
	hmeng1 on 414/514 The theorems of Rieman…
	580 -Cardinal arithm… on 580 -Cardinal arithmetic …

M	T	W	T	F	S	S
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30

A kind of library