If $\Phi$ has only finite models, there is some $n\in \mathbb{N}$ such that each model has at most $n$ elements.

414 Views Asked by At

I want to prove the following claim:

Let $\Phi \subseteq \mathrm{Sent}_{\Sigma}$ be such that each model $\mathcal{M}$ of $\Phi$ is finite. Show that there is some $n\in \mathbb{N}$ such that each model of $\Phi$ has at most $n$ elements.

My try: I have proved the following statement which I can use as a fact: If $\Phi \subseteq \mathrm{Sent}_{\Sigma}$ admites finite models of arbitrarily big cardinal, the $\Phi$ has an infinite model.

So let's assume otherwise, that is, given $n\in \mathbb{N}$, suppose I can find a model $\mathcal{M}\in \mathcal{Mod}(\Phi)$ such that $|\mathcal{M}|\geq n$. This means I can find models of $\Phi$ arbitrarily big, so by the fact above, $\Phi$ possesses an infinite model $\mathcal{N}$, which contradicts the hypothesis that $\Phi$ has only finite models.

Is this prove okay? It looks like a simple proof by contradiction and that makes me doubt.

2

There are 2 best solutions below

2
On BEST ANSWER

The proof is not correct. Arbitrarily big is not the same as infinite.

The standard proof of this fact makes use of the compactness theorem.

It is easy to construct a sentence $S_n$ such that $S_n$ is true in a model iff the model has more than $n$ elements (can you show this?).

Then consider $\Phi + \{S_n\}_{n=1}^{\infty}$. Clearly every finite subset of the theory is satisfiable, since $\Phi$ has arbitrarily large models.

But then by compactness the whole theory is satisfiable, and since only an infinite model can satisfy all the $S_n$, we have found an infinite model for our theory $\Phi$.

0
On

Yes, that proof is correct - the statement you're trying to prove is basically the contrapositive of the statement you already know.