Tree (descriptive set theory): Difference between revisions

Revision as of 22:00, 27 February 2017

Latest revision as of 19:58, 3 January 2021

(12 intermediate revisions by 10 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 8 ⟶ 5:

===Trees===

The collection of all finite sequences of elements of a set <math>X</math> is denoted <math>X^{<\omega}</math>.

With this notation, a tree is a nonempty subset <math>T</math> of <math>X^{<\omega}</math>, such that if

<math>\langle x_0,x_1,\ldots,x_{n-1}\rangle</math> is a sequence of length <math>n</math> in <math>T</math>, and if <math>0\le m<n</math>,

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===

A finite sequence that belongs to a tree <math>T</math> is called a '''terminal node''' if it is not a prefix of a longer sequence in <math>T</math>. Equivalently, <math>\langle x_0,x_1,\ldots,x_{n-1}\rangle \in T</math> is terminal if there is no element <math>x</math> of <math>X</math> such that that <math>\langle x_0,x_1,\ldots,x_{n-1},x\rangle \in T</math>. A tree that does not have any terminal nodes is called '''pruned''' This is all bullshit.

==Relation to other types of trees==

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)}}