Proof that given an empty vocabulary, P = { $\Omega$ $\in$ STRUCT[L] | $\Omega$ has domain countable and infinity} is not definable.

Question

Hi there i would like to prove this:

Given an empty vocabulary L ( by empty I mean L = $\emptyset$),

the property P = { $\Omega$ $\in$ STRUCT[L] | $\Omega$ has domain countable and infinity} is not definable.

where STRUCT[L]is a set with all the possibles structures that satisfies L

Given that by definable I mean that exists a set of formulas that describes the property. Moreover the set must contain a finite number of elements.

If any one could give a hint of how to solve this i would really appreciate it.

Thanks!

Answer 1

The upward Löwenheim-Skolem theorem states:

If $\Omega$ is an infinite structure over a language $L$ then for every cardinal $\lambda\ge\max(|\Omega|,|L|)$ there is a structure $\Omega'$ of cardinality $\lambda$ that is an elementary extension of $\Omega$ -- that it, it satisfies exactly the same first-order $L$-sentences as $\Omega$ does.

This means that there cannot be any (finite or infinite) set of axioms that pinpoint exactly the countably infinite $L$-structures.

Namely, whenever you have some axioms that are satisfied by one countably infinite $L$-structure, the upward Löwenheim-Skolem gives you an uncountable structure that also satisfies the axioms.

This is in particular the case where $L=\varnothing$.

---

Alternatively, use the answer to If a theory over a vocabulary L has a model with countable domain, then it has a model with uncountable domain.