What is the cardinality (finite, infinite and countable, or infinite and uncountable) of the smallest model of the following set?

Question

So the set of sentences is such that

$\{\gamma _{\geq n}$ : $n$ is even}

where $\gamma _{\geq n}$ is a sentence such that its models have the cardinality of at least $n$.

I think the answer is that the smallest model of the set is enumerable and infinite, but it's just a guess.

Answer 1

This is just going to be the formalization of the answers given by Ned and Harry in the comments.

Claim 1. The set of sentences $\Sigma = \{\gamma_{\geq n} : n \ \ \text{is even}\}$ has no finite models.

Proof of Claim 1. Assume for contradiction there exists an $\mathscr L$-structure $\mathscr M$ (in some language $\mathscr L$) such that $\mathscr M \models \Sigma$ and $|\mathscr M| = m$ for some $m \in \mathbb N$. We have two cases:

• If $m$ is even then so is $m+2$, and in this case $\mathscr M \not\models \gamma_{\geq m+2}$ (since $|\mathscr M| = m < m+2$); therefore $\mathscr M \not\models \Sigma$ (since $\gamma_{\geq m+2} \in \Sigma$), a contradiction.
• If $m$ is odd then $m+1$ is even, and in this case $\mathscr M \not\models \gamma_{\geq m+1}$ (since $|\mathscr M| = m < m+1$); therefore $\mathscr M \not\models \Sigma$ (since $\gamma_{\geq m+1} \in \Sigma$), a contradiction.

In both cases we reach a contradiction, so our assumption was false and hence $\Sigma = \{\gamma_{\geq n} : n \ \ \text{is even}\}$ has no finite models, as required. $\blacksquare$

---

Now that we know that $\Sigma$ has no finite models, we want to show that it has a countably infinite model.

Claim 2. The set of sentences $\Sigma = \{\gamma_{\geq n} : n \ \ \text{is even}\}$ has a countably infinite model.

Proof of Claim 2. We just need to provide a language $\mathscr L$ and an $\mathscr L$-structure $\mathscr M$ such that $\mathscr M \models \Sigma$. Consider $\mathscr L = \varnothing$, so that $\mathscr L$-structures are just sets; in particular, $\mathbb N$ is an infinite $\mathscr L$-structure and we claim that $\mathbb N \models \Sigma$.

Indeed, let $\phi \in \Sigma$, so that $\phi$ is $\gamma_{\geq n}$ for some even natural number $n$. Since $\mathbb N$ is infinite it has at least $n$ elements for every even natural number $n$, so $\mathbb N \models \phi \ $ for all $\phi \in \Sigma$ and thus the claim follows. $\blacksquare$