나무 (집합론)

틀:위키데이터 속성 추적 순서론과 집합론에서 나무(틀:Llang)는 임의의 원소에 대하여 그 미만의 원소들로 구성된 부분 집합이 정렬 전순서 집합을 이루는 부분 순서 집합이다.

정의

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

순서론적 정의

부분 순서 집합 $(T,\le )$가 다음 조건을 만족시킨다면, 나무라고 한다.

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

나무 $T$의 원소 $t\in T$에 대하여, $T_t$의 순서형인 순서수 ${\mathrm{ht}}_T(t)$를 $t$의 높이라고 한다. 이는 함수

${\mathrm{ht}}_T:T\to \mathrm{Ord}$

를 정의한다. 높이가 0인 원소는 극소 원소이며, 나무의 극소 원소를 뿌리(틀:Llang)라고 한다.

나무 $T$의 $\alpha$번째 단계(段階, 틀:Llang)는 높이 $\alpha$의 원소들의 집합이다. 이를 $\mathrm{lv}(T,\alpha )$로 표기하자. 나무 $T$의 너비(틀:Llang)는 그 단계들의 크기들의 상한이다.

나무 $T$의 높이 $\mathrm{ht}(T)$는 모든 원소들의 높이를 초과하는 최소의 순서수이다.

$\mathrm{ht}(T)=\min \{\alpha \in \mathrm{Ord}:\mathrm{\forall }t\in T:\alpha >{\mathrm{ht}}_T(t)\}$

나무 $T$의 가지(틀:Llang)는 극대 사슬이다. 나무의 가지 역시 정렬 전순서 집합을 이루며, 따라서 가지의 높이를 정의할 수 있다. $T$의 가지들의 집합을 $\mathrm{Br}(T)$라고 하자.

나무 $T$가 다음 두 조건을 만족시킨다면, $T$를 정돈된 나무(整頓-, 틀:Llang)라고 한다.

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

범주론적 정의

임의의 순서수 $\lambda$에 대하여,

$\lambda =\{\alpha \in \mathrm{Ord}:\alpha <\lambda \}$

는 정렬 전순서 집합이므로 작은 얇은 범주로 간주할 수 있다.

높이 $\lambda$ 이하의 나무는 $\lambda$ 위의 준층이다. 즉, 함자

$T:{\lambda }^{\mathrm{op}}\to \mathrm{Set}$

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

• 각 순서수 $\alpha <\lambda$에 대하여, 집합 $T(\alpha )$. 이를 나무 $T$의 $\alpha$번째 단계라고 한다.
• 임의의 두 순서수 $\alpha \le \beta <\lambda$에 대하여, 함수 $f_{\beta \alpha }:S_{\beta }\to S_{\alpha }$.

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

• 임의의 세 순서수 $\alpha \le \beta \le \gamma <\alpha$에 대하여, $f_{\beta \alpha }\circ f_{\gamma \beta }=f_{\gamma \alpha }$
• 임의의 $\alpha <\lambda$에 대하여, $f_{\alpha \alpha }:S_{\alpha }\to S_{\alpha }$는 항등 함수이다.

이 경우, 분리 합집합

$T=\underset{\alpha <\lambda }{⨆}T(\alpha )$

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

$\mathrm{\forall }s\in T(\alpha )\mathrm{\forall }t\in T(\beta ):s\le t⟺(\alpha \le \beta )\wedge (f_{\beta \alpha }(t)=s)$

종류

기수 $\kappa$에 대하여, $\kappa$-아론샤인 나무(틀:Llang)는 다음 세 조건들을 만족시키는 나무 $T$이다.틀:Rp틀:Rp

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

만약 $\kappa$가 주어지지 않았으면 $\kappa ={\mathrm{\aleph }}_1$을 뜻한다.

기수 $\kappa$에 대하여, $\kappa$-수슬린 나무(Суслин-, 틀:Llang)는 다음 조건을 만족시키는 나무이다.틀:Rp

• 높이가 $\kappa$이다.
• 모든 사슬의 크기는 $\kappa$ 미만이다.
• 모든 반사슬의 크기는 $\kappa$ 미만이다.

