If a sentence $\varphi$ is true in all enumerable models, then is $\varphi$ true in all non-enumerable models too?

127 Views Asked by At

If a sentence $\varphi$ is true in all enumerable models, then is $\varphi$ true in all non-enumerable models too?

If a sentence $\varphi$ is true in all enumerable models, then $\varphi$ is true in all denumerable models. Then by Upward Lowenheim Skolem Theorem, does this entail that $\phi$ is true in all non-denumerable models as well?

1

There are 1 best solutions below

10
On BEST ANSWER

Based on your previous question, for you "enumerable" means countable = finite or countably infinite, and "denumerable" means countably infinite.

So you you want to prove that if a sentence $\varphi$ is true in all countable structures, then $\varphi$ is true in all uncountably infinite structures. It would suffice to prove the stronger statement that if a sentence $\varphi$ is true in all countably infinite structures, then $\varphi$ is true in all uncountably infinite structures. Applying Upward Löwenheim-Skolem doesn't help, because it only gives you some model of $\varphi$ in each uncountable cardinality.

Instead, let's prove the contrapositive of this statement: If a sentence $\varphi$ is false in some uncountably infinite structure, then $\varphi$ is false in some countably infinite structure.

If $\varphi$ is false in some uncountably infinite structure, then $\lnot \varphi$ has an uncountably infinite model. Now we just have to apply the Downward Löwenheim-Skolem theorem to $\lnot \varphi$ to get a countably infinite model. So $\varphi$ is false in some countably infinite structure.

This argument assumes the language is countable. The statement may not be true in an uncountable language.


Regarding terminology: "enumerable" and "denumerable". The problem is that conventions are not universal. Here's my experience, I welcome comments from others with different experiences!

There are two notions we want to name, which I'll refer to in this post as "countably infinite" and "finite or countably infinite".

These days, almost no one says "enumerable" or "denumerable". They say "countable". Now "countable" may mean "countably infinite" or "finite or countably infinite" depending on the author. If "countable" means "countably infinite", then the author would refer to the other notion as "finite or countable" or "at most countable". If "countable" means "finite or countably infinite", then the author would refer to the other notion as "countably infinite".

Some authors use "countable" and "denumerable" for the two notions, or "countable" and "enumerable" for the two notions. But again, you'd have to check the conventions. To make things worse, "denumerable" and "enumerable" have both been commonly used as synonyms for "countable", so that all three words can mean the same thing. I think the most common usage of "enumerable" these days is in the notion of "recursively enumerable" from computability theory, which is something quite different.

My main complaint was that you're using "enumerable" and "denumerable" for the two notions. I think this is really confusing, because the words sound so similar. It's hard to remember which one means which notion. If you've learned this convention from some source, I'd be curious to know what it is.