Введение

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

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

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

Ключевые узлы

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

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

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

Топология

Множество бесконечных последовательностей над (обозначается как ) может быть наделено топологией произведения, рассматривая X как дискретное пространство. В этой топологии каждое замкнутое подмножество имеет вид для некоторого усеченного дерева. А именно, пусть состоит из множества конечных префиксов бесконечных последовательностей в . Обратно, тело каждого дерева образует замкнутое множество в этой топологии. Часто рассматриваются деревья на декартовых произведениях. В этом случае, по соглашению, мы рассматриваем только подмножество пространства произведения , содержащее только последовательности, чьи четные элементы принадлежат , а нечетные элементы принадлежат (например, ). Элементы в этом подпространстве естественным образом отождествляются с подмножеством произведения двух пространств последовательностей (подмножеством, для которого длина первой последовательности равна или на 1 больше длины второй последовательности). Таким образом, мы можем отождествить с для над пространством произведения. Затем мы можем сформировать проекцию , .