사전식 순서

틀:위키데이터 속성 추적 순서론에서 사전식 순서(辭典式順序, 틀:Llang)는 여러 개의 부분 순서 집합들의 곱집합 위에 존재하는 부분순서이다. 사전에 쓰이는 가나다순이나 알파벳순의 정렬 방법은 사전식 순서의 예이다. 순서론, 전산학 등의 분야에서 사용된다.

정의

$(I,\le )$가 정렬 집합이며, 각 $i\in I$에 대하여 $(X_i,\le )$가 부분 순서 집합이라고 하자. 그렇다면 곱집합

$\prod _{i\in I}{X}_i$

위의 사전식 순서는 다음과 같은 부분 순서이다.

$x\le y⟺x=y\vee x_{\min \{j\in I:x_j\ne y_j\}}<y_{\min \{j\in I:x_j\ne y_j\}}$

만약 모든 $X_i$가 전순서 집합이라면, $\prod _{i\in I}{X}_i$ 또한 전순서 집합이다. 만약 모든 $X_i$가 정렬 집합이며 $I$가 유한 집합이라면, $\prod _{i\in I}{X}_i$ 또한 정렬 집합이다.

예

$X$가 전순서 집합이라고 하고, 이를 "알파벳 집합"이라고 하자. 또한, $X\bigsqcup \{\bullet \}$에

$\bullet \le x\mathrm{\forall }x\in X$

와 같은 전순서를 주자.

그렇다면 $X$의 클레이니 스타 $X^{*}$의 원소 $s\in X^{*}$는 함수 $s:{\mathbb{Z}}^{+}\to X\bigsqcup \{\bullet \}$로 여길 수 있다. 이 경우 어떤 $k_0\in {\mathbb{Z}}^{+}\cup \{0\}$에 대하여

$s(k)\in X\mathrm{\forall }k\le k_0$

$s(k)=\bullet \mathrm{\forall }k>k_0$

이 되며, $k_0$은 $s$의 길이다. 따라서, $X^{*}$는 $(X\bigsqcup \{\bullet \}{)}^{{\mathbb{Z}}^{+}}$의 부분집합이다. 이 경우, $(X\bigsqcup \{\bullet \}{)}^{{\mathbb{Z}}^{+}}$에 사전식 순서를 부여한 뒤 이를 $X^{*}$에 국한시키면, 이는 $X^{*}$ 위의 전순서를 정의한다. 이는 사전에 쓰이는 문자열의 정렬법과 같다.

같이 보기

• 긴 직선
• 전순서 집합

외부 링크

• 틀:Eom
• 틀:매스월드
• 틀:웹 인용