정렬가능성 정리 (편집)

[[분류:가져온 문서/오메가]]
Well-ordered theorem

임의의 집합이 정렬 가능하다는 정리이다. 이 정리는 ZF 위에서 [[선택공리]]와 동치이다.

== 진술 ==
[math(A)]가 집합이면, 그 위의 관계 [math(\prec)]가 존재해 [math(\prec)]가 정렬순서가 된다.

== 증명 ==
선택공리를 가정하자. 우리들은 정렬 순서를 초한 귀납적으로 [math(A)]의 모든 원소에 대응되는 서수 단사열을 구성할 것이다. 만약 이러한 서수열이 구성되었다면, 그 수열을 이용해서 [math(A)] 위의 정렬 순서를 정의할 수 있다 ― 구체적으로 말하자면, [math(f)]가 어떤 서수들의 집합에서 [math(A)]로 가는 전단사라 했을 때

><math>f(\alpha)\prec f(\beta) \iff \alpha\le\beta</math>

으로 정의한다.

우선 [math(A)]의 원소 하나를 고르고 이를 [math(a_0)]라 정의하자. 만약 [math(\alpha)]가 서수이고 [math(\xi<\alpha)]인 모든 서수 [math(\xi)]에 대해 [math(a_\xi)]가 정의되었을 때

><math>a_\alpha = F(A \setminus \{a_\xi: \xi<\alpha\})</math>

으로 정의한다. 이 때 [math(F)]는 [math(A)] 위에서 정의되는 선택 함수이다. 이렇게 정의된 서수열은 명백히 단사이다. 그리고 위에서 정의한 서수열은 어느 순간 내에 정의가 끝나게 되는데, 그렇지 않다고 가정하면 서수들의 모임에서 집합으로 가는 단사 함수가 존재하게 되고, 여기서 모든 서수들의 모임이 집합임을 이끌어낼 수 있어서 모순이다. 그리고 서수열의 정의에서, 주어진 서수열이 전사임을 알 수 있다.

== 따름정리 ==
정렬가능성 정리를 이용하면, 모든 [[기수]]가 [[알레프 수]]라는 사실을 증명할 수 있다. 그리고 여기에서 모든 기수들의 집합이 정렬 가능함이 따라 나온다.

== 선택공리와의 동치성 ==
정렬가능성 정리는 선택공리와 동치이다. 정렬가능성 정리에서 선택공리를 이끌어 내는 것은 그 역보다 쉽다.

=== 증명 ===
[math(A)]가 집합이고 [math(\prec)]가 그 위의 정렬순서라고 하자. 이 때 함수 [math(f:\mathcal{P}(A)\setminus\{\varnothing\} \to A)]를
><math>f(S) = \min \!{}_\prec S</math>
으로 정의한다. 이 때  [math(\min_\prec)]은 [math(\prec)]라는 순서에 의한 최소원이라는 의미이다. 이 때 주어진 함수는 선택 함수가 된다.

== 참고 문헌 ==
* Thomas Jech (2003) Set Theory: The Third Millennium Edition, Revised and Expanded. Springer-Verlag. ISBN 3-540-44085-2.

[Include(틀:가져옴2,O=오메가, C=[[https://creativecommons.org/licenses/by-nc-sa/3.0/deed.ko|CC BY-NC-SA 3.0]])]

(임시 저장) (임시 저장 불러오기)

(↪️) (💎) (🛠️) (추가)