나무 (집합론)

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

나무(tree)는 순서론적 또는 범주론적으로 정의되는 수학적 구조이다. 순서론적으로는 특정 조건을 만족하는 부분 순서 집합으로 정의되며, 범주론적으로는 순서수 위의 준층으로 생각할 수 있다. 트리 구조는 그래프 이론, 컴퓨터 과학, 오토마타 이론 등 다양한 분야에서 활용된다. 나무의 종류로는 아론샤인 나무, 수슬린 나무, 쿠레파 나무 등이 있으며, 이들은 높이, 가지, 단계의 조건에 따라 구분된다. 수슬린 가설과 쿠레파 가설은 집합론과 관련된 중요한 문제로, ZFC 공리계와 독립적임이 밝혀졌다.

2. 정의

순서론적으로 나무는 특정 조건을 만족시키는 부분 순서 집합으로 정의할 수 있으며, 범주론적으로는 순서수 위의 준층으로 생각할 수도 있다.

'''트리'''는 각 $t \in T$ 에 대해 집합 $\{s \in T : s < t\}$ 가 관계 $<$ 에 의해 정렬 전순서 집합인 부분 순서 집합 $(T, <)$ 이다. 특히 각 전순서 집합 $(T, <)$ 는 트리이다.

단일 루트를 가진 트리는 그래프 이론의 루트가 있는 트리로 볼 수 있는데, 트리(그래프 이론) 또는 자명하게 완전한 그래프로 볼 수 있다. 그러나 $T$ 가 ω보다 큰 높이를 가지는 경우 하세 다이어그램 정의는 작동하지 않는다. 예를 들어, 부분 순서 집합 $\omega + 1 = \{0, 1, 2, \dots, \omega\}$ 는 ω의 이전 요소가 없으므로 하세 다이어그램이 없다.

