0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You seem to be confusd about what you want to prove. The claim you are after says "at least $n$ elements", so yoy want to show that there are no models with less than $n$ elements. $\endgroup$ – Mariano Suárez-Álvarez Jun 4 '17 at 19:01
  • $\begingroup$ As for the claim you want to prove: why don't you just take $n=1$? $\endgroup$ – Mariano Suárez-Álvarez Jun 4 '17 at 19:03
  • $\begingroup$ @MarianoSuárez-Álvarez Ohh so sorry, I meant "at most", not "at least". Translation problems. I'll edit the question. Thank you! $\endgroup$ – user313212 Jun 4 '17 at 19:09
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Excuse me, but how this answers my question? You answered to "arbitrarily big finite models implies that there is an infinite one". I just said I knew this result and could actually use it as a fact. $\endgroup$ – user313212 Jun 4 '17 at 19:27
  • $\begingroup$ @user313212 Then your reasoning is correct. I thought you though the result was trivial, which it is not by any means (compactness is a huge theorem) $\endgroup$ – Jsevillamol Jun 4 '17 at 19:35
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.