Talk:Tree (set theory)

Untitled

Why is this page called infinite tree, when the given definition does not require the tree to be infinite? A better name might be "Tree (set theory)" or "Rooted tree (graph theory)" -- the latter to distinguish from the existing article "Tree (graph theory)", which refers to trees without distinguished roots.

Once a final name is picked, the link should be placed on "Tree (disambiguation)" as well.--Trovatore 16:15, 11 July 2005 (UTC)

---

On reflection I think my vote is "Tree (set theory)", as long as the "See also" to "Tree (descriptive set theory)" is kept. "Rooted tree (graph theory)" is kind of ugly and, more to the point, is not what people usually say, except in the unusual circumstance that they have to make the distinction with unrooted trees.

An alternative possibility would be a merge with Tree (graph theory), but the uses of the two sorts of trees are so distinct that I doubt that's a good idea. Also, while I don't know much about graph theory, I don't really think graph theorists are all that interested in infinite rooted trees; it's really more of a set theory concept, which my proposed name reflects. --Trovatore 16:45, 11 July 2005 (UTC)

---

Oops. Set-theoretic trees don't have to be graph-theoretic trees at all. My comments about rooted and unrooted were more appropriate to descriptive-set-theoretic trees, which do have a graph-theoretic tree structure plus a distinguished root. I'll have to think about how/whether to say that on the tree (descriptive set theory) page.

Still, this is if anything a better reason than before for the move to "Tree (set theory)", since "Infinite tree (graph theory)" is even more clearly an inaccurate description. --Trovatore 06:29, 12 July 2005 (UTC)

(Formerly) Disputed

Well, "disputed" might be too strong a word, but that's what the template wants. I'm concerned that the given definition for "branch" doesn't require it to be downward-closed, which I would think is intuitively a requirement. Of course I'm more used to descriptive-set-theoretic trees. Are there any infinitary combinitorists who can weigh in on whether a "branch" is necessarily downward-closed? --Trovatore 23:58, 12 July 2005 (UTC)

Actually, more than downward closed. I think a branch should be a maximal totally ordered chain -- that is, it should not be possible to add another element of the tree to the branch without violating total orderedness. But I'm not sure--Kunen doesn't actually define "branch" in this context, as far as I can tell. --Trovatore 00:11, 13 July 2005 (UTC)

OK, I found the def in Jech. A branch is a maximal totally ordered subset of the tree. Removed {{dubious}} tag. --Trovatore 02:32, 13 July 2005 (UTC)

Definition of "height"

The page says

The height of a tree is the least ordinal α such that any branch has length at most α. If we have an element x of our tree and the well ordered section of the tree smaller than it is order isomorphic to α then we say x has height α.

This is equivalent to the definition in Kunen, but it takes a little thought to be sure of that. I think I'd prefer the following:

The height of an element x of a tree T is the ordinal isomorphic to the collection of all elements of T that are less than x in the tree ordering. The height of a tree is the least ordinal α such that no element of the tree has height α

I'll look at it here and reflect before making the edit in the actual article. --Trovatore 00:58, 14 July 2005 (UTC)

The use of greek ε for set membership

Is there a reason the introduction for the article uses ε instead of $\in$? This way, the text is very hard to read and understand. Since I'm a newbie here on Wikipedia, I don't know if there is any precendent regarding the use of set membership operator in introductory text, but I would definitely vote for a change.

Avakar 13:43, 7 December 2006 (UTC)

Complex math deserves a hug

Yes, I hug ALL types of trees.Notorious Tree Hugger Phinneas J. Hippy 01:54, 7 October 2007 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified 3 external links on Tree (set theory). Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit User:Cyberpower678/FaQs#InternetArchiveBot*this simple FaQ for additional information. I made the following changes:

• Added archive http://web.archive.org/web/20070930230404/http://planetmath.org/encyclopedia/TreeSetTheoretic.html to http://planetmath.org/encyclopedia/TreeSetTheoretic.html
• Added archive http://web.archive.org/web/20070712031425/http://planetmath.org/encyclopedia/Branch.html to http://planetmath.org/encyclopedia/Branch.html
• Added archive http://web.archive.org/web/20070930231713/http://planetmath.org/encyclopedia/ExampleOfTreeSetTheoretic.htm to http://planetmath.org/encyclopedia/ExampleOfTreeSetTheoretic.htm

