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

редактировать

В теории множеств дерево представляет собой частично упорядоченный набор (T, <) such that for each t ∈ T, the set {s ∈ T : s < t} is упорядоченный отношением <. Frequently trees are assumed to have only one root (i.e. минимальный элемент ), поскольку типичные вопросы, исследуемые в этой области, легко сводятся к вопросам о однокорневых деревьях.

Содержание

1 Определение
2 Теоретико-множественные свойства
3 См. Также
4 Ссылки
5 Внешние ссылки

Определение

A дерево - это частично упорядоченное множество (poset) (T, <) such that for each t ∈ T, the set {s ∈ T : s < t} is упорядоченное отношением <. In particular, each well-ordered set (T, <) is a tree. For each t ∈ T, the тип заказа для {s ∈ T: s порядковым номером, превышающим высоту каждого элемента T. A root дерева T является элементом высоты 0. Часто предполагается, что деревья имеют только один корень. Обратите внимание, что деревья в теории множеств часто определяются так, чтобы расти вниз, делая корень самым большим узлом.

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

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

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

A поддерево дерева $(T, <) {\displaystyle (T,<)}$ ${\ displaystyle (T, <)}$ - дерево $(T ′, <) {\displaystyle (T',<)}$ $(T',<)$ , где $T ′ ⊆ T {\ displaystyle T '\ substeq T}$ $T'\subseteq T$ и $T ′ {\ displaystyle T '}$ $T'$ закрывается вниз под $< {\displaystyle <}$ $<$ , т. Е. Если $s, t ∈ T {\ displaystyle s, t \ in T}$ ${ \ displaystyle s, t \ in T}$ и $s < t {\displaystyle s$ ${\ displaystyle s <t}$ , тогда $t ∈ T ′ ⟹ s ∈ T ′ {\ displaystyle t \ in T '\ подразумевает s \ in T'}$ $t\in T'\implies s\in T'$ .

Теоретико-множественная properties

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

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

См. также

Ссылки

Jech, Thomas (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.

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

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