Talk:Tree (descriptive set theory)

closed under "subsequence"?

subsequence can be more general than a truncated sequence with coinciding initial parts. Subsequence might include consecutive terms, not necessarily beginning with the sequence's first term. It is used in other areas of mathematics to mean a sequence obtained by omitting any number of elements from the original sequence, hence they would not have to be consecutive. The beginning of this article needs to be more clear. It might read "... that is closed under truncation of the terminal end," if that is all that is meant by "closed under subsequence."24.58.63.18 (talk) 02:06, 23 February 2009 (UTC)

I definitely think you are right and I change the world "subsequences" to "initial segments". (Which is the term that is common in descriptive set theory for this.) --Kompik (talk) 08:03, 18 October 2009 (UTC)

cartesian products

$(X\times Y)^{\omega }\cong X^{\omega }\times Y^{\omega }$ this is natural. Was

$(X\times Y)^{<\omega }$ is naturally identified with a subset of $X^{<\omega }\times Y^{<\omega }$

what was meant? 24.58.63.18 (talk) 02:21, 23 February 2009 (UTC)

I believe I fixed this issue. What was meant was that one can identify the tree T which interleaves the elements from X and Y with a subset of the product $X^{<\omega }\times Y^{<\omega }$ **in such a way that** $[T]\cong X^{\omega }\times Y^{\omega }$. It's simply not true that

$(X\times Y)^{\omega }\cong X^{\omega }\times Y^{\omega }$ as there are elements of $(X\times Y)^{\omega }$ which are members of $(X)^{\omega }$ (where X, Y are disjoint). Peter M. Gerdes (talk) 02:41, 20 October 2016 (UTC)

Merge With Tree (set theory)

The notion of tree in DST is the same as that in set theory except that one is usually interested in trees of height $\omega$. However, even that isn't really true as one will sometimes consider trees of height $\omega _{1}^{CK}$, e.g., the tree of all effective ordinal notations.

So we duplicate a fair bit and even invite confusion by leaving these two articles separate. I would merge them myself now but I don't know the proper procedure and assume I should ask first. Peter M. Gerdes (talk) 21:55, 19 October 2016 (UTC)

I agree that a merge is not totally implausible; you can certainly represent the height-ω DST concept as a special case of the more general set-theory concept.

My feeling, though, is that the DST concept is easiest to think of on its own, rather than as a special case of "anti-wellfounded partial order with a greatest element", which is the abstract way of representing the set-theory concept. If you have in mind a less abstract version of the set-theory concept, that might be different. --Trovatore (talk) 00:23, 20 October 2016 (UTC)

To my mind, the kind of trees described by Tree (descriptive set theory) have a lot more in common with the (rooted) trees in Tree (graph theory) rather than the trees in Tree (set theory). For instance, they can equally well be described by their parent function than by their ancestor relation, something that is not true of the set-theoretic trees. For this reason, I think they are distinct enough concepts that it would be difficult to make a merged article that is unified enough to be an article. (Per WP:NOTDICT, articles here are about single concepts, and if different concepts have similar names they should be separate articles.) —David Eppstein (talk) 00:43, 20 October 2016 (UTC)

The reason I wanted to merge (I was making a bunch of changes to this article and decided to put them in the set theory tree but happy to move them here) is that there seemed to be a lot of necessary definitions and context in the set theory tree section. In particular my reasons are:

1. It is literally the same concept. If you define it as if it wasn't a special case of the set theory tree (with subsequence as the < relation) one loses this connection which seems to be both part of the culture and helpful to apply some theorems.
2. All the notation presumes familiarity with set theory anyway, e.g. $2^{<\omega }$ and it is easier to handle as part of the set theory concept. If I believed there were people doing DST to whom the set theoretic notion wouldn't already be familiar I would be less convinced.
3. Without being part of the set theory section one has to redefine subtree, ht(u), branch (just with the remark that one normally means infinite branch).
4. The definition of a well-founded and ill-founded don't make any sense without using the set theory definition of a tree as (T, <) as well as bootstrapping off the fact that trees in set theory are often taken to grow down (so a tree with an infinite branch has an infinite decreasing chain relative to >). **This means there isn't really much of a choice about regarding the DST trees in some sense as sets as a special case of the set theory concept**.