When you have finished reviewing my changes, please set the checked parameter below to true or failed to let others know (documentation at {{Sourcecheck}}).

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 18 January 2022).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—^{cyberbot II}_{Talk to my owner:Online} 19:40, 2 June 2016 (UTC)

Contrary to the merging with Tree_(descriptive_set_theory).

Of course, parts of the pages overlap, but the notion of a tree in general set theory bears significance also in other contexts, eg, a definition of weakly compact cardinals. Paolo Lipparini (talk) 23:22, 24 August 2017 (UTC)

Infinite binary tree

@User:David Eppstein, about File:Infinite Binary Tree.gif The elements are all the nodes of the tree. They are partially ordered. For two nodes x and y, x<y if x and y are on the same branch and x is below y. Isn't it right? (I'm not an expert in this field). TD (talk) 01:11, 27 August 2023 (UTC)

Is it a picture of a set-theoretic tree? Does it accurately depict the important distinction between set-theoretic trees and graph-theoretic infinite trees, that the nodes are related by ancestor-descendant and not by edges (because edge-to-edge connection may not be possible when the total orderings of ancestors and descendants are more complicated than the ordering of an integer sequence)? What is the significance of being "binary", in the context of a set-theoretic tree? How is a binary set-theoretic tree even defined, and is it studied in the literature? And what are "nodes" in the context of the picture? I see only line segments; there are no nodes depicted. —David Eppstein (talk) 01:19, 27 August 2023 (UTC)

The nodes are the points where two branches begin. Binary means that there are always two branches from a node. I'm sorry but I'm not familiar with this field, and its terminology. It looks like a tree. That's all I know. If you think this example should be elsewhere in Wikipedia, please inform me.TD (talk) 01:33, 27 August 2023 (UTC)

Your new caption makes it clear that you have failed to understand the point of this article. Your caption describes two nodes as being one less than the other only when they "are on the same branch", and the earlier text of the caption makes clear that you intend "branch" to mean the line segment between two nodes. That is a graph-theoretic tree. In set-theoretic trees, there are no edges and is not always possible to reach the root by stepping from elements to their parents; indeed, an element might not have a parent. For instance, the set of numbers $x-{\tfrac {1}{y}}$ for positive integer $x$ and $y$, ordered numerically, forms a set-theoretic tree (rooted at $0=1-{\tfrac {1}{1}}$, with a single linear order of its elements) but $1$ has no parent: all the numbers $1-{\tfrac {1}{2}},1-{\tfrac {1}{3}},1-{\tfrac {1}{4}},\dots$ are ancestors but none of them is directly connected to $1$.

By using an illustration that does not depict this crucial aspect of this topic, the primary difference between this kind of trees from graph-theoretic trees, you mislead the readers.

Further, the less-than relation you describe is not a total order, because a total order should obey the transitive law and the relation you describe does not. Further, you have failed to properly address my question: is there a definition of "binary tree" that applies to set theoretic trees that are not graphs? What does "two branches from each node" mean in a structure that is not based on direct connections between nodes? For instance, if I linearly ordered the positive integers, and then added countably many "leaf" elements, each of which is above all the integers but incomparable to all the other leaves, would that obey your definition? It is not very binary but each non-leaf element has only one other element for which it is the parent. —David Eppstein (talk) 04:27, 27 August 2023 (UTC)

A branch is not only a line between two successive nodes, but also any succession of nodes such that one is always below the next. With this interpretation, x<y is transitive. This tree is only a simple example. It doesn't pretend to do the impossible, illustrate the definition of a tree in its full generality. Of course there are partial well-orderings such that the order can't be defined by a connected line. Your last example is a binary tree. TD (talk) 09:01, 27 August 2023 (UTC)

For now, it should easily be possible to obtain a fairly nontrivial example by stacking two copies of the current image one upon the other, connecting the root of the upper tree to e.g. the end of the leftmost branch of the lower tree. The leftmost branch of the composed tree would correspond to order type $\omega +\omega$. By stacking $\omega$ trees one upon the other in a similar way, an example with the leftmost branch corresponding to order type $\omega \cdot \omega$ could be generated. However, I feel that a precise mathematical definition of the depicted tree should be given in the caption, or at least somewhere in the article. - Jochen Burghardt (talk) 11:32, 27 August 2023 (UTC)

