Terminology about trees












9












$begingroup$


In set theory, a tree is usually defined as a partial order such that the set of elements below any given one is well-ordered. I am interested in the class of partial orders $P$ such that for every $p in P$, the set of $q leq p$ is just linearly ordered. Does this have a name?










share|cite|improve this question











$endgroup$








  • 1




    $begingroup$
    rd.springer.com/article/10.1007/BF00571186
    $endgroup$
    – Asaf Karagila
    12 hours ago






  • 1




    $begingroup$
    Prefix orders seem to be relevant, if for no other reason than they appear to fit the required definitional niche. See en.m.wikipedia.org/wiki/Prefix_order
    $endgroup$
    – Not Mike
    11 hours ago












  • $begingroup$
    Thanks @NotMike! It's nice to see this coming from outside of pure set theory. Feel free to put this as an answer.
    $endgroup$
    – Monroe Eskew
    11 hours ago










  • $begingroup$
    Adeleke and Neumann have a Memoir of the AMS 'Relations related to betweenness' which considers various structures along these lines. In particular, a partially ordered set satisfying the property above which is also assumed to be connected (every pair of elements has a common lower bound) is called a semilinearly ordered set. I don't know if they have a name for such objects if they're not connected.
    $endgroup$
    – shane.orourke
    9 hours ago
















9












$begingroup$


In set theory, a tree is usually defined as a partial order such that the set of elements below any given one is well-ordered. I am interested in the class of partial orders $P$ such that for every $p in P$, the set of $q leq p$ is just linearly ordered. Does this have a name?










share|cite|improve this question











$endgroup$








  • 1




    $begingroup$
    rd.springer.com/article/10.1007/BF00571186
    $endgroup$
    – Asaf Karagila
    12 hours ago






  • 1




    $begingroup$
    Prefix orders seem to be relevant, if for no other reason than they appear to fit the required definitional niche. See en.m.wikipedia.org/wiki/Prefix_order
    $endgroup$
    – Not Mike
    11 hours ago












  • $begingroup$
    Thanks @NotMike! It's nice to see this coming from outside of pure set theory. Feel free to put this as an answer.
    $endgroup$
    – Monroe Eskew
    11 hours ago










  • $begingroup$
    Adeleke and Neumann have a Memoir of the AMS 'Relations related to betweenness' which considers various structures along these lines. In particular, a partially ordered set satisfying the property above which is also assumed to be connected (every pair of elements has a common lower bound) is called a semilinearly ordered set. I don't know if they have a name for such objects if they're not connected.
    $endgroup$
    – shane.orourke
    9 hours ago














9












9








9


1



$begingroup$


In set theory, a tree is usually defined as a partial order such that the set of elements below any given one is well-ordered. I am interested in the class of partial orders $P$ such that for every $p in P$, the set of $q leq p$ is just linearly ordered. Does this have a name?










share|cite|improve this question











$endgroup$




In set theory, a tree is usually defined as a partial order such that the set of elements below any given one is well-ordered. I am interested in the class of partial orders $P$ such that for every $p in P$, the set of $q leq p$ is just linearly ordered. Does this have a name?







set-theory terminology posets trees






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited 13 hours ago







Monroe Eskew

















asked 15 hours ago









Monroe EskewMonroe Eskew

7,64512157




7,64512157








  • 1




    $begingroup$
    rd.springer.com/article/10.1007/BF00571186
    $endgroup$
    – Asaf Karagila
    12 hours ago






  • 1




    $begingroup$
    Prefix orders seem to be relevant, if for no other reason than they appear to fit the required definitional niche. See en.m.wikipedia.org/wiki/Prefix_order
    $endgroup$
    – Not Mike
    11 hours ago












  • $begingroup$
    Thanks @NotMike! It's nice to see this coming from outside of pure set theory. Feel free to put this as an answer.
    $endgroup$
    – Monroe Eskew
    11 hours ago










  • $begingroup$
    Adeleke and Neumann have a Memoir of the AMS 'Relations related to betweenness' which considers various structures along these lines. In particular, a partially ordered set satisfying the property above which is also assumed to be connected (every pair of elements has a common lower bound) is called a semilinearly ordered set. I don't know if they have a name for such objects if they're not connected.
    $endgroup$
    – shane.orourke
    9 hours ago














  • 1




    $begingroup$
    rd.springer.com/article/10.1007/BF00571186
    $endgroup$
    – Asaf Karagila
    12 hours ago






  • 1




    $begingroup$
    Prefix orders seem to be relevant, if for no other reason than they appear to fit the required definitional niche. See en.m.wikipedia.org/wiki/Prefix_order
    $endgroup$
    – Not Mike
    11 hours ago












  • $begingroup$
    Thanks @NotMike! It's nice to see this coming from outside of pure set theory. Feel free to put this as an answer.
    $endgroup$
    – Monroe Eskew
    11 hours ago










  • $begingroup$
    Adeleke and Neumann have a Memoir of the AMS 'Relations related to betweenness' which considers various structures along these lines. In particular, a partially ordered set satisfying the property above which is also assumed to be connected (every pair of elements has a common lower bound) is called a semilinearly ordered set. I don't know if they have a name for such objects if they're not connected.
    $endgroup$
    – shane.orourke
    9 hours ago








