나무 (집합론)

1. 개요

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

2. 정의

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

트리는 각 $t\; \backslash in\; T$에 대해 집합 가 관계 에 의해 정렬 전순서 집합인 부분 순서 집합 이다. 특히 각 전순서 집합 는 트리이다.

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

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

트리 의 서브트리는 트리이며 $T\text{'}\; \backslash subseteq\; T$이고 $T\text{'}$가 에 따라 아래로 닫혀 있다.

2.1. 순서론적 정의

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

* 임의의 $s\backslash in\; T$에 대하여, 하집합

나무 $T$의 원소 $t\backslash in\; T$에 대하여, $T\_t$의 순서형인 순서수 $\backslash operatorname\{ht\}\_T(t)$를 $t$의 높이라고 한다. 이는 함수
:$\backslash operatorname\{ht\}\_T\backslash colon\; T\backslash to\backslash operatorname\{Ord\}$
를 정의한다. 높이가 0인 원소는 극소 원소이며, 나무의 극소 원소를 뿌리(root^영어)라고 한다.

나무 $T$의 $\backslash alpha$번째 단계(段階, level^영어)는 높이 $\backslash alpha$의 원소들의 집합이다. 이를 $\backslash operatorname\{lv\}(T,\backslash alpha)$로 표기한다. 나무 $T$의 너비(width^영어)는 그 단계들의 크기들의 상한이다.

나무 $T$의 높이 $\backslash operatorname\{ht\}(T)$는 모든 원소들의 높이를 초과하는 최소의 순서수이다.
:$\backslash operatorname\{ht\}(T)=\backslash min\backslash left\backslash \{\backslash alpha\backslash in\backslash operatorname\{Ord\}\backslash colon\; \backslash forall\; t\backslash in\; T\backslash colon\backslash alpha>\backslash operatorname\{ht\}\_T(t)\backslash right\backslash \}$

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

나무 $T$가 다음 두 조건을 만족시킨다면, $T$를 정돈된 나무(整頓-, well pruned tree^영어)라고 한다.
* 임의의 순서수 및 높이 $\backslash alpha$의 원소 $s\backslash in\; T$에 대하여,
* 뿌리가 유일하다.

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. 종류

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

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

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

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

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

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

3.1. 수슬린 나무 (Souslin tree)

Souslin tree^영어는 높이가 $\backslash kappa$이고, 모든 사슬과 반사슬의 크기가 $\backslash kappa$ 미만인 나무이다. $\backslash kappa$가 주어지지 않았으면 $\backslash kappa=\backslash aleph\_1$을 뜻한다. 모든 단계는 반사슬이므로, $\backslash kappa$-수슬린 나무는 항상 $\backslash kappa$-아론샤인 나무이다.

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

"$\backslash aleph\_1$-수슬린 나무(또는 수슬린 직선)가 존재하지 않는다"는 명제를 수슬린 가설(Souslin’s hypothesis^영어) $\backslash mathsf\{SH\}$이라고 한다.

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

3.2. 아론샤인 나무 (Aronszajn tree)

기수 $\backslash kappa$에 대하여, $\backslash kappa$-아론샤인 나무($\backslash kappa$-Aronszajn tree^영어)는 다음 세 조건들을 만족시키는 나무 $T$이다.

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

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

모든 단계는 반사슬이므로, $\backslash kappa$-수슬린 나무는 항상 $\backslash kappa$-아론샤인 나무이다. $\backslash kappa$가 무한 기수라면, 모든 $\backslash kappa$-수슬린 나무는 $\backslash kappa$-아론샤인 나무이나, 그 역은 성립하지 않는다.

$\backslash kappa$-특수 아론샤인 나무(special Aronszajn tree^영어)는 다음 조건을 만족시키는 $\backslash kappa$-아론샤인 나무 $T$이다.
* $T$는 $\backslash kappa$ 미만 개의 반사슬들의 합집합이다.

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

3.3. 쿠레파 나무 (Kurepa tree)

기수 $\backslash kappa$에 대하여, $\backslash kappa$-쿠레파 나무(Kurepa tree^영어)는 다음 조건을 만족시키는 나무이다.
* 높이가 $\backslash kappa$이다.
* 크기 $\backslash kappa$의 가지의 수가 $\backslash kappa$를 초과한다.
* 모든 단계의 크기는 $\backslash kappa$ 미만이다.

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

"$\backslash aleph\_1$-쿠레파 나무가 존재한다"는 명제를 쿠레파 가설(Курепа假說, Kurepa hypothesis^영어) $\backslash mathsf\{KH\}$라고 한다.

4. 구성

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

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

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

