Tree (descriptive set theory): Difference between revisions

Revision as of 22:03, 19 October 2016

Latest revision as of 19:58, 3 January 2021

(14 intermediate revisions by 12 users not shown)

Line 1:

{{about|mathematical trees described by prefixes of finite sequences|trees described by partially ordered sets|Tree (set theory)}}

{{merge|Tree (set theory)|discuss=Talk:Tree_(descriptive_set_theory)#Merge With Tree (set theory)|date=October 2016}}

In [[descriptive set theory]], a '''tree''' on a set <math>X</math> is a collection of [[finite sequence]]s of elements of <math>X</math> such that every [[Prefix (computer science)|prefix]] of a sequence in the collection also belongs to the collection.

Line 16 ⟶ 13:

A '''branch''' through a tree <math>T</math> is an infinite sequence of elements of <math>X</math>, each of whose finite prefixes belongs to <math>T</math>. The set of all branches through <math>T</math> is denoted <math>[T]</math> and called the '''''body''''' of the tree <math>T</math>.

A tree that has no branches is called '''''[[wellfounded]]'''''; a tree with at least one branch is '''''illfounded'''''. By [[KönigKőnig's lemma]], a tree on a [[finite set]] with an infinite number of sequences must necessarily be illfounded.

===Terminal nodes===

Line 34 ⟶ 31:

Namely, let <math>T</math> consist of the set of finite prefixes of the infinite sequences in <math>C</math>. Conversely, the body <math>[T]</math> of every tree <math>T</math> forms a closed set in this topology.

Frequently trees on [[Cartesian product]]s <math>X\times Y</math> are considered. In this case, by convention, thewe setconsider ofonly finitethe sequencessubset of members<math>T</math> of the product space, <math>(X\times Y)^{<\omega}</math>, iscontaining only sequences whose even elements come from <math>X</math> and odd elements come from <math>Y</math> (e.g., <math>\langle x_0,y_1,x_2,y_3\ldots,x_{2m}, y_{2m+1}\rangle</math>). Elements in this subspace are identified in the natural way with a subset of the product of two spaces of sequences, <math>X^{<\omega}\times Y^{<\omega}</math> (the subset offor memberswhich the length of the secondfirst productsequence foris whichequal bothto sequencesor have1 themore samethan the length of the second sequence).

In this way a tree <math>[T]</math> over the product spacewe may be considered as a subset ofidentify <math>[X^{<\omega}]\times [Y^{<\omega}]</math> with <math>[T]</math> for over the product space. We may then form the '''projection''' of <math>[T]</math>,

: <math>p[T]=\{\vec x\in X^{\omega} | (\exists \vec y\in Y^{\omega})\langle \vec x,\vec y\rangle \in [T]\}</math>.

Line 42 ⟶ 39:

==References==

* {{Cite book| last = Kechris | first = Alexander S. | authorlink = Alexander S. Kechris | title = Classical Descriptive Set Theory | others = [[Graduate Texts in Mathematics]] 156 | publisher = Springer | year = 1995 | id = ISBN {{isbn|0-387-94374-9}} ISBN {{isbn|3-540-94374-9}}}}

{{DEFAULTSORT:Tree (Descriptive Set Theory)}}