최근 수정 시각 : 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] 특정한 원소보다 작은 원소들만 모은 집합

분류