선택 공리
집합론에서, 선택 공리(選擇公理, , 약자 AC)는 공집합이 아닌 집합에서 한 원소를 고를 수 있으며, 또한 이를 무한 번 반복할 수 있다는 공리이다. 직관적으로 자연스러워 보이지만, 비직관적인 결과를 함의한다.
집합족 formula_1 위의 선택 함수(選擇函數, )는 다음 성질을 만족시키는 함수 formula_2이다.
만약 formula_5라면, formula_1는 물론 선택 함수를 가질 수 없다. 선택 공리 formula_7에 의하면, 공집합을 포함하지 않는 모든 집합족은 선택 함수를 갖는다.
임의의 기수 formula_8에 대하여, formula_9는 "크기가 formula_8 이하인, 공집합을 포함하지 않는 집합족은 선택 함수를 갖는다"는 명제이다. 특히, formula_11일 때 formula_12를 가산 선택 공리(可算選擇公理, )라고 한다.
임의의 집합 formula_13 및 이항 관계 formula_14가 주어졌고, 또한 이들이 다음 성질들을 만족시킨다고 하자.
그렇다면, 의존적 선택 공리(依存的選擇公理, ) formula_19에 따르면 다음 성질을 만족시키는 열
이 존재한다.
집합론의 언어 formula_24에 1항 연산 formula_25를 추가하자. 그렇다면, 이 언어 formula_26에서, 대역적 선택 공리(大域的選擇公理, )는 다음과 같은 문장이다.
이 경우, formula_25를 선택 연산()이라고 한다.
대역적 선택 공리는 선택 공리를 함의하며, ZF + 대역적 선택 공리는 ZFC의 보존적 확장이다.
집합족 formula_29가 주어졌으며, 각 formula_30 위에 정렬 순서 formula_31가 주어졌다고 하자. 그렇다면, 선택 함수
를 다음과 같이 자명하게 정의할 수 있다.
특히, 만약 formula_34 위에 정렬 순서가 주어졌다면, 이는 각 formula_30에 대하여 제한할 수 있으며, 이에 따라 선택 함수를 정의할 수 있다.
체르멜로-프렝켈 집합론 아래, 임의의 자연수 formula_36에 대하여 formula_37을 증명할 수 있다.
즉, 체르멜로-프렝켈 집합론에서는 유한 개의 선택을 할 수 있지만, 무한 개의 선택은 (체르멜로-프렝켈 집합론이 무모순적이라면) 불가능하다.
체르멜로-프렝켈 집합론 아래, 선택 공리는 의존적 선택 공리를 함의하며, 의존적 선택 공리는 가산 선택 공리를 함의한다.
만약 체르멜로-프렝켈 집합론(ZF)이 일관적이라면, 선택 공리는 체르멜로-프렝켈 집합론과 독립적이다. 즉, 다음을 보일 수 있다.
구성 가능 전체에서는 선택 공리가 성립한다.
즉, 체르멜로-프렝켈 집합론의 모형 formula_43이 주어졌을 때, formula_43 속의 구성 가능 전체 formula_45은 ZFC의 모형을 이룬다.
반면, 강제법을 사용하여 선택 공리가 실패하는 모형들을 구성할 수 있다.
체르멜로-프렝켈 집합론 아래, 다음 명제들은 선택 공리를 함의한다.
체르멜로-프렝켈 집합론(ZF)을 가정하면, 선택 공리는 수많은 동치 명제들을 가지며, 다음과 같다. 즉,
인 명제 formula_48의 예는 다음을 들 수 있다.
만약 체르멜로-프렝켈 집합론이 일관적이라면 체르멜로-프렝켈 집합론으로 다음 정리들을 증명할 수 없지만, 선택 공리를 추가하면 증명할 수 있다.
그러나 선택 공리를 의존적 선택 공리(또는 가산 선택 공리)로 약화시킨다면, 이들 가운데 상당수는 증명 불가능하다.
공식적인 형식화가 없었음에도 불구하고 19세기 말까지 선택 공리는 암묵적으로 수학자들 사이에서 사용되어 왔다. 예를 들어, 집합 formula_61가 공집합이 아닌 집합만을 포함한다고 했을 때, 수학자들은 종종 “모든 formula_61에 포함된 (집합) formula_63에 대해, formula_64를 formula_63의 원소라고 하자” 라고 기술하곤 했다. 일반적으로 (함수) formula_66 가 선택 공리 없이 존재할 수 있음을 증명하기란 불가능했고, 그로 인해 체르멜로 이전까지는 이를 심각한 문제로 여기지 않았다.
한편, 모든 함수가 선택 공리를 필요로 하지는 않는다. 유한 집합 formula_61의 경우, 선택 공리는 다른 집합론의 공리들로부터 도출될 수 있다. 각각에 적어도 하나의 물건이 담긴 (유한한) 여러 개의 상자들을 상상 해 보자. 이때 우리는 각 상자에서 정확히 하나의 물건을 선택할 수 있다. 예를 들자면 이런 식이다. 첫 번째 상자에서 물건 한 개를 선택하고, 두 번째 상자로 옮겨 여기서도 물건 한 개를 선택한다. 그 후 세 번째 상자에서도 물건을 하나 선택하고, 이런 방식을 유한한 횟수로 반복해서, 마지막 상자에서 물건을 하나 선택하는 것으로 이 과정을 마칠 수 있다. 이 때, 각 상자에서 하나 씩의 물건을 선택함으로서 보여지는 상자-물건의 관계를 선택 함수에 해당한다고 할 수 있다. 그러나 이런 방법은 공집합이 아닌 집합의 모든 가산 집합족에 대해서도 선택 함수가 존재한다는, 가산 선택 공리를 증명하는 데에는 사용될 수 없다. 같은 방법이 공집합이 아닌 집합들의 무한열에 적용될 경우, 각각의 유한한 단계에서는 함수가 정의되나 전체 집합족에 대한 함수가 정의되는 단계가 존재하지 않게 된다. 결과적으로 체르멜로-프렝켈 집합론의 체계 아래서 선택 공리 없이는 어떤 “극한” 선택 함수도 구성할 수 없게 되는 것이다.
게오르크 칸토어는 선택 공리와 동치인 정렬 정리가 증명이 필요 없을 정도로 자명한 "사고 법칙"()이라고 여겼다. 그러나 다른 수학자들은 이 "사고 법칙"에 대하여 회의적이었다. 1904년에 헝가리의 수학자 쾨니그 줄러()는 정렬 정리를 반증하였다고 발표하였다. 그러나 몇 주 뒤 펠릭스 하우스도르프가 이 "반증"의 오류를 지적하였다.
1904년에 에른스트 체르멜로는 정렬 정리를 보다 더 자명한 원리로부터 유도하기 위하여 선택 공리를 도입하였고, 이를 통해 정렬 정리를 증명하였다.
1923년에 다비트 힐베르트는 일종의 선택 연산을 포함한 논리 체계를 제시하였다. 힐베르트는 이 기호를 formula_68이라고 표기하였다. 예를 들어, 술어 formula_69에 대하여 formula_70는 (만약 formula_71라면) formula_72를 만족시키는 집합이다. 이와 유사하게, 니콜라 부르바키는 1954년에 집합론 교재에서 선택 연산 formula_25를 사용하였다.
1924년에 알프레트 타르스키는 타르스키 정리(선택 공리가 모든 무한 집합 formula_61에 대하여 formula_75인 것과 동치)를 프랑스의 한 유명 저널에 출판하려 하였는데, 이때 원고를 심사한 모리스 르네 프레셰는 "자명하게 참인 두 명제의 동치는 출판될 가치가 없다"고 답변하였고, 반면 같은 원고를 심사한 앙리 르베그는 "자명하게 거짓인 두 명제의 동치는 출판될 가치가 없다"고 답변하였다고 한다. 타르스키는 결국 논문을 타 저널에 출판하였다.
1938년에 쿠르트 괴델은 내부 모형 이론을 사용하여, 선택 공리가 체르멜로-프렝켈 집합론과 일관적임을 보였다. 구체적으로, 구성 가능 전체 formula_76은 체르멜로-프렝켈 집합론의 모형이며, 이 모형에서는 선택 공리가 성립한다. 폴 코언은 강제법을 사용하여 선택 공리의 부정이 체르멜로-프렝켈 집합론과 일관적임을 보였다.
의존적 선택 공리는 1942년에 파울 베르나이스가 도입하였다.
현재까지도, 많은 수학자들은 선택 공리에 대하여 회의적인 입장을 보인다. 미국의 수학자 제리 로이드 보나(, 1945~)는 1977년에 이에 대하여 다음과 같이 농담하였다.
이는 위 세 명제가 체르멜로-프렝켈 집합론 아래 서로 동치이지만 직관적으로는 그 참·거짓 여부가 모순되게 보인다는 것에 대한 농담이다.