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

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

Определения [ править ]

Деревья [ править ]

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

Филиалы и органы [ править ]

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

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

Терминальные узлы [ править ]

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

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

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

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

Топология [ править ]

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

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

${\displaystyle p[T]=\{{\vec {x}}\in X^{\omega }|(\exists {\vec {y}}\in Y^{\omega })\langle {\vec {x}},{\vec {y}}\rangle \in [T]\}}$.

См. Также [ править ]

• Дерево Лейвера , тип дерева, используемый в теории множеств как часть понятия принуждения

Ссылки [ править ]

• Кечрис, Александр С. (1995). Классическая описательная теория множеств . Тексты для выпускников по математике 156. Springer. ISBN 0-387-94374-9 ISBN 3-540-94374-9 .