선택 공리
집합론에서, 선택 공리(選擇公理, 영어: axiom of choice, 약자 AC)는 공집합이 아닌 집합에서 한 원소를 고를 수 있으며, 또한 이를 무한 번 반복할 수 있다는 공리이다. 직관적으로 자연스러워 보이지만, 비직관적인 결과를 함의한다.
목차
정의[편집]
집합족 위의 선택 함수(選擇函數, 영어: choice function)는 다음 성질을 만족시키는 함수 이다.
만약 라면, 는 물론 선택 함수를 가질 수 없다. 선택 공리 에 의하면, 공집합을 포함하지 않는 모든 집합족은 선택 함수를 갖는다.
약화된 형태[편집]
임의의 기수 에 대하여, 는 "크기가 이하인, 공집합을 포함하지 않는 집합족은 선택 함수를 갖는다"는 명제이다. 특히, 일 때 를 가산 선택 공리(可算選擇公理, 영어: axiom of countable choice)라고 한다.
임의의 집합 및 이항 관계 가 주어졌고, 또한 이들이 다음 성질들을 만족시킨다고 하자.
- 임의의 에 대하여, 인 가 존재한다.
그렇다면, 의존적 선택 공리(依存的選擇公理, 영어: axiom of dependent choice) 에 따르면 다음 성질을 만족시키는 열
이 존재한다.
- 임의의 에 대하여,
대역적 선택 공리[편집]
집합론의 언어 에 1항 연산 를 추가하자. 그렇다면, 이 언어 에서, 대역적 선택 공리(大域的選擇公理, 영어: axiom of global choice)는 다음과 같은 문장이다.
이 경우, 를 선택 연산(영어: choice operator)이라고 한다.
대역적 선택 공리는 선택 공리를 함의하며, ZF + 대역적 선택 공리는 ZFC의 보존적 확장이다.
성질[편집]
집합족 가 주어졌으며, 각 위에 정렬 순서 가 주어졌다고 하자. 그렇다면, 선택 함수
를 다음과 같이 자명하게 정의할 수 있다.
특히, 만약 위에 정렬 순서가 주어졌다면, 이는 각 에 대하여 제한할 수 있으며, 이에 따라 선택 함수를 정의할 수 있다.
함의 관계[편집]
체르멜로-프렝켈 집합론 아래, 임의의 자연수 에 대하여 을 증명할 수 있다.
즉, 체르멜로-프렝켈 집합론에서는 유한 개의 선택을 할 수 있지만, 무한 개의 선택은 (체르멜로-프렝켈 집합론이 무모순적이라면) 불가능하다.
체르멜로-프렝켈 집합론 아래, 선택 공리는 의존적 선택 공리를 함의하며, 의존적 선택 공리는 가산 선택 공리를 함의한다.
증명 ():
집합족 이 주어졌다고 하자. 집합
위에 다음과 같은 이항 관계 를 정의한다.
그렇다면, 에 의하여 열
가 존재한다. 따라서 를 사용하여
를 고른 뒤
이라고 정의하면, 이다. 따라서 는 가산 무한 집합족 의 선택 함수이다.
증명 ():
집합 위의 이항 관계 가 주어졌다고 하고, 또한
가 성립한다고 하자. 그렇다면, 선택 공리에 의하여 집합족
의 선택 함수
가 존재한다. 임의의 원소 를 고르고
을 정의하면, 이는 의존적 선택 공리에 등장하는 조건을 만족시킨다.
증명 이론적 성질[편집]
만약 체르멜로-프렝켈 집합론(ZF)이 일관적이라면, 선택 공리는 체르멜로-프렝켈 집합론과 독립적이다. 즉, 다음을 보일 수 있다.
모형 이론적 성질[편집]
구성 가능 전체에서는 선택 공리가 성립한다.
즉, 체르멜로-프렝켈 집합론의 모형 이 주어졌을 때, 속의 구성 가능 전체 은 ZFC의 모형을 이룬다.
반면, 강제법을 사용하여 선택 공리가 실패하는 모형들을 구성할 수 있다.
선택 공리를 함의하는 명제[편집]
체르멜로-프렝켈 집합론 아래, 다음 명제들은 선택 공리를 함의한다.
선택 공리와 동치인 명제[편집]
체르멜로-프렝켈 집합론(ZF)을 가정하면, 선택 공리는 수많은 동치 명제들을 가지며, 다음과 같다. 즉,
인 명제 의 예는 다음을 들 수 있다.
- 공집합을 포함하지 않는 집합족 에 대하여, 이다.
- 초른의 보조정리
- 정렬 정리
- 티호노프 정리
- (타르스키 정리 영어: Tarski theorem) 임의의 무한 기수 에 대하여, 이다.[1]
- (기수의 비교 가능성) 임의의 두 기수 , 에 대하여, 이거나, 이거나, 이다.
- (타이히뮐러-투키 보조정리 영어: Teichmüller-Tukey lemma) 임의의 유한 특성 집합족은 극대 원소를 갖는다.
- 모든 벡터 공간은 기저를 갖는다.
- 자명환이 아닌 (단위원을 갖는) 환은 극대 아이디얼을 갖는다.
- 망각 함자 의 상은 공집합이 아닌 모든 집합의 모임이다.
- (무한군에 대한) 라그랑주 정리 (군론)
- 모든 연결 그래프는 생성나무를 갖는다.
선택 공리로부터 함의되는 명제[편집]
만약 체르멜로-프렝켈 집합론이 일관적이라면 체르멜로-프렝켈 집합론으로 다음 정리들을 증명할 수 없지만, 선택 공리를 추가하면 증명할 수 있다.
- 괴델의 완전성 정리
- 모든 체는 대수적 폐포를 갖는다.
- 와 는 덧셈군으로서 서로 동형이다.
- (닐센-슈라이어 정리) 자유군의 모든 부분군은 자유군이다.
- 한-바나흐 정리
- 베르의 범주 정리
- 바나흐-타르스키 역설
- 르베그 가측 집합이 아닌 실수 집합이 존재한다.
그러나 선택 공리를 의존적 선택 공리(또는 가산 선택 공리)로 약화시킨다면, 이들 가운데 상당수는 증명 불가능하다.
역사[편집]
공식적인 형식화가 없었음에도 불구하고 19세기 말까지 선택 공리는 암묵적으로 수학자들 사이에서 사용되어 왔다. 예를 들어, 집합 가 공집합이 아닌 집합만을 포함한다고 했을 때, 수학자들은 종종 “모든 에 포함된 (집합) 에 대해, 를 의 원소라고 하자” 라고 기술하곤 했다. 일반적으로 (함수) 가 선택 공리 없이 존재할 수 있음을 증명하기란 불가능했고, 그로 인해 체르멜로 이전까지는 이를 심각한 문제로 여기지 않았다.
한편, 모든 함수가 선택 공리를 필요로 하지는 않는다. 유한 집합 의 경우, 선택 공리는 다른 집합론의 공리들로부터 도출될 수 있다. 각각에 적어도 하나의 물건이 담긴 (유한한) 여러 개의 상자들을 상상 해 보자. 이때 우리는 각 상자에서 정확히 하나의 물건을 선택할 수 있다. 예를 들자면 이런 식이다. 첫 번째 상자에서 물건 한 개를 선택하고, 두 번째 상자로 옮겨 여기서도 물건 한 개를 선택한다. 그 후 세 번째 상자에서도 물건을 하나 선택하고, 이런 방식을 유한한 횟수로 반복해서, 마지막 상자에서 물건을 하나 선택하는 것으로 이 과정을 마칠 수 있다. 이 때, 각 상자에서 하나 씩의 물건을 선택함으로서 보여지는 상자-물건의 관계를 선택 함수에 해당한다고 할 수 있다. 그러나 이런 방법은 공집합이 아닌 집합의 모든 가산 집합족에 대해서도 선택 함수가 존재한다는, 가산 선택 공리를 증명하는 데에는 사용될 수 없다. 같은 방법이 공집합이 아닌 집합들의 무한열에 적용될 경우, 각각의 유한한 단계에서는 함수가 정의되나 전체 집합족에 대한 함수가 정의되는 단계가 존재하지 않게 된다. 결과적으로 체르멜로-프렝켈 집합론의 체계 아래서 선택 공리 없이는 어떤 “극한” 선택 함수도 구성할 수 없게 되는 것이다.
게오르크 칸토어는 선택 공리와 동치인 정렬 정리가 증명이 필요 없을 정도로 자명한 "사고 법칙"(독일어: Denkgesetz 뎅크게제츠[*])이라고 여겼다. 그러나 다른 수학자들은 이 "사고 법칙"에 대하여 회의적이었다. 1904년에 헝가리의 수학자 쾨니그 줄러(헝가리어: Kőnig Gyula)는 정렬 정리를 반증하였다고 발표하였다. 그러나 몇 주 뒤 펠릭스 하우스도르프가 이 "반증"의 오류를 지적하였다.
1904년에 에른스트 체르멜로는 정렬 정리를 보다 더 자명한 원리로부터 유도하기 위하여 선택 공리를 도입하였고, 이를 통해 정렬 정리를 증명하였다.[2]
1923년에 다비트 힐베르트는 일종의 선택 연산을 포함한 논리 체계를 제시하였다.[3][4] 힐베르트는 이 기호를 이라고 표기하였다. 예를 들어, 술어 에 대하여 는 (만약 라면) 를 만족시키는 집합이다. 이와 유사하게, 니콜라 부르바키는 1954년에 집합론 교재에서 선택 연산 를 사용하였다.[5]
1924년에 알프레트 타르스키는 타르스키 정리(선택 공리가 모든 무한 집합 에 대하여 인 것과 동치)를 프랑스의 한 유명 저널에 출판하려 하였는데, 이때 원고를 심사한 모리스 르네 프레셰는 "자명하게 참인 두 명제의 동치는 출판될 가치가 없다"고 답변하였고, 반면 같은 원고를 심사한 앙리 르베그는 "자명하게 거짓인 두 명제의 동치는 출판될 가치가 없다"고 답변하였다고 한다.[6] 타르스키는 결국 논문을 타 저널에 출판하였다.[1]
1938년에 쿠르트 괴델은 내부 모형 이론을 사용하여, 선택 공리가 체르멜로-프렝켈 집합론과 일관적임을 보였다.[7][8] 구체적으로, 구성 가능 전체 은 체르멜로-프렝켈 집합론의 모형이며, 이 모형에서는 선택 공리가 성립한다. 폴 코언은 강제법을 사용하여 선택 공리의 부정이 체르멜로-프렝켈 집합론과 일관적임을 보였다.
의존적 선택 공리는 1942년에 파울 베르나이스가 도입하였다.[9]
현재까지도, 많은 수학자들은 선택 공리에 대하여 회의적인 입장을 보인다. 미국의 수학자 제리 로이드 보나(영어: Jerry Lloyd Bona, 1945~)는 1977년에 이에 대하여 다음과 같이 농담하였다.
“ | 선택 공리는 당연히 참이고, 정렬 정리는 당연히 거짓이고, 초른의 보조정리는 글쎄……? The Axiom of Choice is obviously true; the Well Ordering principle is obviously false; and who can tell about Zorn’s lemma? |
” |
— [10]
|
이는 위 세 명제가 체르멜로-프렝켈 집합론 아래 서로 동치이지만 직관적으로는 그 참·거짓 여부가 모순되게 보인다는 것에 대한 농담이다.
참고 문헌[편집]
- ↑ 가 나 Tajtebaum-Tarski, A. (1924). “Sur quelques théorèmes qui équivalent à l’axiome du choix”. 《Fundamenta Mathematicae》 (프랑스어) 5: 147–154.
- ↑ Zermelo, Ernst (1904). “Beweis, daß jede Menge wohlgeordnet werden kann. (Aus einem an Herrn Hilbert gerichteten Briefe)”. 《Mathematische Annalen》 (독일어) 59 (4): 514–516. ISSN 0025-5831. JFM 35.0088.03. doi:10.1007/BF01445300.
- ↑ Hilbert, David (1923). “Die logischen Grundlagen der Mathematik”. 《Mathematische Annalen》 (독일어) 88: 151-165. ISSN 0025-5831. JFM 48.1120.01.
- ↑ Hilbert, David (1925). “Über das Unendliche”. 《Mathematische Annalen》 (독일어) 95: 161–190. ISSN 0025-5831. JFM 51.0044.02.
- ↑ Bourbaki, Nicolas (1954). 《Éléments de mathematique. Théorie des ensembles. Chapitre 1. Description de la mathématique formelle》 (프랑스어) 1판. Hermann et compagnie. Zbl 0055.27902.
- ↑ Mycielski, Jan (2006년 2월). “A system of axioms of set theory for the rationalists” (PDF). 《Notices of the American Mathematical Society》 (영어) 53 (2): 206–213. Zbl 1102.03050.
- ↑ Gödel, Kurt (1938). “The consistency of the axiom of choice and of the generalized continuum-hypothesis”. 《Proceedings of the National Academy of Sciences of the United States of America》 (영어). JFM 64.0035.01. JSTOR 87239. PMC 1077160. PMID 16577857. Zbl 0020.29701. doi:10.1073/pnas.24.12.556.
- ↑ Ruelle, David (2007). 《The Mathematician's Brain》. Princeton University Press. ISBN 978-0-691-12982-2.
- ↑ Bernays, Paul (1942년 6월). “A system of axiomatic set theory. Part III. Infinity and enumerability. Analysis”. 《The Journal of Symbolic Logic》 (영어) 7 (2): 65–89. ISSN 0022-4812. JSTOR 2266303. MR 6333. Zbl 0061.09201. doi:10.2307/2266303.
- ↑ Schechter, Eric (1997). 《Handbook of analysis and its foundations》 (영어). Academic Press. Zbl 0943.26001. doi:10.1016/B978-0-12-622760-4.50033-9.
- Herrlich, Horst (2006). 《Axiom of choice》. Lecture Notes in Mathematics (영어) 1876. Springer. ISBN 978-3-540-30989-5. ISSN 0075-8434. Zbl 1102.03049. doi:10.1007/11601562.
- Howard, Paul; Rubin, Jean E. (1998). 《Consequences of the axiom of choice》. Mathematical Surveys and Monographs (영어) 59. American Mathematical Society. ISBN 978-0-8218-0977-8.
- Rubin, Herman; Rubin, Jean E. (1985). 《Equivalents of the axiom of choice II》. Studies in Logic and the Foundations of Mathematics (영어) 116. Elsevier. ISBN 9780444877086. ISSN 0049-237X. doi:10.1016/S0049-237X(08)70285-4.
- Jech, Thomas (1973). 《The axiom of choice》. Studies in Logic and the Foundations of Mathematics (영어) 75. North-Holland. ISBN 978-0-486-46624-8. Zbl 0259.02051.
- Moore, Gregory H. (1982). 《Zermelo’s axiom of choice: its origins, development and influence》. Studies in the History of Mathematics and Physical Sciences (영어) 8. Springer. ISBN 978-1-4613-9480-8. ISSN 0172-570X. doi:10.1007/978-1-4613-9478-5.
- Martin-Löf, Per (2008). 〈100 years of Zermelo’s axiom of choice: what was the problem with it?〉 (PDF). Lindström, Sten; Palmgren, Erik; Segerberg, Krister; Stoltenberg-Hansen, Viggo. 《Logicism, Intuitionism, and Formalism: What Has Become of Them?》 (영어). ISBN 1-4020-8925-2. doi:10.1007/978-1-4020-8926-8_10.
- Maddy, Penelope (1988년 6월). “Believing the axioms I”. 《Journal of Symbolic Logic》 (영어) 53 (2): 481–511. ISSN 0022-4812. JSTOR 2274520. MR 0947855. Zbl 0652.03033. doi:10.2307/2274520.
- Herrlich, Horst (1997). “Choice principles in elementary topology and analysis” (PDF). 《Commentationes Mathematicae Universitatis Carolinae》 (영어) 38 (3): 545–552. ISSN 0010-2628. Zbl 0938.54007.
외부 링크[편집]
- Grishin, V.N. (2001). “Axiom of choice”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. ISBN 978-1-55608-010-4.
- Weisstein, Eric Wolfgang. “Axiom of choice”. 《Wolfram MathWorld》 (영어). Wolfram Research.
- Bell, John L. (2015년 3월 18일). “The axiom of choice”. 《Stanford Encyclopedia of Philosophy》 (영어). 스탠퍼드 대학교.
- Avigad, Jeremy; Zach, Richard (2013년 11월 27일). “The epsilon calculus”. 《Stanford Encyclopedia of Philosophy》 (영어). 스탠퍼드 대학교.
- Slater, Barry Hartley. “Epsilon calculi”. 《Internet Encyclopedia of Philosophy》 (영어). ISSN 2161-0002.
- “Axiom of choice”. 《nLab》 (영어).
- “Dependent choice”. 《nLab》 (영어).
- “Countable choice”. 《nLab》 (영어).
- “Choice operator”. 《nLab》 (영어).
- “Choice object”. 《nLab》 (영어).
- “Small violations of choice”. 《nLab》 (영어).
- “Axiom of multiple choice”. 《nLab》 (영어).
- “Small cardinality selection axiom”. 《nLab》 (영어).
- Schechter, Eric (2009년 11월 11일). “A home page for the Axiom of Choice” (영어).
- “Definition: choice function”. 《ProofWiki》 (영어).
- “Axiom: axiom of choice”. 《ProofWiki》 (영어).
- “Axiom: axiom of dependent choice”. 《ProofWiki》 (영어).
- “Axiom: axiom of countable choice”. 《ProofWiki》 (영어).
- “Axiom of dependent choice implies axiom of countable choice”. 《ProofWiki》 (영어).
- “Equivalence of versions of axiom of choice”. 《ProofWiki》 (영어).
- “Equivalence of forms of axiom of countable choice”. 《ProofWiki》 (영어).
- “Axiom of choice implies law of excluded middle”. 《ProofWiki》 (영어).
집합론 | |
---|---|
집합 | |
함수 | |
기수 | |
순서수 | |
역설의 해소 | |
선택 공리 | |
집합론의 모형 | |
큰 기수 | |
ZF와 독립된 명제 |