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$?
$\begingroup$
$\endgroup$
4
asked Oct 26, 2017 at 12:58
-
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 KruckmanCommented Oct 26, 2017 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 HippelCommented Oct 26, 2017 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 KruckmanCommented Oct 26, 2017 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 HippelCommented Oct 26, 2017 at 21:37
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
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.
answered Oct 26, 2017 at 13:00
-
$\begingroup$ Thanks! This has indeed caused me a lot of confusion. $\endgroup$ Commented Oct 26, 2017 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$ Commented Oct 26, 2017 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$ Commented Oct 28, 2017 at 18:36
$\begingroup$
$\endgroup$
0
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.
answered Oct 26, 2017 at 12:59