3.4: Substructures and the Löwenheim-Skolem Theorems

Last updated
Save as PDF
Share
1. Share
2. Share
3. Tweet

Page ID: 9696

[ "article:topic", "authorname:learykristiansen" ]

$Leary.jpg$
Contributed by Christopher Leary and Lars Kristiansen
Professor (Mathmatics) at SUNY Geneseo and University of Oslo

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $

$ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $

In this section we will discuss a relation between structures. A given set of sentences may have many different models, and it will turn out that in some cases those models are related in surprising ways. We begin by defining the notion of a substructure.

Definition 3.4.1.

If $\mathfrak{A}$ and $\mathfrak{B}$ are two $\mathcal{L}$-structures, we will say that $\mathfrak{A}$ is a substructure of $\mathfrak{B}$, and write $\mathfrak{A} \subseteq \mathfrak{B}$, if:

$A \subseteq B$.
For every constant symbol $c$, $c^\mathfrak{A} = c^\mathfrak{B}$.
For every $n$-ary relation symbol $R$, $R^\mathfrak{A} = R^\mathfrak{B} \cap A^n$.
For every $n$-ary function symbol $f$, $f^\mathfrak{A} = f^\mathfrak{B} \upharpoonright_{A^n}$. In other words, for every $n$-ary function symbol $f$ and every $a \in A$, $f^\mathfrak{A} \left( a \right) = f^\mathfrak{B} \left( a \right)$. (This is called the restriction of the function $f^\mathfrak{B}$ to the set $A^n$.)

Thus a substructure of $\mathfrak{B}$ is completely determined by its universe, and this universe can be any nonempty subset of $B$ that contains the constants and is closed under every function $f$.

Example 3.4.2:

Suppose that we try to build a substructure $\mathfrak{A}$ of the structure $\mathfrak{N} = \left( \mathbb{N}, 0, S, +, \cdot, E, < \right)$. Since $A$ must be closed under the functions and contain the constants, the number 0 must be an element of the universe $A$. But now, since the substructure must be closed under the function $S$, it is clear that every natural number must be an element of $A$. Thus $\mathfrak{N}$ has no proper substructures.

Example 3.4.3:

Now, suppose that we try to find some substructures of the structure $\mathfrak{B} = \left( \mathbb{N}, 0, < \right)$, with the usual interpretations of 0 and $<$. Since there are no function symbols, any nonempty subset of $\mathbb{N}$ that includes the number 0 can serve as the universe of a substructure $\mathfrak{A} \subseteq \mathfrak{B}$.

Suppose that we let $\mathfrak{A} = \left( \{ 0 \}, 0, < \right)$. Then notice that even though $\mathfrak{A} \subseteq \mathfrak{B}$, there are plenty of sentences that are true in one structure that are not true in the other structure. For example, $\left( \forall x \right) \left( \exists y \right) x < y$ is false in $\mathfrak{A}$ and true in $\mathfrak{B}$. It will not be hard for you to find an example of a sentence that is true in $\mathfrak{A}$ and false in $\mathfrak{B}$.

As Example 3.4.3 shows, if we are given two structures such that $\mathfrak{A} \subseteq \mathfrak{B}$, most of the time you would expect that $\mathfrak{A}$ and $\mathfrak{B}$ would be very different, and there would be lots of sentences that would be true in one of the structures that would not be true in the other.

Sometimes, however, truth in the smaller structure is more closely tied to truth in the larger structure.

Definition 3.4.4.

Suppose that $\mathfrak{A}$ and $\mathfrak{B}$ are $\mathcal{L}$-structures and $\mathfrak{A} \subseteq \mathfrak{B}$. We say that $\mathfrak{A}$ is an elementary substructure of $\mathfrak{B}$ (equivalently, $\mathfrak{B}$ is an elementary extension of $\mathfrak{A}$), and write $\mathfrak{A} \prec \mathfrak{B}$, if for every $s : Vars \rightarrow A$ and for every $\mathcal{L}$-formula $\phi$,

\[\mathfrak{A} \models \phi \left[ s \right] \: \text{if and only if} \: \mathfrak{B} \models \phi \left[ s \right].\]

