정렬 순서

위키백과, 우리 모두의 백과사전.
(정렬순서에서 넘어옴)
이동: 둘러보기, 검색

순서론집합론에서, 정렬 순서(整列順序, 영어: well-order)는 모든 부분 집합이 최소 원소를 갖는 전순서이다.

정의[편집]

집합 S 위의 전순서 \le가 다음 성질을 만족시킬 경우, \le정렬 순서라고 한다.

  • (내림 사슬 조건) 모든 부분집합 A\subseteq S에 대하여, 만약 A\ne\varnothing인 경우, 모든 a\in A에 대하여 \min A\le a인 원소 \min A\in A가 존재한다.

즉, 정렬 순서는 내림 사슬 조건을 만족시키는 전순서이다.

정렬 집합(整列順序集合, 영어: well-ordered set)은 정렬 순서가 갖추어진 집합이다.

정렬 집합 (S,\le_S), (T,\le_T) 사이의 시뮬레이션(영어: simulation) f\colon S\to T는 다음 성질들을 만족시키는 함수이다.

  • 만약 s,s'\in S에 대하여 s\le s'라면, f(s)\le f(s')이다.
  • 임의의 s\in St\in T에 대하여, 만약 t\le f(s)라면 f^{-1}(t)\in S가 존재한다.

정렬 순서와 시뮬레이션들의 범주부분 순서 고유 모임이며, 이는 순서수의 범주와 동치이다.

정렬 순서의 동형은 정렬 순서와 시뮬레이션의 범주에서의 동형이다. 이 동형에 대한 동치류순서형(順序型, 영어: order type)이라고 한다. 순서수는 각 순서형의 표준적인 대표원을 제공한다.

성질[편집]

정렬 집합 (S,\le)의 부분 집합 A\subset S이 주어졌을 때, (A,\le) 역시 정렬 집합이다.

서로 동형인 두 정렬 집합은 같은 집합의 크기를 갖는다. 반대로, 집합의 크기가 같은 두 유한 정렬 집합은 서로 동형이다. 반면, 집합의 크기가 같지만 서로 다른 무한 정렬 집합이 존재한다. 예를 들어, 순서수 \omega에 대응하는 정렬 집합과 순서수 \omega+1에 대응하는 정렬 집합은 서로 동형이지 않다.

[편집]

자연수 집합의 표준적인 순서는 정렬 순서이다. 반면, 정수 집합의 표준적인 순서는 정렬 순서가 아니다. 예를 들어, 정수 집합 전체는 최소 원소를 갖지 않는다.

유리수의 집합이나 실수의 집합, 심지어 음이 아닌 유리수나 실수의 집합의 표준적인 순서는 정렬 순서가 아니다. 예를 들어, 음이 아닌 유리수들의 집합

A=\{1,1/2,1/3,1/4,\dots\}\subset[0,\infty)

의 경우, 하계 \min A가 존재하지 않으며, 오직 하한 \inf A=0\not\in A만이 존재한다.

모든 순서수고유 모임 \operatorname{Ord} (또는 그 임의의 부분 모임)의 표준적인 순서는 정렬 순서이다. 선택 공리를 가정할 경우, 기수고유 모임의 표준적인 순서 역시 정렬 순서이다.

만약 선택 공리를 가정하면, 정렬 정리에 따라서 모든 집합이 정렬 순서를 갖는다. 다만, 이 정렬 순서는 구체적으로 명시하지 못할 수 있다.

바깥 고리[편집]

같이 보기[편집]