1




1




$begingroup$
rd.springer.com/article/10.1007/BF00571186
$endgroup$
– Asaf Karagila
12 hours ago




$begingroup$
rd.springer.com/article/10.1007/BF00571186
$endgroup$
– Asaf Karagila
12 hours ago




1




1




$begingroup$
Prefix orders seem to be relevant, if for no other reason than they appear to fit the required definitional niche. See en.m.wikipedia.org/wiki/Prefix_order
$endgroup$
– Not Mike
11 hours ago






$begingroup$
Prefix orders seem to be relevant, if for no other reason than they appear to fit the required definitional niche. See en.m.wikipedia.org/wiki/Prefix_order
$endgroup$
– Not Mike
11 hours ago














$begingroup$
Thanks @NotMike! It's nice to see this coming from outside of pure set theory. Feel free to put this as an answer.
$endgroup$
– Monroe Eskew
11 hours ago




$begingroup$
Thanks @NotMike! It's nice to see this coming from outside of pure set theory. Feel free to put this as an answer.
$endgroup$
– Monroe Eskew
11 hours ago












$begingroup$
Adeleke and Neumann have a Memoir of the AMS 'Relations related to betweenness' which considers various structures along these lines. In particular, a partially ordered set satisfying the property above which is also assumed to be connected (every pair of elements has a common lower bound) is called a semilinearly ordered set. I don't know if they have a name for such objects if they're not connected.
$endgroup$
– shane.orourke
9 hours ago




$begingroup$
Adeleke and Neumann have a Memoir of the AMS 'Relations related to betweenness' which considers various structures along these lines. In particular, a partially ordered set satisfying the property above which is also assumed to be connected (every pair of elements has a common lower bound) is called a semilinearly ordered set. I don't know if they have a name for such objects if they're not connected.
$endgroup$
– shane.orourke
9 hours ago










2 Answers
2






active

oldest

votes


















9












$begingroup$

They are also called trees.



In that terminology, trees of your first kind are known as the well-founded trees, since they are trees where the tree order is well-founded (and well-founded linear orders are the same as well-orders).



I think that the situation is that because set theorists are mainly interested in the well-founded case, the terminology evolved to drop the adjective from well-founded trees.



There are many competing definitions of tree in mathematics, not all equivalent. For graph-theorists, for example, a tree is a certain kind of cycle-free graph.






share|cite|improve this answer









$endgroup$









  • 1




    $begingroup$
    This is also what I thought off the top of my head, but Jech, Kunen, and Kanamori all put well-foundedness into the definition of a tree. Do you know of a reference the defines trees as the more general class?
    $endgroup$
    – Monroe Eskew
    13 hours ago










  • $begingroup$
    Well, those are all set theory references, and so they use the set theory convention, which as we said is focused on the well-founded case. I've seen the linearly ordered version sometimes in talks, but I don't know a specific reference. And in truth, I think that the non-well-founded tree case is simply much less studied. For finite trees, however, saying linear is enough (for every finite order is well-founded), and one can definitely find that.
    $endgroup$
    – Joel David Hamkins
    11 hours ago






  • 1




    $begingroup$
    I guess the complication also is that "well-founded tree" now means something else in set theory, where the tree is growing downward and has no infinite branches.
    $endgroup$
    – Joel David Hamkins
    10 hours ago










  • $begingroup$
    For one reference: Keisler uses the linear order definition in his article "Models with tree structures". Full citation: H. Jerome Keisler. “Models with tree structures”. In: Proceedings of the Tarski Symposium (Proc. Sympos. Pure Math., Vol. XXV, Univ. California, Berkeley, Calif., 1971) . Amer. Math. Soc., Providence, R.I., 1974, pp. 331–348.
    $endgroup$
    – Kameryn Williams
    6 hours ago





















