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

Чтобы узнать о других понятиях дерева в теории множеств, см. Дерево (дескриптивная теория множеств) и Дерево (значения) .

Ветвь (выделена зеленым) теоретико-множественного дерева. Здесь точки представляют элементы, стрелки представляют отношение порядка, а эллипсы и пунктирные стрелки представляют (возможно, бесконечные) неизображенные элементы и отношения.

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

Определение

Небольшие конечные примеры: три частично упорядоченных множества слева — это деревья (синим цветом); одна ветка выделена одного из деревьев (зеленым цветом). Частично упорядоченное множество справа (красное) не является деревом, поскольку x ₁ < x ₃ и x ₂ < x ₃ , но x ₁ не сравним с x ₂ (пунктирная оранжевая линия).

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

Деревья с одним корнем можно рассматривать как корневые деревья в смысле теории графов одним из двух способов: либо как дерево (теория графов) , либо как тривиально совершенный граф . В первом случае граф представляет собой неориентированную диаграмму Хассе частично упорядоченного множества, а во втором случае граф представляет собой просто основной (неориентированный) граф частично упорядоченного множества. Однако если T — дерево высоты > ω , то определение диаграммы Хассе не работает. Например, частично упорядоченный набор $\omega +1=\left\{0,1,2,\dots ,\omega \right\}$ не имеет диаграммы Хассе, так как у ω нет предшественника. Следовательно, в этом случае требуется высота не более ω.

Ветвью входящий в ветку дерева называется максимальная цепь в дереве (т. е. любые два элемента ветки сравнимы, а любой элемент дерева, не , несравним хотя бы с одним элементом ветки). Длина , ветви — это порядковый номер изоморфный по порядку ветви. Для каждого ординала α α-й уровень T представляет собой множество всех элементов T высоты α. Дерево является κ-деревом для порядкового номера κ тогда и только тогда, когда оно имеет высоту κ и мощность каждого уровня меньше мощности κ. Ширина . дерева — это верхняя граница мощностей его уровней

Любое однокорневое дерево высоты $\leq \omega$ образует встречу-полурешетку, где встреча (общий предок) задается максимальным элементом пересечения предков, который существует, поскольку множество предков непусто и конечно хорошо упорядочено, следовательно, имеет максимальный элемент. Без единого корня пересечение родителей может быть пустым (два элемента не обязательно должны иметь общих предков), например $\left\{a,b\right\}$ где элементы несопоставимы; в то время как если существует бесконечное число предков, не обязательно должен быть максимальный элемент - например, $\left\{0,1,2,\dots ,\omega _{0},\omega _{0}'\right\}$ где $\omega _{0},\omega _{0}'$ не сопоставимы.

Поддерево ​ дерева $(T,<)$ это дерево $(T',<)$ где $T'\subseteq T$ и $T'$ закрыто вниз под $<$, то есть, если $s,t\in T$ и $s<t$ затем $t\in T'\implies s\in T'$.

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

В теории бесконечного дерева есть несколько довольно просто сформулированных, но сложных проблем. Примерами этого являются гипотеза Курепы и гипотеза Суслина . Обе эти проблемы, как известно, не зависят от теории множеств Цермело–Френкеля . По лемме Кенига каждое ω-дерево имеет бесконечную ветвь. С другой стороны, теорема ZFC гласит , что существуют несчетные деревья без несчетных ветвей и несчетных уровней; такие деревья известны как деревья Ароншайна . Учитывая кардинальное число κ, κ- дерево Суслина — это дерево высоты κ, не имеющее цепей или антицепей размера κ. В частности, если κ сингулярно , то существуют κ-дерево Ароншайна и κ-дерево Суслина. В самом деле, для любого бесконечного кардинала κ каждое κ-дерево Суслина является κ-деревом Ароншайна (обратное неверно).

Гипотеза Суслина первоначально была сформулирована как вопрос о некоторых полных порядках , но она эквивалентна утверждению: каждое дерево высоты ω ₁ имеет антицепь мощности ω ₁ или ветвь длины ω ₁ .

Если ( T ,<) — дерево, то рефлексивное замыкание ≤ < является префиксным порядком на T .Обратное неверно: например, обычный порядок ≤ на множестве Z целых чисел является итоговым и, следовательно, префиксным порядком, но ( Z ,<) не является теоретико-множественным деревом, поскольку, например, множество { n ∈ Z : n <0} не имеет наименьшего элемента.

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

Теоретико-множественное дерево высоты $\omega \cdot 2$ и ширина $2^{\omega \cdot 2}$. Каждый узел соответствует точке соединения красной и зеленой линии. Из-за ограничений места доступны только ветки с префиксом ( 0 , 0 , 0 ,...) или ( 1 , 1 , 1 ,...) показаны в полный рост.

• Позволять $\kappa$ будет порядковым числом, и пусть $X$ быть набором. Позволять $T$ быть набором всех функций $f:\alpha \mapsto X$ где $\alpha <\kappa$. Определять $f<g$ если домен ​ $f$ является собственным подмножеством области $g$ и эти две функции согласуются в области определения $f$. Затем $(T,<)$ является теоретико-множественным деревом. Его корень — это уникальная функция на пустом множестве, а его высота равна $\kappa$. Объединение всех функций вдоль ветви дает функцию из $\kappa$ к $X$, то есть обобщенная последовательность членов $X$. Если $\kappa$ является предельным ординалом , ни одна из ветвей не имеет максимального элемента (« листа »). На картинке показан пример $\kappa =\omega \cdot 2$ и $X=\{0,1\}$.

• Каждая древовидная структура данных в информатике представляет собой теоретико-множественное дерево: для двух узлов $m,n$, определять $m<n$ если $n$ является прямым потомком $m$. Понятия корня , высоты узла и длины ветки совпадают, а понятия высоты дерева отличаются на единицу.

• Бесконечные деревья, рассматриваемые в теории автоматов (см., например, дерево (теория автоматов) ), также являются теоретико-множественными деревьями с высотой дерева до $\omega$.

• Теоретико -графовое дерево можно превратить в теоретико-множественное, выбрав корневой узел. $r$ и определение $m<n$ если $m\neq n$ и $m$ лежит на (единственном) ненаправленном пути от $r$ к $n$.

• Каждое дерево Кантора , каждое дерево Курепы и каждое дерево Лейвера является теоретико-множественным деревом.

См. также

• Дерево (дескриптивная теория множеств)
• Непрерывный график

Ссылки

• Я, Томас (2002). Теория множеств . Спрингер Верлаг. ISBN  3-540-44085-2 .
• Кунен, Кеннет (1980). Теория множеств: введение в доказательства независимости . Северная Голландия. ISBN  0-444-85401-0 . Глава 2, Раздел 5.
• Монк, Дж. Дональд (1976). Математическая логика . Нью-Йорк: Springer-Verlag. п. 517 . ISBN  0-387-90170-1 .
• Рассвет, Андраш ; Гамбургер, Питер (1999). Теория множеств . Кембридж: Издательство Кембриджского университета. ISBN  9780521596671 .
• Кекрис, Александр С. (1995). Классическая описательная теория множеств . Тексты для аспирантов по математике 156. Спрингер. ISBN   0-387-94374-9 ISBN   3-540-94374-9 .

Внешние ссылки

• Множества, модели и доказательства Ике Мурдейка и Яапа ван Остена , см. определение 3.1 и упражнение 56 на стр. 68–69.
• дерево (теоретико-множество) Генри , на PlanetMath
• ветка Генри ​ на PlanetMath
• пример дерева (теоретико-множественный), автор uzeromay на PlanetMath