:$B\backslash le\; B\text{'}\backslash iff\; B\_\backslash alpha\backslash le\; B\text{'}\_\backslash alpha$
:

이를 $T$의 가지 공간(branch space^영어)이라고 한다.

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

최대 원소 및 최소 원소를 갖지 않는 전순서 집합 $(L,\backslash le)$이 주어졌고, $L$의 (순서 위상에서의) 최소 조밀 집합의 크기가 무한 기수 $\backslash kappa$라고 하자. 그렇다면, $L$의, 공집합이 아닌 열린구간들의 집합
* $I\_\backslash alpha$는 와 서로소인, $\backslash le^\backslash circ$-최소 열린구간이다.
그렇다면, 는 포함 관계에 대하여 부분 순서 집합을 이루며, 그 반대 부분 순서 집합 $T$는 $L$에 대응하는 나무이다.

4.3. 수슬린 직선 (Souslin line)

전순서 집합 $L$이 다음 두 조건을 만족시키면 수슬린 직선(Souslin line^영어)이라고 한다.
* $\backslash operatorname\{Open\}(L)\backslash setminus\backslash \{\backslash varnothing\backslash \}$은 가산 강하향 반사슬 조건을 만족시킨다. 여기서 $\backslash operatorname\{Open\}(L)\backslash setminus\backslash \{\backslash varnothing\backslash \}\backslash subseteq\backslash mathcal\; P(L)$은 ($L$의 순서 위상에서) $L$의 공집합이 아닌 열린집합들의 집합족이다.
* 분해 가능 공간이 아니다.

정돈된 수슬린 직선은 다음 조건을 추가로 만족시키는 수슬린 직선이다.
* $L$은 최소 원소와 최대 원소를 갖지 않는다.
* $L$은 선형 연속체이다.

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

다음이 성립한다.
* 정돈된 $\backslash aleph\_1$-수슬린 나무에 대응하는 전순서 집합은 수슬린 직선이다.
* 정돈된 수슬린 직선에 대응하는 나무는 $\backslash aleph\_1$-수슬린 나무이다.

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

5. 성질

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

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

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

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

5.1. 순서론적 성질

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

나무의 경우 다음 두 조건은 서로 동치이다.
* 하향 원순서 집합이다.
* 정확히 한 개의 뿌리를 갖는다.

다음 세 개념은 서로 동치이다.
* 전순서 집합인 나무
* 모든 단계가 한원소 집합이거나 공집합인 나무
* 정렬 전순서 집합

5.2. 논리학적 성질

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

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

도달 불가능한 기수 $\backslash kappa$에 대하여 다음 두 조건은 서로 동치이다.
* $\backslash kappa$-아론샤인 나무는 존재하지 않는다.
* 약콤팩트 기수이다.

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

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

다음 데이터가 주어졌다고 하자.
* ZFC의 표준 추이적 모형 $M$
* $M$ 속에서의 비가산 정칙 기수 $\backslash kappa\backslash in\backslash operatorname\{Card\}^M$, $\backslash kappa>\backslash omega$
* $M$ 속에서의 정돈된 $\backslash kappa$-수슬린 나무 $T\backslash in\; M$
* $T$의 포괄적 순서 아이디얼 $G\backslash subseteq\; T$

그렇다면, 강제법 모형 $M[G]$를 생각할 수 있다. 그렇다면, 다음이 성립한다.
* $M[G]$ 속에서, 나무 $T$는 $\backslash kappa$-수슬린 나무가 아니다.

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

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

6. 역사

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

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

도달 불가능한 기수 $\backslash kappa$에 대하여 다음 두 조건은 서로 동치이다.
* $\backslash kappa$-아론샤인 나무는 존재하지 않는다.
* 약콤팩트 기수이다.

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

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

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

7. 예

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

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

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

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

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

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

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

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

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

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

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

7.1. 자명한 나무

임의의 집합 $X$에 대하여, 자명한 부분 순서 $a\backslash le\; b\backslash iff\; a=b$를 정의하면, $X$는 나무가 된다. 이때, $X$가 공집합이면 나무의 높이는 0이고, 공집합이 아니면 높이는 1이다.

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

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^영어)라고 한다. 만약 \(S\)가 한원소 집합이라면, 높이 \(\alpha\)의 완비 \(S\)진 나무는 \(\alpha\)와 순서 동형이다.

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

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

S를 이산 공간으로, S^ω를 그 가산 무한 곱공간으로 생각하면, 임의의 부분 집합 A ⊆ S^ω에 대해 다음 두 조건은 서로 동치이다.
* A = [T]인 하집합 T ⊆ S^<ω가 존재한다.
* A는 S^ω의 닫힌집합이다.

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