나무(순서론)

1. 개요[편집]

---

Tree
임외에 원소에 대하여 그보다 작은 원소들로 구성된 부분집합이 정렬전순서인 부분순서 집합

2. 정의[편집]

---

순서론적으로 다음과 같이 정의한다.
나무 [math(T)]의 원소 [math(t\in T)]에 대하여, [math(T_t)]의 순서형인
서수 [math(\mathrm{ht}_T(t))]를 [math(t)]의 높이라고 한다.
이는 함수 [math(\mathrm{ht}:T\rightarrow \mathrm{Ord})] 를 정의한다. 높이가 0인 원소는 극소 원소이며
나무의 극소원소를 뿌리라고한다.
나무 [math(T)]의 [math(\alpha)]번째 단계란 높이 [math(\alpha)]의 원소들에 집합이다. 이를 [math(\mathrm{lv}(T,\alpha))]라고 표기하자.
나무 [math(T)]의 너비란 단계들에 크기에 상한이다.
즉 [math(\mathrm{ht}(T)=\mathrm{min}\{\alpha\in \mathrm{Ord}:\forall t:\alpha>\mathrm{ht}_T (t)\})]
나무 [math(T)]의 가지는 극대 사슬이다. 나무의 가지 역시 정렬 전순서 집합을 이루기에 가지의 높이를 정의할 수 있다.
[math(T)]의 가지에 집합을 [math(\mathrm{Br}(T))]라고 하자.
나무 [math(T)]가 다음 두 조건을 만족하면 [math(T)]를 정돈된 나무라고 한다.

• 임외에 서수 [math(\alpha<\beta<\mathrm{ht}(T))] 및 높이 [math(\alpha)]의 원소 [math(s\in T)]에 대하여 [math(s
• 뿌리가 유일하다.