만약 $\kappa$가 주어지지 않았으면 $\kappa ={\mathrm{\aleph }}_1$을 뜻한다. 모든 단계는 반사슬이므로, $\kappa$-수슬린 나무는 항상 $\kappa$-아론샤인 나무이다.

만약 $\kappa$가 무한 기수라면, 모든 $\kappa$-수슬린 나무는 $\kappa$-아론샤인 나무이나, 그 역은 성립하지 않는다.

기수 $\kappa$에 대하여, $\kappa$-쿠레파 나무(Курепа-, 틀:Llang)는 다음 조건을 만족시키는 나무이다.틀:Rp

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

만약 $\kappa$가 주어지지 않았으면 $\kappa ={\mathrm{\aleph }}_1$을 뜻한다.

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

"${\mathrm{\aleph }}_1$-수슬린 나무(또는 수슬린 직선)가 존재하지 않는다"는 명제를 수슬린 가설(Суслин假說, 틀:Llang) $𝖲𝖧$이라고 한다.틀:Rp틀:Rp "${\mathrm{\aleph }}_1$-쿠레파 나무가 존재한다"는 명제를 쿠레파 가설(Курепа假說, 틀:Llang) $𝖪𝖧$라고 한다.틀:Rp (역사적 이유로 인하여, 수슬린 가설과 쿠레파 가설의 정의는 서로 반대이다.)

$\kappa$-특수 아론샤인 나무(틀:Llang)는 다음 조건을 만족시키는 $\kappa$-아론샤인 나무 $T$이다.틀:Rp

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

구성

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

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

나무 $T$의 마디(틀:Llang)는 다음 조건을 만족시키는 부분 집합 $N\subseteq T$이다.

$\mathrm{\forall }a,b\in N:(\downarrow \{a\})\setminus \{a\}=(\downarrow \{b\})\setminus \{b\}$

나무 $T$가 주어졌으며, 각 마디 $N\subseteq T$에 대하여 $N$ 위의 전순서가 주어졌다고 하자. 그렇다면, 가지 집합 $\mathrm{Br}(T)$ 위에 다음과 같은 전순서를 줄 수 있다.

