나무 (집합론)

순서론과 집합론에서 **나무**(tree)는 임의의 원소에 대하여 그 미만의 원소들로 구성된 부분 집합이 정렬 전순서 집합을 이루는 부분 순서 집합이다.언어=en언어=en
# 정의
나무의 개념은 순서론적으로 특정 조건을 만족시키는 부분 순서 집합으로 정의할 수 있으며, 또 범주론적으로 순서수 위의 준층으로 생각할 수도 있다.
## 순서론적 정의
부분 순서 집합 (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\omega * M 속에서의 정돈된 \kappa-수슬린 나무 T\in M * T의 포괄적 순서 아이디얼 G\subseteq T 그렇다면, 강제법 모형 M[G]를 생각할 수 있다. 그렇다면, 다음이 성립한다.229, Theorem VII.8.4 * M[G] 속에서, 나무 T는 \kappa-수슬린 나무가 아니다.
# 예

## 자명한 나무
임의의 집합 X에 대하여, 자명한 부분 순서 a\le b\iff a=b를 주면, X는 나무를 이룬다. 그 높이는 만약 X가 공집합이라면 0이며, 만약 X가 공집합이 아니라면 1이다. 임의의 순서수 \alpha는 (폰 노이만 정의에서) 높이 \alpha의 나무를 이룬다.
## 완비 나무
임의의 순서수 \alpha와 집합 S에 대하여, :S^{_{\operatorname{KB(s_0,s_1)>_{\operatorname{KB(s_0,s_1,s_2)>_{\operatorname{KB\dotsb 이므로 >_{\operatorname{KB는 정렬 전순서가 아니다. 반대로, 만약 :s^0,s^1,s^2,\dotsc\in T :s^0>_{\operatorname{KBs^1>_{\operatorname{KBs^2>_{\operatorname{KB\dotsb 라면, :s^0_0\ge_Ss^1_0\ge_Ss^2_0\ge_S\dotsb 이다. (S,\le_S)가 정렬 전순서 집합이므로, :a_0=s^{n_1}_0=s^{n_1+1}_0=s^{n_1+2}_0=\dotsb :n_1<\omega 인 a_0\in S 및 n_1<\omega가 존재한다. 이 경우, (a_0)\le s^{n_1}이므로 (a_0)\in T이다. 마찬가지로, :s^{n_1}_1\ge_Ss^{n_1+1}_1\ge_Ss^{n_1+2}_1\ge_S\dotsb 이므로, :a_1=s^{n_2}_1=s^{n_2+1}_1=s^{n_2+2}_1=\dotsb :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,\dotsc)\in[T] 를 얻는다. 증명 끝
# 역사

## 19세기~20세기 초
게오르크 칸토어는 1895년에 최대·최소 원소를 갖지 않는, 분해 가능 선형 연속체가 항상 실수의 전순서 집합과 순서 동형임을 증명하였다.언어=de§11, 510–512 미하일 수슬린은 1920년에 사후 출판된 원고에서 칸토어의 위 정리에서 분해 가능 공간 조건을 가산 강하향 반사슬 조건으로 약화시키면 어떻게 되는지 여부에 대한 문제를 제시하였다.언어=fr223언어=en 이 논문에서 수슬린 가설은 다음과 같이 3번 문제로 수록되어 있다. 3) Un ensemble ordonné (linéairement) sans sauts ni lacunes et tel que tout ensemble de ses intervalles (contenant plus qu’un élément) n’empiétant pas les uns sur les autres est au plus dénumerable, est-il nécessairement un continue linéaire (ordinaire)? Problème de M. M. Souslin. 이후 주로 쿠레파가 수슬린 나무의 개념을 도입하였고, 수슬린 가설을 수슬린 나무로서 서술할 수 있음을 보였다.69, §II.5 이처럼 역사적으로 수슬린 가설은 전순서 집합의 이론에서 유래하였지만, 케네스 쿠넌은 다음과 같이 적었다. 68, §II.5 아론샤인 나무는 1938년에 주로 쿠레파의 논문에서 최초로 등장하였다.언어=fr 쿠레파는 이 개념을 "아론샤인 씨의 분기 집합"(앙상블 라미피에 드 므쇠 아론샤인)이라고 일컬었으며, 이 논문에서 다음과 같이 적었다. 132 쿠레파 나무 역시 주로 쿠레파가 도입하였다.
## 20세기 중반~21세기
토마시 예흐(Tomáš J. Jech)언어=en와 스탠리 테넨바움언어=en이 수슬린 나무가 존재하는 강제법 모형을 제시하였다.§2 곧 또한 로널드 비언 젠슨(Ronald Björn Jensen)은 다이아몬드 원리를 가정하면 수슬린 나무가 존재함을 증명하였다.언어=en§2 1971년에 로버트 솔로베이와 스탠리 테넨바움은 반복 강제법을 도입하여, 연속체 가설의 부정과 마틴 공리를 가정하면 수슬린 나무가 존재하지 않음을 증명하였다.언어=en§3 같은 해에 잭 하워드 실버(Jack Howard Silver)는 쿠레파 가설 역시 (ZFC가 무모순적이라면) ZFC와 독립적임을 증명하였다.언어=en 수슬린 문제에 대하여 메리 엘런 루딘은 다음과 같이 적었다. 언어=en 즉, 수슬린 문제는 사실과 달리 "당연히 참"이거나 "당연히 거짓"인 것처럼 보인다는 것이다. 얀 미치엘스키는 수슬린 가설을 옹호하기 위하여 다음과 같이 적었다. 209