정렬 원순서 집합

순서론과 집합론에서 정렬 원순서 집합(整列原順序集合, )은 모든 부분 집합이 양의 정수 개의 극소 원소 동치류를 갖는 원순서 집합이다. 정렬 원순서 집합 위에서는 초한 귀납법이 가능하다. 정렬 원순서 집합 가운데 전순서 집합인 것 (즉, 모든 부분 집합이 최소 원소를 갖는 전순서 집합)을 정렬 전순서 집합(整列全順序集合, ) 또는 단순히 정렬 집합(整列集合)이라고 한다. 이들의 동형류는 순서수를 이룬다.
정의.
정렬 원순서 집합.
원순서 집합 formula_1에 대하여 다음 다섯 조건들이 서로 동치이며, 이를 만족시키는 원순서 집합을 정렬 원순서 집합(整列原順序集合, )이라고 한다.
여기서 formula_23는 formula_24를 뜻한다.
정렬 원순서 집합인 부분 순서 집합을 정렬 부분 순서 집합(整列部分順序集合, )이라고 한다. 정렬 원순서 집합인 전순서 집합을 정렬 전순서 집합(整列全順序集合, ) 또는 정렬 집합()이라고 한다. 즉, 전순서 집합 formula_25에 대하여 다음 조건들이 서로 동치이며, 이를 만족시키는 전순서 집합을 정렬 전순서 집합이라고 한다.
시뮬레이션.
두 정렬 원순서 집합 formula_39, formula_40 사이의 시뮬레이션() formula_41는 다음 성질들을 만족시키는 함수이다.
정렬 전순서 집합과 시뮬레이션들의 범주는 순서수의 얇은 범주와 동치이다.
정렬 전순서의 동형은 정렬 전순서와 시뮬레이션의 범주에서의 동형이다. 이 동형에 대한 동치류를 순서형(順序型, )이라고 한다. 순서수는 각 순서형의 표준적인 대표원을 제공한다.
성질.
함의 관계.
다음과 같은 함의 관계가 성립한다.
정렬 전순서 집합.
정렬 전순서 집합 formula_51의 부분 집합 formula_52이 주어졌을 때, formula_53 역시 정렬 전순서 집합이다.
서로 동형인 두 정렬 전순서 집합은 같은 집합의 크기를 갖는다. 반대로, 집합의 크기가 같은 두 유한 정렬 전순서 집합은 서로 동형이다. 반면, 집합의 크기가 같지만 서로 다른 무한 정렬 전순서 집합이 존재한다. 예를 들어, 순서수 formula_54에 대응하는 정렬 전순서 집합과 순서수 formula_55에 대응하는 정렬 전순서 집합은 서로 동형이지 않다.
정렬 원순서 집합.
정렬 원순서 집합들의 유한 족 formula_56이 주어졌다고 하자. 그렇다면, 분리합집합 formula_57 위에 순서
를 줄 수 있다. 이 역시 정렬 원순서 집합이다.
정렬 원순서 집합들의 유한 족 formula_56이 주어졌다고 하자. 그렇다면, 곱집합 formula_60 위에 순서
를 준다면, formula_62 역시 정렬 원순서 집합이다 (딕슨 보조 정리 ).
증명:
수학적 귀납법을 통해 formula_63인 경우를 증명하면 족하다. (formula_64은 자명하다.) formula_65 속의 점렬 formula_66이 주어졌다고 하자. 이제,
가 formula_68의 증가 부분열이라고 하자. 또한,
가 formula_70의 증가 부분열이라고 하자. 그렇다면
는 formula_66의 증가 부분열이다.
정렬 정리.
정렬 정리(整列定理, )에 따르면, 모든 집합은 적어도 하나 이상의 정렬 전순서를 갖는다. (다만, 이 정렬 전순서는 구체적으로 명시하지 못할 수 있다.) 다시 말해, 임의의 크기를 갖는 순서수가 존재한다. 이를 통해, 임의의 집합 위에 초한 귀납법을 적용할 수 있다. 사실, 1차 논리의 체르멜로-프렝켈 집합론에서, 정렬 정리는 선택 공리 및 초른 보조정리와 서로 동치이다. 즉, 체르멜로-프렝켈 집합론의 공리들로, 이 셋 가운데 하나가 주어지면 나머지 둘을 증명할 수 있다.
증명 (초른 보조정리 ⇒ 정렬 정리):
임의의 집합 formula_17가 주어졌다고 하자. formula_17의 부분 집합들 위의 정렬 전순서 집합 formula_75를 생각하자. 여기에 다음과 같은 부분 순서를 주자.
이에 따라 formula_75는 부분 순서 집합을 이룬다.
formula_75의 임의의 사슬 formula_81에 대하여, formula_82는 사슬의 상계이다. 따라서, formula_75의 모든 사슬은 상계를 갖는다.
따라서, 초른 보조정리에 따라 formula_75는 극대 원소 formula_85를 갖는다.
귀류법을 사용하여, 만약 formula_86라고 하자. 그렇다면 formula_87가 존재하는데, 이 경우 formula_88 위에 다음과 같은 정렬 전순서를 줄 수 있다.
즉, formula_90이 formula_91의 모든 원소보다 더 크다. 이 정렬 전순서를 주었을 때,
이므로 formula_91는 극대 원소일 수 없다. 즉, formula_94이며, formula_95는 formula_17 위의 정렬 전순서이다.
증명 (정렬 정리 ⇒ 선택 공리):
정렬 정리를 가정하자. 공집합이 아닌 집합들의 집합족 formula_97가 주어졌다고 하자. 정렬 정리를 사용하여, formula_98에 정렬 전순서를 주자. 이 경우, 함수
는 formula_97 위의 선택 함수이므로, 선택 공리는 참이다.
폰 노이만-베르나이스-괴델 집합론이나 모스-켈리 집합론과 같은, 모임을 다루는 이론에서는 모든 모임이 정렬 전순서를 갖는지에 대하여 생각할 수 있다. (선택 공리를 제외한) 이들 체계에서는 다음 두 조건이 서로 동치이다.
예.
정렬 전순서 집합.
모든 유한 원순서 집합은 (자명하게) 정렬 원순서 집합을 이룬다. 특히, 자연수 집합의 표준적인 전순서는 정렬 전순서이다.
보다 일반적으로, 임의의 순서수 formula_102보다 작은 순서수들의 집합
는 정렬 전순서 집합이다. 모든 순서수의 고유 모임 formula_104 (또는 그 임의의 부분 모임)의 표준적인 전순서는 정렬 전순서이다. 선택 공리를 가정할 경우, 기수의 고유 모임의 표준적인 전순서 역시 정렬 전순서이며, 이 사실은 알레프 수의 정의의 기반을 이룬다.
문자열.
원순서 집합 formula_105 위의 유한 문자열 집합 (클레이니 스타) formula_106 위에 다음과 같은 부분 문자열 관계를 주자. 즉, formula_107과 formula_108에 대하여, formula_109이라는 것은
가 되는 단사 증가 함수
가 존재함을 뜻한다. 이는 원순서이며, 만약 formula_112가 부분 순서라면 부분 문자열 관계는 부분 순서이다. 히그먼 보조 정리()에 따르면, formula_113는 정렬 원순서 집합을 이룬다.
그래프.
(무향) 유한 그래프들의 가산 무한 집합은 그래프 마이너 관계에 대하여 원순서 집합을 이룬다. 로버트슨-시모어 정리()에 따르면, 이는 정렬 원순서 집합이다.
반례.
순서체 formula_114(예를 들어, 유리수체나 실수체)는 정렬 전순서 집합이 될 수 없다. 모든 순서체는 formula_115를 부분환으로 포함하는데, 이 경우 formula_115 전체는 최소 원소를 갖지 않기 때문이다. 마찬가지로, 자명환이 아닌 순서환은 항상 정렬 전순서 집합이 될 수 없다.
순서체 formula_114에서, 음이 아닌 원소들의 전순서 집합 formula_118 역시 정렬 전순서 집합이 될 수 없다. 이는 formula_118는 양의 유리수들의 집합 formula_120을 포함하는데, 이는 최소 원소를 갖지 않기 때문이다.
양의 정수의 집합에 약수 관계 formula_121를 부여하면, 이는 부분 순서 집합이지만 정렬 부분 순서 집합이 아니다. 이는 소수의 집합은 무한 반사슬을 이루기 때문이다.
역사.
정렬 전순서 집합()의 용어 및 개념은 1883년에 게오르크 칸토어가 순서수를 도입하기 위하여 정의하였다. 게오르크 칸토어는 정렬 정리가 증명이 필요없을 정도로 자명한 "사고 법칙"()이라고 간주했지만, 이를 증명하지 않고 공리로 가정하였다. (칸토어는 선택 공리를 직접적으로 사용하지 않았다.) 그러나 다른 수학자들은 이 "사고 법칙"에 대하여 회의적이었다.
1904년 8월의 하이델베르크 세계 수학자 대회에서 헝가리의 수학자 쾨니그 줄러()는 정렬 정리를 반증하였다고 발표하였다. 그러나 몇 주 뒤 펠릭스 하우스도르프가 이 "반증"의 오류를 지적하였다.
1904년에 에른스트 체르멜로는 선택 공리를 도입하였고, 이를 통해 정렬 정리를 증명하였다.
1937년에 주로 쿠레파가 "부분 정렬 순서 집합"()이라는 용어를 사용하였으나, 쿠레파는 무한 반사슬의 부재를 가정하지 않았다. 1952년에 그레이엄 히그먼()은 정렬 부분 순서와 동치인 개념을 "유한 기저 성질"()이라는 이름으로 도입하였고, 히그먼 보조 정리를 증명하였다. 같은 해에 에르되시 팔과 리하르트 라도() 역시 한 논문에서 "부분 정렬 순서 집합"()이라는 용어를 도입하였다.
현재까지도, 많은 수학자들은 정렬 정리가 직관적이지 않다고 여긴다. 그러나 이와 동치인 선택 공리는 대체로 더 직관적이라고 여겨진다. 미국의 수학자 제리 로이드 보나(, 1945~)는 1977년에 이에 대하여 다음과 같이 농담하였다.