Thanks for your examples. A precise mathematical definition can't be given in the caption, because it would be too long. I think about giving it in the article, but since I'm not an expert in this field, it's a difficult task for me. I will try.TD (talk) 12:01, 27 August 2023 (UTC)

The Python file which generated this image is here.TD (talk) 12:35, 27 August 2023 (UTC)

The point is, this image DOES NOT ILLUSTRATE THE CONCEPT OF A SET-THEORETIC TREE. It illustrates the concept of a graph-theoretic tree. As such it is a bad image for this article. Please remove it. —David Eppstein (talk) 15:03, 27 August 2023 (UTC)

An ordered tree in graph theory is also a set-theoretic tree. Set-theoretic trees are more general than ordered trees in graph theory, but this is not a reason to exclude this example from this page. It's only a simple example, it gives insight into the concept of a set-theoretic tree. TD (talk) 15:31, 27 August 2023 (UTC)

It misleads readers into a false understanding of the concept. —David Eppstein (talk) 15:36, 27 August 2023 (UTC)

Why? TD (talk) 15:38, 27 August 2023 (UTC)

By analogy: In the article real number, you wouldn't write "For example, 1, 2, 3, ... are real numbers". The sentence is true, but is far from illustrating the whole extension of the concept. - Jochen Burghardt (talk) 16:11, 27 August 2023 (UTC)

This tree is a clear illustration of the concept of partial ordering, which is essential to the concept of tree. I agree that its well-ordering is trivial. So we need more examples, not less. Your examples are very good ones. TD (talk) 16:55, 27 August 2023 (UTC)

It is not clear even as an example of a partial ordering, first because of the same issue (partial orders do not require any concept of edges; consider the partial order on the real numbers) and second because the illustration is not drawn in a way that makes clear what the elements being ordered are. Also what are the colors supposed to mean? —David Eppstein (talk) 19:55, 27 August 2023 (UTC)

The colors mean nothing. I don't understand why you think this illustration is not clear. We see the branches, hence we see the order. The tree shows clearly the difference between a partial order and a total one: for nodes x and y, x<y or x>y or x=y is not always true. The ordinary order on the real line is total, what is the partial order you mention?

I have a reason to make use of two colors. There is a bijection between the set of infinite branches from the root in this tree and the set of sets of natural numbers. Without the two colors, or the left-right relation, I need the axiom of choice to explain this point.TD (talk) 20:53, 27 August 2023 (UTC)

A total order is an example of a partial order. It is equally good and equally bad as an example of a partial order to your examples: it illustrates some aspects of the subject but misses its generality. (The positive real number line is not however a tree in the sense described here because it is not a well order.)

Also, you keep talking about "branches". This is not a concept that has meaning for set-theoretic trees. —David Eppstein (talk) 21:21, 27 August 2023 (UTC)

Read the present article (Tree(set theory)): "a branch of a tree is a maximal chain in the tree" in the definition section. My intuitive use of the concept of branch was not in agreement with this definition.TD (talk) 21:58, 27 August 2023 (UTC)

I uploaded at File:2 Stacked infinite binary trees.png an experimental version with 2 stacked copies of TD's tree, aligned along the rightmost path. The resulting set-theoretic tree has a rightmost branch of length $\omega \cdot 2$. (File:6 Stacked infinite binary trees.png shows 6 similarly stacked trees, but the image is too large for an article.) If this example would be acceptable for now, I'd try to come up with a mathematical definition for it. - Jochen Burghardt (talk) 16:51, 27 August 2023 (UTC)

A precise mathematical definition of this tree: an initial segment of the set of natural numbers is the set of all natural numbers n such that n<N for a natural number N. A finite sequence of binary digits is a map from an initial segment of natural numbers to the set {0,1}. An ordering can be defined on the set T of all finite sequences of binary digits: x<=y if and only if x(n)=y(n) for all n in the domain of x. T is a (set-theoretic) tree for this ordering. The root of the tree is the map [] whose domain is the null set {}. [0] (the map x whose domain is {0} such that x(0)=0) and [1] are the next nodes. [00] (the map y whose domain is {0,1} such that y(0)=0 and y(1)=0), [01], [10] and [11] follow, and so on. My image is a visualization of T. TD (talk) 00:46, 28 August 2023 (UTC)

