Consequence of Löwenheim-Skolem-Theorem

Question

They say it follows from above mentioned theorem that the structure $(\mathbb{R}, +, \times, 0,1)$ has a countable model which is super-counterintuitive since $\mathbb{R}$ has uncountably many numbers, so how can a model be countable there? Can one give one example that shows how a countable model could come from a structure with uncountable many elements?

I mean in above structure there are truths like "$1+1=2$", "$0.5 \times 0.5 = 0.25$" etc., right? These are easily uncountably many truths = uncountable model. So how is it possible to reduce this uncountable model to a countable model without manipulating the structure?

Answer 1

You ask for an example. Let $R = \overline{\mathbb{Q}}\cap \mathbb{R} = \{r\in \mathbb{R}\mid r\text{ is algebraic over }\mathbb{Q}\}$ be the set of real algebraic numbers. Then $R$ is countable, and $(R,+,\times,0,1)$ is a model of the complete theory of $\mathbb{R}$.

This is not easy to see directly, but it follows from the fact that the complete theory of $\mathbb{R}$ is axiomatized by the axioms of real closed fields, and $R$ is a real closed field.

---

Your question suggests that you have serious misunderstandings about the meanings of "theory" and "model". To start, you write

The structure $(\mathbb{R},+,\times,0,1)$ has a countable model

This is nonsense. Structures don't have models, theories do. What the Löwenheim-Skolem theorem says is that every theory in a countable language which has an infinite model has a countably infinite model. So what we can conclude is $\text{Th}(\mathbb{R})$, the set of all sentences in the language $\{+,\times,0,1\}$ true in $\mathbb{R}$, has a countable model.

These are easily uncountably many truths = uncountable model. So how is it possible to reduce this uncountable model to a countable model without manipulating the structure?

There would be uncountably many truths (sentences in $\text{Th}(\mathbb{R})$) if we could talk about arbitrary real numbers in our sentences. But we can't: we're restricted to using the symbols $+,\times,0,1$. There are only countably many formulas in the language, so there are only countably many truths in $\text{Th}(\mathbb{R})$.

Now you could expand the language to include a constant symbol naming every element of $\mathbb{R}$. Then the language would be uncountable, and the Löwenheim-Skolem theorem would fail to give us a countable model.

I have no idea what "without manipulating the structure" means.

Answer 2

I am going to take a shot at this, but my understanding of model theory is rather sketchy, so I can only hope that I don't get the details too wrong. Corrections will be welcome.

(This is long because I tried to explain it starting from zero and without using too much technical language. I desperately hope that I have hit a sweet spot between clarity, accuracy, and brevity.)

First we need to get the terminology clear. As Alex Kruckman points out, the phrase

the structure $(\mathbb{R}, +, \times, 0,1)$ has a countable model

is very confused. The Löwenheim-Skolem theorem relates theories to models. Theories have models. The structure you described (which from now on I'll call $\mathcal M$) is an example of a model. To say that $\mathcal M$ “has” a countable model is wrong because theories, not structures, have models.

A theory is a set of statements that we would like to be true, such as

• For all objects $a$ and $b$, $a+b = b+a$
• There is an object $0$ with the property that for all $a$, $0+a=a$
• For all objects $a$ and $b$, $a<0$ or $b<0$ or $a·b ≥ 0$.
• For all $a$ with $a>0$, there is a $b$ such that $a·b=1$

(More properly, the “statements” are formulas of first-order logic, and we interpret them to be statements about the model.)

The model is then a family of mathematical objects, and the statements of the theory might or might not be true of a particular model. For example, if we consider the set of real numbers, and the conventional definitions of $+, ·, 0, <$, and so on, then all four statements above are true of that model. But if we instead consider the set of integers, the first three statements are true and the fourth is not. You suggested

the structure $\mathcal M = (\mathbb{R}, +, \times, 0,1)$ has a countable model

but that's not how model theory works. Rather:

• Theories have models
• $\mathcal M$ is an example of a model
• It is a model of the usual theory of the real numbers
  • (Including the four statements I listed above, and many others.)

As you correctly observed, $\Bbb R$ is uncountable, so $\mathcal M$ is an uncountable model of the theory of the real numbers.

The Löwenheim-Skolem theorem tells us that there is another model of the same theory which, unlike $\mathcal M$, is countable.

Alex Kruckman has given one very concrete example. I will give a less concrete but more general one.

---

Our theory is written down in some symbolic language. Suppose we want to show that our theory requires that the number $\frac23$ must exist. Our language may not have an atomic symbol that represents $\frac23$; in fact it usually doesn't; typically is only has explicit notations for $0$ and $1$. That is okay though. We can certainly express the claim that there is a unique object $a$ for which $a · (1 + 1 + 1) = 1 + 1$, and then we might be able to prove that claim. Having proved the existence and uniqueness of the object with this property, we can give it a name, and call it $\frac23$.

That tells us that any model of our theory must contain $\frac23$: the axioms are true of any model, so the proof will go through in any model. The proof identifies a single specific object $a$ with the property $a · (1 + 1 + 1) = 1 + 1$, so any model of the axioms must include a single specific object with that property. So every model contains a $\frac23$.

(Similarly we can prove that any model of the axioms must contain an object that we can identify as $\sqrt2$; it is the unique object satisfying $a·a = 2 \text{ and } a>0$; we can prove the existence of negative numbers; we can prove the model does not contain an object $a$ satisfying $a·a+1=0$, and so on.)

Now let's consider $\Bbb D$, the set of all real numbers that can be described in this way, as the unique number satisfying some particular property. $\Bbb R$ was a model of our original theory, so $D$ must be too. Why? If $\Bbb D$ wasn't a model of the theory, then there would be some theorem we could prove which would be true for $\Bbb R$ but false for $\Bbb D$, something like “there exists an object satisfying such-and-so formula” where $\Bbb R$ did contain such an object but $\Bbb D$ didn't.

But there is no such formula because $\Bbb D$ is exactly the set of objects that can be described by formulas. So if $\Bbb R$ is a model of our theory, $\Bbb D$ must be too.

And (here is the crucial step): Every element of $\Bbb D$ satisfies some particular formula. There are only countably many formulas, because each is a finite sequence of symbols. So $\Bbb D$ is countable.

---

To really pin this down properly we have to have a formal definition of what a formula is. We have to specify a language for writing down formulas and a set of rules for stating and proving statements written in that language. The details of how we do this matter greatly. There is a standard system for doing this, called first-order logic, and it is important to know that the Löwenheim-Skolem theorem is about systems based on first-order logic, and may not apply to theories expressed in higher-order logic. So if you really want to understand what the theorem says, you have to look specifically at the definition of first-order logic and what it means for something to be a proof in first-order logic.

---

Sorry this was so long, but I hope some of it was helpful.