Chaff: Notice that if we want to prove $\mathfrak{A} \prec \mathfrak{B}$, we need only prove $\mathfrak{A} \models \phi \left[ s \right] \rightarrow \mathfrak{B} \models \phi \left[ s \right]$, since once we have done that, the other direction comes for free by using the contrapositive and negations.

Proposition 3.4.5.

Suppose that $\mathfrak{A} \prec \mathfrak{B}$. Then a sentence $\sigma$ is true in $\mathfrak{A}$ if and only if it is true in $\mathfrak{B}$.

proof

Exercise 5.

Example 3.4.6:

We saw earlier that the structure $\mathfrak{B} = \left( \mathbb{N}, 0, < \right)$ has lots of substructures. However, $\mathfrak{B}$ has no proper elementary substructures. For suppose that $\mathfrak{A} \prec \mathfrak{B}$. Certainly, $0 \in A$, as $\mathfrak{A}$ is a substructure. Since the sentence $\left( \exists y \right) \left[ 0 < y \land \left( \forall x \right) \left( 0 < x \rightarrow y \leq x \right) \right]$ is true in $\mathfrak{B}$, it must be true in $\mathfrak{A}$ as well. So

\[\mathfrak{A} \models \left( \exists y \right) \left[ 0 < y \land \left( \forall x \right) \left( 0 < x \rightarrow y \leq x \right) \right].\]

Thus, for any assignment function $s : Vars \rightarrow A$ there is some $a \in A$ such that

\[\mathfrak{A} \models \left[ 0 < y \land \left( \forall x \right) \left( 0 < x \rightarrow y \leq x \right) \right] \left[ s \left[ y | a \right] \right].\]

Fix such an $s$ and such an $a \in A$. Now we use elementarity again. Since $\mathfrak{A} \prec \mathfrak{B}$ and $s \left[ y | a \right] : Vars \rightarrow A$, we know that

\[\mathfrak{B} \models \left[ 0 < y \land \left( \forall x \right) \left( 0 < x \rightarrow y \leq x \right) \right] \left[ s \left[ y | a \right] \right].\]

But in the structure $\mathfrak{B}$, there is a unique element that makes the formula $\left[ 0 < y \land \left( \forall x \right) \left( 0 < x \rightarrow y \leq x \right) \right]$ true, namely the number 1. So $a$ must be the number 1, and so 1 must be an element of $A$. Similarly, you can show that $2 \in A$, $3 \in A$, and so on. Thus $\mathbb{N} \subseteq A$, and $\mathfrak{A}$ will not be a proper elementary substructure of $\mathfrak{B}$.

This example shows that when building an elementary substructure of a given structure $\mathfrak{B}$, we need to make sure that witnesses for each existential sentence true in $\mathfrak{B}$ must be included in the universe of the elementary substructure $\mathfrak{A}$. That idea will be the core of the proof of the Downward Löwenheim-Skolem Theorem, Theorem 3.4.8. In fact, the next lemma says that making sure that such witnesses are elements of $\mathfrak{A}$ is all that is needed to ensure that $\mathfrak{A}$ is an elementary substructure of $\mathfrak{B}$.

Lemma 3.4.7.

Suppose that $\mathfrak{A} \subseteq \mathfrak{B}$ and that for every formula $\alpha$ and every $s : Vars \rightarrow A$ such that $\mathfrak{B} \models \exists x \alpha \left[ s \right]$ there is an $a \in A$ such that $\mathfrak{B} \models \alpha \left[ s \left[ x | a \right] \right]$. Then $\mathfrak{A} \prec \mathfrak{B}$.

proof

We will show, given the assumptions of the lemma, that if $\phi$ is any formula and $s$ is any variable assignment function into $A$, $\mathfrak{A} \models \phi \left[ s \right]$ if and only if $\mathfrak{B} \models \phi \left[ s \right]$, and thus $\mathfrak{A} \prec \mathfrak{B}$.

This is an easy proof by induction on the complexity of $\phi$, which we will make even easier by noting that we can replace the $\forall$ inductive step by an $\exists$ inductive step, as $\forall$ can be defined in terms of $\exists$.