@Thierry Dugnolle: I reverted your addition of the above since (1) your definition of <= seems flawed, (2) disallowing infinite sequences make your example even more trivial as an example of set-theoretic tree, and (3) I'd prefer to settle the dispute here before adding new material. - Jochen Burghardt (talk) 08:05, 28 August 2023 (UTC)

@Jochen Burghardt where is the flaw? if the domain of y is larger then the domain of x we can't have both x<=y and y<=x because there is at least an n such that y(n) exists and x(n) doesn't exist.TD (talk) 08:03, 28 August 2023 (UTC)

You didn't require the domain of y to be larger than that of x. - Jochen Burghardt (talk) 08:07, 28 August 2023 (UTC)

I didn't have to. If the domain of y is larger than the domain of x, we can't have y<=x with the present definition. TD (talk) 08:09, 28 August 2023 (UTC)

Why not first construct a good example on the talk page, and then publish it? - Jochen Burghardt (talk) 08:08, 28 August 2023 (UTC)

I did it. I wrote the example on the talk page last night and published later. I'm sorry that I didn't wait for your answer. TD (talk) 08:14, 28 August 2023 (UTC)

About your point (2): you asked for a precise definition of this tree, not of another tree.TD (talk) 08:26, 28 August 2023 (UTC)

What about showing File:2 Stacked infinite binary trees.png, and giving the following definition:

