What is the name of a theorem which says that if $alpha$ and $beta$ are ordinals, then $alphainbeta$, or...












0












$begingroup$


This Math.SE question contains the following information:




There is a theorem which says given any two ordinals $alpha$ and $beta$, exactly one of the following holds: $alphainbeta$, or $betainalpha$, or $alpha=beta$.




What is the name of this theorem and where can I find it?










share|cite|improve this question









$endgroup$








  • 3




    $begingroup$
    Ordinal Membership is Trichotomy - proofwiki.org/wiki/Ordinal_Membership_is_Trichotomy
    $endgroup$
    – mlerma54
    Dec 20 '18 at 4:30










  • $begingroup$
    First let me clarify a bit here regarding the question/answers in the linked thread. For ordinals less than $epsilon_0$ we often write a single ordinals in multiple ways. For example, we could write either $omega^omega$ or $omega^2+omega^omega$ etc. This is perhaps somewhat analogous to how we can write $7$, $(5+(2 cdot 1))$, $(2+(5 cdot 1))$ and so on. The point in the linked question was that if we are given a "finite string" which uses the alphabet ${+,cdot,e,(,),omega,0,s }$ ($e$ is for exponent, $s$ for successor), then there are two further questions.
    $endgroup$
    – SSequence
    Dec 20 '18 at 5:16












  • $begingroup$
    $(1)$ Is it decidable in a (strict) algorithmic sense whether a given string from these alphabet forms a "valid" expression? $(2)$ Is it decidable whether the ordinals that two different strings represent are same or not? And if not, which one is greater? The answer to both of these questions is positive (that's all that I was trying to say in the answer to linked question).
    $endgroup$
    – SSequence
    Dec 20 '18 at 5:18












  • $begingroup$
    Given your comment in the other question, I think what you might be meaning to ask is that: "Suppose we are given two well-orders (of $mathbb{N}$) say $W_1,W_2$ with order-types $alpha_1, alpha_2$ respectively. Then is there a "reasonable sense" in which we can compare $alpha_1$ and $alpha_2$ and determine which one is greater? And if one of them is greater, then can we find the "address" (very informally speaking ... this needs to be made precise) of the smaller ordinal?" I think the answer to that would depend on what do we mean by a "reasonable sense".
    $endgroup$
    – SSequence
    Dec 20 '18 at 5:30












  • $begingroup$
    @SSequence: but is it always possible to provide a precise description for an arbitrary ordinal using a finite string? For example, what language (and alphabet) would we use to describe this ordinal?
    $endgroup$
    – lyrically wicked
    Dec 20 '18 at 5:34


















0












$begingroup$


This Math.SE question contains the following information:




There is a theorem which says given any two ordinals $alpha$ and $beta$, exactly one of the following holds: $alphainbeta$, or $betainalpha$, or $alpha=beta$.




What is the name of this theorem and where can I find it?










share|cite|improve this question









$endgroup$








  • 3




    $begingroup$
    Ordinal Membership is Trichotomy - proofwiki.org/wiki/Ordinal_Membership_is_Trichotomy
    $endgroup$
    – mlerma54
    Dec 20 '18 at 4:30










  • $begingroup$
    First let me clarify a bit here regarding the question/answers in the linked thread. For ordinals less than $epsilon_0$ we often write a single ordinals in multiple ways. For example, we could write either $omega^omega$ or $omega^2+omega^omega$ etc. This is perhaps somewhat analogous to how we can write $7$, $(5+(2 cdot 1))$, $(2+(5 cdot 1))$ and so on. The point in the linked question was that if we are given a "finite string" which uses the alphabet ${+,cdot,e,(,),omega,0,s }$ ($e$ is for exponent, $s$ for successor), then there are two further questions.
    $endgroup$
    – SSequence
    Dec 20 '18 at 5:16












  • $begingroup$
    $(1)$ Is it decidable in a (strict) algorithmic sense whether a given string from these alphabet forms a "valid" expression? $(2)$ Is it decidable whether the ordinals that two different strings represent are same or not? And if not, which one is greater? The answer to both of these questions is positive (that's all that I was trying to say in the answer to linked question).
    $endgroup$
    – SSequence
    Dec 20 '18 at 5:18












  • $begingroup$
    Given your comment in the other question, I think what you might be meaning to ask is that: "Suppose we are given two well-orders (of $mathbb{N}$) say $W_1,W_2$ with order-types $alpha_1, alpha_2$ respectively. Then is there a "reasonable sense" in which we can compare $alpha_1$ and $alpha_2$ and determine which one is greater? And if one of them is greater, then can we find the "address" (very informally speaking ... this needs to be made precise) of the smaller ordinal?" I think the answer to that would depend on what do we mean by a "reasonable sense".
    $endgroup$
    – SSequence
    Dec 20 '18 at 5:30












  • $begingroup$
    @SSequence: but is it always possible to provide a precise description for an arbitrary ordinal using a finite string? For example, what language (and alphabet) would we use to describe this ordinal?
    $endgroup$
    – lyrically wicked
    Dec 20 '18 at 5:34
















0












0








0





$begingroup$


This Math.SE question contains the following information:




There is a theorem which says given any two ordinals $alpha$ and $beta$, exactly one of the following holds: $alphainbeta$, or $betainalpha$, or $alpha=beta$.




What is the name of this theorem and where can I find it?










share|cite|improve this question









$endgroup$




This Math.SE question contains the following information:




There is a theorem which says given any two ordinals $alpha$ and $beta$, exactly one of the following holds: $alphainbeta$, or $betainalpha$, or $alpha=beta$.




What is the name of this theorem and where can I find it?







reference-request ordinals






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










asked Dec 20 '18 at 4:23









lyrically wickedlyrically wicked

20818




20818








  • 3




    $begingroup$
    Ordinal Membership is Trichotomy - proofwiki.org/wiki/Ordinal_Membership_is_Trichotomy
    $endgroup$
    – mlerma54
    Dec 20 '18 at 4:30










  • $begingroup$
    First let me clarify a bit here regarding the question/answers in the linked thread. For ordinals less than $epsilon_0$ we often write a single ordinals in multiple ways. For example, we could write either $omega^omega$ or $omega^2+omega^omega$ etc. This is perhaps somewhat analogous to how we can write $7$, $(5+(2 cdot 1))$, $(2+(5 cdot 1))$ and so on. The point in the linked question was that if we are given a "finite string" which uses the alphabet ${+,cdot,e,(,),omega,0,s }$ ($e$ is for exponent, $s$ for successor), then there are two further questions.
    $endgroup$
    – SSequence
    Dec 20 '18 at 5:16












  • $begingroup$
    $(1)$ Is it decidable in a (strict) algorithmic sense whether a given string from these alphabet forms a "valid" expression? $(2)$ Is it decidable whether the ordinals that two different strings represent are same or not? And if not, which one is greater? The answer to both of these questions is positive (that's all that I was trying to say in the answer to linked question).
    $endgroup$
    – SSequence
    Dec 20 '18 at 5:18












  • $begingroup$
    Given your comment in the other question, I think what you might be meaning to ask is that: "Suppose we are given two well-orders (of $mathbb{N}$) say $W_1,W_2$ with order-types $alpha_1, alpha_2$ respectively. Then is there a "reasonable sense" in which we can compare $alpha_1$ and $alpha_2$ and determine which one is greater? And if one of them is greater, then can we find the "address" (very informally speaking ... this needs to be made precise) of the smaller ordinal?" I think the answer to that would depend on what do we mean by a "reasonable sense".
    $endgroup$
    – SSequence
    Dec 20 '18 at 5:30












  • $begingroup$
    @SSequence: but is it always possible to provide a precise description for an arbitrary ordinal using a finite string? For example, what language (and alphabet) would we use to describe this ordinal?
    $endgroup$
    – lyrically wicked
    Dec 20 '18 at 5:34
















  • 3




    $begingroup$
    Ordinal Membership is Trichotomy - proofwiki.org/wiki/Ordinal_Membership_is_Trichotomy
    $endgroup$
    – mlerma54
    Dec 20 '18 at 4:30










  • $begingroup$
    First let me clarify a bit here regarding the question/answers in the linked thread. For ordinals less than $epsilon_0$ we often write a single ordinals in multiple ways. For example, we could write either $omega^omega$ or $omega^2+omega^omega$ etc. This is perhaps somewhat analogous to how we can write $7$, $(5+(2 cdot 1))$, $(2+(5 cdot 1))$ and so on. The point in the linked question was that if we are given a "finite string" which uses the alphabet ${+,cdot,e,(,),omega,0,s }$ ($e$ is for exponent, $s$ for successor), then there are two further questions.
    $endgroup$
    – SSequence
    Dec 20 '18 at 5:16












  • $begingroup$
    $(1)$ Is it decidable in a (strict) algorithmic sense whether a given string from these alphabet forms a "valid" expression? $(2)$ Is it decidable whether the ordinals that two different strings represent are same or not? And if not, which one is greater? The answer to both of these questions is positive (that's all that I was trying to say in the answer to linked question).
    $endgroup$
    – SSequence
    Dec 20 '18 at 5:18












  • $begingroup$
    Given your comment in the other question, I think what you might be meaning to ask is that: "Suppose we are given two well-orders (of $mathbb{N}$) say $W_1,W_2$ with order-types $alpha_1, alpha_2$ respectively. Then is there a "reasonable sense" in which we can compare $alpha_1$ and $alpha_2$ and determine which one is greater? And if one of them is greater, then can we find the "address" (very informally speaking ... this needs to be made precise) of the smaller ordinal?" I think the answer to that would depend on what do we mean by a "reasonable sense".
    $endgroup$
    – SSequence
    Dec 20 '18 at 5:30












  • $begingroup$
    @SSequence: but is it always possible to provide a precise description for an arbitrary ordinal using a finite string? For example, what language (and alphabet) would we use to describe this ordinal?
    $endgroup$
    – lyrically wicked
    Dec 20 '18 at 5:34










3




3




$begingroup$
Ordinal Membership is Trichotomy - proofwiki.org/wiki/Ordinal_Membership_is_Trichotomy
$endgroup$
– mlerma54
Dec 20 '18 at 4:30




$begingroup$
Ordinal Membership is Trichotomy - proofwiki.org/wiki/Ordinal_Membership_is_Trichotomy
$endgroup$
– mlerma54
Dec 20 '18 at 4:30












$begingroup$
First let me clarify a bit here regarding the question/answers in the linked thread. For ordinals less than $epsilon_0$ we often write a single ordinals in multiple ways. For example, we could write either $omega^omega$ or $omega^2+omega^omega$ etc. This is perhaps somewhat analogous to how we can write $7$, $(5+(2 cdot 1))$, $(2+(5 cdot 1))$ and so on. The point in the linked question was that if we are given a "finite string" which uses the alphabet ${+,cdot,e,(,),omega,0,s }$ ($e$ is for exponent, $s$ for successor), then there are two further questions.
$endgroup$
– SSequence
Dec 20 '18 at 5:16






$begingroup$
First let me clarify a bit here regarding the question/answers in the linked thread. For ordinals less than $epsilon_0$ we often write a single ordinals in multiple ways. For example, we could write either $omega^omega$ or $omega^2+omega^omega$ etc. This is perhaps somewhat analogous to how we can write $7$, $(5+(2 cdot 1))$, $(2+(5 cdot 1))$ and so on. The point in the linked question was that if we are given a "finite string" which uses the alphabet ${+,cdot,e,(,),omega,0,s }$ ($e$ is for exponent, $s$ for successor), then there are two further questions.
$endgroup$
– SSequence
Dec 20 '18 at 5:16














$begingroup$
$(1)$ Is it decidable in a (strict) algorithmic sense whether a given string from these alphabet forms a "valid" expression? $(2)$ Is it decidable whether the ordinals that two different strings represent are same or not? And if not, which one is greater? The answer to both of these questions is positive (that's all that I was trying to say in the answer to linked question).
$endgroup$
– SSequence
Dec 20 '18 at 5:18






$begingroup$
$(1)$ Is it decidable in a (strict) algorithmic sense whether a given string from these alphabet forms a "valid" expression? $(2)$ Is it decidable whether the ordinals that two different strings represent are same or not? And if not, which one is greater? The answer to both of these questions is positive (that's all that I was trying to say in the answer to linked question).
$endgroup$
– SSequence
Dec 20 '18 at 5:18














$begingroup$
Given your comment in the other question, I think what you might be meaning to ask is that: "Suppose we are given two well-orders (of $mathbb{N}$) say $W_1,W_2$ with order-types $alpha_1, alpha_2$ respectively. Then is there a "reasonable sense" in which we can compare $alpha_1$ and $alpha_2$ and determine which one is greater? And if one of them is greater, then can we find the "address" (very informally speaking ... this needs to be made precise) of the smaller ordinal?" I think the answer to that would depend on what do we mean by a "reasonable sense".
$endgroup$
– SSequence
Dec 20 '18 at 5:30






$begingroup$
Given your comment in the other question, I think what you might be meaning to ask is that: "Suppose we are given two well-orders (of $mathbb{N}$) say $W_1,W_2$ with order-types $alpha_1, alpha_2$ respectively. Then is there a "reasonable sense" in which we can compare $alpha_1$ and $alpha_2$ and determine which one is greater? And if one of them is greater, then can we find the "address" (very informally speaking ... this needs to be made precise) of the smaller ordinal?" I think the answer to that would depend on what do we mean by a "reasonable sense".
$endgroup$
– SSequence
Dec 20 '18 at 5:30














$begingroup$
@SSequence: but is it always possible to provide a precise description for an arbitrary ordinal using a finite string? For example, what language (and alphabet) would we use to describe this ordinal?
$endgroup$
– lyrically wicked
Dec 20 '18 at 5:34






$begingroup$
@SSequence: but is it always possible to provide a precise description for an arbitrary ordinal using a finite string? For example, what language (and alphabet) would we use to describe this ordinal?
$endgroup$
– lyrically wicked
Dec 20 '18 at 5:34












1 Answer
1






active

oldest

votes


















3












$begingroup$

This is the trichotomy principle (or law of trichotomy, or etc.) for ordinals. It can also be phrased for arbitrary well-orderings, as follows:




For any two well-orderings $A,B$, exactly one of the following situations occurs: $(i)$ there is a non-surjective order-preserving embedding of $A$ into $B$; $(ii)$ there is a non-surjective order-preserving embedding of $B$ into $A$; $(iii)$ there is an order-preserving bijection between $A$ and $B$.




Intuitively, $(i)$ means $A<B$, $(ii)$ means $B<A$, and $(iii)$ means $A=B$. (Exercise: the principle above does in fact imply trichotomy for ordinals as you've phrased it.) Note also that we can replace "embedding" with "initial segment embedding" (= embedding whose image is an initial segment).



You can find proofs of the trichotomy in any decent introductory set theory textbook - for example, it's Theorem $6.3$ in Kunen's book (phrased there in terms of arbitrary well-orderings).



Note that nowhere do we need to assume that the ordinals (or well-orderings) involved are countable; this is a generally, always-applying principle. Also, to forestall a frequent (in my experience) confusion, note that it does not need the axiom of choice (rather, replacement is the key principle).






share|cite|improve this answer











$endgroup$














    Your Answer





    StackExchange.ifUsing("editor", function () {
    return StackExchange.using("mathjaxEditing", function () {
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
    });
    });
    }, "mathjax-editing");

    StackExchange.ready(function() {
    var channelOptions = {
    tags: "".split(" "),
    id: "69"
    };
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function() {
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled) {
    StackExchange.using("snippets", function() {
    createEditor();
    });
    }
    else {
    createEditor();
    }
    });

    function createEditor() {
    StackExchange.prepareEditor({
    heartbeatType: 'answer',
    autoActivateHeartbeat: false,
    convertImagesToLinks: true,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    imageUploader: {
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    },
    noCode: true, onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    });


    }
    });














    draft saved

    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3047151%2fwhat-is-the-name-of-a-theorem-which-says-that-if-alpha-and-beta-are-ordina%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    1 Answer
    1






    active

    oldest

    votes








    1 Answer
    1






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    3












    $begingroup$

    This is the trichotomy principle (or law of trichotomy, or etc.) for ordinals. It can also be phrased for arbitrary well-orderings, as follows:




    For any two well-orderings $A,B$, exactly one of the following situations occurs: $(i)$ there is a non-surjective order-preserving embedding of $A$ into $B$; $(ii)$ there is a non-surjective order-preserving embedding of $B$ into $A$; $(iii)$ there is an order-preserving bijection between $A$ and $B$.




    Intuitively, $(i)$ means $A<B$, $(ii)$ means $B<A$, and $(iii)$ means $A=B$. (Exercise: the principle above does in fact imply trichotomy for ordinals as you've phrased it.) Note also that we can replace "embedding" with "initial segment embedding" (= embedding whose image is an initial segment).



    You can find proofs of the trichotomy in any decent introductory set theory textbook - for example, it's Theorem $6.3$ in Kunen's book (phrased there in terms of arbitrary well-orderings).



    Note that nowhere do we need to assume that the ordinals (or well-orderings) involved are countable; this is a generally, always-applying principle. Also, to forestall a frequent (in my experience) confusion, note that it does not need the axiom of choice (rather, replacement is the key principle).






    share|cite|improve this answer











    $endgroup$


















      3












      $begingroup$

      This is the trichotomy principle (or law of trichotomy, or etc.) for ordinals. It can also be phrased for arbitrary well-orderings, as follows:




      For any two well-orderings $A,B$, exactly one of the following situations occurs: $(i)$ there is a non-surjective order-preserving embedding of $A$ into $B$; $(ii)$ there is a non-surjective order-preserving embedding of $B$ into $A$; $(iii)$ there is an order-preserving bijection between $A$ and $B$.




      Intuitively, $(i)$ means $A<B$, $(ii)$ means $B<A$, and $(iii)$ means $A=B$. (Exercise: the principle above does in fact imply trichotomy for ordinals as you've phrased it.) Note also that we can replace "embedding" with "initial segment embedding" (= embedding whose image is an initial segment).



      You can find proofs of the trichotomy in any decent introductory set theory textbook - for example, it's Theorem $6.3$ in Kunen's book (phrased there in terms of arbitrary well-orderings).



      Note that nowhere do we need to assume that the ordinals (or well-orderings) involved are countable; this is a generally, always-applying principle. Also, to forestall a frequent (in my experience) confusion, note that it does not need the axiom of choice (rather, replacement is the key principle).






      share|cite|improve this answer











      $endgroup$
















        3












        3








        3





        $begingroup$

        This is the trichotomy principle (or law of trichotomy, or etc.) for ordinals. It can also be phrased for arbitrary well-orderings, as follows:




        For any two well-orderings $A,B$, exactly one of the following situations occurs: $(i)$ there is a non-surjective order-preserving embedding of $A$ into $B$; $(ii)$ there is a non-surjective order-preserving embedding of $B$ into $A$; $(iii)$ there is an order-preserving bijection between $A$ and $B$.




        Intuitively, $(i)$ means $A<B$, $(ii)$ means $B<A$, and $(iii)$ means $A=B$. (Exercise: the principle above does in fact imply trichotomy for ordinals as you've phrased it.) Note also that we can replace "embedding" with "initial segment embedding" (= embedding whose image is an initial segment).



        You can find proofs of the trichotomy in any decent introductory set theory textbook - for example, it's Theorem $6.3$ in Kunen's book (phrased there in terms of arbitrary well-orderings).



        Note that nowhere do we need to assume that the ordinals (or well-orderings) involved are countable; this is a generally, always-applying principle. Also, to forestall a frequent (in my experience) confusion, note that it does not need the axiom of choice (rather, replacement is the key principle).






        share|cite|improve this answer











        $endgroup$



        This is the trichotomy principle (or law of trichotomy, or etc.) for ordinals. It can also be phrased for arbitrary well-orderings, as follows:




        For any two well-orderings $A,B$, exactly one of the following situations occurs: $(i)$ there is a non-surjective order-preserving embedding of $A$ into $B$; $(ii)$ there is a non-surjective order-preserving embedding of $B$ into $A$; $(iii)$ there is an order-preserving bijection between $A$ and $B$.




        Intuitively, $(i)$ means $A<B$, $(ii)$ means $B<A$, and $(iii)$ means $A=B$. (Exercise: the principle above does in fact imply trichotomy for ordinals as you've phrased it.) Note also that we can replace "embedding" with "initial segment embedding" (= embedding whose image is an initial segment).



        You can find proofs of the trichotomy in any decent introductory set theory textbook - for example, it's Theorem $6.3$ in Kunen's book (phrased there in terms of arbitrary well-orderings).



        Note that nowhere do we need to assume that the ordinals (or well-orderings) involved are countable; this is a generally, always-applying principle. Also, to forestall a frequent (in my experience) confusion, note that it does not need the axiom of choice (rather, replacement is the key principle).







        share|cite|improve this answer














        share|cite|improve this answer



        share|cite|improve this answer








        edited Dec 23 '18 at 5:13

























        answered Dec 23 '18 at 5:08









        Noah SchweberNoah Schweber

        128k10152294




        128k10152294






























            draft saved

            draft discarded




















































            Thanks for contributing an answer to Mathematics Stack Exchange!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid



            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.


            Use MathJax to format equations. MathJax reference.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3047151%2fwhat-is-the-name-of-a-theorem-which-says-that-if-alpha-and-beta-are-ordina%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            Popular posts from this blog

            Plaza Victoria

            In PowerPoint, is there a keyboard shortcut for bulleted / numbered list?

            How to put 3 figures in Latex with 2 figures side by side and 1 below these side by side images but in...