11
$\begingroup$

Every proof that I read seems to assume that $|L|\leq\aleph_0$. But then how do you model things like field over $\mathbb{R}$ without running out of variable symbols?

More importantly, how can I prove that $|L|\leq\aleph_0$?

$\endgroup$
  • 2
    $\begingroup$ You say that every proof you read seems to assume a countable language. I'm curious what sources you're reading. $\endgroup$ – Alex Kruckman Oct 26 '17 at 15:00
  • $\begingroup$ I think typically the requirement is enumerability, not countability. For example, if I remember correctly, Gödel's Incompleteness Theorem requires an enumerable set of symbols with an arbitrary ordering so you can write functions that can encode & decode stuff. (I just used the wrong word at every possible opportunity in that last sentence; hopefully my meaning is nonetheless clear.) $\endgroup$ – Max von Hippel Oct 26 '17 at 19:35
  • 1
    $\begingroup$ @MaxvonHippel By enumerable, you mean recursively/computably enumerable? This assumption is certainly relevant when you're doing foundational work (e.g. Gödel coding), or computable model theory, or asking questions about decidability. But it's completely irrelevant for ordinary model theory. $\endgroup$ – Alex Kruckman Oct 26 '17 at 21:09
  • $\begingroup$ @AlexKruckman yep that's what I meant. And thanks for telling me, that's good to know! The only 1st order stuff I've learned is Gödel coding and some computable model theory, so it makes sense that I had this incorrect view. $\endgroup$ – Max von Hippel Oct 26 '17 at 21:37
14
$\begingroup$

You can have as many symbols as you like in your language! For instance, with a possibly uncountable language $L$, the Lowenheim-Skolem theorem becomes:

If $\mathcal{M}$ is an $L$-structure, then there is an elementary substructure $\mathcal{N}\preccurlyeq\mathcal{M}$ of cardinality at most $\aleph_0\cdot\vert L\vert$.

Some authors choose to restrict attention to countable languages for simplicity; I think that's a terrible decision most of the time, since it can lead exactly to your confusion.

That said, there are situations where it does matter that the language be countable. For example:

  • Morley's theorem only applies to theories in countable languages. I can have a theory $T$ in an uncountable language $L$ which is $\omega_2$-categorical but not $\omega_1$-categorical. And in fact, extending Morley's theorem to uncountable languages is very nontrivial.

  • Computable structure theory really only works when the language is countable, since everything has to be coded by natural numbers.

But yes, except in rare occasions (at least, they seem rare to me) there is no need to restrict attention to countable languages; and texts which do restrict attention to countable languages just to simplify things should state this extremely explicitly to avoid confusion.

$\endgroup$
  • $\begingroup$ Thanks! This has indeed caused me a lot of confusion. $\endgroup$ – Sid Caroline Oct 26 '17 at 13:18
  • 1
    $\begingroup$ The omitting types theorem is another important example of a situation in which you have to assume a countable language. $\endgroup$ – Alex Kruckman Oct 26 '17 at 14:58
  • 1
    $\begingroup$ Another important example is the Ryll-Nardzewski theorem (i.e. $\omega$-categoricity is equivalent to finitely many $n-$types for each $n$). This does not work for uncountable languages and the countable requirement is necessary. $\endgroup$ – Kyle Oct 28 '17 at 18:36
8
$\begingroup$

This is not true precisely for the reason you stated. For example, to apply the compactness theorem so as to prove the existence of a hyperreal extension of the real numbers, Abraham Robinson exploited a language with uncountably many symbols.

$\endgroup$

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.