1
$\begingroup$

Begin with the empty set then construct the set of the empty set, then construct the set of all subsets of the latter set, then at each level of construction construct the next level as the set all subsets of that level that are definable using formulas restricted to that level, i.e. follow Godel's construction of stages, then continue that iterative construction, lets have a first limit level among levels of that construction, lets continue this construction transfinitely as long as at each level $L_{\alpha}$ there exists a set $x$ constructed at a prior level such that there is a well ordering on the class of all levels from the empty set till $L_{\alpha}$, that is isomorphic to $x$, i.e. the height of each level corresponds to a well ordering that is a set formed at a prior level.

Question: what is the limit to this construction?

Is it $L_{\omega_1}$? or is it some fixed countable point, like $L_{\omega^{\omega^{\omega^{.^{.^{.}}}}}}$?

I tend to think it is $L_{\omega^{\omega^{\omega^{.^{.^{.}}}}}}$, and that this (I suppose) would make it of the strength of $PA$?

Improve this question
$\endgroup$
9
  • $\begingroup$ What do you mean by "the well-ordering"? Both when you talk of the well-ordering class and the well-ordering of some set. I'm afraid I don't understand yet what you are trying to say. $\endgroup$
    – Andrés E. Caicedo
    Commented Nov 24, 2018 at 13:54
  • $\begingroup$ Ok, I've deleted 'the', it is some well ordering, not a specific one. $\endgroup$
    – Zuhair Al-Johar
    Commented Nov 24, 2018 at 14:02
  • $\begingroup$ I still don't understand. At stage $\alpha$, by "a well ordering on the class of all levels from the empty set till $L_\alpha$" you may mean either "a well-ordering of $\alpha$", "a well-ordering of $L_\alpha$", or something else. Which one do you mean? (If you mean something else, please clarify.) Thanks. $\endgroup$
    – Andrés E. Caicedo
    Commented Nov 24, 2018 at 14:20
  • $\begingroup$ You get (orderings of $\omega$ isomorphic to) all the recursive ordinals at $L_{\omega + 1}$, so the answer is greater than $\Omega_1^{CK}$. Probably it's consistent both that the answer is $\omega_1$ and that it is not. $\endgroup$
    – Nik Weaver
    Commented Nov 24, 2018 at 15:11
  • $\begingroup$ @AndrésE.Caicedo by a level I mean a stage $L_{\alpha}$ of the constructible hierarchy, the well ordering is on the class $\{L_0, L_1,....,L_{\alpha}\}$, in other words suppose you have a well ordering $s$ that is a set (i.e. an element of some level $L_{\alpha}$, then there is a subclass $\{L_0,L_1...,L_{\kappa}\}$ (that is a hierarchy) of the class of all levels of the hierarchy that is isomorphic to $s$. For example the stage $L_{\omega_1}$ is not reachable from below, because no stage $L_{\alpha}$ for a countable $\alpha$ would contain a set that is a well ordering that is isomorphic to $\endgroup$
    – Zuhair Al-Johar
    Commented Nov 24, 2018 at 15:56

1 Answer 1

Reset to default
4
$\begingroup$

If I've correctly understood the question, then I think the answer is $\omega_1^{CK}$, the first non-recursive ordinal.

On the one hand, as Nik Weaver pointed out in a comment, all recursive well-orderings of $\omega$ are in $L_{\omega+1}$, so your construction certainly goes through at least all the recursive ordinals.

On the other hand, every well-ordering of $\omega$ that is an element of $L_{\omega_1^{CK}}$ is hyperarithmetical. (This has nothing much to do with well-ordering; it's true for all relations on $\omega$ that are in $L_{\omega_1^{CK}}$.) And the lengths of hyperarithmetical well-orderings of $\omega$ are only the recursive ordinals. So $L_{\omega_1^{CK}}$ contains no well-orders of $\omega$ of length $\omega_1^{CK}$ (or more), and your construction ends at that stage.

Improve this answer
$\endgroup$
13
  • $\begingroup$ But the class of all equivalence classes of recursive well orderings of $\omega$ that are elements of $L_{\omega +1}$ under equivalence relation "isomorphism", is a set (I'm just using Scott's trick)! and it would be well orderable by a well ordering relation that is a set, and that would be a well ordering that is isomorphic to a well ordering on $\omega_1^{CK}$, clearly this theory is going way beyond $\omega_1^{CK}$ $\endgroup$
    – Zuhair Al-Johar
    Commented Nov 24, 2018 at 18:17
  • 2
    $\begingroup$ @ZuhairAl-Johar The set of equivalence classes that you described in your first comment is indeed a set, but it is not in $L_{\omega_1^{CK}}$. $\endgroup$
    – Andreas Blass
    Commented Nov 24, 2018 at 23:10
  • 1
    $\begingroup$ @ZuhairAl-Johar The set of well-orderings on $\omega$ that are elements of $L_{\omega+1}$ and the set of equivalence classes of such well-orderings are not elements of $L_{\omega+5}$ or even of $L_{\omega_1^{CK}}$. The same is true if you use the word "set" (in the definition of well-ordering) to mean "set in the constructible hierarchy". (continued in next comment) $\endgroup$
    – Andreas Blass
    Commented Nov 25, 2018 at 12:44
  • 1
    $\begingroup$ If, on the other hand, you use "set" to mean "set in $L_{\omega+2}$", then the resulting definition of "well-ordering" will include some relations that are not order-isomorphic to ordinals and therefore don't make sense in the context of using them to determine the extent of a hierarchy. $\endgroup$
    – Andreas Blass
    Commented Nov 25, 2018 at 12:45
  • 2
    $\begingroup$ @ZuhairAl-Johar To answer your latest comment, have you really looked at all the quantifiers in "$x$ is a well-ordering on $\omega$"? In either of the two formulations "every nonempty subset has a first element" or "there is no infinite decreasing sequence", there is a quantifier which, if interpreted as ranging only over $L_{\omega+1}$, is too weak to ensure that $x$ is really well-founded, i.e., is order-isomorphic to an ordinal. $\endgroup$
    – Andreas Blass
    Commented Nov 25, 2018 at 22:07

You must log in to answer this question.

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