Дерево (дескриптивная теория множеств)

В дескриптивной теории множеств дерево множестве на $X$ представляет собой совокупность конечных последовательностей элементов $X$ так, что каждый префикс последовательности в коллекции также принадлежит коллекции.

Определения

Деревья

Совокупность всех конечных последовательностей элементов множества $X$ обозначается $X^{<\omega }$ .В этих обозначениях дерево представляет собой непустое подмножество. $T$ из $X^{<\omega }$ , такой, что если $\langle x_{0},x_{1},\ldots ,x_{n-1}\rangle$ представляет собой последовательность длины $n$ в $T$ , и если $0\leq m<n$ ,затем сокращенная последовательность $\langle x_{0},x_{1},\ldots ,x_{m-1}\rangle$ также принадлежит $T$ . В частности, выбирая $m=0$ показывает, что пустая последовательность принадлежит каждому дереву.

Филиалы и органы

Ветка дерево через $T$ представляет собой бесконечную последовательность элементов $X$ , каждый из конечных префиксов которого принадлежит $T$ . Набор всех ветвей через $T$ обозначается $[T]$ и назвал тело дерева $T$ .

Дерево, у которого нет ветвей, называется прочным ; дерево, имеющее хотя бы одну ветвь, необоснованно . По лемме Кенига дерево на конечном множестве с бесконечным числом последовательностей обязательно должно быть необоснованным.

Терминальные узлы

Конечная последовательность, принадлежащая дереву $T$ называется терминальным узлом, если он не является префиксом более длинной последовательности в $T$ . Эквивалентно, $\langle x_{0},x_{1},\ldots ,x_{n-1}\rangle \in T$ является терминальным, если нет элемента $x$ из $X$ такой, что $\langle x_{0},x_{1},\ldots ,x_{n-1},x\rangle \in T$ . Дерево, не имеющее конечных узлов, называется обрезанным .

Отношение к другим видам деревьев

В теории графов корневое дерево — это ориентированный граф , в котором каждая вершина, за исключением специальной корневой вершины, имеет ровно одно выходящее ребро и в котором путь, образованный путем следования по этим ребрам из любой вершины, в конечном итоге приводит к корневой вершине.Если $T$ является деревом в смысле дескриптивной теории множеств, то оно соответствует графу с одной вершиной для каждой последовательности в $T$ и выходящее ребро каждой непустой последовательности, которое соединяет ее с более короткой последовательностью, образованной удалением ее последнего элемента. Этот граф является деревом в смысле теории графов. Корнем дерева является пустая последовательность.

В теории порядка используется другое понятие дерева: дерево теории порядка — это частично упорядоченное множество с одним минимальным элементом , в котором каждый элемент имеет хорошо упорядоченный набор предшественников.Каждое дерево в дескриптивной теории множеств также является теоретико-порядковым деревом, использующим частичный порядок, в котором две последовательности $T$ и $U$ заказаны по $T<U$ тогда и только тогда, когда $T$ является правильным префиксом $U$ . Пустая последовательность является уникальным минимальным элементом, и каждый элемент имеет конечный и упорядоченный набор предшественников (набор всех его префиксов).Теоретико-порядковое дерево может быть представлено изоморфным деревом последовательностей тогда и только тогда, когда каждый из его элементов имеет конечную высоту (то есть конечное множество предшественников).

Топология

Множество бесконечных последовательностей над $X$ (обозначается как $X^{\omega }$ ) может быть задана топология произведения , рассматривающая X как дискретное пространство .В этой топологии каждое закрытое подмножество $C$ из $X^{\omega }$ имеет форму $[T]$ за какое-то обрезанное дерево $T$ .А именно, пусть $T$ состоят из множества конечных префиксов бесконечных последовательностей в $C$ . И наоборот, тело $[T]$ каждого дерева $T$ образует замкнутое множество в этой топологии.

Часто деревья в декартовых произведениях $X\times Y$ считаются. В этом случае по соглашению мы рассматриваем только подмножество $T$ пространства продукта, $(X\times Y)^{<\omega }$ , содержащий только последовательности, четные элементы которых происходят из $X$ и нечетные элементы происходят из $Y$ (например, $\langle x_{0},y_{1},x_{2},y_{3}\ldots ,x_{2m},y_{2m+1}\rangle$ ). Элементы этого подпространства естественным образом отождествляются с подмножеством произведения двух пространств последовательностей: $X^{<\omega }\times Y^{<\omega }$ (подмножество, для которого длина первой последовательности равна или на 1 больше длины второй последовательности).Таким образом, мы можем идентифицировать $[X^{<\omega }]\times [Y^{<\omega }]$ с $[T]$ за пространство продукта. Тогда мы можем проекцию сформировать $[T]$ ,