1
$\begingroup$

I want to prove the following statement:

Let $\Gamma_1$ and $\Gamma_2$ be two theories formulated in a countable language. Show that if $\Gamma_1$ and $\Gamma_2$ have the same countably infinite models, then they have the same models of each finite cardinality.

But since I'm relatively new to metalogic, I do not really understand what it is I should do. I know what a countable language is but I do not know what it means that the set of sentences have the same countable models? My first thought is that the two theories should be the same, is that correct?

Does anyone want to help me clarify this task so I can understand what it is I should do?

Edit: After the feedback I received I realized that the statement must be misspelled, so I found out what it was really going to say:

Let $\Gamma_1$ and $\Gamma_2$ be two theories formulated in a countable language. Show that if $\Gamma_1$ and $\Gamma_2$ have the same countably infinite models, then they have the same models of each infinite cardinality.

This also made it easier for me to understand. Here I think that you first must prove that they have the same models, possibly with Löwenheim-Skolem's theorem. And then we know that consistent theories, which have a model, also have a model of cardinality $\kappa$ for each infinite cardinality $\kappa$. Is it possible to prove the statement with only these two approaches?

Thanks in advance!

$\endgroup$
5
  • $\begingroup$ Where did you find this statement? If "enumerable" is supposed to mean "countably infinite" this is not true for the most common definitions. Maybe it is talking about first-order logic without equality? $\endgroup$
    – Eric Wofsey
    Commented Apr 16, 2021 at 22:20
  • $\begingroup$ @EricWofsey And conversely if "enumerable" means "countable or finite" then the statement is vacuously true. I suspect you're right, that first-order logic without equality is intended. $\endgroup$
    – Noah Schweber
    Commented Apr 16, 2021 at 22:23
  • $\begingroup$ Re: the edit just now, I think "countably models" should be "countably infinite models." (And if so, as Eric says the statement is then false without further restrictions on the theories involved.) $\endgroup$
    – Noah Schweber
    Commented Apr 16, 2021 at 22:24
  • $\begingroup$ The question comes from my lecture and was left as an exercise without explanation. I changed it to "countably infinite" just now, thank you! And yes, this is within first-order logic. $\endgroup$
    – idlatva
    Commented Apr 16, 2021 at 22:26
  • 1
    $\begingroup$ The statement is very badly worded - what does "have the same infinite models" mean? For a possible counterexample, consider the sentence $\exists x, y\forall z(z = x \lor y = z)$: it has no infinite models, but has two finite models (up to equivalence of models). $\endgroup$
    – Rob Arthan
    Commented Apr 16, 2021 at 22:55

2 Answers 2

Reset to default
2
$\begingroup$

The premise that confuses you must be

if $\Gamma_1$ and $\Gamma_2$ have the same countably infinite models ...

This means that for every interpretation of the language (that is, a carrier set, together with functions and relations over that carrier set which represent that non-logical symbols of the language), if the carrier set is countably infinite, then the interpretation is either both a model of $\Gamma_1$ and a model of $\Gamma_2$, or not a model of either theory.

You're then asked to prove under this assumption that "either a model of both theories or a model of neither" actually holds for all infinite interpretations, no matter what their precise cardinality is.

Does this help?

$\endgroup$
3
  • $\begingroup$ Thanks. Yes, this definitely helped me understand the issue! Does this mean that I do not have to prove that they have the same models (as I wrote earlier) as is it an assumption? $\endgroup$
    – idlatva
    Commented Apr 18, 2021 at 20:54
  • $\begingroup$ @idlatva: "Have the same models" is an assumption as far as models of cardinality $\aleph_0$ goes. For models of cardinality $>\aleph_0$, it is what you're being asked to prove. $\endgroup$
    – Troposphere
    Commented Apr 18, 2021 at 20:58
  • $\begingroup$ Thanks you so much! Then I can finally try to actually come up with a solution to the task! $\endgroup$
    – idlatva
    Commented Apr 18, 2021 at 21:03
1
$\begingroup$

If $M$ is an infinite structure such that $M\models \Gamma_1$ and $M\not\models \Gamma_2,$ then by the downward Lowenheim-Skolem theorem, $M$ has a countably infinite elementary substructure $N$ and since it is an elementary substructure, $N\models \Gamma_1$ and $N\not\models \Gamma_2.$

$\endgroup$

You must log in to answer this question.

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