사전식 순서

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

정의[편집]

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

\prod_{i\in I}X_i

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

x\le y\iff x=y\lor x_{\min\{j\in I\colon x_j\ne y_j\}}<y_{\min\{j\in I\colon x_j\ne y_j\}}

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

[편집]

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

\bullet\le x\;\forall x\in X

와 같은 전순서를 주자.

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

s(k)\in X\;\forall k\le k_0
s(k)=\bullet\;\forall k>k_0

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

바깥 고리[편집]