최근 수정 시각 : 2023-04-25 17:53:08

나무(순서론)

이 문서는 토막글입니다.

토막글 규정을 유의하시기 바랍니다.


1. 개요2. 정의

1. 개요

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

2. 정의

순서론적으로 다음과 같이 정의한다.
부분 순서 집합 [math((T,\leq))]가 다음 조건을 만족하면 나무라고 한다.
  • 임외의 [math(s\in T)]에 대하여
    하집합[1] [math(T_s=\{t\in T:t<s\})]는 정렬전순서 집합이다.
나무 [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<t)]이자 [math(\mathrm{ht}_T(t)=\beta)]인 원소 [math(t\in T)]가 존재한다.
  • 뿌리가 유일하다.

[1] 특정한 원소보다 작은 원소들만 모은 집합