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?
$\begingroup$
$\endgroup$
4
asked Jan 18, 2019 at 12:42
-
1$\begingroup$ rd.springer.com/article/10.1007/BF00571186 $\endgroup$– Asaf Karagila ♦Commented Jan 18, 2019 at 15:45
-
3$\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 MikeCommented Jan 18, 2019 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 EskewCommented Jan 18, 2019 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.orourkeCommented Jan 18, 2019 at 19:22
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
8
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.
answered Jan 18, 2019 at 13:26
-
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$ Commented Jan 18, 2019 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$ Commented Jan 18, 2019 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$ Commented Jan 18, 2019 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$– bofCommented Jan 23, 2019 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$ Commented Jan 24, 2019 at 9:36
$\begingroup$
$\endgroup$
0
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".)
