사전식 순서 문서 원본 보기

{{위키데이터 속성 추적}}
[[순서론]]에서 '''사전식 순서'''(辭典式順序, {{llang|en|lexicographical order}})는 여러 개의 [[부분 순서 집합]]들의 [[곱집합]] 위에 존재하는 부분순서이다. 사전에 쓰이는 가나다순이나 알파벳순의 정렬 방법은 사전식 순서의 예이다.  [[순서론]], [[전산학]] 등의 분야에서 사용된다.

== 정의 ==
<math>(I,\le)</math>가 [[정렬 집합]]이며, 각 <math>i\in I</math>에 대하여 <math>(X_i,\le)</math>가 [[부분 순서 집합]]이라고 하자. 그렇다면 [[곱집합]]
:<math>\prod_{i\in I}X_i</math>
위의 '''사전식 순서'''는 다음과 같은 [[부분 순서]]이다.
:<math>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\}}</math>
만약 모든 <math>X_i</math>가 [[전순서 집합]]이라면, <math>\prod_{i\in I}X_i</math> 또한 [[전순서 집합]]이다. 만약 모든 <math>X_i</math>가 [[정렬 집합]]이며 <math>I</math>가 [[유한 집합]]이라면, <math>\prod_{i\in I}X_i</math> 또한 [[정렬 집합]]이다.

== 예 ==
<math>X</math>가 [[전순서 집합]]이라고 하고, 이를 "알파벳 집합"이라고 하자. 또한, <math>X\sqcup\{\bullet\}</math>에
:<math>\bullet\le x\;\forall x\in X</math>
와 같은 [[전순서]]를 주자.

그렇다면 <math>X</math>의 [[클레이니 스타]] <math>X^*</math>의 원소 <math>s\in X^*</math>는 함수 <math>s\colon\mathbb Z^+\to X\sqcup\{\bullet\}</math>로 여길 수 있다. 이 경우 어떤 <math>k_0\in\mathbb Z^+\cup\{0\}</math>에 대하여
:<math>s(k)\in X\;\forall k\le k_0</math>
:<math>s(k)=\bullet\;\forall k>k_0</math>
이 되며, <math>k_0</math>은 <math>s</math>의 길이다. 따라서, <math>X^*</math>는 <math>(X\sqcup\{\bullet\})^{\mathbb Z^+}</math>의 부분집합이다. 이 경우, <math>(X\sqcup\{\bullet\})^{\mathbb Z^+}</math>에 사전식 순서를 부여한 뒤 이를 <math>X^*</math>에 국한시키면, 이는 <math>X^*</math> 위의 [[전순서]]를 정의한다. 이는 사전에 쓰이는 문자열의 정렬법과 같다.

== 같이 보기 ==
* [[긴 직선]]
* [[전순서 집합]]

== 외부 링크 ==
* {{eom|title=Lexicographic order}}
* {{매스월드|id=LexicographicOrder|title=Lexicographic order}}
* {{웹 인용|url=http://ncatlab.org/nlab/show/lexicographic+order|제목=Lexicographic order|웹사이트=nLab|언어=en|확인날짜=2014-11-17|보존url=https://web.archive.org/web/20141129033314/http://ncatlab.org/nlab/show/lexicographic+order|보존날짜=2014-11-29|url-status=dead}}

{{전거 통제}}

[[분류:순서론]]