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

정의

편집

 정렬 집합이며, 각  에 대하여  부분 순서 집합이라고 하자. 그렇다면 곱집합

 

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

 

만약 모든  전순서 집합이라면,   또한 전순서 집합이다. 만약 모든  정렬 집합이며  유한 집합이라면,   또한 정렬 집합이다.

 전순서 집합이라고 하고, 이를 "알파벳 집합"이라고 하자. 또한,  

 

와 같은 전순서를 주자.

그렇다면  클레이니 스타  의 원소  는 함수  로 여길 수 있다. 이 경우 어떤  에 대하여

 
 

이 되며,   의 길이다. 따라서,   의 부분집합이다. 이 경우,  에 사전식 순서를 부여한 뒤 이를  에 국한시키면, 이는   위의 전순서를 정의한다. 이는 사전에 쓰이는 문자열의 정렬법과 같다.

같이 보기

편집

외부 링크

편집