If a set of sentences $\Gamma$ has an infinite model, then it has a denumerable model too?

287 Views Asked by At

I think this is false since, by Downward Lowenheim-Skolem Theorem, we can only conclude that $\Gamma$ has an enumerable model, whether this enumerable model is also infinite is not shown. Sure our $\Gamma$ already has an infinite model, but nothing says that its enumerable model must be identical to its infinite model.

I can't see how this claim is true, but I guess it's supposed to be true?

3

There are 3 best solutions below

2
On BEST ANSWER

The usual statement of the downward Löwenheim-Skolem theorem is the following:

Suppose $T$ is a theory in a language $\mathcal{L}$. Let $M\models T$ be an infinite model of cardinality $\kappa$. Let $\lambda$ be an infinite cardinal with $|\mathcal{L}| \leq \lambda \leq \kappa$. Then $M$ has an elementary substructure of cardinality $\lambda$.

It seems you are working with a weaker statement $(\star)$. By "countable", I mean finite or countably infinite.

$(\star)$ Suppose $T$ is a theory in a countable language $\mathcal{L}$. If $T$ has an infinite model, then $T$ has a countable model.

... and you want to conclude $(\dagger)$:

$(\dagger)$ Suppose $T$ is a theory in a countable language $\mathcal{L}$. If $T$ has an infinite model, then $T$ has a countably infinite model.

Well, $(\star)$ easily implies $(\dagger)$. Assume $T$ is a theory in a countable language $\mathcal{L}$, and assume $T$ has an infinite model $M$. Let $\mathcal{L}' = \mathcal{L}\cup \{c_n\mid n\in \mathbb{N}\}$, where each $c_n$ is a new constant symbol, and let $T' = T\cup \{c_n\neq c_m\mid n\neq m\}$. Then since $M\models T$ and $M$ is infinite, we can expand $M$ to a model $M'\models T'$, by interpreting the new constant as any infinite set of distinct elements of $M$. Now $T'$ is a theory in a countable language which has an infinite model $M'$, so by $(\star)$ is has a countable model $N'\models T'$. But in $N'$, the constant symbols $c_n$ are all distinct, so $N'$ is countably infinite. Let $N$ be the reduct of $N'$ to $\mathcal{L}$ (forget about the constant symbols $c_n$). Then $N$ is a countably infinite model of $T$. So we have $(\dagger)$.

Incidentally, the Skolem function construction which is usually used to prove the Löwenheim-Skolem theorem produces an elementary substructure $N\preceq M$ with $|N| \leq |\mathcal{L}|$. Adjusting this construction to force $|N| = \lambda$ (for a fixed $|\mathcal{L}|\leq \lambda \leq \kappa$) is accomplished using exactly the trick in my previous paragraph: expand the language to $\mathcal{L'}$ by adding $\lambda$-many new constant symbols and add axioms saying they're distinct. Then the model $N$ produced by the Skolem function construction has $|N|\leq |\mathcal{L}'| = \lambda$, and also $|N| \geq \lambda$ since the constant symbols are distinct.

3
On

The (downward) [Löwenheim-Skolem] theorem actually does say that if $\Gamma$ has an infinite model, there also is a countably infinite model (so of the cardinality of $\Bbb N$).

0
On

As the other answers have said, there are various formulations of the downward Lowenheim-Skolem theorem which are ultimately equivalent. I'll assume - like Alex Kruckman - that you mean the version "If $T$ is a satisfiable theory of size $\le\kappa$ with $\kappa$ infinite, then $T$ has a model of size $\le\kappa$."


Answer

Suppose $T$ is a countable theory and $M$ is an infinite model of $T$. Consider the larger theory $$T'=T\cup\{\exists x_1,...,x_n(\bigwedge_{1\le i<j\le n}x_i\not=x_j):n\in\mathbb{N}\}.$$ The additional sentences in $T'$ say "the domain has size at least $n$."

Since $M\models T$ and $M$ is infinite, we have $M\models T'$. Now apply downward Lowenheim-Skolem to the theory $T'$. We get a finite-or-countable $M'\models T'$. But clearly every model of $T'$ is infinite, so $M'$ is countably infinite.

  • Actually, we can do even better in a sense: rather than stopping at $T'$, we can "go all the way" and move from $T'$ to the full elementary diagram (or theory) of $M$: $$Th(M)=\{\varphi:M\models\varphi\}.$$ While $Th(M)$ is in one sense overkill (there are possibly many sentences in $Th(M)$ which aren't in $T'$), in another sense it's ultimately better since the assignment $M\mapsto Th(M)$ is an absolutely crucial thing in model theory.

The "right" Lowenheim-Skolem theorem

Where the "expand-the-theory" trick above breaks down is when we try to push to higher cardinalities. For example, suppose $T$ is a theory of cardinality $\aleph_1$ and $M\models T$ with $\vert M\vert=\aleph_2$, and we want to find a model $M'$ of $T$ with $\vert M'\vert=\aleph_1$. The approach above would not work, since we would need to add "size axioms" of length $\omega_1$, and first-order formulas can only be finitely long. Here we need to use the "expand-the-language" trick that Alex Kruckman describes.

However, really the takeaway here is that we should just prove the strong version of Lowenheim-Skolem right from the get-go:

Suppose $T$ is a satisfiable theory of size $\le\kappa$ with $\kappa$ infinite. Then:

  • (Downward part) For each $M\models T$ there is some $N\preccurlyeq M$ with $\vert N\vert\le\kappa$.

  • (Upward part) For each $M\models T$ and $\lambda\ge\kappa+\vert M\vert$ there is an $N\models T$ with $M\preccurlyeq N$ and $\vert N\vert=\lambda$.

(Really the upward part is just a corollary of compactness, but we tend to bundle it with the genuinely-different downward part nonetheless.)


A technical coda

Interestingly, the "$\kappa+$" bit in the upward part is essential. This is a cute argument. Suppose $2^{\aleph_0}>\aleph_1$ (this is consistent with the usual axioms of set theory). The example is a bit complicated, so I'll just sketch it:

  • We start with a structure consisting of disjoint copies of the infinite binary tree $T=2^{<\mathbb{N}}$ and the linear order $L=(\mathbb{N},<)$, with a function $F:T\rightarrow L:\sigma\mapsto\vert\sigma\vert$ and a binary relation $B\subseteq T\times L$ with $B(\sigma,n)\leftrightarrow n<\vert\sigma\vert\wedge \sigma(n)=1$.

  • For each infinite binary sequence $g\in 2^\mathbb{N}$ we add a unary relation $R_g\subseteq T$ with $R_g(\sigma)\leftrightarrow \sigma\prec g$.

  • Call this resulting structure $A$. We can now show that any proper elementary extension of $A$ - and in particular, every uncountable model of $Th(A)$ - has size $\ge 2^{\aleph_0}$, the point being that if one of the $R_g$-relations gets an "infinitely long element" then all the $R_g$-relations must get an "infinitely long element" (this is where the $(\mathbb{N},<)$-part comes in), and these have to be distinct. Since we've assumed the continuum hypothesis fails, this means that $Th(A)$ has no models of size $\aleph_1$ even though $\aleph_1>\vert A\vert$.

A natural question at this point is whether we can produce a counterexample in ZFC alone. If I recall correctly the answer is yes, but I don't have a construction in mind at the moment; I'll address this at a later point.