사전식 순서

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

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

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

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

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

와 같은 전순서를 주자.

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

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

 같이 보기 
 긴 직선
 전순서 집합

 외부 링크 




분류:순서론