순서론에서 사전식 순서(辭典式順序, 영어: lexicographical order)는 여러 개의 부분 순서 집합들의 곱집합 위에 존재하는 부분순서이다. 사전에 쓰이는 가나다순이나 알파벳순의 정렬 방법은 사전식 순서의 예이다. 순서론, 전산학 등의 분야에서 사용된다.
가 정렬 집합이며, 각
에 대하여
가 부분 순서 집합이라고 하자. 그렇다면 곱집합
![{\displaystyle \prod _{i\in I}X_{i}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8e4cf2ee0af61dd971a31005ff6d10fb3fe3267f)
위의 사전식 순서는 다음과 같은 부분 순서이다.
![{\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}\}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/80539294a043987df49e680020da20ffcdff9b1d)
만약 모든
가 전순서 집합이라면,
또한 전순서 집합이다. 만약 모든
가 정렬 집합이며
가 유한 집합이라면,
또한 정렬 집합이다.
가 전순서 집합이라고 하고, 이를 "알파벳 집합"이라고 하자. 또한,
에
![{\displaystyle \bullet \leq x\;\forall x\in X}](https://wikimedia.org/api/rest_v1/media/math/render/svg/644c88307f36680403a2e2a189c98bd601bba533)
와 같은 전순서를 주자.
그렇다면
의 클레이니 스타
의 원소
는 함수
로 여길 수 있다. 이 경우 어떤
에 대하여
![{\displaystyle s(k)\in X\;\forall k\leq k_{0}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f3957c1f7bcb78b5c9b9ea61d753069d9d17eea0)
![{\displaystyle s(k)=\bullet \;\forall k>k_{0}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9426342e0c548faebe400bd5ac3cc669167e7ac6)
이 되며,
은
의 길이다. 따라서,
는
의 부분집합이다. 이 경우,
에 사전식 순서를 부여한 뒤 이를
에 국한시키면, 이는
위의 전순서를 정의한다. 이는 사전에 쓰이는 문자열의 정렬법과 같다.
같이 보기[편집]
외부 링크[편집]