Let $U$ be the set of all real numbers in the interval $[0,1)$ such that their decimal representation (omitting the leading zero) contains no other digits than $1$ and $2$. For $u,v\in U$ define $u<v$ if the decimal representation of $u$ is a proper prefix of that of $v$. (This should formalize TD's intention from the definition above.) Let $T=U\times U$ with the lexicographic order, i.e. define $(u_{1},u_{2})<(v_{1},v_{2})$ if $u_{1}<u_{2}$ or $u_{1}=u_{2}{\text{ and }}v_{1}<v_{2}$. Then $T$ is a fairly nontrivial set-theoretic tree, but is hard to depict. However, the subset $T'=(\{0.111111...\}\times U)\cup (U\times \{0.\})$ can be depicted, viz. by File:2 Stacked infinite binary trees.png.

This definition is admittedly still clumsy. I thought by referring to real numbers it could shortened (compared to speaking about sequences over $\mathbb {N}$ or an initial segment thereof), but I didn't succeed. An alternative might be to use the set of mappings from the ordinal $\omega \cdot 2$, or initial segments thereof, to $\{0,1\}$. This could avoid Cartesian product and lexicographic order; however, reals are better known than ordinals.

In any case, we'll still have to explain that in the image only line junctions represent set members. This seems unavoidable, since in any kind of fractal figure, we don't have space to draw e.g. circles for nodes. Jochen Burghardt (talk) 09:09, 28 August 2023 (UTC)

My definitions (see below) seem to me to be simpler than yours. And it can easily be extended to many kinds of non-trivial infinite trees. TD (talk) 09:18, 28 August 2023 (UTC)

In an article about trees, the concept of ordinal can be supposed to be known, because the definition of a tree require the concept of well-ordering, and an ordinal is essentially a well-ordered set.TD (talk) 09:31, 28 August 2023 (UTC)

Can someone clarify what the list of features are that need to be depicted to get across the concept of a set-theoretic tree? The current image to me looks like a demonstration of the way to fill an isosceles right triangle by (tilted) squares in a fractal pattern, and doesn't really convey much about trees per se. I could also see it as a representation of infinite binary fractions, though I think for that the image could be made substantially clearer with some design changes. –jacobolus (t) 16:58, 28 August 2023 (UTC)

Read the definition: "a tree is a partially ordered set (T, <) such that for each t ∈ T, the set {s ∈ T : s < t} is well-ordered by the relation <." TD (talk) 17:59, 28 August 2023 (UTC)

Yes, I can read the definition. But what I don't really understand from the article is, e.g.: what are some non-trivial examples of set theoretic trees? Which partially ordered sets are usually studied as trees per se rather than for some other structural prooerties?

Why is it called a "tree"? Why are the chains called "branches"? Can particular elements be members of more than one branch? Are people interested in finite set theoretic trees or only infinite ones? What theorems or problems does the structure of "tree" help solve that other structures don't suffice for? ...

Reading the definition (and the rest of the article) gives me a few bits of trivia and some pointers to other places to look for answers, but doesn't really give me enough context to know why anyone should care about this. As a newcomer to set theoretic trees I can't really make meaningful sense of the figures you made here. –jacobolus (t) 20:02, 28 August 2023 (UTC)

One kind of of diagram that might be helpful to newcomers would be a finite tree with a relatively small number of elements involving a fairly obvious (but not entirely trivial) order, where all of the branches could be clearly labeled. –jacobolus (t) 20:19, 28 August 2023 (UTC)

You seem to be honest so I'd like to help you. But I'm not an expert in this field. I'm a newcomer too. Here are a few tentative answers to your interesting questions:

• Trivial examples are finite trees (but trivial doesn't mean they are not interesting). They look like real trees in the air. A root (the trunk), branches which start from the trunk, and more branches which start at nodes from preceding branches.
• Usually (but not necessarily) an element of a tree (a node) is an element of many branches. More precisely, the concept of branch in this theory is defined as a maximal chain. This means that it starts from the root and ends with a 'leaf'.
• The concept of well-ordering is essential here. An ordered set is well-ordered if and only if all its subsets have a minimal element. $\mathbb {N}$ is well-ordered, but $\mathbb {Z}$ and $\mathbb {R} ^{+}$ aren't. All the branches of a tree shall be well ordered, else the partial order doesn't define a tree. If you want to know more about well-orderings, study the theory of ordinal numbers. A trivial well-ordering is finite or is the order of natural numbers, but there are many more infinite well-orderings (Cantor theory and after).TD (talk) 20:33, 28 August 2023 (UTC)

Okay, is this an example of a set theoretic tree then? (Where the dots are elements, the arrows indicate order, and elements not on any branch with each-other are not comparable.) –jacobolus (t) 23:19, 28 August 2023 (UTC)

Consider the third point (from bottom to top). The set of its ascendants (the two points at the bottom) is not ordered. Therefore it is not a tree. TD (talk) 23:29, 28 August 2023 (UTC)

Okay, great. That's what I thought. So I think what the lead section should show is a small handful of such finite posets, highlighting which ones are or aren't 'trees' and clearly explaining why or why not. Then a reader can get a quick visual concept of what "tree" means in this context. –jacobolus (t) 23:32, 28 August 2023 (UTC)

I added a figure to the article. Does that seem helpful? –jacobolus (t) 16:40, 29 August 2023 (UTC)

It does. But why did you delete my figure? TD (talk) 16:55, 29 August 2023 (UTC)

Why do you find this image confusing? TD (talk) 17:06, 29 August 2023 (UTC)

Okay, I put it back in the 'infinite trees' section.

I find this image confusing because the elements are not pictured but only implied, the order relations (which are depicted as line segments) use two unrelated colors and have dramatically different lengths from half the diagram down to invisibly small, distinct elements from different branches of the tree are infinitely close together at the top of the diagram, and many aspects of the particular tree are arbitrary (i.e. not essential to the concept of trees).

I think your example would work better if you found a concrete poset matching the picture (e.g. strings of arbitrary length over a 2-letter alphabet, ordered by a "starts with" relationship), and then explicitly described it in text (in body copy, not a caption). Otherwise readers have to make a lot of inferences about the picture. –jacobolus (t) 17:40, 29 August 2023 (UTC)

I guess there is an example in the text. I wonder if it can be copyedited a bit to make it more accessible to a broader audience. –jacobolus (t) 17:44, 29 August 2023 (UTC)

What's the purpose of the zooming picture? –jacobolus (t) 17:45, 29 August 2023 (UTC)

It's obvious. The purpose of a zoom is to see details which would be otherwise unseen. TD (talk) 21:58, 30 August 2023 (UTC)

Sure, but the zooming picture doesn't actually show any visual data that isn't already in the static picture, and the infinite repetition is already implied. I'm not sure whatever benefit is intended is worth the extra space and added visual distraction of a moving picture. YMMV. –jacobolus (t) 22:33, 30 August 2023 (UTC)

Without the zoom, would the viewer understand that the details are already in the whole picture? See File:Cantor Set Expansion.gif for another example. Please stop disturbing me with such requests, which are near nonsense.TD (talk) 22:49, 30 August 2023 (UTC)

Perhaps other readers find it useful, but I personally don't find this zooming cantor set image very helpful or easy to interpret. I think File:Cantor_set_in_seven_iterations.svg is much clearer. –jacobolus (t) 22:55, 30 August 2023 (UTC)

Also, nobody here is forcibly "disturbing you" or forcing you to work on or otherwise engage with any particular Wikipedia page. Whatever notifications you have set about talk page discussions are in your own personal settings, which nobody else has control over. As always on this entirely volunteer driven project, anyone is free to just go away and do something else whenever they feel like. –jacobolus (t) 23:01, 30 August 2023 (UTC)

This page is on my watchlist because I'm interested in it. And if someone asks for something I feel obliged to answer. TD (talk) 23:40, 30 August 2023 (UTC)

The reason of the zoom is to show scale invariance.TD (talk) 23:52, 30 August 2023 (UTC)

@Jacobolus: This image would fit better to Tree_(data_structure)#Examples_of_trees_and_non-trees where a collection of similar examples and non-examples of finite trees is already shown. in tree (set theory), a much more general concept is explained, allowing branches that are not just "infinitely long" (like e.g. rational trees in unification theory), but have lengths corresponding to arbitrary ordinal numbers. Jochen Burghardt (talk) 17:29, 30 August 2023 (UTC)

Someone reading this particular article should be able to have some kind of picture for what "tree" means that doesn't involve interpreting 3 layers of advanced mathematical jargon. These kinds of simple finite examples give a basic pictorial impression that readers can subsequently embellish by imagining the generalization to infinite cases. If there are better images elsewhere feel free to copy them here. For a similar example from a different field, look at the pictorial representation of "neighborhood" in topology. Clearly a dotted-line circle around a point within a blobby shape in a plane does not represent the full range of possible topological neighborhoods. But the point is only to give readers something basic to get them started understanding what the definition says, not to provide a comprehensive representation of the subject. –jacobolus (t) 17:34, 30 August 2023 (UTC)

With that said though, if you like we could also try to make some more schematic / abstract top-of-page drawing, not necessarily showing a specific concrete tree or collection of trees. If you can sketch out on paper how you think a more abstracted drawing could look (with little bundles of lines representing infinite branches, or whatever), I'd be happy to try to make a legible and "pretty" version. –jacobolus (t) 18:11, 30 August 2023 (UTC)

@Jochen Burghardt and @David Eppstein I added a new "infinite" top image. Does this one properly demonstrate the features needed here? –jacobolus (t) 06:59, 31 August 2023 (UTC)

It seems significantly better to me, after already having some idea what this topic is supposed to be about and how it differs from other kinds of trees. Whether it would be informative to someone coming to the article for the first time is a different question. —David Eppstein (talk) 07:02, 31 August 2023 (UTC)

I think it would have helped me at least. I tried to attach a picture to several features that are somewhat abstractly described (which always takes more effort for me to make sense of): "root", "branch", "height", ... But I can't answer for whether it will help anyone else. If nothing else, I tried to make it look tree-like. :-) –jacobolus (t) 07:27, 31 August 2023 (UTC)

Examples of infinite trees

I would like to add the following section to this article. Are there objections against it?

A proper initial segment of the set $\mathbb {N}$ of natural numbers is the set of all natural numbers $n$ such that $n<N$ for a natural number $N$. A finite sequence of binary digits is a map from an initial segment of natural numbers to the set $\{0,1\}$. An ordering can be defined on the set $T$ of all finite sequences of binary digits: $f\leq g$ if and only if $f(n)=g(n)$ for all $n$ in the domain of $f$. $T$ is a tree for this ordering. The root of the tree is the map $\langle \rangle$ whose domain is the null set $\varnothing$. $\langle 0\rangle$ (the map $f$ whose domain is $\{0\}$ such that $f(0)=0$ ) and $\langle 1\rangle$ are the next nodes. $\langle 00\rangle$ (the map $g$ whose domain is $\{0,1\}$ such that $g(0)=0$ and $g(1)=0$ ), $\langle 01\rangle$, $\langle 10\rangle$ and $\langle 11\rangle$ follow, and so on. The image at the top of this page is a visualization of $T$.

The well-ordering of branches of $T$ is trivial. It is the well-ordering of the set $\mathbb {N}$ of natural numbers. We can obtain less trivial well-orderings if we replace in the above definition $\mathbb {N}$ by any ordinal greater than $\omega$ (when considered as an ordinal $\mathbb {N}$ is usually noted $\omega$). TD (talk) 08:53, 28 August 2023 (UTC) We can also replace the set {0,1} by any other set.TD (talk) 09:22, 28 August 2023 (UTC)

Another example:

TD (talk) 10:10, 28 August 2023 (UTC)

A better example, that would actually get at the concept of a set-theoretic tree: Let the elements of the tree be functions $f:\alpha \mapsto \mathbb {Z}$ where $\alpha$ is a countable ordinal, and let the predecessors of any such function $f$ be all functions $g:\beta \mapsto \mathbb {Z}$ where $\beta <\alpha$ and $g$ agrees with $f$ on all arguments they have in common. The root is the (unique) function on the empty set. —David Eppstein (talk) 18:19, 28 August 2023 (UTC)

I already mentioned this kind of example. Replace {0,1} by $\mathbb {Z}$ and $\mathbb {N}$ by the first uncountable ordinal in the definition of $T$, and you get your example.TD (talk) 18:26, 28 August 2023 (UTC) modifiedTD (talk) 15:21, 30 August 2023 (UTC)

@David Eppstein: Thanks, that is much more concise than my above attempt. In order that a particular tree remains a set, $\alpha$ would have to be restricted to be less or equal to some fixed ordinal, say $\kappa$. I suggest we include this example in the corresponding section, show the above picture File:An infinite tree with a non-trivial well-ordering.gif, and refer from its caption to the example, adding

• that only junction points represent tree nodes,
• that the range set is $\{0,1\}$ (corresponding to red and green; larger sets can hardly be depicted),
• that $\kappa =\omega \cdot 2$, and
• that only branches with an initial segment of $(0,0,0,...)$ or $(1,1,1,...)$ are shown in full length, due to space restrictions.

I'd suggest to add more examples in the section, establishing the relation to

• tree (graph theory),
• tree (data structure) (always finite),
• tree (automata theory) (apparently may be infinite, up to $\omega$),

which I guess are all subsumed here (maybe with a grain of salt, such as different choices of root node in graph theory). I'm less sure about

• tree (descriptive set theory) (didn't yet read the article).

Jochen Burghardt (talk) 14:51, 29 August 2023 (UTC)

Your plan looks good to me. Re "In order that a particular tree remains a set": that is why I implicitly restricted $\alpha$ to $\alpha <\omega _{1}$ by asking for it to be countable. —David Eppstein (talk) 18:03, 29 August 2023 (UTC)

[Oops, I'd overlooked that. In my suggestion below, I stuck with $\kappa$ rather than "countable" or $\omega _{1}$ in order to have some variable that can be instantiated in the picture caption.]

Meanwhile, I came up, at User:Jochen_Burghardt/sandbox#Tree_(set_theory), with a suggestion for the examples section. If, after some improvements and corrections, it is acceptable as a consensus, I'd like to ask TD to revert his image to the original colored version, since I referred to the colors. I marked some sentences with {{clarify span}} to indicate that I'm particularly unsure whether they are right; please check and fix them where necessary. - Jochen Burghardt (talk) 20:25, 30 August 2023 (UTC)

I won't change my images for your pleasure. TD (talk) 21:23, 30 August 2023 (UTC)

No objection for 4 days - installing the suggestion now. - Jochen Burghardt (talk) 06:34, 4 September 2023 (UTC)