So for the base case, assume that $\phi$ is atomic. For example, if $\phi$ is $R \left( x, y \right)$, then $\mathfrak{A} \models \phi \left[ s \right]$ if and only if $\left( s \left( x \right), s \left( y \right) \right) \in R^\mathfrak{A}$. But $R^\mathfrak{A} = R^\mathfrak{B} \cap A^2$, so $\left( s \left( x \right), s \left( y \right) \right) \in R^\mathfrak{A}$ if and only if $\left( s \left( x \right), s \left( y \right) \right) \in R^\mathfrak{B}$. But $\left( s \left( x \right), s \left( y \right) \right) \in R^\mathfrak{B}$ if and only if $\mathfrak{B} \models \phi \left[ s \right]$, as needed.

For the inductive clauses, assume that $\phi$ is $\neg \alpha$. Then

\[\begin{array}{rll} \mathfrak{A} \models \phi \left[ s \right] & \text{if and only if} \: \mathfrak{A} \models \neg \alpha \left[ s \right] & \\ & \text{if and only if} \: \mathfrak{A} \not\models \alpha \left[ s \right] & \\ & \text{if and only if} \: \mathfrak{B} \not\models \alpha \left[ s \right] & \text{inductive hypothesis \\ & \text{if and only if} \: \mathfrak{B} \models \neg \alpha \left[ s \right] & \\ & \text{if and only if} \: \mathfrak{B} \models \phi \left[ s \right]. \end{array}\]

The second inductive clause, if $\phi$ is $\alpha \lor \beta$, is similar.

For the last inductive clause, suppose that $\phi$ is $\exists x \alpha$. Suppose also that $\mathfrak{A} \models \phi \left[ s \right]$; in other words, $\mathfrak{A} \models \exists x \alpha \left[ s \right]$. Then, for some $a \in A$, $\mathfrak{A} \models \alpha \left[ s \left[ x | a \right] \right]$. Since $s \left[ x | a \right]$ is a function mapping variables into $A$, by our inductive hypothesis, $\mathfrak{B} \models \alpha \left[ s \left[ x | a \right] \right]$. But then $\mathfrak{B} \models \exists x \alpha \left[ s \right]$, as needed. For the other direction, assume that $\mathfrak{B} \models \exists x \alpha \left[ s \right]$, where $s : Vars \rightarrow A$. We use the assumption of the lemma to find an $a \in A$ such that $\mathfrak{B} \models \alpha \left[ s \left[ x | a \right] \right]$. As $s \left[ x | a \right]$ is a function with codomain $A$, by the inductive hypothesis $\mathfrak{A} \models \alpha \left[ s \left[ x | a \right] \right]$, and thus $\mathfrak{B} \models \exists x \alpha \left[ s \right]$, and the proof is complete.

Chaff: We are now going to look at the Löwenheim-Skolem Theorems, which were published in 1915. To understand these theorems, you need to have at least a basic understanding of cardinality, a topic that is outlined in the Appendix. However, if you are in a hurry, it will suffice if you merely remember that there are many different sizes of infinite sets. An infinite set $A$ is countable if there is a bijection between $A$ and the set of natural numbers $\mathbb{N}$, otherwise, the set is uncountable. Examples of countable sets include the integers and the set of rational numbers. The set of real numbers is uncountable, in that there is no bijection between $\mathbb{R}$ and $\mathbb{N}$. So there are more reals than natural numbers. There are infinitely many different sizes of infinite sets. The smallest infinite size is countable.

Theorem 3.4.8: Downward löwenheim-skolem theorem

Suppose that $\mathcal{L}$ is a countable language and $\mathfrak{B}$ is an $\mathcal{L}$-structure. Then $\mathfrak{B}$ has a countable elementary substructure.

proof

If $B$ is finite or countable infinite, then $\mathfrak{B}$ is its own countable elementary substructure, so assume that $B$ is uncountable. As the language $\mathcal{L}$ is countable, there are only countably many $\mathcal{L}$-formulas, and thus only countably many formulas of the form $\exists x \alpha$.

Let $A_0$ be any nonempty countable subset of $B$. We show how to build $A_1$ such that $A_0 \subseteq A_1$, and $A_1$ is countable. The idea is to add to $A_0$ witnesses for the truth (in $\mathfrak{B}$) of existential statements.

Notice that as $A_0$ is countable, there are only countably many functions $s^\prime : Vars \rightarrow A_0$ that are eventually constant, by which we mean there is a natural number $k$ such that if $i, j > k$, then $s^\prime \left( v_i \right) = s^\prime \left( v_j \right)$. (This is a nice exercise for those of you have had a course in set theory or are reasonably comfortable with cardinality arguments.) Also, if we are given any $\phi$ and any $s : Vars \rightarrow A_0$, we can find an eventually constant $s^\prime : Vars \rightarrow A_0$ such that $s$ and $s^\prime$ agree on the free variables of $\phi$, and thus $\mathfrak{B} \models \phi \left[ s \right]$ if and only if $\mathfrak{B} \models \phi \left[ s^\prime \right]$.

The construction of $A_1$: For each formula of the form $\exists x \alpha$ and each $s : Vars \rightarrow A_0$ such that $\mathfrak{B} \models \exists x \alpha \left[ s \right]$, find an eventually constant $s^\prime : Vars \rightarrow A_0$ such that $s$ and $s^\prime$ agree on the free variables of $\exists x \alpha$. Pick an element $a_{\alpha, s^\prime} \in B$ such that $\mathfrak{B} \models \alpha \left[ s \left[ x | a_{\alpha, s^\prime} \right] \right]$, and let

\[A_1 = A_0 \cup \{ a_{\alpha, s^\prime} \}_{\text{all} \: \alpha, s : Vars \rightarrow A_0}.\]

Notice that $A_1$ is countable, as there are only countably many $\alpha$'s and countably many $s^\prime$.

Continue this construction, iteratively building $A_{n+1}$ from $A_n$. Let $A = \cup_{n=0}^\infty A_n$. As $A$ is a countable union of countable sets, $A$ is countable.

Now we have constructed a potential universe $A$ for a substructure for $\mathfrak{B}$. We have to prove that $A$ is closed under the functions of $\mathfrak{B}$ (by the remarks following Definition 3.4.1 this shows that $\mathfrak{A}$ is a substructure of $\mathfrak{B}$), and we have to show that $\mathfrak{A}$ satisfies the criteria set out in Lemma 3.4.7, so we will know that $\mathfrak{A}$ is an elementary substructure of $\mathfrak{B}$.

First, to show that $A$ is closed under the functions of $\mathfrak{B}$, suppose that $a \in A$ and $f$ is a unary function symbol (the general case is identical) and that $b = f^\mathfrak{B} \left( a \right)$. We must show that $b \in A$. Fix an $n$ so large that $a \in A_n$, let $\phi$ be the formula $\left( \exists y \right) y = f \left( x \right)$, and let $s$ be any assignment function into $A$ such that $s \left( x \right) = a$. We know that $\mathfrak{B} \models \left( \exists y \right) y = f \left( x \right) \left[ s \right]$, and we know that if $\mathfrak{B} \models \left( y = f \left( x \right) \right) \left[ s \left[ y | d \right] \right]$, then $d = b$. So, in our construction of $A_{n+1}$ we must have used $a_{y = f \left( x \right), s} = b$, so $b \in A_{n+1}$, and $b \in A$, as needed.

In order to use Lemma 3.4.7, we must show that if $\alpha$ is a formula and $s : Vars \rightarrow A$ is such that $\mathfrak{B} \models \alpha \left[ s \left[ x | a \right] \right]$. So, fix such an $\alpha$ and such an $s$. Find an eventually constant $s^\prime : Vars \rightarrow A$ such that $s$ and $s^\prime$ agree on all the free variables of $\alpha$. Thus $\mathfrak{B} \models \exists x \alpha \left[ s^\prime \right]$, and all of the values of $s^\prime$ are elements of some fixed $A_n$, as $s^\prime$ takes on only a finite number of values. But then by construction of $A_{n+1}$ such that $\mathfrak{B} \models \alpha \left[ s \left[ x | a \right] \right]$, as needed.

So we have met the hypotheses of Lemma 3.4.7, and thus $\mathfrak{A}$ is a countable elementary substructure of $\mathfrak{B}$, as needed.

Chaff: We would like to look at a bit of this proof a little more closely. In the construction of $A_1$, what we did was to find an $a_{\infty, s^\prime}$ for each formula $\exists x \alpha$ and each $s : Vars \rightarrow A$, and the point was that $a_{\infty, s^\prime}$ would be a witness to the truth in $\mathfrak{B}$ of the existential statement $\exists x \alpha$. So we have constructed a function which, given an existential formula $\exists x \alpha$ and an assignment function, finds a value for $x$ that makes the formula $\alpha$ true. A function of this sort is called a Skolem function, and the construction of $A$ in the proof of the Downward Löwenheim-Skolem Theorem can thus be summarized: Let $A_0$ be a countable subset of $B$, and form the closure of $A_0$ under the set of all Skolem functions. Then show that this closure is an elementary substructure of $\mathfrak{B}$.

Example 3.4.9:

We saw an indication in Exercise 4 in Section 2.8 that the axioms of Zermelo-Fraenkel set theory (known as ZF) can be formalized in first-order logic. Accepting that as true (which it is), we know that if the axioms are consistent they have a model, and then by the Downward Löwenheim-Skolem Theorem, there must be a countable model for set theory. But this is interesting, as the following are all theorems of ZF:

There is a countably infinite set.
If a set $a$ exists, then the collection of subsets of $a$ exists.
If $a$ is countably infinite, then the collection of subsets of $a$ is uncountable. (This is Cantor's Theorem).

Now, let us suppose that $\mathfrak{A}$ is our countable model of ZF, and suppose that $a$ is an element of $A$ and is countably infinite. If $b$ is the set of all of the subsets of $a$, we know that $b$ is uncountable (by Cantor's Theorem) and yet $b$ must be countable, as all of the elements of $b$ are in the model $\mathfrak{A}$, and $\mathfrak{A}$ is countable! So $b$ must be both countable and uncountable! This is called (somewhat incorrectly) Skolem's paradox, and Exercise 8 asks you to figure out the solution to the paradox

Probably the way to think about the Downward Löwenheim-Skolem Theorem is that it guarantees that if there are any infinite models of a given set of formulas, then there is a small (countably infinite means small) model of that set of formulas. It seems reasonable to ask if there is a similar guarantee about big models, and there is.

Proposition 3.4.10.

Suppose that $\Sigma$ is a set of $\mathcal{L}$-formulas with an infinite model. If $\kappa$ is an infinite cardinal, then there is a model of $\Sigma$ of cardinality greater than or equal to $\kappa$.

proof

This is an easy application of the Compactness Theorem. Expand $\mathcal{L}$ to include $\kappa$ new constant symbols $c_i$, and let $\Gamma = \Sigma \cup \{ c_i \neq c_j | i \neq j \}$. Then $\Gamma$ is finitely satisfiable, as we can take our given infinite model of $\Sigma$ and interpret the $c_i$ in that model in such a way that $c_i \neq c_j$ for any finite set of constant symbols. By the Compactness Theorem, there is a structure $\mathfrak{A}$ that is a model of $\Gamma$, and thus certainly the cardinality of $A$ is greater than or equal to $\kappa$. If we restrict $\mathfrak{A}$ to the original language, we get a model of $\Sigma$ of the required cardinality.

corollary 3.4.11.

If $\Sigma$ is a set of formulas from a countable language with an infinite model, and if $\kappa$ is an infinite cardinal, then there is a model of $\Sigma$ of cardinality $\kappa$.

proof

First, use Proposition 3.4.10 to get $\mathfrak{B}$, a model of $\Sigma$ of cardinality greater than or equal to $\kappa$. Then, mimic the proof of the Downward Löwenheim-Skolem Theorem, starting with a set $A_0 \subseteq B$ of cardinality exactly $\kappa$. Then the $A$ that is constructed in that proof also will have cardinality $\kappa$, and as $\mathfrak{A} \prec \mathfrak{B}$, $\mathfrak{A}$ will be a model of $\Sigma$ of cardinality $\kappa$.

corollary 3.4.12

If $\mathfrak{A}$ is an infinite $\mathcal{L}$-structure, then there is no set of first-order formulas that characterize $\mathfrak{A}$ up to isomorphism.

proof

More precisely, the corollary says that there is no set of formulas $\Sigma$ such that $\mathfrak{B} \models \Sigma$ if and only if $\mathfrak{A} \cong \mathfrak{B}$. We know that there are models of $\Sigma$ of all cardinalities, and we know that there are no bijections between sets of different cardinalities. So there must be many models of $\Sigma$ that are not isomorphic to $\mathfrak{A}$.

Chaff: There are sets of axioms that do characterize infinite structures. For example, the second-order axioms of Peano Arithmetic include axioms to ensure that addition and multiplication behave normally, and they also include the principle of mathematical induction: If $M$ is a set of numbers, if $0 \in M$, and if $S \left( n \right) \in M$ for every $n$ such that $n \in M$, then $\left( \forall n \right) \left( n \in M \right)$.

Any model of Peano Arithmetic is isomorphic to the natural numbers, but notice that we used two notions (sets of numbers and the elementhood relation) that are not part of our description of $\mathfrak{N}$. By introducing sets of numbers we have left the world of first-order logic and have entered second-order logic, and it is only by using second-order logic that we are able to characterize $\mathfrak{N}$. For a nice discussion of this topic, see [Bell and Machover 77, Chapter 7, Section 2].

The results from Proposition 3.4.10 to Corollary 3.4.12 give us models that are large, but they have a slightly different flavor from the Downward Löwenheim-Skolem Theorem, in that they do not guarantee that the small model is an elementary substructure of the large model. That is the content of the Upward Löwenheim-Skolem Theorem, a proof of which is outlined in the Exercises.

theorem 3.4.13: Upward löwenheim-Skolem theorem

If $\mathcal{L}$ is a countable language, $\mathfrak{A}$ is an infinite $\mathcal{L}$-structure, and $\kappa$ is a cardinal, then $\mathfrak{A}$ has an elementary extension $\mathfrak{B}$ such that the cardinality of $B$ is greater than or equal to $\kappa$.

Exercises

Suppose that $\mathfrak{B} \subseteq \mathfrak{A}$, that $\phi$ is of the form $\left( \forall x \right) \psi$, where $\psi$ is quantifier-free, and that $\mathfrak{A} \models \phi$. Prove that $\mathfrak{B} \models \phi$. The short version of this fact is, "Universal sentences are preserved downward." Formulate and prove the corresponding fact for existential sentences.
Justify the Chaff following Definition 3.4.4.
Show that if $\mathfrak{A} \prec \mathfrak{B}$ and $\mathfrak{C} \prec \mathfrak{B}$ and $\mathfrak{A} \subseteq \mathfrak{C}$, then $\mathfrak{A} \prec \mathfrak{C}$.
Suppose that we have an elementary chain, a set of $\mathcal{L}$-structures such that
\[\mathfrak{A}_1 \prec \mathfrak{A}_2 \prec \mathfrak{A}_3 \prec \cdots\]
and let $\mathfrak{A} = \bigcup^\infty_{i=1} \mathfrak{A}_i$. So the universe $A$ of $\mathfrak{A}$ is the union of the universes $A_i$, $R^\mathfrak{A} = \bigcup^\infty_{i=1} R^{\mathfrak{A}_i}$, etc. Show that $\mathfrak{A}_i \prec \mathfrak{A}$ for each $i$. [Suggestion: To show that $\mathfrak{A}_i \subseteq \mathfrak{A}$ is pretty easy by the definition. To get that $\mathfrak{A}$ is an elementary extension, you have to use induction on the complexity of formulas. Notice by the comments following Definition 3.4.4 that you need only prove one direction. You may find it easier to use $\exists$ rather than $\forall$ in the quantifier part of the inductive step of the proof.]
Prove Proposition 3.4.5.
Show that if $\mathfrak{A} \prec \mathfrak{B}$ and if there is an element $b \in B$ and a formula $\phi \left( x \right)$ such that $\mathfrak{B} \models \phi \left[ s \left[ x | b \right] \right]$ and for every other $\hat{b} \in B$, $\mathfrak{B} \not\models \phi \left[ s \left[ x | \hat{b} \right] \right]$, then $b \in A$. [Suggestion: This is very similar to Example 3.4.6.]
Suppose that $\mathfrak{B} = \{ \mathbb{N}, +, \cdot \}$, and let $A_0 = \{ 2, 3 \}$. Let $F$ be the set of Skolem functions $\{ f_{\alpha, s} \}$ corresponding to $\alpha$'s of the form $\left( \exists x \right) x = yz$. Find the closure of $A_0$ under $F$. [Suggestion: Do not forget that the assignment functions $s$ that you need to consider are functions mapping into $A_0$ at first, then $A_1$, and so on. You probably want to explicitly write out $A_1$, then $A_2$, etc. We are using the notation here corresponding to the proof of Theorem 3.4.8.]
To say that a set $a$ is countable means that there is a function with domain the natural numbers and codomain $a$ that is a bijection. Notice that this is an existential statement, saying that a certain kind of function exists. Now, think about Example 3.4.9 and see if you can figure out why it is not really a contradiction that the set $b$ is both countable and uncountable. In particular, think about what it means for an existential statement to be true in a structure $\mathfrak{A}$, as opposed to true in the real world (whatever that means!).
(Toward the Proof of the Upward Löwenheim-Skolem Theorem) If $\mathfrak{A}$ is an (\mathcal{L}\)-structure, let $\mathcal{L} \left( A \right) = \mathcal{L} \cup \{ \bar{a} | a \in A \}$, where each $\bar{a}$ is a new constant symbol. Then, let $\bar{\mathfrak{A}}$ be the $\mathcal{L} \left( A \right)$-structure having the same universe as $\mathfrak{A}$ and the same interpretation of the symbols of $\mathcal{L}$ as $\mathfrak{A}$, and interpreting each $\bar{a}$ as $a$. Then we define the complete diagram of $\mathfrak{A}$ as
\[Th \left( \bar{\mathfrak{A}} \right) = \{ \sigma | \sigma \: \text{is an} \: \mathcal{L} \left( A \right) \text{-formula such that} \: \bar{\mathfrak{A}} \models \sigma \}.\]
Show that if $\bar{\mathfrak{B}}$ is any model of $Th \left( \bar{\mathfrak{A}} \right)$, and if $\mathfrak{B} = \bar{\mathfrak{B}} \upharpoonright_\mathcal{L}$, then $\mathfrak{A}$ is isomorphic to an elementary substructure of $\mathfrak{B}$. [Suggestion: Let $h : A \rightarrow B$ be given by $h \left( a \right) = \bar{a}^\mathfrak{B}$. Let $C$ be the range of $h$. Show $C$ is closed under $f^\mathfrak{B}$ for every $f$ in $\mathcal{L}$, and thus $C$ is the universe of $\mathfrak{C}$, a substructure of $\mathfrak{B}$. Then show $h$ is an isomorphism between $\mathfrak{A}$ and $\mathfrak{C}$. Finally, show that $\mathfrak{C} \prec \mathfrak{B}$.]
Use Exercise 9 to prove the Upward Löwenheim-Skolem Theorem by finding a model $\bar{\mathfrak{B}}$ of the complete diagram of the given model $\mathfrak{A}$ such that the cardinality of $\bar{B}$ is greater than or equal to $\kappa$.
We can now fill in some of the details of our discussion of nonstandard analysis from Example 3.3.5. As the language $\mathcal{L}_\mathbb{R}$ of that example already includes constant symbols for each real number, the complete diagram of $\mathfrak{R}$ is nothing more than $Th \left( \mathfrak{R} \right)$. Explain how Exercise 9 shows that there is an isomorphic copy of the real line living inside the structure $\mathfrak{A}$.