Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm trying to prove the following: If $T$ is a first-order theory with the property that for every natural number $n$ there is a natural number $m>n$ such that $T$ has an $m$-element model then $T$ has an infinite model.

My thoughts: If $M$ is an $n$-element model then $\varphi_n = \exists v_1, \dots, v_n ((v_1 \neq v_2) \land \dots \land (v_{n-1} \neq v_n))$ is true in $M$. Can I use this to show that $T$ has an infinite model? How? Perhaps combine it with the compactness theorem somehow? Thanks for your help.

share|improve this question
add comment

2 Answers 2

up vote 4 down vote accepted

You are close.

Yes, this is what you need to do, but remember that inequality is not transitive. It is not enough to require $v_i\neq v_{i+1}$, but you need to have $\varphi_n=\bigwedge_{i\neq j<n} v_i\neq v_j$.

If there are arbitrarily large finite models, then every finite collection of sentences of the form above is consistent with $T$, therefore $T\cup\{\varphi_n\mid n\in\omega\}$ is consistent and any model of that cannot be finite.

share|improve this answer
add comment

This is a standard fact. The result you are looking for is exactly the compactness theorem, but you can also do it directly. Just take an ultraproduct of a sequence $M_i$ of larger and larger finite models. Since every one of these models $T$, so does the ultraproduct, by Łoś's theorem.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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