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$
3
  • 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$ Jun 10, 2017 at 10:23
  • 3
    $\begingroup$ Moreover 2) isn't true, so you'll want to find a counterexample $\endgroup$ Jun 10, 2017 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, 2017 at 0:34

2 Answers 2

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$
6
  • $\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$ Jun 11, 2017 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$
    – user231101
    Jun 11, 2017 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$ Jun 11, 2017 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$
    – user231101
    Jun 11, 2017 at 8:14
  • $\begingroup$ @Max It's alright, you're fine. :-) $\endgroup$
    – user231101
    Jun 11, 2017 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$
2
  • $\begingroup$ Your first sentence kind of confused me. What do you mean? $\endgroup$
    – NikosEllin
    Jun 11, 2017 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$ Jun 12, 2017 at 6:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .