정렬 원순서 집합
순서론과 집합론에서, 정렬 원순서 집합(整列原順序集合, )은 모든 부분 집합이 양의 정수 개의 극소 원소 동치류를 갖는 원순서 집합이다. 정렬 원순서 집합 위에서는 초한 귀납법이 가능하다. 정렬 원순서 집합 가운데 전순서 집합인 것 (즉, 모든 부분 집합이 최소 원소를 갖는 전순서 집합)을 정렬 전순서 집합(整列全順序集合, ) 또는 단순히 정렬 집합(整列集合)이라고 한다. 이들의 동형류는 순서수를 이룬다.
원순서 집합 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 역시 정렬 원순서 집합이다 (딕슨 보조 정리 ).
정렬 정리(整列定理, )에 따르면, 모든 집합은 적어도 하나 이상의 정렬 전순서를 갖는다. (다만, 이 정렬 전순서는 구체적으로 명시하지 못할 수 있다.) 다시 말해, 임의의 크기를 갖는 순서수가 존재한다. 이를 통해, 임의의 집합 위에 초한 귀납법을 적용할 수 있다. 사실, 1차 논리의 체르멜로-프렝켈 집합론에서, 정렬 정리는 선택 공리 및 초른의 보조정리와 서로 동치이다. 즉, 체르멜로-프렝켈 집합론의 공리들로, 이 셋 가운데 하나가 주어지면 나머지 둘을 증명할 수 있다.
폰 노이만-베르나이스-괴델 집합론이나 모스-켈리 집합론과 같은, 모임을 다루는 이론에서는 모든 모임이 정렬 전순서를 갖는지에 대하여 생각할 수 있다. (선택 공리를 제외한) 이들 체계에서는 다음 두 조건이 서로 동치이다.
모든 유한 원순서 집합은 (자명하게) 정렬 원순서 집합을 이룬다. 특히, 자연수 집합의 표준적인 전순서는 정렬 전순서이다.
보다 일반적으로, 임의의 순서수 formula_63보다 작은 순서수들의 집합
는 정렬 전순서 집합이다. 모든 순서수의 고유 모임 formula_65 (또는 그 임의의 부분 모임)의 표준적인 전순서는 정렬 전순서이다. 선택 공리를 가정할 경우, 기수의 고유 모임의 표준적인 전순서 역시 정렬 전순서이며, 이 사실은 알레프 수의 정의의 기반을 이룬다.
원순서 집합 formula_66 위의 유한 문자열 집합 (클레이니 스타) formula_67 위에 다음과 같은 부분 문자열 관계를 주자. 즉, formula_68과 formula_69에 대하여, formula_70이라는 것은
가 되는 단사 증가 함수
가 존재함을 뜻한다. 이는 원순서이며, 만약 formula_73가 부분 순서라면 부분 문자열 관계는 부분 순서이다. 히그먼 보조 정리()에 따르면, formula_74는 정렬 원순서 집합을 이룬다.
(무향) 유한 그래프들의 가산 무한 집합은 그래프 마이너 관계에 대하여 원순서 집합을 이룬다. 로버트슨-시모어 정리()에 따르면, 이는 정렬 원순서 집합이다.
순서체 formula_75(예를 들어, 유리수체나 실수체)는 정렬 전순서 집합이 될 수 없다. 모든 순서체는 formula_76를 부분환으로 포함하는데, 이 경우 formula_76 전체는 최소 원소를 갖지 않기 때문이다. 마찬가지로, 자명환이 아닌 순서환은 항상 정렬 전순서 집합이 될 수 없다.
순서체 formula_75에서, 음이 아닌 원소들의 전순서 집합 formula_79 역시 정렬 전순서 집합이 될 수 없다. 이는 formula_79는 양의 유리수들의 집합 formula_81을 포함하는데, 이는 최소 원소를 갖지 않기 때문이다.
양의 정수의 집합에 약수 관계 formula_82를 부여하면, 이는 부분 순서 집합이지만 정렬 부분 순서 집합이 아니다. 이는 소수의 집합은 무한 반사슬을 이루기 때문이다.
정렬 전순서 집합()의 용어 및 개념은 1883년에 게오르크 칸토어가 순서수를 도입하기 위하여 정의하였다. 게오르크 칸토어는 정렬 정리가 증명이 필요없을 정도로 자명한 "사고 법칙"()이라고 간주했지만, 이를 증명하지 않고 공리로 가정하였다. (칸토어는 선택 공리를 직접적으로 사용하지 않았다.) 그러나 다른 수학자들은 이 "사고 법칙"에 대하여 회의적이었다.
1904년 8월의 하이델베르크 세계 수학자 대회에서 헝가리의 수학자 쾨니그 줄러()는 정렬 정리를 반증하였다고 발표하였다. 그러나 몇 주 뒤 펠릭스 하우스도르프가 이 "반증"의 오류를 지적하였다.
1904년에 에른스트 체르멜로는 선택 공리를 도입하였고, 이를 통해 정렬 정리를 증명하였다.
1937년에 주로 쿠레파가 "부분 정렬 순서 집합"()이라는 용어를 사용하였으나, 쿠레파는 무한 반사슬의 부재를 가정하지 않았다. 1952년에 그레이엄 히그먼()은 정렬 부분 순서와 동치인 개념을 "유한 기저 성질"()이라는 이름으로 도입하였고, 히그먼 보조 정리를 증명하였다. 같은 해에 에르되시 팔과 리하르트 라도() 역시 한 논문에서 "부분 정렬 순서 집합"()이라는 용어를 도입하였다.
현재까지도, 많은 수학자들은 정렬 정리가 직관적이지 않다고 여긴다. 그러나 이와 동치인 선택 공리는 대체로 더 직관적이라고 여겨진다. 미국의 수학자 제리 로이드 보나(, 1945~)는 1977년에 이에 대하여 다음과 같이 농담하였다.