트리 (집합이론)

집합 이론에서, 트리는 부분적으로 순서화된 집합(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인 원소입니다.트리가 하나의 루트만 있는 것으로 가정하는 경우가 많습니다.집합론에서 나무는 종종 뿌리가 가장 큰 ^{[citation needed]}노드가 되도록 아래쪽으로 자라도록 정의됩니다.

뿌리가 하나인 나무는 그래프 이론의 의미에서 뿌리가 있는 나무로 간주될 수 있습니다. 즉, 나무(그래프 이론) 또는 극히 완벽한 그래프로 간주될 수 있습니다.첫 번째 경우 그래프는 부분 순서 집합의 무방향 하세 다이어그램이고, 두 번째 경우 그래프는 단순히 부분 순서 집합의 기본(무방향) 그래프입니다.그러나 T가 높이 > ω의 트리인 경우 Hasse 다이어그램 정의가 작동하지 않습니다.예를 들어 부분 순서 집합 $\omega +1=\left\{0,1,2,\dots ,\omega \right\}$ ω + $\omega +1=\left\{0,1,2,\dots ,\omega \right\}$ = { $\omega +1=\left\{0,1,2,\dots ,\omega \right\}$ $\omega +1=\left\{0,1,2,\dots ,\omega \right\}$ $\omega +1=\left\{0,1,2,\dots ,\omega \right\}$ $\omega +1=\left\{0,1,2,\dots ,\omega \right\}$ ω $\omega +1=\left\{0,1,2,\dots ,\omega \right\}$ {\ $displaystyle \omega +$ 1=\ $left\{0, 1, 2,\$ dots $,\omega \right\}$ 에는 ω의 이전 집합이 없으므로 Hasse 다이어그램이 없습니다.따라서 이 경우 최대 1/2의 높이가 필요합니다.

트리의 분기는 트리의 최대 체인입니다(즉, 분기의 임의의 두 요소는 비교 가능하며, 분기에 없는 트리의 임의의 요소는 분기의 하나 이상의 요소와 비교 가능하지 않음).가지의 길이는 가지와 동형인 순서입니다.각 서수 α에 대하여, T의 α번째 레벨은 높이 α의 T의 모든 원소의 집합입니다.트리는 서수 κ에 해당하는 κ-트리로, 높이 κ를 가지고 모든 레벨이 κ의 카디널리티보다 작은 카디널리티를 가질 경우에만 해당합니다.나무의 너비는 나무 수준의 기본값입니다.

$\leq \omega$ 가 $\leq \omega$ ≤ $\leq \omega$ 인 $\leq \omega$ 모든 단일 근 트리는 조상의 교집합이라는 최대 요소에 의해 주어지는 접선 반격자를 형성하며, 여기서 접선(공통 조상)은 조상의 집합이 비어 있지 않고 유한한 순서로 존재하므로 최대 요소를 갖습니다.단 하나의 근이 없으면 부모의 교집합은 비어 있을 수 있는데, 예를 들어 {a, b } {\displaystyle \left\{a,b\right\}, 만약 무한히 많은 조상이 있다면 최대 원소가 존재할 필요는 없다. 예를 들어 {0, 1, 2, … ω 0, ω 0 ′ } {\displ $aystyle \left\{0,1,2,\$ lota $,\omega$ _ ${$ $0}},\omega$ _{ $0}'\right\},$ 여기서 $ω$ $\omega _{0},\omega _{0}'$ 0 $'$ ${\displaystyle$ \ $omega$ _ ${0$ }},\ $omega$ _ ${$ 0 $}'$ 는 비교할 수 없습니다.

트리 $(T,<)$ < ) $(T,<)$ {\ $displaystyle ($ $T,<)}$ 의 하위 트리는 T $<$ ⊆ T ${\$ $displaystyle$ T'\ $subseteq$ T $<$ 및 $T$ ∈ $s,t\in T$ ∈ {\ $displaystyle$ T $'}$ 가 {\ $displaystyle s,t$ T} $s<t$ s $s,t\in T$ < t {\displaystyle s< $t}$ 에서 아래쪽으로 $(T',<)$ 있는 트리 $(T',<)$ T $(T',<)$ ⟹ $t\in T'\implies s\in T'$ $T'\subseteq T$ ∈ $(T',<)$ T style \ $displaystyle$ $s<t$ t $'$ \ $t\in T'\implies s\in T'$ T $'\in T$ ')입니다. $}$ .^{[citation needed]}

집합론적 성질

무한 트리 이론에는 꽤 간단하게 언급되지만 어려운 문제들이 있습니다.그 예로 쿠레파 추측과 설린 추측이 있습니다.이 두 문제는 모두 저멜로-프랭켈 집합 이론과 독립적인 것으로 알려져 있습니다.키니그의 보조정리에 의하면, 모든 π-나무에는 무한한 가지가 있습니다.한편, 셀 수 없는 가지와 셀 수 없는 레벨이 없는 셀 수 없는 나무가 있다는 것이 ZFC의 정리입니다; 그러한 나무는 Aronzajn 나무로 알려져 있습니다.κ-술린 나무는 κ 크기의 사슬이나 안티체인이 없는 높이 κ의 나무입니다.특히 κ가 단수인 경우 κ-Aronszajn 트리와 κ-Suslin 트리가 존재합니다.사실, 임의의 무한 기수 π에 대하여, 모든 π-설린 트리는 π-아론자인 트리입니다(반대는 성립하지 않습니다).

설린 추측은 원래 특정 총 순서에 대한 질문으로 언급되었지만 다음과 같은 진술과 같습니다.높이 ω의 모든 트리에는 카디널리티 ω 또는 길이 ω의 가지가 있습니다.

그것(T,<)은 트리이고, 그 다음 <의 반사적 폐쇄 ≤는 T의 접두사 순서입니다.역은 성립하지 않습니다. 예를 들어 정수의 집합 Z에서 일반적인 순서 ≤는 총합이므로 접두사 순서이지만 (Z,<) 집합 {n ∈Z: n < 0}에는 최소한의 요소가 없으므로 집합 이론 트리가 아닙니다.

무한 트리의 예

κ ${\displaystyle \kappa$ }을 $($ 를) 순서수라고 하고 $,$ X {\ $displaystyle$ X $}$ 을(를) 집합이라고 합니다.T {\ $displaystyle$ T $}$ 를 모든 $f:\alpha \mapsto X$ f $:$ $f:\alpha \mapsto X$ ↦ $f:\alpha \mapsto X$ ${\displaystyle$ f $:\alpha \mapsto$ X}, $\alpha <\kappa$ 서 $\alpha <\kappa$ α < $\alpha <\kappa$ κ {\ $displaystyle \alpha <\kappa$ $\alpha <\kappa$ 의 집합이라고 $T$ . f{\ $displaystyle$ f} 의 $f$ 이 g{\ $displaystyle$ g $}$ 의 정의역의 적절한 부분 집합이고 두 함수가 f{\ $displaystyle$ f $f$ 의 정의역과 일치할 경우 $f<g$ f < $f<g$ {\ $displaystyle$ f $<g}$ 를 $f<g$ 하자. 그러면 $(T,<)$ $(T,<)$ < $(T,<)$ ) {\ $displaystyle (T,<)}$ 은 $(T,<)$ (는) 집합 이론 트리입니다 $.$ 그것의 루트는 빈 집합의 고유 함수이고, 그것의 높이는 κ $\kappa$ {\ $displaystyle \kappa$ 입니다. 분지를 따라 모든 함수의 결합은 κ $\kappa$ {\ $displaystyle \kappa}$ 에서 X{\ $displaystyle$ X $X$ 까지의 함수, 즉 X ${\displaystyle$ X $X$ 의 멤버들의 일반화된 순서를 산출합니다. 만약 κ $\kappa$ 가 극한 순서라면,어떤 가지도 최대 요소("잎")를 가지고 있지 않습니다.그림은 $X=\{0,1\}$ κ = $X=\{0,1\}$ ω ⋅ ⋅ 2 $\kappa =\omega \cdot 2$ { = \ \ k and \ style display x } { . \ cd $\kappa =\omega \cdot 2$ the \ x appa omega κ \ ot style 2 { for $X=\{0,1\}$ display 1 an shows picture example { $X=\{0,1\}$ ω \ }} 0 , = 1 = } 0 , style \ ⋅

컴퓨터 과학의 각 트리 데이터 구조는 집합 이론 트리입니다. 두 $노드$ m에 $대해$ n ${\displaystyle$ m, $n$ 에 대해n {\ $displaystyle$ n $n$ }이(가 $)$ m {\ $displaystyle$ m}의 올바른 하위인 $경우$ $m<n$ m < $m<n$ ${\displaystyle$ m $<n}$ 을 $m<n$ (를) $m<n$ 합니다.뿌리, 마디 높이 및 가지 길이의 개념은 일치하고, 나무 높이의 개념은 하나씩 다릅니다.

오토마타 이론(예: 트리(오토마타 이론) 참조)에서 고려되는 무한 트리는 또한 최대 ω ${\displaystyle \omega$ 의 트리 높이를 가진 세트 이론 트리입니다.

m ≠ $m\neq n$ {\ $displaystyle$ m $\neq$ n} 및 $m$ ${\displaystyle$ m $}$ 이(가) r{\ $displaystyle$ m $n$ 에서 n{\ $displaystyle$ n}(으)로의 (유일한) 무방향 경로에 있는 $m\neq n$ 루트 $r$ r{\ $displaystyle$ m}을(를) 선택하고 $m<n$ m < $m<n$ ${\displaystyle$ m $<n}$ 을(를) 정의하여 그래프 이론 트리를 집합 이론 트리로 변환할 수 있습니다.

각각의 칸토어 나무, 각각의 쿠레파 나무, 그리고 각각의 레이버 나무는 집합론적인 나무입니다.

참고 항목

참고문헌

Jech, Thomas (2002). Set Theory. Springer-Verlag. ISBN 3-540-44085-2.
Kunen, Kenneth (1980). Set Theory: An Introduction to Independence Proofs. North-Holland. ISBN 0-444-85401-0. 2장 5절.
Monk, J. Donald (1976). Mathematical Logic. New York: Springer-Verlag. p. 517. ISBN 0-387-90170-1.
Hajnal, András; Hamburger, Peter (1999). Set Theory. Cambridge: Cambridge University Press. ISBN 9780521596671.
Kechris, Alexander S. (1995). Classical Descriptive Set Theory. Graduate Texts in Mathematics 156. Springer. ISBN 0-387-94374-9 ISBN 3-540-94374-9.

외부 링크

Ieke Moerdijk 및 Jaap van Oosten에 의한 세트, 모델 및 증명, 페이지 68–69의 정의 3.1 및 연습 56 참조.
행성 수학에 관한 헨리의 트리 (집합 이론)
행성수학에 관한 헨리의 지음
PlanetMath에서 useromay에 의한 트리(집합이론) 예제

Search