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

Эта статья включает в себя список литературы , связанной литературы или внешних ссылок , но ее источники остаются неясными, поскольку в ней отсутствуют встроенные цитаты . Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Январь 2021 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

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

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

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

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

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

Поддерево дерева является дерево , где и находится вниз закрыта под , то есть, если и тогда . ${\ Displaystyle (Т, <)}$ ${\ Displaystyle (Т ', <)}$ ${\ displaystyle T '\ substeq T}$ ${\ displaystyle T '}$ ${\ displaystyle <}$ $s,t\in T$ $s<t$ $t\in T'\implies s\in T'$

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

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

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

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

Кантор дерево
Курепа дерево
Лавровое дерево
Дерево (описательная теория множеств)
Непрерывный график
Порядок префиксов

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

Jech, Томас (2002). Теория множеств . Springer-Verlag. 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. Springer. ISBN 0-387-94374-9 ISBN 3-540-94374-9 .

Внешние ссылки [ править ]

Наборы, Модель и Доказательства по Ик Моердик и Яап ван Oosten , см определения 3.1 и упражнение 56 на стр. 68-69.
дерево (набор Теоретико) от Генри на PlanetMath
филиал по Генри на PlanetMath
пример дерева (теоретико-множественное) от узеромая на PlanetMath