정렬 원순서 집합 document_id A220623207555

순서론과 집합론에서, 정렬 원순서 집합(整列原順序集合, well preordered set, well quasiordered set)은 모든 부분 집합이 양의 정수 개의 극소 원소 동치류를 갖는 원순서 집합이다. 정렬 원순서 집합 위에서는 초한 귀납법이 가능하다. 정렬 원순서 집합 가운데 전순서 집합인 것 (즉, 모든 부분 집합이 최소 원소를 갖는 전순서 집합)을 정렬 전순서 집합(整列全順序集合, well (totally) ordered set, woset) 또는 단순히 정렬 집합(整列集合)이라고 한다. 이들의 동형류는 순서수를 이룬다. <heading>정의 >> 정렬 원순서 집합 </heading> 원순서 집합 (X,lesssim)에 대하여 다음 다섯 조건들이 서로 동치이며, 이를 만족시키는 원순서 집합을 정렬 원순서 집합(整列原順序集合, well preordered set)이라고 한다. 여기서 xsim y는 xlesssim ylesssim x를 뜻한다. 정렬 원순서 집합인 부분 순서 집합을 정렬 부분 순서 집합(整列部分順序集合, well partially ordered set)이라고 한다. 정렬 원순서 집합인 전순서 집합을 정렬 전순서 집합(整列全順序集合, well totally ordered set) 또는 정렬 집합(well ordered set)이라고 한다. 즉, 전순서 집합 (X,le)에 대하여 다음 조건들이 서로 동치이며, 이를 만족시키는 전순서 집합을 정렬 전순서 집합이라고 한다. evarnothing이라면, S는 최소 원소를 갖는다. <heading>시뮬레이션 </heading> 두 정렬 원순서 집합 (S,lesssim_S), (T,lesssim_T) 사이의 시뮬레이션(simulation) fcolon S o T는 다음 성질들을 만족시키는 함수이다. 정렬 전순서 집합과 시뮬레이션들의 범주는 순서수의 얇은 범주와 동치이다. 정렬 전순서의 동형은 정렬 전순서와 시뮬레이션의 범주에서의 동형이다. 이 동형에 대한 동치류를 순서형(順序型, order type)이라고 한다. 순서수는 각 순서형의 표준적인 대표원을 제공한다. <heading>성질 >> 함의 관계 </heading> 다음과 같은 함의 관계가 성립한다. <heading>정렬 전순서 집합 </heading> 정렬 전순서 집합 (S,le)의 부분 집합 Asubset S이 주어졌을 때, (A,le) 역시 정렬 전순서 집합이다. 서로 동형인 두 정렬 전순서 집합은 같은 집합의 크기를 갖는다. 반대로, 집합의 크기가 같은 두 유한 정렬 전순서 집합은 서로 동형이다. 반면, 집합의 크기가 같지만 서로 다른 무한 정렬 전순서 집합이 존재한다. 예를 들어, 순서수 omega에 대응하는 정렬 전순서 집합과 순서수 omega+1에 대응하는 정렬 전순서 집합은 서로 동형이지 않다. 를 줄 수 있다. 이 역시 정렬 원순서 집합이다. <heading>그래프 </heading> (무향) 유한 그래프들의 가산 무한 집합은 그래프 마이너 관계에 대하여 원순서 집합을 이룬다. 로버트슨-시모어 정리(Robertson–Seymour theorem)에 따르면, 이는 정렬 원순서 집합이다. <heading>반례 </heading> 순서체 K(예를 들어, 유리수체나 실수체)는 정렬 전순서 집합이 될 수 없다. 모든 순서체는 mathbb Z를 부분환으로 포함하는데, 이 경우 mathbb Z 전체는 최소 원소를 갖지 않기 때문이다. 마찬가지로, 자명환이 아닌 순서환은 항상 정렬 전순서 집합이 될 수 없다. 순서체 K에서, 음이 아닌 원소들의 전순서 집합 K_{ge0} 역시 정렬 전순서 집합이 될 수 없다. 이는 K_{ge0}는 양의 유리수들의 집합 mathbb Q^+을 포함하는데, 이는 최소 원소를 갖지 않기 때문이다. 양의 정수의 집합에 약수 관계 (mathbb Z^+,mid)를 부여하면, 이는 부분 순서 집합이지만 정렬 부분 순서 집합이 아니다. 이는 소수의 집합은 무한 반사슬을 이루기 때문이다. 1904년 8월의 하이델베르크 세계 수학자 대회에서 헝가리의 수학자 쾨니그 줄러(Kőnig Gyula)는 정렬 정리를 반증하였다고 발표하였다.