정렬가능성 정리 - 시드위키

Well-ordered theorem

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

목차

1. 진술
2. 증명
3. 따름정리
4. 선택공리와의 동치성
4.1. 증명
5. 참고 문헌

1. 진술 _{✎ ⊖}

A가 집합이면, 그 위의 관계 \\prec가 존재해 \\prec가 정렬순서가 된다.

2. 증명 _{✎ ⊖}

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

f(\\alpha)\\prec f(\\beta) \\iff \\alpha\\le\\beta

으로 정의한다.

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

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

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

3. 따름정리 _{✎ ⊖}

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

4. 선택공리와의 동치성 _{✎ ⊖}

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

4.1. 증명 _{✎ ⊖}

A가 집합이고 \\prec가 그 위의 정렬순서라고 하자. 이 때 함수 f:\\mathcal{P}(A)\\setminus\\{\\varnothing\\} \\to A를

f(S) = \\min \\!{}_\\prec S

으로 정의한다. 이 때 \\min_\\prec은 \\prec라는 순서에 의한 최소원이라는 의미이다. 이 때 주어진 함수는 선택 함수가 된다.

5. 참고 문헌 _{✎ ⊖}

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

정렬가능성 정리

1. 진술 ✎ ⊖

2. 증명 ✎ ⊖

3. 따름정리 ✎ ⊖

4. 선택공리와의 동치성 ✎ ⊖

4.1. 증명 ✎ ⊖