2
$\begingroup$

There is this problem I am working on that has two parts : Let $T$ be an incomplete countable theory. Either prove or provide an example for the following.

1)If T has an uncountable model, then T has a countable model.

2)If T has finite models and a denumerable model, then T has arbitrarily large finite models.

Any ideas of how to show the (1)?

In (2), I picked a cardinal $k$. I considered the $L'$-theory, which is the full theory of our infinite model and the extra axioms $c_a \neq c_b$ for all $a\neq b$. Is that enough?

Thank you in advance.

$\endgroup$
  • 2
    $\begingroup$ For 1), since $T$ is countable you may assume that the language is countable and then use Löwenheim-Skolem's theorem. For 2), what you say wouldn't work, you may only get infinite models this way $\endgroup$ – Max Jun 10 '17 at 10:23
  • 3
    $\begingroup$ Moreover 2) isn't true, so you'll want to find a counterexample $\endgroup$ – Max Jun 10 '17 at 10:29
  • $\begingroup$ Thank you for your help!I proved (1). I cannot think of any counterexample in (2), any ideas? $\endgroup$ – NikosEllin Jun 11 '17 at 0:34
3
$\begingroup$

It sounds like you've already solved part (1): as others have said, you need to apply downward Löwenheim-Skolem.

For (2), the result is false. By way of a hint, can you write a sentence (in some language) that has only infinite models? Can you think of another sentence whose models are all smaller than some finite size? What happens when you take the disjunction of these sentences?

$\endgroup$
  • $\begingroup$ That wouldn't work for 2) since there is no unique sentence that has only infinite models : being infinite is not finitely axiomatizable . $\endgroup$ – Max Jun 11 '17 at 8:08
  • $\begingroup$ @Max There are definitely sentences that are true only in infinite models. Consider "$\leq$ is a total order with no upper bound", for example. $\endgroup$ – Mike Haskel Jun 11 '17 at 8:12
  • $\begingroup$ Oh my bad, I'm so stupid. I had for some reason convinced myself that you meant "a sentence that axiomatizes 'being infinite' " $\endgroup$ – Max Jun 11 '17 at 8:14
  • $\begingroup$ @Max Moreover, there's a whole branch of model theory that studies pseudofinite theories. A theory $T$ is pseudofinite just if every sentence consistent with it has a finite model. The whole study would be vacuous if what you say were true. $\endgroup$ – Mike Haskel Jun 11 '17 at 8:14
  • $\begingroup$ @Max It's alright, you're fine. :-) $\endgroup$ – Mike Haskel Jun 11 '17 at 8:14
0
$\begingroup$

For the second question , what you could try to do is choose an $n$, such that you don't want there to be finite models with $n$ or more elements.

Once you've done that you can try and write the following sentences in a first order language :

"If there are $n$ distinct objects, then there are $n+1$ distinct objects"

And for $k\geq 0$, "If there are $n+k$ distinct objects, then there are $n+k+1$". Call this sentence $F_k$.

Then what kind of models does $T=\{F_k\mid k\in \Bbb{N}\}$ have ?

$\endgroup$
  • $\begingroup$ Your first sentence kind of confused me. What do you mean? $\endgroup$ – NikosEllin Jun 11 '17 at 23:41
  • 1
    $\begingroup$ What I mean is that you can choose any $n$ and you will have the theorem "There exists a countable theory such that it has finite models, but every model with more than $n$ element is infinite" $\endgroup$ – Max Jun 12 '17 at 6:08

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.