2












$begingroup$

Upgraded from a comment:



After a little bit of searching, the notion of prefix order seems to be relevant; if for no other reason than that it appears to fit the required definitional niche.



(Also, it seemed worth pointing out the notion of prefix-order is precisely that of a "first-order tree".)






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: "504"
    };
    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%2fmathoverflow.net%2fquestions%2f321178%2fterminology-about-trees%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    2 Answers
    2






    active

    oldest

    votes








    2 Answers
    2






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    9












    $begingroup$

    They are also called trees.



    In that terminology, trees of your first kind are known as the well-founded trees, since they are trees where the tree order is well-founded (and well-founded linear orders are the same as well-orders).



    I think that the situation is that because set theorists are mainly interested in the well-founded case, the terminology evolved to drop the adjective from well-founded trees.



    There are many competing definitions of tree in mathematics, not all equivalent. For graph-theorists, for example, a tree is a certain kind of cycle-free graph.






    share|cite|improve this answer









    $endgroup$









    • 1




      $begingroup$
      This is also what I thought off the top of my head, but Jech, Kunen, and Kanamori all put well-foundedness into the definition of a tree. Do you know of a reference the defines trees as the more general class?
      $endgroup$
      – Monroe Eskew
      13 hours ago










    • $begingroup$
      Well, those are all set theory references, and so they use the set theory convention, which as we said is focused on the well-founded case. I've seen the linearly ordered version sometimes in talks, but I don't know a specific reference. And in truth, I think that the non-well-founded tree case is simply much less studied. For finite trees, however, saying linear is enough (for every finite order is well-founded), and one can definitely find that.
      $endgroup$
      – Joel David Hamkins
      11 hours ago






    • 1




      $begingroup$
      I guess the complication also is that "well-founded tree" now means something else in set theory, where the tree is growing downward and has no infinite branches.
      $endgroup$
      – Joel David Hamkins
      10 hours ago










    • $begingroup$
      For one reference: Keisler uses the linear order definition in his article "Models with tree structures". Full citation: H. Jerome Keisler. “Models with tree structures”. In: Proceedings of the Tarski Symposium (Proc. Sympos. Pure Math., Vol. XXV, Univ. California, Berkeley, Calif., 1971) . Amer. Math. Soc., Providence, R.I., 1974, pp. 331–348.
      $endgroup$
      – Kameryn Williams
      6 hours ago


















    9












    $begingroup$

    They are also called trees.



    In that terminology, trees of your first kind are known as the well-founded trees, since they are trees where the tree order is well-founded (and well-founded linear orders are the same as well-orders).



    I think that the situation is that because set theorists are mainly interested in the well-founded case, the terminology evolved to drop the adjective from well-founded trees.



    There are many competing definitions of tree in mathematics, not all equivalent. For graph-theorists, for example, a tree is a certain kind of cycle-free graph.






    share|cite|improve this answer









    $endgroup$









    • 1




      $begingroup$
      This is also what I thought off the top of my head, but Jech, Kunen, and Kanamori all put well-foundedness into the definition of a tree. Do you know of a reference the defines trees as the more general class?
      $endgroup$
      – Monroe Eskew
      13 hours ago










    • $begingroup$
      Well, those are all set theory references, and so they use the set theory convention, which as we said is focused on the well-founded case. I've seen the linearly ordered version sometimes in talks, but I don't know a specific reference. And in truth, I think that the non-well-founded tree case is simply much less studied. For finite trees, however, saying linear is enough (for every finite order is well-founded), and one can definitely find that.
      $endgroup$
      – Joel David Hamkins
      11 hours ago






    • 1




      $begingroup$
      I guess the complication also is that "well-founded tree" now means something else in set theory, where the tree is growing downward and has no infinite branches.
      $endgroup$
      – Joel David Hamkins
      10 hours ago










    • $begingroup$
      For one reference: Keisler uses the linear order definition in his article "Models with tree structures". Full citation: H. Jerome Keisler. “Models with tree structures”. In: Proceedings of the Tarski Symposium (Proc. Sympos. Pure Math., Vol. XXV, Univ. California, Berkeley, Calif., 1971) . Amer. Math. Soc., Providence, R.I., 1974, pp. 331–348.
      $endgroup$
      – Kameryn Williams
      6 hours ago
















    9












    9








    9





    $begingroup$

    They are also called trees.



    In that terminology, trees of your first kind are known as the well-founded trees, since they are trees where the tree order is well-founded (and well-founded linear orders are the same as well-orders).



    I think that the situation is that because set theorists are mainly interested in the well-founded case, the terminology evolved to drop the adjective from well-founded trees.



    There are many competing definitions of tree in mathematics, not all equivalent. For graph-theorists, for example, a tree is a certain kind of cycle-free graph.






    share|cite|improve this answer









    $endgroup$



    They are also called trees.



    In that terminology, trees of your first kind are known as the well-founded trees, since they are trees where the tree order is well-founded (and well-founded linear orders are the same as well-orders).



    I think that the situation is that because set theorists are mainly interested in the well-founded case, the terminology evolved to drop the adjective from well-founded trees.



    There are many competing definitions of tree in mathematics, not all equivalent. For graph-theorists, for example, a tree is a certain kind of cycle-free graph.







    share|cite|improve this answer












    share|cite|improve this answer



    share|cite|improve this answer










    answered 15 hours ago









    Joel David HamkinsJoel David Hamkins

    164k25502869




    164k25502869








    • 1




      $begingroup$
      This is also what I thought off the top of my head, but Jech, Kunen, and Kanamori all put well-foundedness into the definition of a tree. Do you know of a reference the defines trees as the more general class?
      $endgroup$
      – Monroe Eskew
      13 hours ago










    • $begingroup$
      Well, those are all set theory references, and so they use the set theory convention, which as we said is focused on the well-founded case. I've seen the linearly ordered version sometimes in talks, but I don't know a specific reference. And in truth, I think that the non-well-founded tree case is simply much less studied. For finite trees, however, saying linear is enough (for every finite order is well-founded), and one can definitely find that.
      $endgroup$
      – Joel David Hamkins
      11 hours ago






    • 1




      $begingroup$
      I guess the complication also is that "well-founded tree" now means something else in set theory, where the tree is growing downward and has no infinite branches.
      $endgroup$
      – Joel David Hamkins
      10 hours ago










    • $begingroup$
      For one reference: Keisler uses the linear order definition in his article "Models with tree structures". Full citation: H. Jerome Keisler. “Models with tree structures”. In: Proceedings of the Tarski Symposium (Proc. Sympos. Pure Math., Vol. XXV, Univ. California, Berkeley, Calif., 1971) . Amer. Math. Soc., Providence, R.I., 1974, pp. 331–348.
      $endgroup$
      – Kameryn Williams
      6 hours ago
















    • 1




      $begingroup$
      This is also what I thought off the top of my head, but Jech, Kunen, and Kanamori all put well-foundedness into the definition of a tree. Do you know of a reference the defines trees as the more general class?
      $endgroup$
      – Monroe Eskew
      13 hours ago










    • $begingroup$
      Well, those are all set theory references, and so they use the set theory convention, which as we said is focused on the well-founded case. I've seen the linearly ordered version sometimes in talks, but I don't know a specific reference. And in truth, I think that the non-well-founded tree case is simply much less studied. For finite trees, however, saying linear is enough (for every finite order is well-founded), and one can definitely find that.
      $endgroup$
      – Joel David Hamkins
      11 hours ago






    • 1




      $begingroup$
      I guess the complication also is that "well-founded tree" now means something else in set theory, where the tree is growing downward and has no infinite branches.
      $endgroup$
      – Joel David Hamkins
      10 hours ago










    • $begingroup$
      For one reference: Keisler uses the linear order definition in his article "Models with tree structures". Full citation: H. Jerome Keisler. “Models with tree structures”. In: Proceedings of the Tarski Symposium (Proc. Sympos. Pure Math., Vol. XXV, Univ. California, Berkeley, Calif., 1971) . Amer. Math. Soc., Providence, R.I., 1974, pp. 331–348.
      $endgroup$
      – Kameryn Williams
      6 hours ago










    1




    1




    $begingroup$
    This is also what I thought off the top of my head, but Jech, Kunen, and Kanamori all put well-foundedness into the definition of a tree. Do you know of a reference the defines trees as the more general class?
    $endgroup$
    – Monroe Eskew
    13 hours ago




    $begingroup$
    This is also what I thought off the top of my head, but Jech, Kunen, and Kanamori all put well-foundedness into the definition of a tree. Do you know of a reference the defines trees as the more general class?
    $endgroup$
    – Monroe Eskew
    13 hours ago












    $begingroup$
    Well, those are all set theory references, and so they use the set theory convention, which as we said is focused on the well-founded case. I've seen the linearly ordered version sometimes in talks, but I don't know a specific reference. And in truth, I think that the non-well-founded tree case is simply much less studied. For finite trees, however, saying linear is enough (for every finite order is well-founded), and one can definitely find that.
    $endgroup$
    – Joel David Hamkins
    11 hours ago




    $begingroup$
    Well, those are all set theory references, and so they use the set theory convention, which as we said is focused on the well-founded case. I've seen the linearly ordered version sometimes in talks, but I don't know a specific reference. And in truth, I think that the non-well-founded tree case is simply much less studied. For finite trees, however, saying linear is enough (for every finite order is well-founded), and one can definitely find that.
    $endgroup$
    – Joel David Hamkins
    11 hours ago




    1




    1




    $begingroup$
    I guess the complication also is that "well-founded tree" now means something else in set theory, where the tree is growing downward and has no infinite branches.
    $endgroup$
    – Joel David Hamkins
    10 hours ago




    $begingroup$
    I guess the complication also is that "well-founded tree" now means something else in set theory, where the tree is growing downward and has no infinite branches.
    $endgroup$
    – Joel David Hamkins
    10 hours ago












    $begingroup$
    For one reference: Keisler uses the linear order definition in his article "Models with tree structures". Full citation: H. Jerome Keisler. “Models with tree structures”. In: Proceedings of the Tarski Symposium (Proc. Sympos. Pure Math., Vol. XXV, Univ. California, Berkeley, Calif., 1971) . Amer. Math. Soc., Providence, R.I., 1974, pp. 331–348.
    $endgroup$
    – Kameryn Williams
    6 hours ago






    $begingroup$
    For one reference: Keisler uses the linear order definition in his article "Models with tree structures". Full citation: H. Jerome Keisler. “Models with tree structures”. In: Proceedings of the Tarski Symposium (Proc. Sympos. Pure Math., Vol. XXV, Univ. California, Berkeley, Calif., 1971) . Amer. Math. Soc., Providence, R.I., 1974, pp. 331–348.
    $endgroup$
    – Kameryn Williams
    6 hours ago













    2












    $begingroup$

    Upgraded from a comment:



    After a little bit of searching, the notion of prefix order seems to be relevant; if for no other reason than that it appears to fit the required definitional niche.



    (Also, it seemed worth pointing out the notion of prefix-order is precisely that of a "first-order tree".)






    share|cite|improve this answer









    $endgroup$


















      2












      $begingroup$

      Upgraded from a comment:



      After a little bit of searching, the notion of prefix order seems to be relevant; if for no other reason than that it appears to fit the required definitional niche.



      (Also, it seemed worth pointing out the notion of prefix-order is precisely that of a "first-order tree".)






      share|cite|improve this answer









      $endgroup$
















        2












        2








        2





        $begingroup$

        Upgraded from a comment:



        After a little bit of searching, the notion of prefix order seems to be relevant; if for no other reason than that it appears to fit the required definitional niche.



        (Also, it seemed worth pointing out the notion of prefix-order is precisely that of a "first-order tree".)






        share|cite|improve this answer









        $endgroup$



        Upgraded from a comment:



        After a little bit of searching, the notion of prefix order seems to be relevant; if for no other reason than that it appears to fit the required definitional niche.



        (Also, it seemed worth pointing out the notion of prefix-order is precisely that of a "first-order tree".)







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered 9 hours ago









        Not MikeNot Mike

        1,3551528




        1,3551528






























            draft saved

            draft discarded




















































            Thanks for contributing an answer to MathOverflow!


            • 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%2fmathoverflow.net%2fquestions%2f321178%2fterminology-about-trees%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

            How to label and detect the document text images

            Vallis Paradisi

            Tabula Rosettana