7
$\begingroup$

Let $Q\colon=\{\alpha \in Ord \mid \exists \beta \in \alpha(\beta \text{ is undefinable in } \langle\alpha,<\rangle )\}$ denote the set of all ordinal numbers which has an undefinable member.

Since there are only countable many formulae, the number of definable members in $\langle\alpha,<\rangle$ must be at most countable infinite. Thus every uncountable ordinal numbers must belong to $Q$. On the other hand, for each natural number, if it's in $\alpha$, then it must be definable, this conclusion is easy to get by induction.

So $q$, the least member of $Q$ is greater than $\omega$ but at most $\omega_1$.

My question: Is $q$ exactly $\omega_1$, or a countable one?

$\endgroup$
  • 1
    $\begingroup$ The significant twist here is that you asked about ordinals $\beta$ that are not definable in $(\alpha, <)$, rather than ordinals that are not definable in $(V, \in)$. There are models of ZFC in which every set is definable over the model, but that does not directly answer the specific question here, because you are only asking about definability over another ordinal. $\endgroup$ – Carl Mummert Jul 16 '13 at 11:28
  • $\begingroup$ @CarlMummert "There are models of ZFC in which every set is definable over the model". Did you mean definable with parameters, or just definable(without parameters)? $\endgroup$ – Popopo Jul 16 '13 at 11:40
  • $\begingroup$ !Popopo: without parameters $\endgroup$ – Carl Mummert Jul 16 '13 at 11:41
  • $\begingroup$ @Carl Mummert: You are raising an important subtlety I had not considered, so thanks. But isn't $\omega + \omega$ countable, and so why give this example? $\endgroup$ – user452 Jul 16 '13 at 11:41
  • $\begingroup$ @CarlMummert I was trying to understand you. Would you please show me more detail? Do these models of ZFC, which every set is definable over the model, themselves may have uncountable(outside) many subsets? Or the cardinalities of their powersets are all at most countable(outside), but some of which are uncountable(inside)? Besides, what about $(V,<)$? $\endgroup$ – Popopo Jul 16 '13 at 14:44
8
$\begingroup$

The standard reference to this is the paper "The Elementary Theory of Well-Ordering -- A Metamathematical Study --" by Doner, Mostowski and Tarski in Logic Colloquim '77 Ed. Macintyre, Pacholski and Paris. In particular the Corollary 46 states:

The set of ordinals definable in $\mathfrak N_\alpha$ [$=\langle \alpha, \le\rangle$], where $\alpha = \omega^\omega \cdot \beta + \gamma$ with $0 < \beta, \gamma < \omega^\omega$, is $$\omega^\omega \cup \{\omega^\omega \cdot \beta + \gamma' : \gamma' < \gamma\}$$ In fact, the restriction of $\mathfrak N_\alpha$ to this set is an elementary substructure of $\mathfrak N_\alpha$.

It follows that every ordinal is definable in $\omega^\omega + \gamma$ for $\gamma < \omega^\omega$. However $\omega^\omega$ is not definable in $\omega^\omega \cdot 2$. So $\omega^\omega \cdot 2 \in Q$.

$\endgroup$
  • $\begingroup$ Nice reference, thanks! $\endgroup$ – Andrés E. Caicedo Jul 16 '13 at 14:15
  • $\begingroup$ It's nice for me, thank you. $\endgroup$ – Popopo Jul 16 '13 at 14:38
2
$\begingroup$

Suppose we have limit ordinals $\alpha < \beta$ and $L_\alpha \prec L_\beta$, then by Theorem 2.4 in Undefinable sets, Rudolf v.B. Rucker, Annals of Mathematical Logic Volume 6, Issues 3–4, March 1974, Pages 395–419 which states

lf x is a model of V=L, then $\alpha$ is strongly inconceivable in x iff $L_\alpha\prec x$. Here $\alpha$ is strongly inconceivable in x means for all $\beta\geq \alpha$, $\beta$ is not definable in $\langle x,\in \rangle$ with parameters from $\alpha\cap x$.

Then $\alpha$ is not definable in $\langle L_\beta,\in\rangle$ with finitely many parameters from $\alpha$. Therefore, $\alpha$ is not definable in $\langle \beta,\in\rangle$ since we could define in $L_\beta$ "x is an ordinal" by describing x to be transitive and totally ordered. It is known that $\{\alpha: L_\alpha\prec L_{\omega_1}\}$ is a closed unbounded set so we could always pick two countable ordinals $\alpha,\beta$ whose properties are described as above. However, it does not really give you the exact ordinal though.

$\endgroup$
0
$\begingroup$

There must be a countable undefinable ordinal, because there are uncountably many countable ordinals.

$\endgroup$
  • $\begingroup$ I don't think this addresses the specific question being asked. $\endgroup$ – Carl Mummert Jul 16 '13 at 11:25
  • $\begingroup$ @Carl Mummert: I'd appreciate some edification here. I realize that there are countable models for uncountable sets. But in this case, it seems like the actual semantic object--the set of ordinals less than $\omega_1$--IS uncountable. So is definability purely a syntactic property? $\endgroup$ – user452 Jul 16 '13 at 11:48
  • $\begingroup$ The question is about the least $\alpha$ such that there is a $\beta < \alpha$ which is not definable in $(\alpha, <)$. If $\alpha$ is countable, there are only countably many smaller ordinals, and there are countably many formulas, so that is not an obstacle to every $\beta < \alpha$ being definable in $(\alpha, <)$ if $\alpha$ is countable. The question is not about "undefinable" ordinals in general. $\endgroup$ – Carl Mummert Jul 16 '13 at 11:51
  • $\begingroup$ For more about "undefinable" ordinals in general, this answer gives a good explanation: mathoverflow.net/questions/44102/… $\endgroup$ – Carl Mummert Jul 16 '13 at 11:53
  • $\begingroup$ But doesn't that mean that $\alpha$ will have to be uncountable? $\endgroup$ – user452 Jul 16 '13 at 11:53

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.