The reason why a tree is ... a tree.

   Introduction: We are familiar with the definition of a tree in graph theory. Meanwhile, in set theory, the term tree also refers to a (partially ordered) set that satisfies certain conditions. In this post, I will try to relate these two definitions of tree. 

1. What is a tree in set theory? 

   Since a graph-theoretic tree is very familiar, I will start with a set-theoretic tree. First, the preliminaries will be recalled. A partial order  on a set S is a relation <= such that: 

   - a <= a for all a belonging to S (reflexive). 

   - If a, b are elements of S and a <= b, b <= a, then a = b (antisymmetric). 

   - If a, b, c are elements of S and a <= b, b <= c, then a <= c (transitive). 

   If a <= b and a is not equal to b, we might say that a is strictly smaller than b, denoted by a < b. If for any two different elements a, b of S, there is an element that is strictly than the other one, we say that the set is totally ordered by the relation <=. For each element a of S, we denote by S(a) the set of all elements of S that is strictly smaller than a. 

   A set S equipped with a partial order <= is called a tree if it has a smallest element M (i.e. M is strictly smaller than any other element of S) and for every a in S, S(a) is totally ordered by the relation <=. The smallest element M is also called the root of the tree. 

2. The equivalence between a tree in set theory and a tree in graph theory in discrete case

   For simplicity, we assume that the set S is finite.  We construct the following directed graph G(S) = (V, E), where V = S and there is a directed arc from u to v (u, v are elements of S) if and only if u is strictly smaller than v and there isn't an element w of S such that u is strictly smaller than w and w is strictly smaller than v. For example, if S is the set of integers and we consider the usual relation <=, then every edge/arc in E goes from n to n + 1 for some integer n. 

   Recall that an underlying graph of a directed graph is an undirected graph on the same set of vertices such that two vertices are adjacent in the undirected graph if and only if there is an arc from a vertex to the other one in the corresponding directed graph. Below is an illustrative example. 

   Proposition 1. The underlying graph of the graph G(S) is a tree. 

   Proof. Let v(0) be the vertex representing the smallest element of S. For any vertex v other than v(0), v(0) is strictly smaller than v. Consider the increasing sequence v(0) < v. If there isn't any element between v(0) and v, by our construction, there is an arc from v(0) to v. Otherwise, we can find an element u such that v(0) < u < v. With this new sequence, we again consider whether an element can be inserted between two consecutive terms of this sequence. The output of this process is a sequence in which two consecutive terms are connected by an arc from the smaller term to the larger term. Since S is finite, the process must terminate, which means that there is always a directed path from v(0) to v. 

   As a result, the underlying graph of G(S) contains a path from v(0) to v (and conversely, from v to v(0)). For any two vertices v, u, there is a path from. v to v(0) and a path from v(0) to u. The concatenation of these two paths is a path from v to u, thus G(S) is connected (1). 

   Assume, for the sake of contradiction, that G(S) contains a cycle with n vertices v(1), v(2), ..., v(n). Among the vertices v(1), v(2), ..., v(n), there must be an element that is not strictly smaller than any other element. Without loss of generosity, assume that v(n) is a such element. Since v(1) and v(n - 1) are adjacent to v(n), they must be strictly smaller than v(n). In other words, they belong to S(v(n)). By the definition of a set-theoretic tree, S(v(n)) is totally ordered and either v(1) < v(n - 1) or v(n - 1) or v(1). 

   * If v(1) < v(n - 1) < v(n), by our construction, v(1) is not adjacent to v(n), a contradiction. 

   * If v(n - 1) < v(1) < v(n), similarly as above, v(n - 1) is also not adjacent to v(n), a contradiction. 

   Therefore, our assumption is wrong and G(S) doesn't contain any cycle (2). 

   By (1) and (2), G(S) is a tree.

   Conversely, a set-theoretic tree can also be constructed from a graph-theoretic tree T = (V, E) as follows. First, pick an arbitrary vertex v(0) in V and select v(0) as the root of the tree T. Note that the set-theoretic structure depends on v(0), thus there might be different such structures arising from the same tree T. Consider the following order <= on V: u <= v if and only if the (unique) path from v(0) to v goes through u. This order obviously satisfies reflexitivity and antisymmetry. To prove the transitivity, assume that v <= u <= w. Since the path from v(0) to w goes through u, it must also contain the path from v(0) to u. As a result, the path from v(0) to w also goes to v, which yields v < w. 

   Proposition 2. The vertex set V, equipped with the order <=, is a (set-theoretic) tree. 

   Proof. For each vertex v, the set S(v) consists of all elements (other than v) that are in the (unique) path from v(0) to v. Let the path be v(0) -> v(1) -> ... -> v(n) = v. For any two different vertices v(i), v(j) in this path (0 <= i, j < n), 

   * If i < j => v(i) < v(j)

   * If i > j => v(i) > v(j)

   Therefore, S(v) is totally ordered and V is a (set-theoretic) tree.

   Remark. (Added on April 5, 2025) The same idea can be used to explain the geometric meaning behind the term "linear order". Again, we consider a finite set S and the directed graph G(S) in which there is an edge from u to v if and only if u < v and there is no w such that u < w < v. In this case, G(S) is a path and, as a result, can be embedded in a line. It is obvious that this embedding is possible if and only if the total on S is linear or total. 

3. An example in which the construction fails due to the "denseness" of the set

   The above arguments only consider finite (set-theoretic) trees. In fact, the construction of G(S) mentioned above might fail if the set S is not assumed to be finite, since S might be too "dense" that there is always an element between two arbitrary element. 

   Example: The set Q of rational numbers, equipped with the usual order, is indeed a tree. However, if we repeat our construction of G(S) in section 2, the output is an edgeless graph on Q. Indeed, for every two rational numbers a < b, there is always a rational number c satisfying a < c < b since Q is dense. As a result, there isn't any arc from a to b and the graph, unfortunately, has no edge/arc.