1. 개요
Tree임외에 원소에 대하여 그보다 작은 원소들로 구성된 부분집합이 정렬전순서인 부분순서 집합
2. 정의
순서론적으로 다음과 같이 정의한다.부분 순서 집합 [math((T,\leq))]가 다음 조건을 만족하면 나무라고 한다.
|
서수 [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<t)]이자 [math(\mathrm{ht}_T(t)=\beta)]인 원소 [math(t\in T)]가 존재한다.
- 뿌리가 유일하다.
[1] 특정한 원소보다 작은 원소들만 모은 집합