To respond to your points:

• The parent function: why is it a dissimilarity that a tree of height $\omega$ has some properties that a tree of arbitrary height does not? *Any* tree in the set theory sense (which as the page tells us means single root) with height $\omega$ can be so described. Besides, the dissimilarity is only apparent. At finite levels the parent function and the the function p(alpha) which returns the set of predecessors to alpha are mere notational variants...all this tells us is that p(alpha) is the right generalization.
• While graph theoretic trees might all be finite they use very different notation and, since their branches aren't elements in an infinite product it doesn't really make sense to apply the product topology etc..

Peter M. Gerdes (talk) 02:35, 20 October 2016 (UTC)

Hmm, it occurs to me that my response came off as very certain that it should be moved. I just wanted to present my reasons. What I really want is someone to take a look below at the outline of how *I* would explain DST trees and see if 1) They think (despite rough parts) it's reasonable not more confusing etc.. 2) If it reasonable is it better here or as part of set theory. It's entierly possible that I just feel more comfortable with the set theoretic style/link because I learned DST in a different setting than others did. Peter M. Gerdes (talk) 02:44, 20 October 2016 (UTC)

But they are not "literally the same concept". These ones are sequences ordered by prefixing, those other ones are arbitrary things ordered by however you would like to order them. There is a type mismatch. One can obviously map sequences-and-prefixes to posets and back, but that's not the same as being literally the same. If you want something that really is literally the same as sequences-and-prefixes (but with the only change being that the underlying set from which the sequences are drawn is restricted to finite), see trie. —David Eppstein (talk) 03:16, 20 October 2016 (UTC)

Okay, I guess I was incautious in my use of language. I didn't mean that DST Tree and Set theory tree define the same concept. I meant that a DST tree corresponded to a sub-type of Set theory trees. That is the relation between the concept DST tree and Set theory tree is the same as the relation between Set theory tree and infinite Set theory tree (or set theory tree of cardinal height...or any other precisification) and we wouldn't dream of dividing up those concepts. I was trying to communicate the fact that (as I have always learned them) a DST tree uses the general concept of tree and if one doesn't regard a DST tree as a sub-type of Set theory tree you this relation (all facts true of Set theory trees are true of DST trees), use of terminology definitions and cultural disconnection from normal practice. To be fair I admit this overlaps with my other points. I'm open to the idea that DST tree should be discussed in a separate page because it has many unique features that don't fully generalize but I feel strongly that it should definitely be regarded (and definitional treated as) a set theory tree with certain additional properties.Peter M. Gerdes (talk) 14:34, 20 October 2016 (UTC)

Closing, given that there is no consensus for the merge, and the discussion has been stale for over 18 months. Klbrain (talk) 12:18, 5 July 2018 (UTC)

Draft of DST tree added as I would add to set theory tree

(maybe I got a bit carried away fixing some minor points)

Trees in descriptive set theory

In descriptive set theory trees are assumed to have height $\omega$ and to be subtrees of $X^{<\omega }$ (the set of all finite sequences from $X$ ordered by subsequence) unless otherwise specified. When $X=\lbrace 0,1\rbrace$ $X^{<\omega }=2^{<\omega }$ is the tree of all finite binary strings and when $X=\omega$ $X^{<\omega }=\omega ^{<\omega }$ is the tree of all finite sequences of integers.