높이가 $\leq \omega$ 인 단일 루트 트리는 교집합의 최대 요소가 주어지는 만남 반격자(meet-semilattice)를 형성한다. 단일 루트가 없으면 부모의 교집합이 비어 있을 수 있다. (예: $\{a, b\}$ ). 무한한 수의 조상이 있는 경우 최대 요소가 없을 수도 있다. (예: $\{0, 1, 2, \dots, \omega_0, \omega_0'\}$ 에서 $\omega_0, \omega_0'$ 은 비교 불가).

트리 $(T,<)$ 의 '''서브트리'''는 $(T',<)$ 트리이며 $T' \subseteq T$ 이고 $T'$ 가 $<$ 에 따라 아래로 닫혀 있다.

2. 1. 순서론적 정의

부분 순서 집합

(T,\le)

가 다음 조건을 만족하면 '''나무'''라고 부른다.

임의의 $s\in T$ 에 대하여, 하집합 $T_s=\{t\in T\colon t 는 정렬 전순서 집합이다.$

나무

T

의 원소

t\in T

에 대하여,

T_t

의 순서형인 순서수

\operatorname{ht}_T(t)

를

t

의 '''높이'''라고 한다. 이는 함수

:

\operatorname{ht}_T\colon T\to\operatorname{Ord}

를 정의한다. 높이가 0인 원소는 극소 원소이며, 나무의 극소 원소를 '''뿌리'''(root^영어)라고 한다.

나무

T

의

\alpha

번째 '''단계'''(段階, level^영어)는 높이

\alpha

의 원소들의 집합이다. 이를

\operatorname{lv}(T,\alpha)

로 표기한다. 나무

T

의 '''너비'''(width^영어)는 그 단계들의 크기들의 상한이다.

나무

T

의 '''높이'''

\operatorname{ht}(T)

는 모든 원소들의 높이를 초과하는 최소의 순서수이다.

:

\operatorname{ht}(T)=\min\left\{\alpha\in\operatorname{Ord}\colon \forall t\in T\colon\alpha>\operatorname{ht}_T(t)\right\}

나무

T

의 '''가지'''(branch^영어)는 극대 사슬이다. 나무의 가지 역시 정렬 전순서 집합을 이루며, 따라서 가지의 '''높이'''를 정의할 수 있다.

T

의 가지들의 집합을

\operatorname{Br}(T)

라고 하자.

나무

T

가 다음 두 조건을 만족시킨다면,

T

를 '''정돈된 나무'''(整頓-, well pruned tree^영어)라고 한다.

임의의 순서수 $\alpha<\beta<\operatorname{ht}T$ 및 높이 $\alpha$ 의 원소 $s\in T$ 에 대하여, $s 이자 \operatorname{ht}_T(t)=\beta 인 원소 t\in T 가 존재한다.$
뿌리가 유일하다.

작은 유한 예시: 왼쪽의 세 부분 순서 집합은 트리(파란색)이며, 트리의 한 '가지'가 강조 표시되어 있습니다(녹색). 오른쪽의 부분 순서 집합(빨간색)은 $x_1 < x_3$ 및 $x_2 < x_3$ 이지만 $x_1$ 은 $x_2$ 와 비교할 수 없기 때문에 트리(점선 주황색 선)가 아닙니다.

2. 2. 범주론적 정의

높이 λ 이하의 '''나무'''는 λ 위의 준층으로 정의할 수 있다. 즉, 함자

:T: λ^op → Set

이다. 이는 구체적으로 다음과 같은 데이터로 구성된다.

각 순서수 α < λ에 대하여, 집합 T(α). 이를 나무 T의 α번째 '''단계'''라고 한다.
임의의 두 순서수 α ≤ β < λ에 대하여, 함수 f_βα: S_β → S_α.

이 데이터는 다음과 같은 함자 조건을 만족시켜야 한다.

임의의 세 순서수 α ≤ β ≤ γ < α에 대하여, f_βα ∘ f_γβ = f_γα
임의의 α < λ에 대하여, f_αα: S_α → S_α는 항등 함수이다.

이 경우, 분리 합집합

:T = ∐_α<λT(α)

위에 다음과 같은 부분 순서를 줄 수 있다.

:∀ s ∈ T(α) ∀ t ∈ T(β): s ≤ t ⇔ (α ≤ β) ∧ (f_βα(t) = s)

3. 종류

여러 기준에 따라 다양한 종류의 트리가 존재한다.

기수 $\kappa$ 에 대해, $\kappa$ -아론샤인 나무, $\kappa$ -수슬린 나무, $\kappa$ -쿠레파 나무 등이 정의된다. 이 세 종류의 나무는 다음 표와 같은 조건을 만족시킨다.^[6]

이름	높이 조건	가지 조건	단계 조건
$\kappa$ -수슬린 나무	높이가 $\kappa$ 이다.	모든 가지의 크기는 $\kappa$ 미만이다.	모든 반사슬의 크기는 $\kappa$ 미만이다.
$\kappa$ -아론샤인 나무		모든 가지의 크기는 $\kappa$ 미만이다.	모든 단계의 크기는 $\kappa$ 미만이다.
$\kappa$ -쿠레파 나무		크기 $\kappa$ 의 가지의 수가 $\kappa$ 초과이다.	모든 단계의 크기는 $\kappa$ 미만이다.

수슬린 가설( $\mathsf{SH}$ )은 " $\aleph_1$ -수슬린 나무가 존재하지 않는다"는 명제이며, 쿠레파 가설( $\mathsf{KH}$ )은 " $\aleph_1$ -쿠레파 나무가 존재한다"는 명제이다.^[6]^[1] (역사적 이유로 수슬린 가설과 쿠레파 가설의 정의는 서로 반대이다.)

쾨니그의 보조정리에 따르면, 모든 ω-나무는 무한 가지를 갖는다.

무한 나무 이론에는 비교적 간단하게 제시되었지만 어려운 문제가 몇 가지 있다. 이러한 예로는 쿠레파 추측과 수슬린 추측이 있다. 이 두 문제는 모두 체르멜로-프렝켈 집합론과는 독립적인 것으로 알려져 있다.

(''T'', <)가 나무이면, <의 반사적 폐포 ≤는 ''T''에 대한 접두 순서이다. 그 역은 성립하지 않는다. 예를 들어, 정수 집합 '''Z'''에 대한 일반적인 순서 ≤는 전순서이므로 접두 순서이지만, ('''Z''', <)는 예를 들어 집합 {''n'' ∈'''Z''': ''n'' < 0}에 최소 원소가 없기 때문에 집합론적 나무가 아니다.

3. 1. 수슬린 나무 (Souslin tree)

Souslin tree^영어는 높이가

\kappa

이고, 모든 사슬과 반사슬의 크기가

\kappa

미만인 나무이다.^[6]

\kappa

가 주어지지 않았으면

\kappa=\aleph_1

을 뜻한다. 모든 단계는 반사슬이므로,

\kappa

-수슬린 나무는 항상

\kappa

-아론샤인 나무이다.

\kappa

가 무한 기수라면, 모든

\kappa

-수슬린 나무는

\kappa

-아론샤인 나무이나, 그 역은 성립하지 않는다.

"

\aleph_1

-수슬린 나무(또는 수슬린 직선)가 존재하지 않는다"는 명제를 '''수슬린 가설'''(Souslin’s hypothesis^영어)

\mathsf{SH}

이라고 한다.^[4]^[6]^[1]

수슬린 추측은 원래 특정 전순서 집합에 대한 질문으로 제시되었지만, 높이가 ω₁인 모든 나무는 크기 ω₁의 반사슬 또는 길이 ω₁의 가지를 갖는다는 명제와 동등하다.

3. 2. 아론샤인 나무 (Aronszajn tree)

기수

\kappa

에 대하여, '''

\kappa

-아론샤인 나무'''(

\kappa

-Aronszajn tree^영어)는 다음 세 조건들을 만족시키는 나무

T

이다.^[6]^[1]

높이가 $\kappa$ 이다.
모든 가지의 크기는 $\kappa$ 미만이다.
모든 단계의 크기는 $\kappa$ 미만이다.

만약

\kappa

가 주어지지 않았으면

\kappa=\aleph_1

을 뜻한다.

모든 단계는 반사슬이므로,

\kappa

-수슬린 나무는 항상

\kappa

-아론샤인 나무이다.

\kappa

가 무한 기수라면, 모든

\kappa

-수슬린 나무는

\kappa

-아론샤인 나무이나, 그 역은 성립하지 않는다.

'''

\kappa

-특수 아론샤인 나무'''(special Aronszajn tree^영어)는 다음 조건을 만족시키는

\kappa

-아론샤인 나무

T

이다.^[6]

$T$ 는 $\kappa$ 미만 개의 반사슬들의 합집합이다.

ZFC의 정리에 따르면, 무한 가지와 무한 레벨이 없는 비가산 나무가 존재하며, 이러한 나무는 아론샤인 나무로 알려져 있다. 기수 κ가 주어졌을 때, "κ-수슬린 나무"는 크기가 κ인 사슬이나 반사슬이 없는 높이 κ인 나무이다. 특히, κ가 특이 기수이면, κ-아론샤인 나무와 κ-수슬린 나무가 존재한다.

3. 3. 쿠레파 나무 (Kurepa tree)

기수

\kappa

에 대하여, '''

\kappa

-쿠레파 나무'''(Kurepa tree^영어)는 다음 조건을 만족시키는 나무이다.^[6]^[3]

높이가 $\kappa$ 이다.
크기 $\kappa$ 의 가지의 수가 $\kappa$ 를 초과한다.
모든 단계의 크기는 $\kappa$ 미만이다.

만약

\kappa

가 주어지지 않았으면

\kappa=\aleph_1

을 뜻한다.

"

\aleph_1

-쿠레파 나무가 존재한다"는 명제를 '''쿠레파 가설'''(Курепа假說, Kurepa hypothesis^영어)

\mathsf{KH}

라고 한다.^[6]

4. 구성

일부 나무는 특정 전순서 집합과 밀접한 관계를 갖는다.

4. 1. 나무에 대응하는 전순서 집합

나무

T

의 각 마디

N\subseteq T

에 전순서가 주어졌다고 하자. 그렇다면, 가지 집합

\operatorname{Br}(T)

위에 다음과 같은 전순서를 줄 수 있다.

:

B\le B'\iff B_\alpha\le B'_\alpha

:

\alpha=\min\{\beta<\operatorname{ht}T\colon B(\beta)\ne B'(\beta)\}

이를

T

의 '''가지 공간'''(branch space^영어)이라고 한다.^[5]

4. 2. 전순서 집합에 대응하는 나무

최대 원소 및 최소 원소를 갖지 않는 전순서 집합

(L,\le)

이 주어졌고,

L

의 (순서 위상에서의) 최소 조밀 집합의 크기가 무한 기수

\kappa

라고 하자. 그렇다면,

L

의, 공집합이 아닌 열린구간들의 집합

X=\{(a,b)\colon a 위에 임의의 정렬 전순서 \le^\circ 를 부여하였을 때, 다음과 같은 원소열 =(I_\alpha)_{\alpha<\kappa}, I_\alpha=\{x\in L\colon a_\alpha 을 정의할 수 있다.

$I_\alpha$ 는 $\textstyle\bigcup_{\beta<\alpha}\{a_\alpha,b_\beta\}$ 와 서로소인, $\le^\circ$ -최소 열린구간이다.

그렇다면,

\{I_\alpha\}_{\alpha<\kappa}

는 포함 관계에 대하여 부분 순서 집합을 이루며, 그 반대 부분 순서 집합

T

는

L

에 대응하는 나무이다.

4. 3. 수슬린 직선 (Souslin line)

전순서 집합

L

이 다음 두 조건을 만족시키면 '''수슬린 직선'''(Souslin line^영어)이라고 한다.^[6]

$\operatorname{Open}(L)\setminus\{\varnothing\}$ 은 가산 강하향 반사슬 조건을 만족시킨다. 여기서 $\operatorname{Open}(L)\setminus\{\varnothing\}\subseteq\mathcal P(L)$ 은 ( $L$ 의 순서 위상에서) $L$ 의 공집합이 아닌 열린집합들의 집합족이다.
분해 가능 공간이 아니다.

'''정돈된 수슬린 직선'''은 다음 조건을 추가로 만족시키는 수슬린 직선이다.^[6]

$L$ 은 최소 원소와 최대 원소를 갖지 않는다.
$L$ 은 선형 연속체이다.

만약 수슬린 직선이 존재한다면, 정돈된 수슬린 직선이 존재한다.^[6]

다음이 성립한다.^[6]

정돈된 $\aleph_1$ -수슬린 나무에 대응하는 전순서 집합은 수슬린 직선이다.
정돈된 수슬린 직선에 대응하는 나무는 $\aleph_1$ -수슬린 나무이다.

따라서, 수슬린 나무의 존재와 수슬린 직선의 존재는 서로 동치이다.^[7]

5. 성질

무한 나무 이론에는 쿠레파 추측과 수슬린 추측과 같이 간단해 보이지만 어려운 문제들이 있다. 이 두 문제는 모두 체르멜로-프렝켈 집합론과 독립적이다.^[6] 쾨니그의 보조정리에 따르면, 모든 ω-나무는 무한 가지를 갖는다. 반면, ZFC에서는 무한 가지와 무한 레벨이 없는 비가산 나무가 존재하며, 이를 아론자이 나무라고 한다.

기수 κ에 대해, "κ-수슬린 나무"는 크기가 κ인 사슬이나 반사슬이 없는 높이 κ인 나무이다. 특히 κ가 특이 기수이면 κ-아론자이 나무와 κ-수슬린 나무가 존재한다. 모든 무한 기수 κ에 대해, 모든 κ-수슬린 나무는 κ-아론자이 나무이지만, 그 역은 성립하지 않는다.

수슬린 추측은 원래 특정 전순서 집합에 대한 질문이었지만, 높이가 ω₁인 모든 나무는 크기 ω₁의 반사슬 또는 길이 ω₁의 가지를 갖는다는 명제와 동등하다.

(''T'', <)가 나무이면, <의 반사적 폐포 ≤는 ''T''에 대한 접두 순서이다. 그 역은 성립하지 않는다. 예를 들어, 정수 집합 '''Z'''에 대한 일반적인 순서 ≤는 전순서이므로 접두 순서이지만, ('''Z''', <)는 집합 {''n'' ∈'''Z''': ''n'' < 0}에 최소 원소가 없기 때문에 집합론적 나무가 아니다.

5. 1. 순서론적 성질

나무에서, 모든 반사슬은 강상향 반사슬이다. 즉, 반사슬과 강상향 반사슬 개념은 일치한다.

나무의 경우 다음 두 조건은 서로 동치이다.

하향 원순서 집합이다.
정확히 한 개의 뿌리를 갖는다.

다음 세 개념은 서로 동치이다.

전순서 집합인 나무
모든 단계가 한원소 집합이거나 공집합인 나무
정렬 전순서 집합

5. 2. 논리학적 성질

쾨니그 보조정리에 의하면,

\aleph_0

-아론샤인 나무는 존재하지 않는다.^[6] ZFC만으로

\aleph_1

-아론샤인 나무가 존재함을 증명할 수 있다.^[6] 그러나

\aleph_1

-수슬린 나무의 존재(수슬린 가설)는 (ZFC가 무모순적이라면) ZFC와 독립적이다.

만약 구성 가능성 공리

V=L

이 참이라면, 모든 순서수

\alpha

에 대하여

\aleph_{\alpha+1}

-수슬린 나무가 존재한다.

도달 불가능한 기수

\kappa

에 대하여 다음 두 조건은 서로 동치이다.

$\kappa$ -아론샤인 나무는 존재하지 않는다.
약콤팩트 기수이다.

또한, 다음이 성립한다.

체르멜로-프렝켈 집합론이 무모순적이라면, 수슬린 가설은 선택 공리를 추가한 체르멜로-프렝켈 집합론과 독립적이다.^[6]
수슬린 가설은 ZFC+일반화 연속체 가설과 무모순적이며, 연속체 가설의 부정과도 무모순적이다.^[6]
마틴 공리와 연속체 가설의 부정 $\mathsf{MA}\land\lnot\mathsf{CH}$ 은 수슬린 가설을 함의한다.^[6]^[8]
다이아몬드 원리 $\diamondsuit$ 는 수슬린 가설의 부정을 함의한다. (구성 가능성 공리 $V=L$ 는 다이아몬드 원리를 함의하므로, 역시 수슬린 가설의 부정을 함의한다.)

ZFC만으로, 모든 분해 가능 공간인 수슬린 직선은

\mathbb R

와 순서 동형임을 증명할 수 있다. 이는 게오르크 칸토어가 증명하였다.

다음 데이터가 주어졌다고 하자.

ZFC의 표준 추이적 모형 $M$
$M$ 속에서의 비가산 정칙 기수 $\kappa\in\operatorname{Card}^M$ , $\kappa>\omega$
$M$ 속에서의 정돈된 $\kappa$ -수슬린 나무 $T\in M$
$T$ 의 포괄적 순서 아이디얼 $G\subseteq T$

그렇다면, 강제법 모형

M[G]

를 생각할 수 있다. 그렇다면, 다음이 성립한다.^[6]

$M[G]$ 속에서, 나무 $T$ 는 $\kappa$ -수슬린 나무가 아니다.

무한 나무 이론에는 비교적 간단하지만 어려운 문제가 몇 가지 있다. 이러한 예로는 쿠레파 추측과 수슬린 추측이 있다. 이 두 문제는 모두 체르멜로-프렝켈 집합론과는 독립적인 것으로 알려져 있다. 쾨니그의 보조정리에 따르면, 모든 ω-나무는 무한 가지를 갖는다. 반면, ZFC의 정리에 따르면, 무한 가지와 무한 레벨이 없는 비가산 나무가 존재하며, 이러한 나무는 아론자이 나무로 알려져 있다. 기수 κ가 주어졌을 때, "κ-수슬린 나무"는 크기가 κ인 사슬이나 반사슬이 없는 높이 κ인 나무이다. 특히, κ가 특이 기수이면, κ-아론자이 나무와 κ-수슬린 나무가 존재한다. 실제로, 모든 무한 기수 κ에 대해, 모든 κ-수슬린 나무는 κ-아론자이 나무이다(그 역은 성립하지 않는다).

수슬린 추측은 원래 특정 전순서 집합에 대한 질문으로 제시되었지만, 높이가 ω₁인 모든 나무는 크기 ω₁의 반사슬 또는 길이 ω₁의 가지를 갖는다는 명제와 동등하다.

6. 역사

쾨니그 보조정리에 의하면, $\aleph_0$ -아론샤인 나무는 존재하지 않는다.^[6] ZFC만으로는 $\aleph_1$ -아론샤인 나무가 존재함을 증명할 수 있다.^[6] 그러나 $\aleph_1$ -수슬린 나무의 존재(수슬린 가설)는 ZFC와 독립적이다. (ZFC가 무모순적이라면)

만약 구성 가능성 공리 $V=L$ 이 참이라면, 모든 순서수 $\alpha$ 에 대하여 $\aleph_{\alpha+1}$ -수슬린 나무가 존재한다.

도달 불가능한 기수 $\kappa$ 에 대하여 다음 두 조건은 서로 동치이다.

$\kappa$ -아론샤인 나무는 존재하지 않는다.
약콤팩트 기수이다.

또한, 다음이 성립한다.

체르멜로-프렝켈 집합론이 무모순적이라면, 수슬린 가설은 선택 공리를 추가한 체르멜로-프렝켈 집합론과 독립적이다.^[6]
수슬린 가설은 ZFC+일반화 연속체 가설과 무모순적이며, 연속체 가설의 부정과도 무모순적이다.^[6]
마틴 공리와 연속체 가설의 부정 ( $\mathsf{MA}\land\lnot\mathsf{CH}$ )은 수슬린 가설을 함의한다.^[6]^[8]
다이아몬드 원리 $\diamondsuit$ 는 수슬린 가설의 부정을 함의한다. (구성 가능성 공리 $V=L$ 는 다이아몬드 원리를 함의하므로, 역시 수슬린 가설의 부정을 함의한다.)

ZFC만으로, 모든 분해 가능 공간인 수슬린 직선은

\mathbb R

와 순서 동형임을 증명할 수 있다. 이는 게오르크 칸토어가 증명하였다.

무한 나무 이론에는 비교적 간단하지만 어려운 문제가 몇 가지 있다. 쿠레파 추측과 수슬린 추측이 그 예시이다. 이 두 문제는 모두 체르멜로-프렝켈 집합론과는 독립적이다. 쾨니그의 보조정리에 따르면, 모든 ω-나무는 무한 가지를 갖는다. 반면, ZFC의 정리에 따르면, 무한 가지와 무한 레벨이 없는 비가산 나무가 존재하며, 이러한 나무는 아론자이 나무로 알려져 있다. 기수 κ가 주어졌을 때, "κ-수슬린 나무"는 크기가 κ인 사슬이나 반사슬이 없는 높이 κ인 나무이다. 특히, κ가 특이 기수이면, κ-아론자이 나무와 κ-수슬린 나무가 존재한다. 실제로, 모든 무한 기수 κ에 대해, 모든 κ-수슬린 나무는 κ-아론자이 나무이다(그 역은 성립하지 않는다).

수슬린 추측은 원래 특정 전순서 집합에 대한 질문으로 제시되었지만, 높이가 ω₁인 모든 나무는 크기 ω₁의 반사슬 또는 길이 ω₁의 가지를 갖는다는 명제와 동등하다.

7. 예

게오르크 칸토어는 1895년에 최대·최소 원소를 갖지 않는 분해 가능 선형 연속체가 항상 실수의 전순서 집합과 순서 동형임을 증명하였다.^[10] 미하일 수슬린은 1920년에 사후 출판된 원고에서 칸토어의 정리에서 분해 가능 공간 조건을 가산 강하향 반사슬 조건으로 약화했을 때 어떤 결과가 나오는지에 대한 문제를 제시하였다.^[11]^[12] 이후 주로 쿠레파가 수슬린 나무의 개념을 도입하였고, 수슬린 가설을 수슬린 나무로 서술할 수 있음을 보였다.^[7]^[6]

아론샤인 나무는 1938년에 주로 쿠레파의 논문에서 최초로 등장하였다. 쿠레파는 이 개념을 "아론샤인 씨의 분기 집합"(ensemble ramifié de M. Aronszajn|앙상블 라미피에 드 므쇠 아론샤인^프랑스어)이라고 일컬었다.^[13] 쿠레파 나무 역시 주로 쿠레파가 도입하였다.

토마시 예흐(Tomáš J. Jech^cs)^[14]와 스탠리 테넨바움^[15]은 수슬린 나무가 존재하는 강제법 모형을 제시하였다.^[12] 로널드 비언 젠슨(Ronald Björn Jensen^영어)은 다이아몬드 원리를 가정하면 수슬린 나무가 존재함을 증명하였다.^[16]^[12]

1971년에 로버트 솔로베이와 스탠리 테넨바움은 반복 강제법을 도입하여, 연속체 가설의 부정과 마틴 공리를 가정하면 수슬린 나무가 존재하지 않음을 증명하였다.^[17]^[12] 같은 해에 잭 하워드 실버(Jack Howard Silver^영어)는 쿠레파 가설 역시 (ZFC가 무모순적이라면) ZFC와 독립적임을 증명하였다.^[18]

'''트리'''는 각 ''t'' ∈ ''T''에 대해 집합 {''s'' ∈ ''T'' : ''s'' < ''t''}가 관계 <에 의해 전순서 집합인 부분 순서 집합(poset) (''T'', <)이다. 각 ''t'' ∈ ''T''에 대해 {''s'' ∈ ''T'' : ''s'' < ''t''}의 순서형을 ''높이''라고 하며, ht(''t'', ''T'')로 표기한다. ''T'' 자체의 ''높이''는 ''T''의 각 요소의 높이보다 큰 가장 작은 서수이다. 트리 ''T''의 ''루트''는 높이 0인 요소이다. 집합론의 트리는 종종 루트가 가장 큰 노드가 되도록 아래쪽으로 성장하도록 정의된다.

트리의 ''가지''는 트리에서 최대 체인이다. 가지의 ''길이''는 가지와 순서 동형인 서수이다. 각 서수 α에 대해 ''T''의 ''α-번째 레벨''은 높이 α인 ''T''의 모든 요소 집합이다. 트리는 서수 κ에 대해 κ-트리인데, 이는 높이가 κ이고 모든 레벨의 기수가 κ의 기수보다 작을 경우이다. 트리의 ''너비''는 레벨의 기수의 상한이다.

높이가 $\omega \cdot 2$ 이고 너비가 $2^{\omega \cdot 2}$ 인 집합론적 트리. 각 노드는 빨간색과 녹색 선의 교차점에 해당합니다.

$\kappa$ 를 서수, $X$ 를 집합이라고 하자. $T$ 를 $\alpha < \kappa$ 인 모든 함수 $f:\alpha \mapsto X$ 의 집합이라고 하고, $f < g$ 를 $f$ 의 정의역이 $g$ 의 정의역의 진부분집합이고 두 함수가 $f$ 의 정의역에서 일치하는 경우로 정의하면 $(T,<)$ 는 집합론적 트리이다. 그 루트는 빈 집합에 대한 고유한 함수이며, 그 높이는 $\kappa$ 이다.

컴퓨터 과학의 각 트리 자료 구조는 집합론적 트리이다.

오토마타 이론에서 고려되는 무한 트리 (예: ''트리 (오토마타 이론)'')도 트리 높이가 최대 $\omega$ 인 집합론적 트리이다.

그래프 이론적 트리는 루트 노드 $r$ 을 선택하고 정의하여 집합론적 트리로 변환할 수 있다.

각 칸토어 트리, 각 쿠레파 트리, 각 라버 트리는 집합론적 트리이다.

7. 1. 자명한 나무

임의의 집합

X

에 대하여, 자명한 부분 순서

a\le b\iff a=b

를 정의하면,

X

는 나무가 된다.^[1] 이때,

X

가 공집합이면 나무의 높이는 0이고, 공집합이 아니면 높이는 1이다.^[1]

임의의 순서수

\alpha

는 (폰 노이만 정의에서) 높이가

\alpha

인 나무를 이룬다.^[2]

7. 2. 완비 나무

임의의 순서수 $\alpha$와 집합 $S$에 대하여, $S^{<\alpha}=\bigsqcup_{\beta<\alpha}S^\beta$는 $\beta<\alpha$에 대한 열 $\beta\to S$들의 집합이다. 여기에 부분 순서 $(s_i)_{i<\beta}\le(s'_{i'})_{i'<\beta'}\iff (\beta\le\beta')\land (s=s'\restriction\beta)$를 부여하면, 이는 높이 $\alpha$의 나무를 이룬다. 이를 높이 $\alpha$의 '''완비 $S$진 나무'''(complete $S$-ary tree^영어)라고 한다.^[6] 만약 $S$가 한원소 집합이라면, 높이 $\alpha$의 완비 $S$진 나무는 $\alpha$와 순서 동형이다.

7. 3. 묘사적 집합론에서의 나무

묘사적 집합론에서는 주로 집합 ''S''^<ω (높이 ω의 완비 ''S''진 나무)의 하집합으로 표현되는 나무들을 사용한다.^[9] 이러한 나무 ''T'' ⊆ ''S''^<ω의 경우, 높이 ω의 가지들의 집합을 [''T'']로 표기하며, 이를 나무의 몸통(body)이라고 부른다.^[9] 이때 [''T''] ⊆ ''S''^ω가 성립한다.

''S''를 이산 공간으로, ''S''^ω를 그 가산 무한 곱공간으로 생각하면, 임의의 부분 집합 ''A'' ⊆ ''S''^ω에 대해 다음 두 조건은 서로 동치이다.^[9]

''A'' = [''T'']인 하집합 ''T'' ⊆ ''S''^<ω가 존재한다.
''A''는 ''S''^ω의 닫힌집합이다.

즉, 묘사적 집합론에서 다루는 나무의 몸통은 ''S''^ω의 닫힌집합과 대응된다는 것을 알 수 있다.

참조

_[1] 저널 Trees 1971-03
_[2] 서적 Handbook of set-theoretic topology https://archive.org/[...] North-Holland
_[3] 저널 Algebraic equivalents of Kurepa’s hypotheses http://projecteuclid[...] 2000
_[4] 서적 The Souslin problem 1974
_[5] 저널 Branch space representations of lines 2005-06-01
_[6] 서적 Set theory: an introduction to independence proofs http://store.elsevie[...] North-Holland 1980
_[7] 서적 Ensembles ordonnés et ramifiés http://elibrary.matf[...] 베오그라드 대학교 1935
_[8] 저널 Internal Cohen extensions 1970-10
_[9] 서적 Classical descriptive set theory Springer-Verlag 1995
_[10] 저널 Beiträge zur Begründung der transfiniten Mengenlehre (Erster Artikel) http://www.digizeits[...]
_[11] 저널 Problèmes http://pldml.icm.edu[...] 1920
_[12] 서적 Set theory, arithmetic, and foundations of mathematics. Theorems, philosophies Cambridge University Press 2011
_[13] 저널 Ensembles linéares et une classe de tableaux ramifiés (tableaux ramifiés de M. Aronszajn) http://elib.mi.sanu.[...] 1938
_[14] 저널 Non-provability of Souslin’s hypothesis http://dml.cz/handle[...]
_[15] 저널 Souslin’s problem 1968-01
_[16] 저널 Souslin’s Hypothesis is incompatible with ''V''=''L'' 1968
_[17] 저널 Iterated Cohen extensions and Souslin’s problem
_[18] 서적 Axiomatic set theory. Part 1 American Mathematical Society 1971
_[19] 저널 Souslin’s conjecture 1969-12
_[20] 저널 A system of axioms of set theory for the rationalists http://www.ams.org/n[...] 2006-02

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com