선택 공리: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
잔글 봇: 틀 이름 및 스타일 정리 |
Osteologia (토론 | 기여) |
||
7번째 줄:
:<math>\forall S\in\mathcal S\colon f(S)\in S</math>
만약 <math>\varnothing\in\mathcal S</math>라면, <math>\mathcal S</math>는 물론 선택 함수를 가질 수 없다. '''선택 공리''' <math>\mathsf{AC}</math>에 의하면, 공집합을 포함하지 않는 모든 집합족 <math>\mathcal S</math>는 선택 함수를 갖는다.
=== 약화된 형태 ===
임의의 [[기수 (수학)|기수]] <math>\kappa</math>에 대하여, <math>\mathsf{AC}_\kappa</math>는 "크기가 <math>\kappa</math> 이하인, 공집합을 포함하지 않는 [[집합족]]은 선택 함수를 갖는다"는 명제이다. 특히, <math>\kappa=\omega</math>일 때 <math>\mathsf{AC}_\omega</math>를 '''가산 선택 공리'''(可算選擇公理, {{llang|en|axiom of countable choice}})라고 한다.
임의의 [[집합]] <math>S</math> 및 [[이항 관계]] <math>R\subseteq S^2</math>가 주어졌고, 또한 이들이 다음 성질들을 만족시킨다고 하자.
* <math>S\ne\varnothing</math>
* 임의의 <math>s\in S</math>에 대하여, <math>(s,t)\in R</math>인 <math>t\in S</math>가 존재한다.
그렇다면, '''의존적 선택 공리'''(依存的選擇公理, {{llang|en|axiom of dependent choice}}) <math>\mathsf{DC}</math>에 따르면 다음 성질을 만족시키는 [[열 (수학)|열]]
:<math>s\colon\mathbb N\to S</math>
:<math>i\mapsto s_i</math>
이 존재한다.
* 임의의 <math>i\in\mathbb N</math>에 대하여, <math>(s_i,s_{i+1})\in R</math>
== 성질 ==
=== 함의 관계 ===
[[체르멜로-프렝켈 집합론]] 아래, 임의의 [[자연수]] <math>n\in\mathbb N</math>에 대하여 <math>\mathsf{AC}_n</math>을 증명할 수 있다.
:<math>\forall n\in\mathbb N\colon(\mathsf{ZF}\vdash\mathsf{AC}_n)</math>
즉, [[체르멜로-프렝켈 집합론]]에서는 유한 개의 선택을 할 수 있지만, 무한 개의 선택은 ([[체르멜로-프렝켈 집합론]]이 무모순적이라면) 불가능하다.
[[체르멜로-프렝켈 집합론]] 아래, 선택 공리는 의존적 선택 공리를 함의하며, 의존적 선택 공리는 가산 선택 공리를 함의한다.
:<math>\mathsf{ZF}\vdash\left(\mathsf{AC}\implies\mathsf{DC}\implies\mathsf{AC}_\omega\right)</math>
<div class="mw-collapsible mw-collapsed toccolours">
'''증명 (<math>\mathsf{DC}\implies\mathsf{AC}_\omega</math>):'''
<div class="mw-collapsible-content">
집합족 <math>(X_i)_{i\in\mathbb N}</math>이 주어졌다고 하자. 그렇다면,
:<math>X=\bigsqcup X_i</math>
위에 다음 [[이항 관계]] <math>R\subseteq X^2</math>를 정의한다.
:<math>(x,y)\in R\iff \left(\exists i\in\mathbb N\colon x\in X_i\land y\in X_{i+1})\right)</math>
그렇다면, <math>\mathsf{DC}</matH>에 의하여 열 <math>(x_i)_{i\in\mathbb N}</math>의 존재를 증명할 수 있으며, 또한 <math>x_i\in X_{i+k}</math>가 되는 자연수 <math>k\in\mathbb N</math>가 증명함을 쉽게 알 수 있다. 따라서 <math>\mathsf{AC}_k</math>를 사용하여 <math>y_i\in X_i\qquad(i=0,1,\dots,k)</math>를 고른 뒤
:<math>y_{i+k}=x_i\qquad(i\in\mathbb N)</math>
으로 정의하면, <math>y_i\in X_i\forall i\in\mathbb N</math>이다. 따라서 <math>i\mapsto y_i</math>는 가산 무한 집합족 <math>(X_i)_{i\in I}</math>의 선택 함수이다.
</div></div><div class="mw-collapsible mw-collapsed toccolours">
'''증명 (<math>\mathsf{AC}\implies\mathsf{DC}</math>):'''
<div class="mw-collapsible-content">
집합 <math>X</math> 위의 이항 관계 <math>R\subseteq X^2</math>가 주어졌다고 하고, 또한
:<math>\forall x\in X\exists y\in X\colon (x,y)\in R</math>
가 성립한다고 하자. 그렇다면, 선택 공리에 의하여 [[집합족]]
:<math>\left\{\{y\in X\colon (x,y)\in R\right\}_{x\in X}</math>
의 선택 함수
:<math>f\colon X\to X</math>
:<math>\forall x\in X\colon f(x)\in \left\{y\in X\colon (x,y)\in R\right\}</math>
가 존재한다. 임의의 원소 <math>x_0\in X</math>를 고르고
:<math>x_i=\overbrace{(f\circ f\circ\cdots\circ f)}^i(x)</math>
를 정의하면, 이는 의존적 선택 공리에 등장하는 조건을 만족시킨다.
</div></div>
=== 일관성 ===
만약 [[체르멜로-프렝켈 집합론]](ZF)이 일관적이라면, 선택 공리는 [[체르멜로-프렝켈 집합론]]과 독립적이다. 즉, 다음을 보일 수 있다.
:<math>\mathsf{ZF}\vdash\operatorname{Con}(\mathsf{ZF})\iff\operatorname{Con}(\mathsf{ZFC})</math>
줄 27 ⟶ 72:
* [[정렬 정리]]
* [[티호노프 정리]]
* (타르스키 정리 {{llang|en|Tarski theorem}}) 임의의 무한 [[기수 (수학)|기수]] <math>\kappa</math>에 대하여, <math>\kappa=\kappa^2</math>이다.<ref name="Tarski">{{저널 인용|저자고리=알프레트 타르스키|last=Tajtebaum-Tarski|first= A.|title= Sur quelques théorèmes qui équivalent à l’axiome du choix|journal=Fundamenta Mathematicae |volume= 5 |날짜=1924|pages= 147-154 |url=http://pldml.icm.edu.pl/pldml/element/bwmeta1.element.bwnjournal-article-fmv5i1p18bwm|언어=fr}}</ref>
* (기수의 비교 가능성) 임의의 두 기수 <math>\kappa_1</math>, <math>\kappa_2</math>에 대하여, <math>\kappa_1=\kappa_2</math>이거나, <math>\kappa_1<\kappa_2</math>이거나, <math>\kappa_1>\kappa_2</math>이다.
* 모든 [[벡터 공간]]은 [[기저 (선형대수학)|기저]]를 갖는다.
줄 37 ⟶ 82:
=== 선택 공리로부터 함의되는 명제 ===
만약 [[체르멜로-프렝켈 집합론]]이 일관적이라면 [[체르멜로-프렝켈 집합론]]으로 다음 정리들을 증명할 수 없지만, 선택 공리를 추가하면 증명할 수 있다.
* [[괴델의 완전성 정리]]
* 모든 [[체 (수학)|체]]는 [[대수적 폐포]]를 갖는다.
줄 46 ⟶ 89:
* [[베르의 범주 정리]]
* [[바나흐-타르스키 역설]]
* [[르베그 측도|르베그 가측 집합]]이 존재한다.
그러나 선택 공리를 의존적 선택 공리(또는 가산 선택 공리)로 약화시킨다면, 이들 가운데 상당수는 증명 불가능하다.
== 역사 ==
공식적인 형식화가 없었음에도 불구하고 19세기 말까지 선택공리는 암묵적으로 수학자들 사이에서 사용되어 왔다. 예를 들어, 집합 <math>X</math>가 공집합이 아닌 집합만을 포함한다고 했을 때, 수학자들은 종종 “모든 <math>X</math>에 포함된 (집합) <math>s</math>에 대해, <math>F(s)</math>를 <math>s</math>의 원소라고 하자” 라고 기술하곤 했다. 일반적으로 (함수) <math>F</math> 가 선택공리 없이 존재할 수 있음을 증명하기란 불가능했고, 그로 인해
한편, 모든 함수가 선택공리를 필요로 하지는 않는다. 유한 집합 <math>X</math>의 경우, 선택공리는 다른 집합론의 공리들로부터 도출될 수 있다. 각각에 적어도 하나의 물건이 담긴 (유한한) 여러 개의 상자들을 상상 해 보자. 이 때 우리는 각 상자에서 정확히 하나의 물건을 선택할 수 있다. 예를 들자면 이런 식이다. 첫 번째 상자에서 물건 한 개를 선택하고, 두 번째 상자로 옮겨 여기서도 물건 한 개를 선택한다. 그 후 세 번째 상자에서도 물건을 하나 선택하고, 이런 방식을 유한한 횟수로 반복해서, 마지막 상자에서 물건을 하나 선택하는 것으로 이 과정을 마칠 수 있다. 이 때, 각 상자에서 하나 씩의 물건을 선택함으로서 보여지는 상자-물건의 관계를 선택 함수에 해당한다고 할 수 있다. 그러나 이런 방법은 공집합이 아닌 집합의 모든 가산
[[게오르크 칸토어]]는 선택 공리와 동치인 [[정렬 정리]]가 증명이 필요 없을 정도로 자명한 "사고 법칙"({{llang|de|Denkgesetz|뎅크게제츠}})이라고 여겼다. 그러나 다른 수학자들은 이 "사고 법칙"에 대하여 회의적이었다. 1904년에 헝가리의 수학자 [[쾨니그 줄러]]({{llang|hu|Kőnig Gyula}})는 정렬 정리를 반증하였다고 발표하였다. 그러나 몇 주 뒤 [[펠릭스 하우스도르프]]가 이 "반증"의 오류를 지적하였다.
1904년에 [[에른스트 체르멜로]]는 [[정렬 정리]]를 보다 더 자명한 원리로부터 유도하기 위하여 선택 공리를 도입하였고, 이를 통해 [[정렬 정리]]를 증명하였다.<ref>{{저널 인용|이름=Ernst|성=Zermelo|저자고리=에른스트 체르멜로|제목=Beweis, daß jede Menge wohlgeordnet werden kann. (Aus einem an Herrn Hilbert gerichteten Briefe)|저널=Mathematische Annalen|권=59|호=4|쪽=514–516|날짜=1904|url=http://resolver.sub.uni-goettingen.de/purl?GDZPPN002260018|doi=10.1007/BF01445300|issn=0025-5831|jfm=35.0088.03|언어=de}}</ref>
1924년에 [[알프레트 타르스키]]는 타르스키 정리(선택 공리가 모든 무한 집합 <math>X</math>에 대하여 <math>|X|=|X^2|</math>인 것과 동치)를 프랑스의 한 유명 저널에 출판하려 하였는데, 이때 원고를 심사한 [[모리스 르네 프레셰]]는 "자명하게 참인 두 명제의 동치는 출판될 가치가 없다"고 답변하였고, 반면 같은 원고를 심사한 [[앙리 르베그]]는 "자명하게 거짓인 두 명제의 동치는 출판될 가치가 없다"고 답변하였다고 한다.<ref>{{저널 인용|제목=A system of axioms of set theory for the rationalists|이름=Jan|성=Mycielski|url=http://www.ams.org/notices/200602/fea-mycielski.pdf|저널=Notices of the American Mathematical Society|날짜=2006-02|권=53|호=2|쪽=206–213|zbl=1102.03050|언어=en}}</ref>{{rp|209}} 타르스키는 결국 논문을 타 저널에 출판하였다.<ref name="Tarski"/>
[[쿠르트 괴델]]은 [[내부 모형]] 이론을 사용하여, 선택 공리가 [[체르멜로-프렝켈 집합론]]과 일관적임을 보였다.<ref>{{저널 인용
줄 61 ⟶ 112:
| pmc = 1077160
| jstor=87239 | zbl = 0020.29701 | jfm = 64.0035.01 |언어=en}}</ref> 구체적으로, [[구성 가능 전체]] <math>L</math>은 [[체르멜로-프렝켈 집합론]]의 [[구조 (논리학)|모형]]이며, 이 모형에서는 선택 공리가 성립한다. [[폴 코언]]은 [[강제법]]을 사용하여 선택 공리의 부정이 체르멜로-프렝켈 집합론과 일관적임을 보였다.
의존적 선택 공리는 1942년에 [[파울 베르나이스]]가 도입하였다.<ref>{{저널 인용|mr=0006333 |last=Bernays|first= Paul | 저자고리=파울 베르나이스 |title=A system of axiomatic set theory III. Infinity and enumerability. Analysis |journal=Journal of Symbolic Logic |volume=7|year=1942|pages= 65–89|언어=en}}</ref>
현재까지도, 많은 수학자들은 선택 공리에 대하여 회의적인 입장을 보인다. 미국의 수학자 제리 로이드 보나({{llang|en|Jerry Lloyd Bona}})는 이에 대하여 다음과 같이 농담하였다.
줄 66 ⟶ 119:
{{lang|en|The Axiom of Choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn's lemma?}}}}
이는 선택 공리 자체는 직관적으로 보이지만, 이와 동치인 여러 명제([[정렬 정리]] 등)는 매우 비직관적임을 시사한다.
▲공식적인 형식화가 없었음에도 불구하고 19세기 말까지 선택공리는 암묵적으로 수학자들 사이에서 사용되어 왔다. 예를 들어, 집합 <math>X</math>가 공집합이 아닌 집합만을 포함한다고 했을 때, 수학자들은 종종 “모든 <math>X</math>에 포함된 (집합) <math>s</math>에 대해, <math>F(s)</math>를 <math>s</math>의 원소라고 하자” 라고 기술하곤 했다. 일반적으로 (함수) <math>F</math> 가 선택공리 없이 존재할 수 있음을 증명하기란 불가능했고, 그로 인해 Zermelo 이전 까지는 이를 심각한 문제로 여기지 않았다.
▲한편, 모든 함수가 선택공리를 필요로 하지는 않는다. 유한 집합 <math>X</math>의 경우, 선택공리는 다른 집합론의 공리들로부터 도출될 수 있다. 각각에 적어도 하나의 물건이 담긴 (유한한) 여러 개의 상자들을 상상 해 보자. 이 때 우리는 각 상자에서 정확히 하나의 물건을 선택할 수 있다. 예를 들자면 이런 식이다. 첫 번째 상자에서 물건 한 개를 선택하고, 두 번째 상자로 옮겨 여기서도 물건 한 개를 선택한다. 그 후 세 번째 상자에서도 물건을 하나 선택하고, 이런 방식을 유한한 횟수로 반복해서, 마지막 상자에서 물건을 하나 선택하는 것으로 이 과정을 마칠 수 있다. 이 때, 각 상자에서 하나 씩의 물건을 선택함으로서 보여지는 상자-물건의 관계를 선택 함수에 해당한다고 할 수 있다. 그러나 이런 방법은 공집합이 아닌 집합의 모든 가산 집합족(countable family)에 대해서도 선택함수가 존재한다는, 가산 선택 공리 (Axiom of Countable Choice)를 증명하는 데에는 사용될 수 없다. 같은 방법이 공집합이 아닌 집합들의 무한열 (infinite sequence of nonempty sets)에 적용될 경우, 각각의 유한한 단계에서는 함수가 정의되나 전체 집합족에 대한 함수가 정의되는 단계가 존재하지 않게 된다. 결과적으로 [[체르멜로-프렝켈 집합론]](ZF) 체계 하에서 선택공리 없이는 어떤 “극한” 선택함수도 구성할 수 없게 되는 것이다.
== 참고 문헌 ==
{{각주}}
* {{서적 인용|last=Herrlich |first=Horst|title=Axiom of Choice |publisher=Springer |날짜=2006 |series=Lecture Notes in Mathematics | 권=1876 |isbn=3-540-30989-6 | 언어=en}}
* {{서적 인용|last=
* {{서적 인용|last=Howard|first=Paul|author2-first=Jean E. |author2-last=Rubin|title= Equivalents of the axiom of choice II |날짜=1998|publisher=Elsevier|isbn=9780444877086|doi=10.1016/S0049-237X(08)70285-4|총서=Studies in Logic and the Foundations of Mathematics|권=116|issn=0049-237X|언어=en}}
* {{서적 인용|이름=Gregory H.|성=Moore|제목=Zermelo’s axiom of choice:
* {{서적 인용|이름=Per|성=Martin-Löf|장=100 years of Zermelo’s axiom of choice:
* {{저널 인용|성=Maddy|이름=Penelope|날짜=1988-06|제목=Believing the axioms I|저널=Journal of Symbolic Logic|권=53|호=2
* {{저널 인용|제목=Choice principles in elementary topology and analysis|이름=Horst|성=Herrlich|저널=Comment. Math. Univ. Carolin.|권=38|호=3|날짜=1997|쪽=545–552|url=http://www.emis.de/journals/CMUC/pdf/cmuc9703/herrli.pdf|언어=en}}
▲* {{서적 인용|이름=Gregory H.|성=Moore|제목=Zermelo’s axiom of choice: Its origins, development and influence|출판사=Springer |날짜=1982| doi = 10.1007/978-1-4613-9478-5 | 총서= Studies in the History of Mathematics and Physical Sciences | 권=8|isbn=978-1-4613-9480-8|issn= 0172-570X|언어=en}}
▲* {{서적 인용|이름=Per|성=Martin-Löf|장=100 years of Zermelo’s axiom of choice: What was the problem with it?|제목=Logicism, Intuitionism, and Formalism: What Has Become of Them?|편집자= Sten Lindström, Erik Palmgren, Krister Segerberg, Viggo Stoltenberg-Hansen | 날짜=2008 | isbn=1-4020-8925-2|doi=10.1007/978-1-4020-8926-8_10|장url=https://people.kth.se/~kurlberg/colloquium/2005/MartinLooef.pdf|언어=en}}
▲* {{저널 인용|성=Maddy|이름=Penelope|날짜=1988-06|제목=Believing the axioms I|저널=Journal of Symbolic Logic|권=53|호=2|날짜=1988-06|쪽=481–511|jstor=2274520|issn=0022-4812|zbl=0652.03033|mr=0947855|doi=10.2307/2274520|언어=en}}
== 바깥 고리 ==
줄 89 ⟶ 135:
* {{매스월드|id=AxiomofChoice|title=Axiom of choice}}
* {{웹 인용|url=http://plato.stanford.edu/entries/axiom-choice/|title=The axiom of choice|웹사이트=Stanford Encyclopedia of Philosophy|성=Bell|이름=John L.|출판사=[[스탠퍼드 대학교]]|날짜=2008-01-09|언어=en}}
* {{
* {{nlab|id=dependent choice|title=Dependent choice}}
* {{nlab|id=countable choice|title=Countable choice}}
* {{웹 인용|url=http://www.math.vanderbilt.edu/~schectex/ccc/choice.html|제목=A home page for the Axiom of Choice|이름=Eric|성=Schechter|날짜=2009-11-11|언어=en}}
* {{웹 인용|url=https://proofwiki.org/wiki/Axiom:Axiom_of_Choice|제목=Axiom: axiom of choice|웹사이트=ProofWiki|언어=en}}
* {{웹 인용|url=https://proofwiki.org/wiki/Axiom:Axiom_of_Dependent_Choice|제목=Axiom: axiom of dependent choice|웹사이트=ProofWiki|언어=en}}
* {{웹 인용|url=https://proofwiki.org/wiki/Axiom:Axiom_of_Countable_Choice|제목=Axiom: axiom of countable choice|웹사이트=ProofWiki|언어=en}}
* {{웹 인용|url=https://proofwiki.org/wiki/Axiom_of_Dependent_Choice_Implies_Axiom_of_Countable_Choice|제목=Axiom of dependent choice implies axiom of countable choice|웹사이트=ProofWiki|언어=en}}
* {{웹 인용|url=https://proofwiki.org/wiki/Equivalence_of_Versions_of_Axiom_of_Choice|제목=Equivalence of versions of axiom of choice|웹사이트=ProofWiki|언어=en}}
* {{웹 인용|url=https://proofwiki.org/wiki/Equivalence_of_Forms_of_Axiom_of_Countable_Choice|제목=Equivalence of forms of axiom of countable choice|웹사이트=ProofWiki|언어=en}}
* {{웹 인용|url=https://proofwiki.org/wiki/Axiom_of_Choice_Implies_Law_of_Excluded_Middle|제목=Axiom of choice implies law of excluded middle|웹사이트=ProofWiki|언어=en}}
{{집합론}}
| |||