8
$\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$
6
  • 2
    $\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$ Commented Jul 16, 2013 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
    Commented Jul 16, 2013 at 11:40
  • $\begingroup$ !Popopo: without parameters $\endgroup$ Commented Jul 16, 2013 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
    Commented Jul 16, 2013 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
    Commented Jul 16, 2013 at 14:44

2 Answers 2

9
$\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$
2
  • $\begingroup$ Nice reference, thanks! $\endgroup$ Commented Jul 16, 2013 at 14:15
  • $\begingroup$ It's nice for me, thank you. $\endgroup$
    – Popopo
    Commented Jul 16, 2013 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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .