선택 공리

집합론에서 선택 공리(選擇公理, , 약자 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을 증명할 수 있다.
즉, 체르멜로-프렝켈 집합론에서는 유한 개의 선택을 할 수 있지만, 무한 개의 선택은 (체르멜로-프렝켈 집합론이 무모순적이라면) 불가능하다.
체르멜로-프렝켈 집합론 아래, 선택 공리는 의존적 선택 공리를 함의하며, 의존적 선택 공리는 가산 선택 공리를 함의한다.
증명 (formula_40):
집합족 formula_41이 주어졌다고 하자. 집합
위에 다음과 같은 이항 관계 formula_43를 정의한다.
그렇다면, formula_45에 의하여 열
가 존재한다. 따라서 formula_48를 사용하여
를 고른 뒤
이라고 정의하면, formula_51이다. 따라서 formula_52는 가산 무한 집합족 formula_41의 선택 함수이다.
증명 (formula_54):
집합 formula_55 위의 이항 관계 formula_43가 주어졌다고 하고, 또한
가 성립한다고 하자. 그렇다면, 선택 공리에 의하여 집합족
의 선택 함수
가 존재한다. 임의의 원소 formula_61를 고르고
을 정의하면, 이는 의존적 선택 공리에 등장하는 조건을 만족시킨다.
증명 이론적 성질.
만약 체르멜로-프렝켈 집합론(ZF)이 일관적이라면, 선택 공리는 체르멜로-프렝켈 집합론과 독립적이다. 즉, 다음을 보일 수 있다.
모형 이론적 성질.
구성 가능 전체에서는 선택 공리가 성립한다.
즉, 체르멜로-프렝켈 집합론의 모형 formula_66이 주어졌을 때, formula_66 속의 구성 가능 전체 formula_68은 ZFC의 모형을 이룬다.
반면, 강제법을 사용하여 선택 공리가 실패하는 모형들을 구성할 수 있다.
선택 공리를 함의하는 명제.
체르멜로-프렝켈 집합론 아래, 다음 명제들은 선택 공리를 함의한다.
선택 공리와 동치인 명제.
집합족 formula_70가 다음 두 조건을 만족시키면, 유한 지표 집합족(有限指標集合族, )이라고 한다.
체르멜로-프렝켈 집합론을 가정하면, 선택 공리는 수많은 동치 명제들을 가지며, 다음과 같다. 즉,
인 명제 formula_79의 예는 다음을 들 수 있다.
선택 공리로부터 함의되는 명제.
만약 체르멜로-프렝켈 집합론이 일관적이라면 체르멜로-프렝켈 집합론으로 다음 정리들을 증명할 수 없지만, 선택 공리를 추가하면 증명할 수 있다.
그러나 선택 공리를 의존적 선택 공리(또는 가산 선택 공리)로 약화시킨다면, 이들 가운데 상당수는 증명 불가능하다. 예를 들어, 의존적 선택 공리는 르베그 가측 집합이 아닌 실수 집합의 존재를 증명할 수 없다.
가산 선택 공리만으로 대부분의 해석학을 전개할 수 있다.
역사.
공식적인 형식화가 없었음에도 불구하고 19세기 말까지 선택 공리는 암묵적으로 수학자들 사이에서 사용되어 왔다. 예를 들어, 집합 formula_55가 공집합이 아닌 집합만을 포함한다고 했을 때, 수학자들은 종종 “모든 formula_55에 포함된 (집합) formula_95에 대해, formula_96를 formula_95의 원소라고 하자” 라고 기술하곤 했다. 일반적으로 (함수) formula_98 가 선택 공리 없이 존재할 수 있음을 증명하기란 불가능했고, 그로 인해 체르멜로 이전까지는 이를 심각한 문제로 여기지 않았다.
한편, 모든 함수가 선택 공리를 필요로 하지는 않는다. 유한 집합 formula_55의 경우, 선택 공리는 다른 집합론의 공리들로부터 도출될 수 있다. 각각에 적어도 하나의 물건이 담긴 (유한한) 여러 개의 상자들을 상상 해 보자. 이때 우리는 각 상자에서 정확히 하나의 물건을 선택할 수 있다. 예를 들자면 이런 식이다. 첫 번째 상자에서 물건 한 개를 선택하고, 두 번째 상자로 옮겨 여기서도 물건 한 개를 선택한다. 그 후 세 번째 상자에서도 물건을 하나 선택하고, 이런 방식을 유한한 횟수로 반복해서, 마지막 상자에서 물건을 하나 선택하는 것으로 이 과정을 마칠 수 있다. 이 때, 각 상자에서 하나 씩의 물건을 선택함으로써 보여지는 상자-물건의 관계를 선택 함수에 해당한다고 할 수 있다. 그러나 이런 방법은 공집합이 아닌 집합의 모든 가산 집합족에 대해서도 선택 함수가 존재한다는, 가산 선택 공리를 증명하는 데에는 사용될 수 없다. 같은 방법이 공집합이 아닌 집합들의 무한열에 적용될 경우, 각각의 유한한 단계에서는 함수가 정의되나 전체 집합족에 대한 함수가 정의되는 단계가 존재하지 않게 된다. 결과적으로 체르멜로-프렝켈 집합론의 체계 아래서 선택 공리 없이는 어떤 “극한” 선택 함수도 구성할 수 없게 되는 것이다.
게오르크 칸토어는 선택 공리와 동치인 정렬 정리가 증명이 필요 없을 정도로 자명한 "사고 법칙"()이라고 여겼다. 그러나 다른 수학자들은 이 "사고 법칙"에 대하여 회의적이었다. 1904년에 헝가리의 수학자 쾨니그 줄러()는 정렬 정리를 반증하였다고 발표하였다. 그러나 몇 주 뒤 펠릭스 하우스도르프가 이 "반증"의 오류를 지적하였다.
1904년에 에른스트 체르멜로는 정렬 정리를 보다 더 자명한 원리로부터 유도하기 위하여 선택 공리를 도입하였고, 이를 통해 정렬 정리를 증명하였다.
1923년에 다비트 힐베르트는 일종의 선택 연산을 포함한 논리 체계를 제시하였다. 힐베르트는 이 기호를 formula_100이라고 표기하였다. 예를 들어, 술어 formula_101에 대하여 formula_102는 (만약 formula_103라면) formula_104를 만족시키는 집합이다. 이와 유사하게, 니콜라 부르바키는 1954년에 집합론 교재에서 선택 연산 formula_25를 사용하였다.
1924년에 알프레트 타르스키는 타르스키 정리(선택 공리가 모든 무한 집합 formula_55에 대하여 formula_107인 것과 동치)를 프랑스의 한 유명 저널에 출판하려 하였는데, 이때 원고를 심사한 모리스 르네 프레셰는 "자명하게 참인 두 명제의 동치는 출판될 가치가 없다"고 답변하였고, 반면 같은 원고를 심사한 앙리 르베그는 "자명하게 거짓인 두 명제의 동치는 출판될 가치가 없다"고 답변하였다고 한다. 타르스키는 결국 논문을 타 저널에 출판하였다.
1938년에 쿠르트 괴델은 내부 모형 이론을 사용하여, 선택 공리가 체르멜로-프렝켈 집합론과 일관적임을 보였다. 구체적으로, 구성 가능 전체 formula_108은 체르멜로-프렝켈 집합론의 모형이며, 이 모형에서는 선택 공리가 성립한다. 폴 코언은 강제법을 사용하여 선택 공리의 부정이 체르멜로-프렝켈 집합론과 일관적임을 보였다.
의존적 선택 공리는 1942년에 파울 베르나이스가 도입하였다.
현재까지도, 많은 수학자들은 선택 공리에 대하여 회의적인 입장을 보인다. 미국의 수학자 제리 로이드 보나(, 1945~)는 1977년에 이에 대하여 다음과 같이 농담하였다.
이는 위 세 명제가 체르멜로-프렝켈 집합론 아래 서로 동치이지만 직관적으로는 그 참·거짓 여부가 모순되게 보인다는 것에 대한 농담이다.