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$?

$\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$ Nov 24 '18 at 13:54
  • $\begingroup$ Ok, I've deleted 'the', it is some well ordering, not a specific one. $\endgroup$ Nov 24 '18 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$ Nov 24 '18 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
    Nov 24 '18 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$ Nov 24 '18 at 15:56
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.

$\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$ Nov 24 '18 at 18:17
  • $\begingroup$ the idea of my construction is that the height of the whole hierarchy must not be ordinally smaller than a set in the hierarchy, so any well ordering on a set that is in the hierarchy must be isomorphic to a well ordering on a sub-hierarchy of the whole hierarchy (a subhierarchy is an initial segment of levels of the hierarchy), see my comments to Andrés E. Caicedo. $\endgroup$ Nov 24 '18 at 20:07
  • $\begingroup$ I think the answer as it stands is wrong, or perhaps I'm missing something. $\endgroup$ Nov 24 '18 at 20:09
  • 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$ Nov 24 '18 at 23:10
  • 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$ Nov 25 '18 at 22:07

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.