A tree $T$ of this type (a subtree of $X^{<\omega }$ for some $X$) is a set of finite sequences of the form $\langle x_{0},x_{1},\ldots ,x_{n-1}\rangle$ ($x_{i}\in X$ satisfying the condition that if $\langle x_{0},x_{1},\ldots ,x_{n-1}\rangle \in T$ and $m\leq n$ then $\langle x_{0},x_{1},\ldots ,x_{m-1}\rangle \in T$. As the height of an element $u\in T$ is just the length of the sequence $u$ it is common to denote $ht(u)$ by $\left\vert u\right\vert$ (so $\left\vert \langle x_{0},x_{1},\ldots ,x_{n-1}\rangle \right\vert =n$.

Branches, bodies and terminal nodes

Infinite branches are of particular interest in descriptive set theory and the word branch is used commonly used to mean infinite branch. We define $[T]$ , the body of $T$ to be the set of all functions from $\omega$ to $X$ whose initial segments are all in $T$, i.e., $[T]=\lbrace f\in X^{\omega }\mid \forall n\in \omega f\upharpoonright _{n}\in T\rbrace$. For example, $[X^{<\omega }]$ is equal to $X^{\omega }$, the set of all functions from $\omega$ to $X$. By identifying the branch $\lbrace \langle f(0),f(1),\ldots ,f(n-1)\rangle \mid n\in \omega \rbrace$ with $f$ we can regard $[T]$ as the set of all (infinite) branches of $T$.

A tree that has no branches is called wellfounded; a tree with at least one branch is illfounded. If (as customary in set theory) we view the tree as growing downward then a tree is wellfounded just if the order relation is wellfounded, i.e., permits no infinite decreasing sequence. By König's lemma, an infinite tree $T$ that is a subtree of $X^{<\omega }$ for some finite set $X$ contains an infinite path, i.e., is illfounded. This fails when $X$ is infinite as in $\omega ^{<\omega }$

A terminal node is an element of $T$ that has no extension in $T$. For subtrees of $X^{<\omega }$ terminal nodes are finite sequences $\langle x_{0},x_{1},\ldots ,x_{n-1}\rangle \in T$ such that there is no $x_{n}$ such that $\langle x_{0},x_{1},\ldots ,x_{n}\rangle \in T$. Note that a (not necessarily infinite) branch of $T$ is finite just if it contains a terminal node allowing us to identify finite branches and terminal nodes.

Topology

We equip $X^{\omega }$ with the product topology where $X$ is endowed with the discrete topology and assign to $[T]\subseteq X^{\omega }$ the subspace topology whenever $T$ is a subtree of $X^{<\omega }$. The topology of $[T]$ has a clopen basis given by the sets $B_{u}=\lbrace f\in [T]\subseteq X^{\omega }\mid f\upharpoonright _{\left\vert u\right\vert }$ for $u\in T$, i.e., sets in the basis are specified by a finite sequence of elements from $X$ and contain all those branches $f\in [T]$ extending that sequence. Every closed set in this topology is of the form $[T']$ for some subtree $T'$ of $T$. Note that by considering the subtree $T_{X\times Y}$ of $(X\times Y)^{<\omega }$ containing only sequences which alternate between elements from $X$ and $Y$, e.g., $\langle x_{0},y_{1},x_{2},y_{3}\ldots ,x_{2m},y_{2m+1}\rangle$, we can identify $X^{\omega }\times Y^{\omega }$ with $[T_{X\times Y}]$. (I included this b/c it was in DST tree page but I think this bit about products isn't very useful)

Taking $T=2^{<\omega }$ gives us the canonical perfect compact Polish Spaces, the Cantor space ($[2^{<\omega }]=2^{\omega }$ and taking $T=\omega ^{<\omega }$ gives us the canonical perfect non-locally compact Polish Spaces, the Baire space ($[\omega ^{<\omega }]=\omega ^{\omega }$. Indeed, the importance of subtrees of $X^{<\omega }$ in descriptive set theory arises (in part) from the fact that if $X$ is a countable set then $[T]$ will be a Polish Spaces for any non-empty subtree $T$ of $X^{<\omega }$.

Moreover, the universality property of the Baire space tells us that every Polish Space is continuously bijectable with $[T]$ for some subtree $T$ of $\omega ^{<\omega }$ (and the homeomorphic image of some $G_{\delta }$ subset of $\omega ^{\omega }$)

Effective descriptive set theory

In effective descriptive set theory subsets of the the Cantor space and Baire space are classified into the hyperarithmetical hierarchy (an extension of the familiar arithmetic hierarchy to ordinals beyond $\omega$). Trees play several critical roles in this process including providing an effective presentation of the Cantor space and Baire space as well as an important role in the analysis of recursive ordinals. A key result establishes that any tree $T$ lacking any infinite paths has an order type given by a recursive ordinal. Using such considerations it is possible to derive more finely grained versions of classic results about Borel sets, e.g., the identification of the Borel sets with the $\mathbf {\Delta _{1}^{1}}$ sets with the refinement that the hyperarithmetic sets are identified with the $\Delta _{1}^{1}$.