$B\le B^{\prime }⟺B_{\alpha }\le B{\text{'}}_{\alpha }$

$\alpha =\min \{\beta <\mathrm{ht}T:B(\beta )\ne B^{\prime }(\beta )\}$

이를 $T$의 가지 공간(틀:Llang)이라고 한다.

임의의 기수 $\kappa$에 대하여, 정돈된 나무 $T$가 $\kappa$-강상향 반사슬 조건을 만족시킨다면, $L=\mathrm{Br}(T)$에 대하여, $\mathrm{Open}(L)\setminus \{\varnothing \}$ 역시 $\kappa$-강상향 반사슬 조건을 만족시킨다.

증명:

$T$가 정돈된 나무라고 하자. 즉, 모든 가지들의 높이가 $\mathrm{ht}(T)$라고 하자. 귀류법을 사용하여,

$\{(B_{\alpha },C_{\alpha }){\}}_{\alpha <\kappa }$

가 $\kappa$개의, 공집합이 아닌 서로소 열린구간들의 집합이라고 하자. 그렇다면, 각 $\alpha <\kappa$에 대하여, $D_{\alpha }\in (B_{\alpha },C_{\alpha })$를 고르고, 또한 순서수열

${\delta }_{\alpha }=\max \{d(B_{\alpha },D_{\alpha }),d(D_{\alpha },C_{\alpha })\}$

을 정의하자. 여기서

$d(B,C)=\min \{\mathrm{ht}(T)\setminus \{{\mathrm{ht}}_T(t){\}}_{t\in B\cap C}\}\in \mathrm{Ord}$

는 두 가지가 공유하지 않는 최소의 단계를 뜻하며, 만약 $B\ne C$라면 잘 정의된다.

그렇다면,

$\{D_{\alpha }({\delta }_{\alpha }){\}}_{\alpha <\kappa }\subseteq T$

는 $T$의, 크기 $\kappa$의 (강상향) 반사슬을 이룬다. 따라서 $T$는 $\kappa$-강상향 반사슬 조건을 만족시키지 않는다.

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

최대·최소 원소를 갖지 않는 전순서 집합 $(L,\le )$이 주어졌으며, $L$의 (순서 위상에서의) 최소 조밀 집합의 크기가 $\kappa$라고 하고, 또한 $\kappa$가 무한 기수라고 하자. 그렇다면, $L$의, 공집합이 아닌 열린구간들의 집합 $X=\{(a,b):a<b\}$ 위에 임의의 정렬 전순서 ${\le }^{\circ }$를 부여하였을 때, 다음과 같은 원소열 $=(I_{\alpha }{)}_{\alpha <\kappa }$, $I_{\alpha }=\{x\in L:a_{\alpha }<x<b_{\alpha }\}$을 정의할 수 있다.

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

그렇다면, $\{I_{\alpha }{\}}_{\alpha <\kappa }$는 포함 관계에 대하여 부분 순서 집합을 이루며, 그 반대 부분 순서 집합 $T$는 $L$에 대응하는 나무이다.

수슬린 직선

다음 두 조건을 만족시키는 전순서 집합 $L$을 수슬린 직선(Суслин直線, 틀:Llang)이라고 한다.

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

정돈된 수슬린 직선(整頓-Суслин直線)은 다음 조건을 추가로 만족시키는 수슬린 직선이다.틀:Rp

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

만약 수슬린 직선이 존재한다면, 정돈된 수슬린 직선이 존재한다.틀:Rp

다음이 성립한다.틀:Rp

• 정돈된 ${\mathrm{\aleph }}_1$-수슬린 나무에 대응하는 전순서 집합은 수슬린 직선이다.
• 정돈된 수슬린 직선에 대응하는 나무는 ${\mathrm{\aleph }}_1$-수슬린 나무이다.

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

성질

순서론적 성질

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

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

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

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

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

논리학적 성질

쾨니그 보조정리에 의하면, ${\mathrm{\aleph }}_0$-아론샤인 나무는 존재하지 않는다.틀:Rp ZFC만으로, ${\mathrm{\aleph }}_1$-아론샤인 나무가 존재한다는 것을 증명할 수 있다.틀:Rp 그러나 ${\mathrm{\aleph }}_1$-수슬린 나무의 존재(수슬린 가설)는 (ZFC가 무모순적이라면) ZFC와 독립적이다.

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

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

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

또한, 다음이 성립한다.

• 만약 체르멜로-프렝켈 집합론이 무모순적이라면, 수슬린 가설은 선택 공리를 추가한 체르멜로-프렝켈 집합론과 독립적이다.틀:Rp
• 수슬린 가설은 ZFC+일반화 연속체 가설과 무모순적이며, 또 연속체 가설의 부정과도 무모순적이다.틀:Rp
• 마틴 공리와 연속체 가설의 부정 $𝖬𝖠\wedge \mathrm{\neg }𝖢𝖧$은 수슬린 가설을 함의한다.틀:Rp
• 다이아몬드 원리 $\mathrm{♢}$는 수슬린 가설의 부정을 함의한다. (구성 가능성 공리 $V=L$는 다이아몬드 원리를 함의하므로, 역시 수슬린 가설의 부정을 함의한다.)

ZFC만으로, 모든 분해 가능 공간인 수슬린 직선은 $ℝ$와 순서 동형임을 증명할 수 있다. 이는 게오르크 칸토어가 증명하였다.

강제법

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

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

그렇다면, 강제법 모형 $M[G]$를 생각할 수 있다. 그렇다면, 다음이 성립한다.틀:Rp

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

예

자명한 나무

임의의 집합 $X$에 대하여, 자명한 부분 순서 $a\le b⟺a=b$를 주면, $X$는 나무를 이룬다. 그 높이는 만약 $X$가 공집합이라면 0이며, 만약 $X$가 공집합이 아니라면 1이다.

임의의 순서수 $\alpha$는 (폰 노이만 정의에서) 높이 $\alpha$의 나무를 이룬다.

완비 나무

임의의 순서수 $\alpha$와 집합 $S$에 대하여,

$S^{<\alpha }=\underset{\beta <\alpha }{⨆}{S}^{\beta }$

는 $\beta <\alpha$에 대한 열 $\beta \to S$들의 집합이다. 여기에 부분 순서

$(s_i{)}_{i<\beta }\le (s{\text{'}}_{i^{\prime }}{)}_{i^{\prime }<{\beta }^{\prime }}⟺(\beta \le {\beta }^{\prime })\wedge (s=s^{\prime }\upharpoonright \beta )$

를 부여하면, 이는 높이 $\alpha$의 나무를 이룬다. 이를 높이 $\alpha$의 완비 $S$진 나무(틀:Llang)라고 한다.틀:Rp 만약 $S$가 한원소 집합이라면, 높이 $\alpha$의 완비 $S$진 나무는 $\alpha$와 순서 동형이다.

묘사적 집합론에서의 나무

집합 $S$가 주어졌다고 하자. 그렇다면, 높이 $\omega$의 완비 $S$진 나무 $S^{<\omega }$를 생각하자. 그렇다면, $S^{<\omega }$의 하집합은 나무를 이룬다.

묘사적 집합론(틀:Llang)에서는 위와 같은 나무들을 주로 사용한다.틀:Rp 이러한 나무 $T\subseteq S^{<\omega }$의 경우, 높이 $\omega$의 가지들의 집합은 보통 $[T]$로 표기하며, 나무의 몸통(틀:Llang)이라고 한다.틀:Rp 이 경우, 자연스럽게 $[T]\subseteq S^{\omega }$가 된다.

$S$를 이산 공간으로 간주하며, $S^{\omega }$를 그 가산 무한 곱공간으로 생각하자. 그렇다면, 임의의 부분 집합 $A\subseteq S^{\omega }$에 대하여 다음 두 조건이 서로 동치이다.틀:Rp

• $A=[T]$인 하집합 $T\subseteq S^{<\omega }$가 존재한다.
• $A$는 $S^{\omega }$의 닫힌집합이다.

증명:

임의의 하집합 $T\subseteq S^{<\omega }$에 대하여, 그 몸통의 여집합은

$S^{\omega }\setminus [T]=\bigcup _{n<\omega }\{s\in S^{\omega }:s\upharpoonright n\in ̸T\}$

인데, 우변의 각 항들은 $S^{\omega }$의 열린집합이다.

반대로, 임의의 닫힌집합 $A\subseteq S^{\omega }$가 주어졌다고 하자. 그렇다면, 다음과 같은 나무를 생각하자.

$T=\underset{n<\omega }{⨆}\{s\upharpoonright n:s\in A\}\subseteq S^{<\omega }$

그렇다면, $[T]=A$가 된다.

정렬 전순서 집합 $(S,{\le }_S)$ 및 하집합 $T\subseteq S^{<\omega }$에 대하여, 다음 두 조건이 서로 동치이다.틀:Rp

• $[T]=\varnothing$
• $T$ 위의 (사전식) 전순서 $s{\le }_{\mathrm{KB}}t⟺s\ge t\vee s_{\min \{\alpha :s_{\alpha }\ne t_{\alpha }\}}{<}_S{t}_{\min \{\alpha :s_{\alpha }\ne t_{\alpha }\}}$는 정렬 전순서이다.

틀:증명 만약 $s\in [T]$라면,

$(s_0){>}_{\mathrm{KB}}(s_0,s_1){>}_{\mathrm{KB}}(s_0,s_1,s_2){>}_{\mathrm{KB}}\cdots$

이므로 ${>}_{\mathrm{KB}}$는 정렬 전순서가 아니다.

반대로, 만약

$s^0,s^1,s^2,\dots \in T$

$s^0{>}_{\mathrm{KB}}{s}^1{>}_{\mathrm{KB}}{s}^2{>}_{\mathrm{KB}}\cdots$

라면,

$s_0^0{\ge }_S{s}_0^1{\ge }_S{s}_0^2{\ge }_S\cdots$

이다. $(S,{\le }_S)$가 정렬 전순서 집합이므로,

$a_0=s_0^{n_1}=s_0^{n_1+1}=s_0^{n_1+2}=\cdots$

$n_1<\omega$

인 $a_0\in S$ 및 $n_1<\omega$가 존재한다. 이 경우, $(a_0)\le s^{n_1}$이므로 $(a_0)\in T$이다. 마찬가지로,

$s_1^{n_1}{\ge }_S{s}_1^{n_1+1}{\ge }_S{s}_1^{n_1+2}{\ge }_S\cdots$

이므로,

$a_1=s_1^{n_2}=s_1^{n_2+1}=s_1^{n_2+2}=\cdots$

$n_1\le n_2<\omega$

라고 하자. 이 경우 $(a_0,a_1)\le s^{n_2}$이므로 $(a_0,a_1)\in T$이다. 이를 반복하면

$(a_0,a_1,a_2,\dots )\in [T]$

를 얻는다. 틀:증명 끝

역사

19세기~20세기 초

게오르크 칸토어는 1895년에 최대·최소 원소를 갖지 않는, 분해 가능 선형 연속체가 항상 실수의 전순서 집합과 순서 동형임을 증명하였다.틀:Rp 미하일 수슬린은 1920년에 사후 출판된 원고에서 칸토어의 위 정리에서 분해 가능 공간 조건을 가산 강하향 반사슬 조건으로 약화시키면 어떻게 되는지 여부에 대한 문제를 제시하였다.틀:Rp 이 논문에서 수슬린 가설은 다음과 같이 3번 문제로 수록되어 있다. 틀:인용문2 이후 주로 쿠레파가 수슬린 나무의 개념을 도입하였고, 수슬린 가설을 수슬린 나무로서 서술할 수 있음을 보였다.틀:Rp 이처럼 역사적으로 수슬린 가설은 전순서 집합의 이론에서 유래하였지만, 케네스 쿠넌은 다음과 같이 적었다. 틀:인용문2

아론샤인 나무는 1938년에 주로 쿠레파의 논문에서 최초로 등장하였다. 쿠레파는 이 개념을 "아론샤인 씨의 분기 집합"(틀:Llang)이라고 일컬었으며, 이 논문에서 다음과 같이 적었다. 틀:인용문2

쿠레파 나무 역시 주로 쿠레파가 도입하였다.

20세기 중반~21세기

토마시 예흐(틀:Llang)와 스탠리 테넨바움이 수슬린 나무가 존재하는 강제법 모형을 제시하였다.틀:Rp 곧 또한 로널드 비언 젠슨(틀:Llang)은 다이아몬드 원리를 가정하면 수슬린 나무가 존재함을 증명하였다.틀:Rp

1971년에 로버트 솔로베이와 스탠리 테넨바움은 반복 강제법을 도입하여, 연속체 가설의 부정과 마틴 공리를 가정하면 수슬린 나무가 존재하지 않음을 증명하였다.틀:Rp

같은 해에 잭 하워드 실버(틀:Llang)는 쿠레파 가설 역시 (ZFC가 무모순적이라면) ZFC와 독립적임을 증명하였다.

수슬린 문제에 대하여 메리 엘런 루딘은 다음과 같이 적었다. 틀:인용문2 즉, 수슬린 문제는 사실과 달리 "당연히 참"이거나 "당연히 거짓"인 것처럼 보인다는 것이다.

얀 미치엘스키는 수슬린 가설을 옹호하기 위하여 다음과 같이 적었다. 틀:인용문2

외부 링크

• 틀:Eom
• 틀:Eom
• 틀:Eom
• 틀:매스월드
• 틀:서적 인용
• 틀:웹 인용
• 틀:웹 인용
• 틀:웹 인용
• 틀:웹 인용
• 틀:웹 인용
• 틀:웹 인용
• 틀:웹 인용
• 틀:웹 인용
• 틀:웹 인용
• 틀:웹 인용