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

$\endgroup$
  • 1
    $\begingroup$ rd.springer.com/article/10.1007/BF00571186 $\endgroup$ – Asaf Karagila Jan 18 at 15:45
  • 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 Jan 18 at 17:18
  • $\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 Jan 18 at 17:26
  • $\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 Jan 18 at 19:22
10
$\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.

$\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 Jan 18 at 15:32
  • 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 Jan 18 at 17:58
  • 2
    $\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 Jan 18 at 22:27
  • 1
    $\begingroup$ But set-theoreticians, who use the word "tree" to mean well-founded tree, must occasionally have to refer to the more general trees. What do they call them? If I use "tree" to mean a poset in which the predecessors of any element are well-ordered, then what should I call a poset in which the predecessors of any element are linearly ordered? I have some vague recollection of hearing them called "pseudotrees" or something like that. $\endgroup$ – bof Jan 23 at 5:58
  • 2
    $\begingroup$ @bof A colleague pointed me to several set-theory papers by Koppelberg-Monk, Bekkali, and Alos-Ferrer and Ritzberger, where the term pseudotree is used for exactly this kind of poset. $\endgroup$ – Monroe Eskew Jan 24 at 9:36
3
$\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".)

$\endgroup$

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.