Tree (descriptive set theory): Difference between revisions

Revision as of 21:58, 7 January 2018

Latest revision as of 19:58, 3 January 2021

(8 intermediate revisions by 6 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 14 ⟶ 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 37 ⟶ 36:

==See also==

*[[Laver tree]], a type of tree used in [[set theory]] as part of a notion of [[deprecateForcing (mathematics)|deprecateforcing]]

==References==