수학에서, 선택 공리를 추가한 체르멜로-프렝켈 집합론(選擇公理를追加한Zermelo-Fraenkel集合論, 영어: Zermelo–Fraenkel set theory with the axiom of choice, 약자 ZFC)은 공리적 집합론의 하나이다. 현대 수학의 표준적인 수학기초론으로 사용된다.
선택 공리를 추가한 체르멜로-프렝켈 집합론은 1차 논리를 기반으로 하는 1차 집합론이며, 등호 밖에 하나의 이항 관계 만을 가진다. 논의 영역은 집합들이다 (집합은 공리를 통해 묘사되기만 할 뿐 직접적으로 정의되지는 않는다). 이항 관계 는 "가 의 원소"라고 읽는다.
는 각각
를 줄여 쓴 것이다.
선택 공리를 추가한 체르멜로-프렝켈 집합론의 공리계는 다음과 같은 공리 7개 및 공리꼴 2개로 정의된다. 이들은 통상적인 1차 술어 논리 공리들에 추가로 가정한 것이다.
체르멜로-프렝켈 공리계(ZF)는 ZFC에서 선택 공리를 제외한 것이며, 체르멜로 공리계(Z)는 ZFC에서 선택 · 정칙성 · 치환 공리(꼴)를 제외한 것이다.
집합의 기본 성질
확장공리와 정칙성 공리는 ZFC에서 쓰이는, 집합의 기본적인 성질들을 나타낸다. 즉, 집합은 순서 및 다른 추가 성질을 갖지 않는 구조이며 (확장성), 스스로를 포함하거나 기타 재귀적인 포함 관계를 가지지 못한다 (정칙성).
- 확장 공리(영어: axiom of extensionality) 혹은 외연 공리: 포함하는 원소가 전부 같은 두 집합은 서로 동일하다. 즉, 이는 사실상 집합의 동일함이 무엇인지를 정의한다. 확장 공리의 역은 서로 같은 집합이 포함하는 원소가 같다는 명제이며, 이는 이미 1차 논리의 공리이다.
- 정칙성 공리(영어: axiom of regularity) 혹은 기초 공리(영어: axiom of foundation): 공집합이 아닌 모든 집합은 자신과 서로소인 원소를 포함한다. 이에 따라, 스스로를 원소로 포함하는 집합이나, 스스로를 원소의 원소로 포함하는 집합 등은 존재할 수 없다. 사실, 정칙성 공리를 가정하면 이는 모든 모임 위에서도 성립하게 된다 (정초 관계#정초 모임 참고).
집합의 구성
분류·치환 공리꼴과 짝·합집합·멱집합 공리들은 주어진 집합으로부터 새로운 집합을 구성하는 방법들을 정의한다. 즉, 이미 구성된 집합들로부터, 이들의 순서쌍·합집합·멱집합을 정의할 수 있으며, 또한 이미 구성된 집합에 주어진 성질을 만족시키는 부분집합을 취하거나 (분류 공리꼴), 함수에 대한 상을 취할 수 있다 (치환 공리꼴).
- 분류 공리꼴(영어: axiom schema of specification): 가 집합이고 가 그 원소들이 만족할 수 있는 성질일 때, 이를 만족하는 것들로 이루어진 의 부분 집합이 존재한다. 여기에서 원소의 범위를 집합 로 제한하는 것은 러셀의 역설 등 역설을 피하기 위함이다. 1차 논리에서는 성질에 한정 기호를 가할 수 없으므로, 이는 낱개의 공리로 나타낼 수 없으며, 각 성질들에 대응하는 "무한 개"의 공리들로 구성된다. 또는 을 자유 변수로 가지는 (특히 를 자유 변수로 갖지 않는) 논리식 에 대하여,
- 치환 공리꼴(영어: axiom schema of replacement): 집합을 정의역으로 갖는, 형식적으로 정의된 함수가 있을 때, 그 치역을 포함하는 집합이 존재한다. 보다 엄밀하게 서술하면, 또는 을 자유변수로 가지는 (특히 를 자유 변수로 갖지 않는) 논리식 에 대하여,
여기에서 한정 기호 는 을 줄여 쓴 것이다. 즉, 성질 를 만족하는 가 유일하게 존재함을 말한다.
- 짝 공리(영어: axiom of pairing): 임의의 두 집합에 대해, 둘 모두를 원소로서 포함하는 집합이 존재한다.
- 합집합 공리(영어: axiom of union): 임의의 집합에 대해, 거기에 포함되는 원소들에 포함되는 원소들을 전부 포함하는 집합이 존재한다.
- 멱집합 공리: 임의의 집합 x에 대해, x의 모든 부분집합을 원소로 갖는 집합 y가 존재한다.
여기에서 는 를 줄여 쓴 것이다.
무한 공리와 선택 공리
무한 공리와 선택 공리는 ZFC 공리계에서 비교적 더 논란이 되는 공리들이다. 무한 공리는 가산 무한 집합의 존재를 가정하며, 여기에 멱집합을 취하여 더 큰 무한 기수와 순서수들을 정의할 수 있다. 선택 공리에 따르면, 무한한 수의 집합들에서 각각 하나의 원소를 무작위로 고를 수 있는데, 이 때 고르는 방법은 명시되지 않으며, 일부 경우 명시할 수 없음을 보일 수 있다.
- 무한 공리: 공집합을 원소로 가지며, 만약 를 원소로 가진다면 언제나 도 원소로 가지는 집합 가 존재한다.
여기서 이며, 공리 1부터 6까지를 이용해 임의의 집합 에 대해 가 유일하게 존재함을 증명할 수 있다. 은 공집합으로, 위의 공리들을 이용해 만약 집합이 하나라도 존재한다면 공집합이 유일하게 존재함을 증명할 수 있다. 정칙성 공리에 따라 항상 이므로, 이는
를 의미한다. 이들은 각각 자연수로 정의할 수 있다.
그렇다면, 이 공리는 자연수의 집합 의 존재를 의미한다. (만약 자연수를 다른 방법으로 정의하고 싶으면, 치환 공리꼴을 사용하여 이를 다른 정의로 번역할 수 있다.)
- 선택 공리: 공집합이 아닌 집합들의 집합 가 주어졌을 때, 의 각 원소로부터 하나씩의 원소를 고르는 함수 가 존재한다. 즉, 모든 에 대하여, 는 의 원소 를 골라낸다.
여기서 는 의 모든 원소들의 합집합이며, 합집합 공리에 따라 존재한다.
ZFC의 논의 영역은 집합만을 포함하며, 고유 모임을 포함하지 않는다. 모임을 직접적으로 다루려면 폰 노이만-베르나이스-괴델 집합론이나 모스-켈리 집합론을 사용하여야 한다.
ZFC의 모든 집합은 집합으로 구성되어 있으며, 원자(영어: atom, urelement)를 갖지 않는다. 또한, ZFC의 집합은 정칙적이다. 즉, 정칙성 공리에 의하여
또는
와 같은, 무한히 재귀적인 집합이 존재할 수 없다.
체르멜로-프렝켈 집합론의 일부 공리들은 서로 독립적이지 않다. 예를 들어, 나머지 공리들로부터 짝 공리를 유도할 수 있다.
멱집합 공리에 따라, 집합 이 존재한다. 임의의 집합 가 주어졌을 때, 다음과 같은 논리식 를 생각하자.
(이는 집합론의 언어 이외의 기호를 사용하지만, 집합론의 언어의 기호만을 사용하도록 번역할 수 있다.) 는 를 자유 변수로 가지며, 의 원소에 대하여 유일한 집합을 대응시킨다. 치환 공리꼴에 따라, 와 의 상을 원소로 포함하는 집합이 존재한다. 의 상은 이며, 의 상은 이다.
상대적 무모순성
ZF(C)와 같은 무모순성을 갖는 이론
다음 이론들은 서로 등무모순적이다.[1]
- . 이는 에서 정칙성 공리를 생략한 공리계이다.[1]:Corollary IV.4.4; 162, Corollary V.2.14
- [1]:Corollary IV.4.4; 162, Corollary V.2.14
- + 도달 불가능한 기수가 존재하지 않는다.[1]:148, Exercise IV.19
- + 일반화 연속체 가설[1]:175, Corollary VI.4.9
- + 일반화 연속체 가설 + 도달 불가능한 기수가 존재하지 않는다.[1]:177, Corollary VI.4.13
- [1]:170, Corollary VI.3.4
- [1]:172, Corollary VI.3.11
- [1]:211, VII.5.17
- [1]:209, Corollary VII.5.15
- [1]:245, Exercise VII.E4
- [1]:148, Exercise IV.19
- (폰 노이만-베르나이스-괴델 집합론). 이는 의 보존적 확장이다. 즉, 순수하게 집합에 대한 명제에 대하여, ZFC에서의 증명 가능성과 NBG에서의 증명 가능성이 서로 동치다.
ZF(C)보다 약한 이론
다음과 같은 이론들은 에 대하여 상대적으로 무모순적이지만 그 역은 성립하지 않는다.
이며,
이다.[1]:149, IV.30[2] 여기서 는 페아노 공리계이며, 는 체르멜로-프렝켈 집합론에서 무한 공리를 생략한 것이다. 따라서, (만약 가 무모순적이라면) 는 보다 무모순성에 따르면 더 강력하다. 물론, 이다.
마찬가지로, 다음이 성립한다.[1]:132, Theorem IV.6.5
여기서 는 에서 멱집합 공리를 제거하고, 대신 "모든 집합이 가산 집합이다"를 추가한 것이다. 사실, 이다. 여기서 은 유전적 가산 집합들의 집합이다.
마찬가지로, 다음이 성립한다.[1]:123, Theorem IV.3.13
여기서 는 에서 무한 공리를 제거하고, 대신 그 부정을 추가한 것이다. 사실, 이다.[3][4] 여기서 는 유전적 유한 집합들의 집합(즉, 폰 노이만 전체의 번째 단계)이다.
마찬가지로, 다음이 성립한다.[5]:110, Theorem II.2.2
여기서 는 에서 치환 공리꼴을 그 부정으로 대체한 것이다. 사실, 이다.[6]
ZFC보다 강한 이론
모스-켈리 집합론(영어: Morse–Kelley set theory) MK는 ZFC의 무모순성을 증명할 수 있어 ZFC보다 더 강한 이론이다.[5]:152, Exercise II.10.2 사실, MK의 유한한 수의 정리들을 공리들로 하는 이론 에 대하여,
이며, 특히 인 경우
이다.
만약 ZFC가 무모순적이라면, ZFC는 도달 불가능한 기수(및 기타 큰 기수)의 존재를 증명할 수 없다. 이는 ZFC+도달 불가능한 기수의 존재로부터 ZFC의 무모순성을 증명할 수 있기 때문이다. 사실,
인데, 이는 도달 불가능한 기수 에 대하여 이기 때문이다.
마찬가지로, ZF+약하게 도달 불가능한 기수의 존재는 ZFC의 무모순성을 보일 수 있다.
유한 공리화의 불가능성
ZFC는 공리꼴(영어: axiom schema)을 포함하고 있으므로, 실제로는 무한히 많은 수의 공리들로 이루어져 있다. 리처드 몬터규는 1961년에 ZFC도 ZF도 (만약 무모순적이라면) 유한개의 공리로는 대체될 수 없음을 증명했다. 사실, ZFC의 유한 부분 이론 에 대하여, 항상
이다.[5]:131, Corollary II.5.4 반면, 폰 노이만-베르나이스-괴델 집합론(NBG)은 유한 개의 공리로 공리화할 수 있다.
1890년대의 칸토어 역설의 발견과 1901년의 러셀의 역설의 발견으로, 엄밀한 수학기초론의 필요성이 대두되었다.
1904년에 에른스트 체르멜로는 정렬 정리를 증명하기 위하여 선택 공리를 도입하였다. 1908년, 에른스트 체르멜로는 최초의 공리적 집합론인 체르멜로 집합론을 발표했다.[7] 그러나 체르멜로 집합론은 순서수를 구성하기에 부족하였다. 구체적으로, 체르멜로 집합론에서는 알레프 수 를 정의할 수 없다. 또한, 체르멜로의 분류 공리꼴(독일어: Axiom der Aussonderung)에는 "명확한"(독일어: definit) 성질이라는 표현이 포함되어 있었는데, 이 개념은 엄밀하게 정의되지 않았다.
1907년에 러시아의 수학자 드미트리 미리마노프(러시아어: Дми́трий Семёнович Мирима́нов)는 집합의 정칙성의 개념을 정의하였고, 이 성질이 체르멜로의 공리계로부터 유도되지 않는다는 사실을 지적하였다.
1910년에 헤르만 바일은 "명확한" 성질을 1차 논리로 정의할 수 있는 성질로 정의하였다.[8] 1922년에 토랄프 스콜렘 또한 같은 제안을 하였다.[9]
또한, 1922년에 아브라함 프렝켈[10]과 스콜렘[9] 은 체르멜로의 공리계에 치환 공리꼴(독일어: Ersetzungsaxiom)을 추가하였다. 존 폰 노이만은 여기에 집합의 정칙성을 표현하는 정칙적 공리를 추가하여 ZFC를 완성하였다.
Cohen 2008, 54쪽, states: "The first really interesting axiom [of ZF set theory] is the Axiom of Infinity. If we drop it, then we can take as a model for ZF the set M of all finite sets which can be built up from ∅. [...] It is clear that M will be a model for the other axioms, since none of these lead out of the class of finite sets."
Weyl, H. (1910). “Über die Definitionen der mathematischen Grundbegriffe”. 《Mathematisch-naturwissenschaftliche Blätter》 (독일어) 7: 93–95, 109–113. JFM 41.0089.03.
Skolem, T. (1923). 〈Einige Bemerkungen zur axiomatischen Begründung der Mengenlehre〉. 《Matematikerkrongressen i Helsingfors den 4–7 Juli 1922, Den femte skandinaviska matematikerkongressen, redogörelse》 (독일어). 217–232쪽. JFM 49.0138.02.
- “ZFC”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4.
- Weisstein, Eric Wolfgang. “Zermelo-Fraenkel axioms”. 《Wolfram MathWorld》 (영어). Wolfram Research.
- Weisstein, Eric Wolfgang. “Zermelo-Fraenkel set thoery”. 《Wolfram MathWorld》 (영어). Wolfram Research.
- “ZFC”. 《nLab》 (영어).
- Bagaria, Joan (2014년 10월 8일). “Set theory”. 《Stanford Encyclopedia of Philosophy》 (영어).
- Ferreirós, José (2011년 7월 6일). “The early development of set theory”. 《Stanford Encyclopedia of Philosophy》 (영어).
- Hallett, Michael (2013년 7월 2일). “Zermelo’s axiomatization of set theory”. 《Stanford Encyclopedia of Philosophy》 (영어).
- Cohen, Paul Joseph (2008) [1966]. 《Set theory and the continuum hypothesis》. Mineola, New York: Dover Publications. ISBN 978-0-486-46921-8.
- Ebbinghaus, Heinz-Dieter (2007). 《Ernst Zermelo: An Approach to His Life and Work》 (영어). Springer. ISBN 978-3-540-49551-2.
- Hinman, Peter (2005). 《Fundamentals of Mathematical Logic》 (영어). A K Peters. ISBN 978-1-56881-262-5.
- Jech, Thomas (2003). 《Set Theory》 (영어) The Thi Millennium, Revis a Expa판. Springer. ISBN 3-540-44085-2.
- Maddy, Penelope (1988년 6월). “Believing the axioms I”. 《Journal of Symbolic Logic》 (영어) 53 (2): 481–511. doi:10.2307/2274520. ISSN 0022-4812. JSTOR 2274520. MR 0947855. Zbl 0652.03033.
- Roitman, Judith (2011) [1990]. 《Introduction to Modern Set Theory》. Virginia Commonwealth University. ISBN 978-0-9824062-4-3.
- Smullyan, Raymond M.; Fitting, Melvin (2010) [revised and corrected republication of the work originally published in 1996 by Oxford University Press, New York]. 《Set Theory and the Continuum Problem》. Dover. ISBN 978-0-486-47484-7.