Деревья в теории множеств

Введение

другие представления о дереве в теории множеств

В теории множеств дерево — это частично упорядоченное множество (T, <), такое что для каждого t ∈ T множество {s ∈ T : s < t} вполне упорядочено отношением <. Часто деревья рассматриваются как имеющие единственный корень (то есть минимальный элемент), поскольку типичные вопросы, изучаемые в этой области, легко сводятся к вопросам об однокорневых деревьях.

Определение

Дерево — частично упорядоченное множество (посеть) (T, <), такое, что для каждого t ∈ T множество {s ∈ T : s < t} хорошо упорядочено отношением <. В частности, любое хорошо упорядоченное множество (T, <) является деревом. Для каждого t ∈ T тип порядка множества {s ∈ T : s < t} называется высотой t и обозначается ht(t, T). Высота самого T является наименьшим ординалом, большим, чем высота каждого элемента T. Корень дерева T — это элемент высоты 0. Часто предполагается, что у деревьев только один корень. Деревья в теории множеств часто определяются как растущие вниз, при этом корень является наибольшим узлом. Деревья с одним корнем можно рассматривать как укорененные деревья в смысле теории графов одним из двух способов: либо как дерево (теория графов), либо как тривиально совершенный граф. В первом случае граф является ненаправленной диаграммой Хассе частично упорядоченного множества, а во втором случае граф является просто базовым (ненаправленным) графом частично упорядоченного множества. Однако, если высота T превышает ω, то определение диаграммы Хассе не работает. Например, частично упорядоченное множество не имеет диаграммы Хассе, так как у ω нет предшественника. Следовательно, в этом случае требуется высота не более ω. Ветвь дерева — это максимальная цепь в дереве (то есть любые два элемента ветви сопоставимы, и любой элемент дерева, не входящий в ветвь, несравним хотя бы с одним элементом ветви). Длина ветви — это ординал, порядково изоморфный ветви. Для каждого ординала α, α-й уровень T — это множество всех элементов T высоты α. Дерево является κ-деревом, для ординала κ, тогда и только тогда, когда его высота равна κ и кардинальность каждого уровня меньше кардинальности κ. Ширина дерева — это супремум кардинальностей его уровней. Любое однокорневое дерево высоты образует полурешетку пересечений, где пересечение (общий предок) задается максимальным элементом пересечения предков, который существует, поскольку множество предков не пусто и конечно хорошо упорядочено, следовательно, имеет максимальный элемент. Без одного корня пересечение родителей может быть пустым (двум элементам не обязательно иметь общих предков), например, когда элементы несравнимы; в то время как если есть бесконечное число предков, максимальный элемент может отсутствовать — например, когда они несравнимы. Поддерево дерева — это дерево, где и замкнуто вниз относительно <, то есть, если и , то .

A tree is a partially ordered set (poset) (T, <) such that for each t ∈ T, the set {s ∈ T : s < t} is well ordered by the relation <. In particular, each well ordered set (T, <) is a tree. For each t ∈ T, the order type of {s ∈ T : s < t} is called the height of t, denoted ht(t, T). The height of T itself is the least ordinal greater than the height of each element of T. A root of a tree T is an element of height 0. Frequently trees are assumed to have only one root. Trees in set theory are often defined to grow downward making the root the greatest node. Trees with a single root may be viewed as rooted trees in the sense of graph theory in one of two ways: either as a tree (graph theory) or as a trivially perfect graph. In the first case, the graph is the undirected Hasse diagram of the partially ordered set, and in the second case, the graph is simply the underlying (undirected) graph of the partially ordered set. However, if T is a tree of height > ω, then the Hasse diagram definition does not work. For example, the partially ordered set does not have a Hasse Diagram, as there is no predecessor to ω. Hence a height of at most ω is required in this case. A branch of a tree is a maximal chain in the tree (that is, any two elements of the branch are comparable, and any element of the tree not in the branch is incomparable with at least one element of the branch). The length of a branch is the ordinal that is order isomorphic to the branch. For each ordinal α, the α th level of T is the set of all elements of T of height α. A tree is a κ tree, for an ordinal number κ, if and only if it has height κ and every level has cardinality less than the cardinality of κ. The width of a tree is the supremum of the cardinalities of its levels. Any single rooted tree of height forms a meet semilattice, where meet (common ancestor) is given by maximal element of intersection of ancestors, which exists as the set of ancestors is non empty and finite well ordered, hence has a maximal element. Without a single root, the intersection of parents can be empty (two elements need not have common ancestors), for example where the elements are not comparable; while if there are an infinite number of ancestors there need not be a maximal element – for example, where are not comparable. A subtree of a tree is a tree where and is downward closed under , i. e., if and then .

Теоретические свойства множеств

В теории бесконечных деревьев есть несколько довольно просто сформулированных, но сложных проблем. Примерами являются гипотеза Курепы и гипотеза Суслина. Известно, что обе эти проблемы независимы от теории множеств Цермело — Френкеля. По лемме Кёнига, каждое ω-дерево имеет бесконечную ветвь. С другой стороны, это теорема ZFC, что существуют несчётные деревья, не имеющие несчётных ветвей и несчётных уровней; такие деревья известны как деревья Аронсжайна. Для кардинального числа κ, κ-дерево Суслина — это дерево высоты κ, не имеющее цепей или антицепей мощности κ. В частности, если κ сингулярно, то существует κ-дерево Аронсжайна и κ-дерево Суслина. Фактически, для любого бесконечного кардинала κ, каждое κ-дерево Суслина является κ-деревом Аронсжайна (обратное неверно). Гипотеза Суслина изначально была сформулирована как вопрос об определённых линейных порядках, но она эквивалентна утверждению: каждое дерево высоты ω1 имеет антицепь мощности ω1 или ветвь длины ω1. Если (T, <) — дерево, то рефлексивное замыкание ≤ отношения < является отношением префикса на T. Обратное неверно: например, обычный порядок ≤ на множестве целых чисел Z является линейным и, следовательно, отношением префикса, но (Z, <) не является теоретико-множественным деревом, поскольку, например, множество {n ∈ Z: n < 0} не имеет наименьшего элемента.

Примеры бесконечных деревьев

Пусть α — порядковое число, а A — множество. Пусть T — множество всех функций f, где область определения f является подмножеством A. Определим отношение ≤, если область определения f является собственным подмножеством области определения g и две функции совпадают на области определения f. Тогда T является теоретико-множественным деревом. Его корень — это единственная функция на пустом множестве, а его высота равна α. Объединение всех функций вдоль ветви дает функцию из A в множество значений этих функций, то есть обобщенную последовательность элементов из A. Если α — предельное порядковое число, ни одна из ветвей не имеет максимального элемента ("листа"). На рисунке показан пример для α = 2 и A = {0, 1}. Каждая структура данных "дерево" в информатике является теоретико-множественным деревом: для двух узлов f и g определим f ≤ g, если f является собственным потомком g. Понятия корня, высоты узла и длины ветви совпадают, в то время как понятия высоты дерева отличаются на единицу. Бесконечные деревья, рассматриваемые в теории автоматов (см., например, "дерево (теория автоматов)"), также являются теоретико-множественными деревьями, с высотой дерева до α. Теоретико-графовое дерево можно преобразовать в теоретико-множественное, выбрав корневой узел r и определив f ≤ g, если f и g лежат на (единственном) неориентированном пути от r к r. Каждое дерево Кантора, каждое дерево Курепы и каждое дерево Лавера является теоретико-множественным деревом.