사전식 순서

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

정의

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

${\displaystyle \prod _{i\in I}X_{i}}$

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

${\displaystyle x\leq y\iff x=y\lor x_{\min\{j\in I\colon x_{j}\neq y_{j}\}}<y_{\min\{j\in I\colon x_{j}\neq y_{j}\}}}$

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

예

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

${\displaystyle \bullet \leq x\;\forall x\in X}$

와 같은 전순서를 주자.

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

${\displaystyle s(k)\in X\;\forall k\leq k_{0}}$

${\displaystyle s(k)=\bullet \;\forall k>k_{0}}$

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

같이 보기

• 긴 직선
• 전순서 집합

외부 링크

• “Lexicographic order”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4.
• Weisstein, Eric Wolfgang. “Lexicographic order”. 《Wolfram MathWorld》 (영어). Wolfram Research.
• “Lexicographic order”. 《nLab》 (영어). 2014년 11월 29일에 원본 문서에서 보존된 문서. 2014년 11월 17일에 확인함.