선택의 공리

Axiom of choice
각 집합 Si 항아리로 표현되고 그 원소는 구슬로 표현되는 선택 공리의 예시. 각 원소 xi 오른쪽에 대리석으로 표현되어 있습니다. 색상은 선택 공리를 채택한 후 구슬의 기능적 연관성을 제안하는 데 사용됩니다. 이러한 선택 함수의 존재는 모든 Si 유한하더라도 무한 카디널리티의 집합에 대해 일반적으로 ZF와 무관합니다.
(Si)는i 실수 R 위에 색인된 무한 색인 집합들이다. 즉, 각각의 실수 i에 대한 집합 S가i 있고, 위에 표시된 작은 표본이 있습니다. 각 집합에는 적어도 하나 이상의 요소가 포함되어 있을 수 있습니다. 선택 공리를 사용하면 각 집합에서 하나의 요소를 선택할 수 있으며i, 이는 x가 S에서i 추출된 실수 위에 색인화된 요소(xi)의 해당 패밀리를 형성합니다. 일반적으로 집합들은 R뿐만 아니라 임의의 집합 I, 즉 집합의 요소들에 대한 인덱스로 사용되는 요소들을 인덱스 집합이라고 합니다.

수학에서 선택의 공리(), 약칭 AC 또는 AoC공집합이 아닌 집합들데카르트 이 공집합이 아니라는 진술과 동등한 집합론공리입니다. 비공식적으로, 선택의 공리는 각각 적어도 하나의 원소를 포함하는 임의의 집합의 집합이 주어지면, 집합이 무한하더라도 각 집합에서 하나의 원소를 선택하여 새로운 집합을 구성할 수 있다고 말합니다. Formally, it states that for every indexed family of nonempty sets, there exists an indexed set such that for every . 선택의 공리는 1904년 에른스트 제르멜로정리의 잘 정리된 증명을 공식화하기 위해 공식화했습니다.[1]

많은 경우 선택 공리를 호출하지 않고 요소를 선택하여 생성된 집합을 만들 수 있습니다. 특히 요소를 선택하는 집합의 수가 유한하거나 요소를 선택하는 방법에 대한 표준 규칙을 사용할 수 있는 경우 각 집합에서 정확히 하나의 요소에 대해 유지되는 몇 가지 구별되는 속성이 있습니다. 예시적인 예는 자연수에서 선택된 집합입니다. 이러한 집합에서 항상 가장 작은 수를 선택할 수 있습니다. 예를 들어, 집합 {{4, 5, 6}, {10, 12}, {1, 400, 617, 8000}}가 주어지면 각 가장 작은 요소를 포함하는 집합은 {4, 10, 1}입니다. 이 경우 "가장 작은 숫자를 선택"하는 것이 선택 함수입니다. 자연수에서 무한히 많은 집합을 모았더라도 각 집합에서 가장 작은 원소를 선택하여 집합을 생성하는 것은 항상 가능할 것입니다. 즉, 선택 함수는 선택한 요소 집합을 제공합니다. 그러나 실수의 비어 있지 않은 모든 부분 집합의 집합에 대한 명확한 선택 함수는 알려져 있지 않습니다. 그런 경우에는 선택의 공리가 발동되어야 합니다.

Bertrand Russell은 비유를 만들었습니다: 어떤 (심지어 무한한) 신발 모음에 대해, 적절한 신발 모음(즉, 세트)을 얻기 위해 각 신발에서 왼쪽 신발을 고를 수 있습니다. 이것은 선택 함수를 직접 정의하는 것을 가능하게 합니다. 무한히 많은 양말 한 켤레의 집합(특징이 없는 것으로 가정)의 경우, 선택 공리를 호출하지 않고 각 양말 한 켤레에서 한 켤레를 선택하여 집합을 구성하는 함수를 만들 수 있는 명백한 방법은 없습니다.[2]

비록 원래 논란의 여지가 있지만, 현재 대부분의 수학자들은 선택 공리를 망설이지 않고 사용하고 있으며,[3] 이는 선택 공리를 가진 Zermelo-Frankel 집합 이론의 표준 형태에 포함되어 있습니다. 를 사용하는 한 가지 동기는 티초노프의 정리와 같이 일반적으로 인정되는 많은 수학적 결과가 증명을 위해 선택 공리를 필요로 하기 때문입니다. 현대 집합 이론가들은 또한 결정론의 공리와 같이 선택의 공리와 양립할 수 없는 공리를 연구합니다. 선택의 공리가 수용된 건설적 수학에는 다양한 종류가 있지만, 일부 건설적 수학에서는 선택의 공리가 회피됩니다.

진술

선택 함수(선택 함수, selector 또는 selection이라고도 )는 비어 있지 않은 집합들의 집합 X에 정의되는 함수 f로서, X의 모든 집합 A에 대하여 f(A)는 A의 원소입니다. 이 개념을 사용하면 다음과 같은 공리를 나타낼 수 있습니다.

공리 — 비어 있지 않은 집합들의 임의의 집합 X에 대하여, X에 정의되고 X의 각 집합을 해당 집합의 원소에 매핑하는 선택 함수 f가 존재합니다.

공식적으로는 다음과 같이 표현할 수 있습니다.

따라서, 공리의 부정은 선택 함수가 없는 비어 있지 않은 집합들의 집합의 존재로 표현될 수 있습니다. 형식적으로, ¬ ∀X [ ( ) →Q( ) ] {\\n 의 논리적 동치를 사용하여 유도될 수 있습니다.를 들어, \ X ~ [) Q(X)] \exists X[P(X)\land \n

비어 있지 않은 집합들의 집합 X에 대한 각 선택 함수는 X에 있는 집합들의 데카르트 곱의 요소입니다. 이것은 주어진 집합이 인자로서 두 번 이상 발생할 수 있는 집합의 데카르트 곱의 가장 일반적인 상황은 아니지만, 주어진 집합이 인자로서 나타날 때마다 동일한 요소를 선택하는 그러한 곱의 요소에 초점을 맞출 수 있습니다. 그리고 그러한 요소들은 가군의 모든 별개의 집합들의 데카르트 곱의 요소에 해당합니다. 선택의 공리는 그러한 요소의 존재를 주장하며, 따라서 다음과 같습니다.

비어 있지 않은 집합들의 임의의 족이 주어졌을 때, 그들의 데카르트 곱은 비어 있지 않은 집합입니다.

명명법 ZF, AC 및 ZFC

이 글과 선택의 공리에 대한 다른 논의에서는 다음과 같은 약어가 일반적입니다.

  • AC – 선택의 공리. 더 드물게 AoC를 사용합니다.[4]
  • ZF – Zermelo–Frankel 집합 이론에서 선택 공리를 생략합니다.
  • ZFC – Zermelo–Frankel 집합론, 선택의 공리를 포함하도록 확장되었습니다.

변종

선택의 공리에 대한 다른 많은 동등한 진술들이 있습니다. 이것들은 집합론의 다른 기본 공리들이 존재할 때, 그것들은 선택 공리를 암시하고 그것에 의해 암시된다는 점에서 동등합니다.

한 가지 변형은 각 선택 함수를 해당 범위로 대체함으로써 선택 함수의 사용을 방지합니다.

쌍으로 서로소인 비어 있지 않은 집합들의 임의의 집합 X가 주어졌을 때, X의 각 집합들과 정확히 하나의 원소를 포함하는 집합 C가 적어도 하나 존재합니다.[5]

이것은 집합 X임의의 분할에 대하여 분할의 각 부분으로부터 정확히 하나의 원소를 포함하는 X의 부분집합 C의 존재를 보장합니다.

또 다른 등가 공리는 다른 집합의 멱집합인 집합 X만 고려합니다.

임의의 집합 A에 대하여, (빈 집합이 제거된) A거듭제곱 집합은 선택 함수를 갖습니다.

이 공식을 사용하는 저자들은 흔히 A에 대한 선택 함수를 말하지만, 이는 선택 함수의 개념이 조금 다릅니다. 정의역은 (빈 집합을 제거한) A의 거듭제곱 집합이므로 모든 집합 A에 대해 의미가 있는 반면, 이 문서의 다른 곳에서 사용된 정의에서는 집합 집합 집합에 대한 선택 함수의 정의역은 해당 집합이므로 집합 집합에 대해서만 의미가 있습니다. 이 대안적인 선택 개념 함수를 사용하면, 선택 공리는 다음과 같이 간결하게 표현될 수 있습니다.

모든 세트에는 선택 기능이 있습니다.[6]

에 해당하는 것.

임의의 집합 A에 대하여, A의 비어 있지 않은 부분집합 B대하여, f(B)가 B놓이는 함수 f가 존재합니다.

따라서 공리의 부정은 다음과 같이 표현할 수 있습니다.

(A의 비어 있지 않은 부분집합들의 집합 위에) 모든 함수 f에 대하여, f(B)가 B에 속하지 않도록 B가 존재하는 집합 A가 존재합니다.

유한 집합에 대한 제한

선택 공리의 일반적인 문장은 비어 있지 않은 집합의 집합이 유한한지 무한한지를 지정하지 않으며, 따라서 비어 있지 않은 집합의 모든 유한 집합은 선택 함수를 가짐을 의미합니다. 그러나 그 특별한 경우는 선택 공리(ZF)가 없는 저멜로-프란켈 집합 이론의 정리입니다. 유한 귀납의 원리로 쉽게 증명됩니다.[7] 간단한 한 집합의 집합의 경우, 선택 함수는 단지 요소에 해당하므로, 이 선택 공리의 예는 비어 있지 않은 모든 집합에 요소가 있다는 것을 말하고, 이것은 사소한 것으로 유지됩니다. 선택의 공리는 이미 유한 집합에 대해 명백한 이 속성의 일반화를 임의 집합에 대해 주장하는 것으로 볼 수 있습니다.

사용.

19세기 후반까지 선택의 공리는 아직 공식적으로 언급되지는 않았지만 함축적으로 사용되는 경우가 많았습니다. 예를 들어, 집합 X가 비어 있지 않은 집합만을 포함한다는 것을 확인한 후, 수학자는 함수 F를 정의하기 위해 "F를 X의 모든 s에 대한 s의 멤버 중 하나로 하자"고 말했을 수 있습니다. 일반적으로 선택의 공리 없이 F가 존재한다는 것을 증명하는 것은 불가능하지만, 이것은 제르멜로까지 눈에 띄지 않은 것으로 보입니다.

집합의 개별 비어 있지 않은 집합의 특성으로 인해 특정 무한 집합에 대해서도 선택 공리를 피할 수 있습니다. 예를 들어, 집합 X의 각 구성원이 자연수의 비어 있지 않은 부분집합이라고 가정하자. 이러한 모든 부분집합은 가장 작은 원소를 가지므로 선택 함수를 지정하기 위해 단순히 각 집합을 해당 집합의 가장 작은 원소와 매핑한다고 말할 수 있습니다. 이것은 우리에게 각 집합에서 요소를 확실하게 선택할 수 있게 해주며, 집합론의 공리에 선택의 공리를 추가할 필요가 없게 만듭니다.

각 집합에서 요소를 자연스럽게 선택할 수 없을 때 어려움이 나타납니다. 만약 우리가 명시적인 선택을 할 수 없다면, 우리의 선택이 (집합 이론의 다른 ZF 공리에 의해 정의되는) 정당한 집합을 형성한다는 것을 어떻게 알 수 있을까요? 예를 들어, X실수의 비어 있지 않은 모든 부분집합의 집합이라고 가정하자. 먼저 우리는 X가 유한한 것처럼 진행하려고 할 수 있습니다. 만약 우리가 각 집합에서 어떤 원소를 선택하려고 한다면, X는 무한하기 때문에 우리의 선택 과정은 결코 끝나지 않을 것이고, 결과적으로 우리는 모든 X에 대한 선택 함수를 만들 수 없을 것입니다. 다음으로 각 집합에서 최소 요소를 지정할 수 있습니다. 그러나 실수의 일부 부분 집합에는 최소 요소가 없습니다. 예를 들어, 열린 구간 (0,1)에는 최소 원소가 없습니다. 만약 x가 (0,1) 안에 있으면 x/2도 마찬가지이고, x/2는 항상 x보다 엄격하게 작습니다. 따라서 이 시도도 실패합니다.

추가적으로, 예를 들어, 단위 원 S와 모든 유리 회전들로 이루어진 군 G에 의한 S에 대한 작용을 생각해 보세요. 즉, 이것은 π의 유리 배수인 각도에 의한 회전입니다. 여기서 G는 셀 수 있고 S는 셀 수 없습니다. 따라서 SG 아래에서 셀 수 없이 많은 궤도로 분리됩니다. 선택의 공리를 사용하여 우리는 각 궤도에서 하나의 점을 선택할 수 있으며, G에 의한 모든 번역이 X와 서로소인 성질을 가진 S의 셀 수 없는 부분집합 X를 얻을 수 있습니다. 이들의 집합은 원을 분할하여 쌍대적으로 합동인 서로소 집합들의 셀 수 있는 집합으로 변환합니다. XS에 대한 회전 불변 가산 유한 척도에 대해 측정할 수 없기 때문에, 각 궤도의 한 점을 선택하여 집합을 형성하는 알고리즘을 찾는 것은 집합 이론의 공리에 선택 공리를 추가해야 합니다. 자세한 내용은 측정 불가능 집합을 참조하십시오.

고전 산술에서, 자연수는 순서가 잘 정해져 있습니다: 자연수의 비어 있지 않은 부분 집합에 대해, 자연수 아래에 고유한 최소 요소가 있습니다. 이러한 방법으로 주어진 부분 집합에서 집합을 지정할 수 있습니다. 어떤 사람은 이렇게 말할지도 모릅니다, "비록 실수의 일반적인 순서가 통하지 않더라도, 잘 정렬된 실수의 다른 순서를 찾을 수 있을지도 모릅니다. 그러면 우리의 선택 함수는 우리의 특이한 순서에 따라 모든 세트에서 최소 요소를 선택할 수 있습니다." 그러면 문제는 그것의 존재를 위해 선택 공리를 필요로 하는 것으로 밝혀진 잘 정렬된 것을 구성하는 것입니다. 모든 집합은 선택 공리가 유지되는 경우에만 잘 정렬될 수 있습니다.

비판과 수용

선택 공리를 요구하는 증명은 집합 이론의 언어로 대상을 명시적으로 정의하지 않고 대상의 존재를 확립할 수 있습니다. 예를 들어, 선택 공리는 실수의 순서가 잘 되어 있다는 것을 의미하지만, 실수의 개별 순서가 정의될 수 없는 선택 공리를 가진 집합 이론의 모델이 있습니다. 마찬가지로, Lebesgue가 측정 가능하지 않은 실수의 부분 집합은 선택 공리를 사용하여 존재한다는 것을 증명할 수 있지만, 그러한 집합은 정의할 수 없다는 것이 일관됩니다.[8]

선택의 공리는 일부 철학적 원칙과 충돌할 수 있는 이러한 무형의 존재(존재하는 것으로 증명되지만 명시적으로 구성될 수 없는 대상)를 증명합니다.[9] 모든 집합의 표준 순서화가 없기 때문에, 순서화에 의존하는 구조는 표준 결과를 원하는 경우에도 표준 결과를 생성하지 못할 수 있습니다(종종 범주 이론의 경우와 마찬가지). 이것은 선택 공리의 사용에 반대하는 주장으로 사용되어 왔습니다.

선택의 공리에 반대하는 또 다른 주장은 그것이 반직관적으로 보일 수 있는 대상의 존재를 암시한다는 것입니다.[10] 3차원 고체 단위공을 무한히 많은 조각으로 분해하고 회전과 번역만으로 조각을 원래의 부피와 같은 두 개의 고체 공으로 다시 조립하는 것이 가능하다는 바나흐-타르스키 역설이 그 예입니다. 선택 공리를 사용하여 구성된 이 분해의 조각은 측정할 수 없는 집합입니다.

게다가, 물리학에서 무신호 원리에 대한 선택 공리의 역설적인 결과들이 최근에 지적되었습니다.[11]

역설적으로 보이는 이러한 결과에도 불구하고, 대부분의 수학자들은 선택의 공리를 수학에서 새로운 결과를 증명하기 위한 유효한 원리로 받아들입니다. 그러나 ZFC(ZF + AC)의 정리가 (ZF 공리만으로) 선택 공리와 논리적으로 동등하고, 수학자들이 선택 공리가 거짓이어야 하는 결과를 찾을 때 주목할 만한 것으로 간주된다는 것은 충분히 흥미로운 논쟁입니다. 이런 유형의 추론은 선택 공리가 참이어야 하는 유형보다 덜 일반적이지만.

ZF의 정리는 그 이론의 어떤 모델에서도 참입니다. 그 특정 모델에서 선택 공리의 참 또는 거짓과 상관없이. 아래 선택의 의미는 ZF의 정리가 아니기 때문에 더 약한 버전의 공리를 포함하여 나열됩니다. 예를 들어, 바나흐-타르스키 역설은 ZF 단독으로는 증명할 수도 없고 반증할 수도 없습니다. ZF에서 필요한 단위 볼의 분해를 구성하는 것은 불가능하지만, 그러한 분해가 없다는 것을 증명하는 것도 불가능합니다. 이러한 문장은 예를 들어 "AC가 유지되면 바나흐-타르스키 역설의 분해가 존재합니다."와 같은 조건문으로 다시 표현될 수 있습니다. 이러한 조건문은 원래 문장이 ZF와 선택 공리로부터 증명될 수 있을 때 ZF에서 증명될 수 있습니다.

건설수학에서

위에서 논의한 바와 같이, ZFC의 고전 이론에서 선택의 공리는 명시적인 인스턴스가 구성되지 않은 상태에서 객체 유형의 존재가 증명되는 비구조적 증명을 가능하게 합니다. 실제로 집합론과 토포스 이론에서 디아코네스쿠의 정리는 선택의 공리가 배제된 중간의 법칙을 내포하고 있음을 보여줍니다. 따라서 이 원리는 비고전적 논리가 사용되는 건설적 집합 이론에서는 사용할 수 없습니다.

마르틴-뢰프 유형 이론에서 원리를 공식화했을 때는 상황이 다릅니다. 거기에 고차 헤이팅 산술에서, 선택 공리의 적절한 진술은 (접근 방식에 따라) 공리로서 포함되거나 정리로서 증명될 수 있습니다.[12] 이러한 차이의 원인은 유형 이론의 선택 공리가 구성 집합 이론의 선택 공리가 하는 확장성 속성을 갖지 않기 때문입니다.[13] 유형 이론적 맥락은 아래에서 더 자세히 설명합니다.

다양한 선택 원리들이 구성적 맥락에서 심도 있게 연구되어 왔고, 그 원리들의 상태는 구성적 수학의 다양한 학파와 다양성에 따라 다릅니다. 건설적 집합론의 일부 결과는 배제된 중간의 법칙을 의미하지 않는 가산 선택의 공리 또는 종속 선택의 공리를 사용합니다. 건설적 분석의 틀을 개발한 것으로 유명한 에렛 비숍은 선택의 공리가 건설적으로 허용된다고 주장했습니다.

건설적인 수학에서 선택 함수는 존재의 의미 자체에 의해 선택이 암시되기 때문에 존재합니다.[14]

특히 셀 수 있는 선택의 공리는 건설 수학에서 일반적으로 사용되지만, 그 사용에 대해서도 의문이 제기되어 왔습니다.[15]

독립

1938년,[16] 쿠르트 괴델은 ZFC를 만족하는 내부 모델(구성 가능한 우주)을 구성하여 ZF 자체가 일관되면 ZFC가 일관됨을 보여줌으로써 선택 공리의 부정이 ZF의 정리가 아님을 보여주었습니다. 1963년 Paul Cohen은 ZF가 일관적이라고 가정할 때 선택의 공리 자체가 ZF의 정리가 아니라는 것을 보여주기 위해 이러한 목적으로 개발된 강제 기술을 사용했습니다. 그는 ZF ¬C(AC의 부정이 공리로 추가된 ZF)를 만족시키는 훨씬 더 복잡한 모델을 구성하여 ZF ¬C가 일관됨을 보여줌으로써 이를 수행했습니다.

이러한 결과는 선택의 공리가 ZF와 논리적으로 독립적이라는 것을 증명합니다. ZF가 일관성이 있다는 가정은 이미 일관성이 없는 계에 다른 공리를 더하면 상황을 더 악화시킬 수 없기 때문에 무해합니다. 독립성 때문에 증명에서 선택의 공리(또는 그 부정)를 사용할 것인지에 대한 결정은 집합론의 다른 공리에 대한 항소로 이루어질 수 없습니다. 다른 이유로 결정해야 합니다.

선택의 공리를 사용하는 것에 찬성하는 한 가지 주장은 그것을 사용하는 것이 편리하다는 것입니다. 왜냐하면 그것은 다른 방법으로는 증명할 수 없었던 몇 가지 단순화된 명제를 증명할 수 있기 때문입니다. 선택을 사용하여 증명할 수 있는 많은 정리들은 우아한 일반적인 성격을 가지고 있습니다: 임의의 두 집합의 기수는 비슷하고, 통일성을 가진 모든 사소한 고리최대 이상을 가지며, 모든 벡터 공간기본을 가지며, 연결된 모든 그래프는 신장 트리를 가지며, 다른 많은 것들 중에서도 콤팩트 공간모든 곱은 콤팩트합니다. 선택의 공리가 없다면, 이 정리들은 큰 카디널리티의 수학적 대상들에 대해 성립하지 않을 수도 있습니다.[clarification needed]

독립성 결과의 증명은 또한 페아노 산술 언어로 표현될 수 있는 모든 진술을 포함하여 광범위한 클래스의 수학적 진술이 ZFC에서 증명될 수 있는 경우에만 ZF에서 증명될 수 있음을 보여줍니다.[18] 이 클래스의 문장에는 P = NP라는 문장, 리만 가설 및 기타 많은 미해결 수학 문제가 포함됩니다. 이 수업에서 문제를 해결하려고 할 때, 증명의 존재만이 문제라면 ZF를 사용하든 ZFC를 사용하든 상관없습니다. 그러나 ZF보다 ZFC에서 더 짧은 정리의 증명이 있을 수 있습니다.

선택의 공리는 ZF와 무관한 유일한 의미 있는 진술은 아닙니다. 예를 들어, 일반화된 연속체 가설(GCH)은 ZF로부터 독립적일 뿐만 아니라 ZFC로부터도 독립적입니다. 그러나 ZF와 GCH는 AC를 의미하므로 둘 다 ZF와 무관함에도 불구하고 GCH가 AC보다 엄격하게 강력한 주장이 됩니다.

더 강한 공리

구성 가능성의 공리와 일반화된 연속체 가설은 각각 선택의 공리를 암시하므로 그것보다 엄격하게 강합니다. 폰 노이만-베르네와 같은 계급이론에서-괴델 집합론모스-켈리 집합론전지구적 선택의 공리라고 불리는 공리가 있는데, 이것은 적절한 계급에도 적용되기 때문에 집합에 대한 선택의 공리보다 더 강합니다. 글로벌 선택의 공리는 크기 제한의 공리로부터 이어집니다. 타르스키-그로텐디크 집합론에서 사용되는 타르스키의 공리는 모든 집합이 어떤 그로텐디크 우주에 속한다고 (국어에서) 진술하는 선택 공리보다 더 강합니다.

등가물

ZF의 공리를 가정하지만 AC나 ¬AC는 선택 공리와 동일하지 않다는 중요한 진술이 있습니다. 그 중에서 가장 중요한 것은 조른의 보조정리질서정연한 정리입니다. 사실, 제르멜로는 잘 정돈된 정리에 대한 자신의 증명을 공식화하기 위해 처음에 선택의 공리를 도입했습니다.

  • 집합론
    • 선택에 관한 타르스키 정리: 모든 무한 집합 A에 대하여 집합 A와 집합A 사이에는 사영 지도가 존재합니다.
    • 삼분절개: 두 집합이 주어지면 같은 카디널리티를 갖거나 한 집합이 다른 집합보다 작은 카디널리티를 갖습니다.
    • 비어 있지 않은 두 집합이 주어졌을 때, 하나는 다른 하나에 대한 사영을 가집니다.
    • 모든 사변 함수오른쪽 역함수를 갖습니다.
    • 비어 있지 않은 집합의 임의의 집합에 대한 데카르트 곱은 비어 있지 않습니다. 즉, 비공집합의 모든 계열은 선택 함수(즉, 각 비공집합을 그 원소 중 하나로 매핑하는 함수)를 갖습니다.
    • 쾨니히 정리: 구어체적으로 추기경 수열의 합은 더 큰 추기경 수열의 곱보다 엄격하게 적습니다. ("구어체적으로"라는 용어의 이유는 선택 공리의 어떤 측면 없이는 추기경 수열의 합 또는 곱 자체를 정의할 수 없기 때문입니다.)
    • 순서 정리: 모든 세트를 잘 주문할 수 있습니다. 결과적으로, 모든 추기경은 첫 번째 서수를 가집니다.
    • 부분 순서 집합 S의 모든 원소는 S에서 엄격한 상한을 갖지 않는 잘 순서화된 부분 집합의 최소 원소입니다.
    • Zorn's lemma: 모든 체인(즉, 완전 순서 부분 집합)이 상한을 가지는 비어 있지 않은 모든 부분 순서 집합은 적어도 하나의 최대 요소를 포함합니다.
    • 하우스도르프 최대 원리: 모든 부분 주문 세트에는 최대 체인이 있습니다. 마찬가지로, 부분 순서 집합에서 모든 사슬은 최대 사슬로 확장될 수 있습니다.
    • Tukey's lemma: 유한 문자의 비어 있지 않은 모든 집합은 포함과 관련하여 최대 요소를 갖습니다.
    • 안티체인 원리: 부분적으로 주문한 모든 세트에는 최대 안티체인이 있습니다. 마찬가지로, 부분 순서 집합에서 모든 안티체인은 최대 안티체인으로 확장될 수 있습니다.
  • 추상대수학
  • 기능분석
  • 점집합 토폴로지
  • 수리논리학
    • 만약 S가 1차 논리의 문장들의 집합이고 B가 S의 일관된 부분집합이라면, BS의 일관된 부분집합 중에서 최대인 집합에 포함됩니다. S가 주어진 서명모든 1차 문장의 집합인 특수한 경우는 부울 소수 이상 정리와 동등하게 약합니다. 아래의 "약한 형태" 항목을 참조하십시오.
  • 대수 위상학
    • 연결된 모든 그래프에는 신장 트리가 있습니다. 마찬가지로, 비어 있지 않은 모든 그래프에는 스패닝 포리스트가 있습니다.[25]

범주론

범주 이론에는 그들의 증명을 위해 선택의 공리를 발동하는 몇 가지 결과가 있습니다. 이러한 결과는 기술적 기반의 강도에 따라 선택 공리보다 약하거나 동등하거나 더 강할 수 있습니다. 예를 들어, 집합의 관점에서 범주를 정의하는 경우, 즉 객체와 형태의 집합(일반적으로 작은 범주라고 함), 또는 홈 객체가 집합인 국소적으로 작은 범주까지 정의하면 모든 집합의 범주가 없으므로 범주 이론 형식이 모든 집합에 적용되기는 어렵습니다. 반면 범주 이론의 다른 기본 설명은 상당히 강하며, 동일한 범주-이론적 선택 진술은 위에서 언급한 표준 공식인 alla 클래스 이론보다 강할 수 있습니다.

선택이 필요한 범주 이론문의 예는 다음과 같습니다.

  • 모든 작은 범주에는 뼈대가 있습니다.
  • 두 개의 작은 범주가 약하게 동치이면 동치입니다.
  • 적절한 해 집합 조건을 만족하는 소-완전 범주의 모든 연속 함수는 좌-접합(Frayd adjoint functor theorem)을 갖습니다.

약한 형태

선택 공리와 동등하지는 않지만 밀접하게 관련된 몇 가지 더 약한 진술이 있습니다. 가지 예는 의존적 선택의 공리(DC)입니다. 더 약한 예는 비어 있지 않은 집합의 셀 수 있는 집합에 대해 선택 함수가 존재한다는 셀 수 있는 선택ω 공리(AC 또는 CC)입니다. 이 공리들은 기초 수학적 분석에서 많은 증명을 위해 충분하며, 모든 실수 집합의 르베그 측정 가능성과 같은 완전한 선택 공리로부터 반증할 수 있는 몇 가지 원리와 일치합니다.

순위가 α보다 작은 모든 집합 S에 대하여 순서형 매개변수 α ≥ ω+2가 주어지면 S는 순서형입니다. 순서형 매개변수 α ≥ 1 – 하토그 수가 ω보다 작은 모든 집합 S에 대하여 S는 순서형입니다. 순서 모수가 증가함에 따라 이들은 선택의 완전한 공리에 점점 더 가깝게 접근합니다.

선택 공리보다 약한 다른 선택 공리에는 부울 소수 이상 정리균일화 공리가 있습니다. 전자는 ZF에서 타르스키의 1930년 초필터 보조제와 동등합니다. 모든 필터는 일부 초필터의 하위 집합입니다.

AC(또는 약한 형태)가 필요하지만 AC보다 약한 결과

선택 공리의 가장 흥미로운 측면 중 하나는 그것이 수학에서 보여주는 많은 자리입니다. 다음은 ZF에서 증명할 수 없지만 ZFC(ZF + AC)에서 증명할 수 있다는 의미에서 선택 공리를 필요로 하는 몇 가지 문입니다. 마찬가지로, 이러한 문장은 ZFC의 모든 모델에서 참이지만 ZF의 일부 모델에서는 거짓입니다.

AC의 동일한 의미일 수 있습니다.

AC와 동등성이 열려 있는 AC가 암시하는 역사적으로 중요한 몇 가지 집합론적 문장이 있습니다. AC 자체보다 먼저 공식화된 분할 원칙을 제르멜로는 AC를 믿는 이유로 꼽았습니다. 1906년 러셀은 PP를 동치라고 선언했지만, 분할 원리가 AC를 의미하는지 여부는 집합 이론에서 여전히 가장 오래된 열린 문제이며,[32] 다른 문장의 동치도 마찬가지로 오래된 열린 문제입니다. 선택에 실패하는 ZF의 알려진 모든 모델에서 이러한 문장도 실패하지만 선택 없이 유지할 수 있는지는 알 수 없습니다.

  • 집합론
    • 분할 원리: A에서 B로의 돌출이 있으면 B에서 A로의 주입이 있습니다. 마찬가지로 집합 S의 모든 분할 P는 크기 S보다 작거나 같습니다.
    • 슈뢰더-번스타인 정리: 두 집합이 서로 사영을 가지면 그들은 등비수입니다.
    • 약한 분할 원리: A에서 B로의 주입돌출이 있으면 AB는 등비수입니다. 마찬가지로 집합 S의 분할은 S보다 엄격하게 클 수 없습니다. WPP가 성립한다면 이는 이미 측정할 수 없는 집합의 존재를 의미합니다. 앞의 세 가지 진술은 모두 앞의 진술이 내포하고 있지만, 이 중 어느 하나라도 번복할 수 있는지는 알 수 없습니다.
    • 무한히 감소하는 추기경 순서는 없습니다. 동치는 1905년에 쇤플라이에 의해 추측되었습니다.
  • 추상대수학
    • 한 임베딩 정리: 모든 순서 아벨 군 G사전적 순서가 부여된 가산 군 Rω\mathbb R} Omega }의 부분군으로 포함되며, 여기서 ω는 G의 아르키메데스 등가 클래스 집합입니다. 이 동등성은 1907년 한씨에 의해 추측되었습니다.

AC의 부정의 더 강력한 형태

실수의 모든 집합이 Baire의 성질을 갖는다는 주장을 BP로 축약하면 BP는 비어 있지 않은 집합의 단 하나의 집합에 대해서만 임의의 선택 함수가 존재하지 않는다고 주장하는 ¬AC보다 강합니다. 강화된 부정은 약화된 형태의 AC와 호환될 수 있습니다. 예를 들어, ZF가 일치하는 경우 ZF + DC[33] + BP가 일치합니다.

또한 모든 실수의 집합이 레베그 측정 가능하다는 것은 ZF + DC와 일치하지만 로버트 M으로 인해 이러한 일관성 결과가 발생합니다. 솔로웨이는 ZFC 자체에서는 증명할 수 없지만 가벼운 큰 기본 가정(접근할 수 없는 기본의 존재)이 필요합니다. 결정론의 훨씬 더 강력한 공리(AD)는 모든 실수 집합이 측정 가능한 르베그이며, Baire의 속성을 가지며, 완벽한 집합 속성을 갖는다는 것을 의미합니다(이 세 결과는 모두 AC 자체에 의해 반박됩니다). ZF + DC + AD는 충분히 강력한 기본 공리가 일관성이 있다면 일관성이 있습니다(무제한적으로 많은 Wood in cardinals의 존재).

의 공리적 집합론 체계인 새로운 기초(NF)는 1937년 논문에서 수학적 논리를 소개한 제목("New Foundations for Mathematical Logic")에서 이름을 따왔습니다. NF 공리계에서는 선택의 공리가 반증될 수 있습니다.[34]

AC의 부정과 일치하는 진술

선택의 공리가 거짓인 저멜로-프랑켈 집합 이론의 모델들이 있습니다. 우리는 ZF ¬C에 의해 "저멜로-프랑켈 집합론 + 선택 공리의 부정"을 축약할 것입니다. ZF ¬C의 특정 모델의 경우 일부 표준 ZFC 정리의 부정성을 검증할 수 있습니다. ZF ¬C의 어떤 모형도 ZF의 모형이므로, 다음 각 문장에 대하여, 그 문장이 참인 ZF의 모형이 존재하는 경우

  • 원래 집합에 원소가 있는 것보다 엄밀하게 더 많은 동등성 클래스로 분할할 수 있는 집합과 도메인이 엄밀하게 그 범위보다 작은 함수가 있습니다. 사실, 이것은 알려진 모든 모델에서 그렇습니다.
  • 실수에서 실수로 가는 함수 f가 있어서 fa에서 연속적이지 않지만 a에서 f는 순차적으로 연속적입니다. 즉, a, 림 f(x)=f(a)로 수렴하는 임의의 수열 {x}에 대하여.
  • 셀 수 없을 정도로 무한한 부분집합이 없는 무한한 실수 집합이 있습니다.
  • 실수는 셀 수 있는 집합의 셀 수 있는 조합입니다.[35] 이것은 실수가 셀 수 있다는 것을 의미하지 않습니다. 위에서 지적한 바와 같이 셀 수 있는 집합들의 셀 수 있는 결합 자체가 셀 수 있다는 것을 보여주기 위해서는 셀 수 있는 선택의 공리가 필요합니다.
  • 대수적 종결이 없는 분야가 있습니다.
  • ZF ¬C의 모든 모델에는 기초가 없는 벡터 공간이 있습니다.
  • 서로 다른 기수를 가진 두 개의 염기를 가진 벡터 공간이 있습니다.
  • 셀 수 없이 많은 생성기에 무료 완전 부울 대수가 있습니다.[36]
  • 선형으로 주문할 수 없는 세트가 있습니다.
  • R의 모든 집합이 측정 가능한 ZF ¬C 모형이 있습니다. 따라서 ZFC에서 입증 가능한 바나흐-타르스키 역설과 같은 반직관적 결과를 배제할 수 있습니다. 또한 이는 AC보다 약하지만 실제 분석을 대부분 개발하기에 충분한 종속 선택 공리를 가정할 때 가능합니다.
  • ZF ¬C의 모든 모델에서 일반화된 연속체 가설은 성립하지 않습니다.

증명에 대해서는 Jech(2008)를 참조하십시오.

또한 (기술 집합 이론의 의미에서) 집합에 정의 가능성 조건을 부과함으로써 일반 선택과 양립할 수 없는 공리로부터 선택 공리의 제한된 버전을 종종 증명할 수 있습니다. 이것은 예를 들어 Moschovakis 코딩 보조제에서 나타납니다.

유형론의 선택 공리

유형 이론에서, 다른 종류의 진술은 선택의 공리로 알려져 있습니다. 이 양식은 σ 및 τ의 두 가지 유형으로 시작되며 유형 σ의 개체와 유형 τ의 개체 간의 관계 R로 시작됩니다. 선택의 공리는 만약 각 유형 σ x에 대하여 R(x,y)와 같은 유형 τ y가 존재한다면, 모든 유형 σ x에 대하여 R(x,f(x))이 성립하는 유형 σ 객체에서 유형 τ 객체로의 함수 f가 존재한다는 것을 말합니다.

집합론과 달리 유형론에서 선택의 공리는 일반적으로 R이 특정 논리 형식의 모든 공식 또는 모든 공식에 걸쳐 변하는 공리 체계로 명시됩니다.

인용문

선택의 공리는 분명히 참이고, 질서정연한 원리는 명백하게 거짓이며, 누가 존의 보조정리에 대해 말할 수 있습니까?

이것은 농담입니다: 비록 이 세 가지는 모두 수학적으로 동등하지만, 많은 수학자들은 선택의 공리가 직관적이라고 생각하고, 잘 정렬된 원리는 반직관적이라고 생각하고, 조른의 보조정리는 어떤 직관에 비해 너무 복잡하다고 생각합니다.

선택의 공리는 무한한 수의 양말에서 한 세트를 선택하는 데 필요하지만 무한한 수의 신발에서 한 세트를 선택하는 데는 필요합니다.

여기서 관찰할 수 있는 것은 예를 들어 각 쌍에서 왼쪽 신발을 선택하여 무한히 많은 수의 신발 중에서 선택할 함수를 정의할 수 있다는 것입니다. 선택 공리가 없으면 왼쪽 양말과 오른쪽 양말을 구별할 수 없기 때문에 이러한 함수가 양말 쌍에 대해 존재한다고 주장할 수 없습니다.

타르스키는 자신의 정리 [AC와 "모든 무한 집합 A는 A × A와 같은 기수를 가진다."]를 렌두스 콩트에 발표하려고 했지만, 프레셰르베그는 그것을 제시하기를 거부했습니다. 프레셰는 잘 알려진 두 [진정한] 명제 사이의 함축은 새로운 결과가 아니라고 썼고, 르베슈는 두 거짓 명제 사이의 함축은 관심이 없다고 썼습니다.

폴란드계 미국인 수학자 얀 마이켈스키(Jan Mycielski)는 2006년 미국 수학자 협회(The Notice of the AMS)의 기사에서 이 일화를 언급했습니다.[39]

그 공리는 수학자들이 다른 공리보다 그것을 선호하기 때문에 붙여진 이름이 아닙니다.

이 인용문은 1989년 4월 사이언티픽 아메리칸(Scientific American)컴퓨터 레크리에이션 칼럼에 실린 유명한 만우절 기사에서 나온 것입니다.

메모들

  1. ^ 저멜로 1904.
  2. ^ Jech 1977, 351쪽
  3. ^ Jech, 1977, p. 348ff; Martin-Löf 2008, p. 210. 멘델슨 1964, 페이지 201:
    선택의 공리의 지위는 최근 몇 년 동안 논란의 여지가 적었습니다. 대부분의 수학자들에게 그것은 꽤 그럴듯해 보이고 그것을 받아들이지 않는 것은 실제 수학의 모든 분야에서 매우 많은 중요한 응용 프로그램을 가지고 있기 때문에 그것을 받아들이지 않는 것은 실천하는 수학자의 의도적인 굴레처럼 보일 것입니다.
  4. ^ Rosenberg, Steven (21 December 2021). An Invitation to Abstract Algebra. CRC Press. ISBN 9781000516333.
  5. ^ Herrlich 2006, p. 9. Supes 1972, p. 243에 따르면, 이것은 원래 Zermelo 1904에 의해 주어졌던 선택 공리의 공식화였습니다. 이 공식은 Halmos 1960, 페이지 60을 참조하십시오.
  6. ^ 1972, 240쪽으로 추정합니다.
  7. ^ Turlakis (2003), pp. 209–210, 215–216.
  8. ^ Fraenkel, Abraham A.; Bar-Hillel, Yehoshua; Lévy, Azriel (1973), Foundations of set theory (2nd ed.), Amsterdam-London: North-Holland Publishing Co., pp. 69–70, ISBN 9780080887050, MR 0345816.
  9. ^ Rosenbloom, Paul C. (2005), The Elements of Mathematical Logic, Courier Dover Publications, p. 147, ISBN 9780486446172.
  10. ^ Dawson, J. W. (August 2006), "Shaken Foundations or Groundbreaking Realignment? A Centennial Assessment of Kurt Gödel's Impact on Logic, Mathematics, and Computer Science", Proc. 21st Annual IEEE Symposium on Logic in Computer Science (LICS 2006), pp. 339–341, doi:10.1109/LICS.2006.47, ISBN 978-0-7695-2631-7, S2CID 15526447, The axiom of choice, though it had been employed unconsciously in many arguments in analysis, became controversial once made explicit, not only because of its non-constructive character, but because it implied such extremely unintuitive consequences as the Banach–Tarski paradox..
  11. ^ 바우멜러, 다키치, B., 델 산토, F., 2022. 선택의 공리와 비신호 원리, arXiv 프리프린트 - arXiv:2206.08467.
  12. ^ 페르 마르틴-뢰프, 직관주의 유형 이론, 1980. Anne Scherp Troelstra, 직관주의 산술분석의 메타수학적 조사, 스프링어, 1973.
  13. ^ Martin-Löf, Per (2006). "100 Years of Zermelo's Axiom of Choice: What was the Problem with It?". The Computer Journal. 49 (3): 345–350. Bibcode:1980CompJ..23..262L. doi:10.1093/comjnl/bxh162.
  14. ^ Erret Bishop과 Douglas S. Bridges, Constructive Analysis, Springer-Verlag, 1985.
  15. ^ Fred Richman, "선택이 없는 건설적 수학"에서: 반음영 재결합 - 연속체의 건설적 및 비표준적 관점 (P. Schuster et al., eds), 신쎄 라이브러리 306, 199–205, 암스테르담, Kluwer Academic Publishers, 2001.
  16. ^ Gödel, Kurt (9 November 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. 24 (12): 556–557. Bibcode:1938PNAS...24..556G. doi:10.1073/pnas.24.12.556. PMC 1077160. PMID 16577857.
  17. ^ Cohen, Paul (2019). "The Independence of the Axiom of Choice" (PDF). Stanford University Libraries. Archived (PDF) from the original on 9 October 2022. Retrieved 22 March 2019.
  18. ^ 이것은 산술적 진술이 구성 가능한 우주 L절대적이기 때문입니다. 쇼엔필드의 절대성 정리는 좀 더 일반적인 결과를 제공합니다.
  19. ^ 74 당량의 구조화된 목록은 Moore 2013, 페이지 330-334를 참조하십시오. 출처 참조와 함께 86개의 동등성에 대해서는 Howard & Rubin 1998, pp. 11-16을 참조하십시오.
  20. ^ Blass, Andreas (1984). "Existence of bases implies the axiom of choice". Axiomatic set theory (Boulder, Colo., 1983). Contemporary Mathematics. Vol. 31. Providence, RI: American Mathematical Society. pp. 31–33. doi:10.1090/conm/031/763890. MR 0763890.
  21. ^ A. Hajnal, A. Kertész: 선택 공리의 새로운 대수적 동치들, Publ. 수학. Debrecen, 19(1972), 339–340, H. Rubin, J. Rubin, 선택 공리의 등가물, II, North-Holland, 1985, p. 111 참조.
  22. ^ a b Blass, Andreas (1979). "Injectivity, Projectivity and the Axiom of Choice". Transactions of the American Mathematical Society. 255: 31–59. doi:10.2307/1998165. JSTOR 1998165.
  23. ^ Awodey, Steve (2010). Category theory (2nd ed.). Oxford: Oxford University Press. pp. 20–24. ISBN 978-0199237180. OCLC 740446073.
  24. ^ nLab투영 객체
  25. ^ Serre, Jean-Pierre (2003), Trees, Springer Monographs in Mathematics, Springer, p. 23Serre, Jean-Pierre (2003), Trees, Springer Monographs in Mathematics, Springer, p. 23.Soukup, Lajos (2008), "Infinite combinatorics: from finite to infinite", Horizons of combinatorics, Bolyai Society Mathematical Studies, vol. 17, Berlin: Springer, pp. 189–213, CiteSeerX 10.1.1.222.5699, doi:10.1007/978-3-540-77200-2_10, ISBN 978-3-540-77199-9, MR 2432534 특히 정리 2.1, 페이지 192-193을 참조하십시오.
  26. ^ Muger, Michael (2020). Topology for the Working Mathematician.
  27. ^ Jech 2008, pp. 119–131에 따르면 가산 선택의 공리는 무한 집합과 데데킨드-무한 집합의 등가성을 의미하지만 무한 집합과 데데킨드-무한 집합의 등가성은 ZF에서 가산 선택의 공리를 의미하지 않습니다.
  28. ^ Lévy 1958 등은 Mostowski 모델을 사용하여 유한 집합의 8가지 정의가 AC를 가정할 때 동일하지만 AC가 없는 ZF에서 독립적이라는 것을 보여주었습니다. 정의는 I-finite, Ia-finite, II-finite, III-finite, IV-finite, V-finite, V-finite, VI-finite, VII-finite 입니다. I-finity는 일반적인 유한성과 같습니다. IV 유한성은 데데킨트 유한성과 같습니다.
  29. ^ "[FOM] Are (C,+) and (R,+) isomorphic". 21 February 2006.
  30. ^ Ash, C. J. (1975). "A consequence of the axiom of choice". Journal of the Australian Mathematical Society. 19 (3): 306–308. doi:10.1017/S1446788700031505. S2CID 122334025.
  31. ^ Schechter 1996, pp. 391–392.
  32. ^ "On the Partition Principle".
  33. ^ 종속선택의 공리
  34. ^ "Quine's New Foundations". Stanford Encyclopedia of Philosophy. Retrieved 10 November 2017.
  35. ^ Jech 2008, pp. 142–144, 증명이 있는 정리 10.6.
  36. ^ Stavi, Jonathan (1974). "A model of ZF with an infinite free complete Boolean algebra". Israel Journal of Mathematics. 20 (2): 149–163. doi:10.1007/BF02757883. S2CID 119543439.
  37. ^ Krantz, Steven G. (2002), "The axiom of choice", Handbook of Logic and Proof Techniques for Computer Science, Springer, pp. 121–126, doi:10.1007/978-1-4612-0115-1_9, ISBN 978-1-4612-6619-8.
  38. ^ 부츠와 양말의 비유는 1919년 러셀 1993, 125-127쪽에 의해 주어졌습니다. 그는 백만장자가 ℵ 켤레의 부츠와 ℵ 양말을 가지고 있을지도 모른다고 제안했습니다.

    부츠 중에서 우리는 오른쪽과 왼쪽을 구별할 수 있고, 따라서 우리는 각 쌍에서 하나를 선택할 수 있습니다. 즉, 우리는 모든 오른쪽 부츠 또는 모든 왼쪽 부츠를 선택할 수 있습니다. 그러나 양말의 경우 그러한 선택의 원리가 그 자체를 시사하지 않으며, 우리가 곱셈 공리를 가정하지 않는 한 우리는 확신할 수 없습니다. 각 쌍에서 하나의 양말로 구성된 클래스가 있다는 것.

    러셀은 일반적으로 선택의 공리에 대해 곱셈 공리라는 용어를 사용했습니다. 그는 무한히 많은 대상들의 쌍들의 순서를 언급하면서 다음과 같이 썼습니다.

    부츠로 하는 데 어려움이 없습니다. 쌍들은 ℵ를 형성하는 것으로 주어지며, 따라서 진행의 장으로 주어집니다. 각 쌍 내에서 왼쪽 부츠를 먼저, 오른쪽 두 번째 부츠를 순서를 변경하지 않고 그대로 두십시오. 이러한 방식으로 모든 부츠의 진행을 얻을 수 있습니다. 그러나 양말을 가지고 우리는 임의로 선택해야 합니다. 각각의 짝을 먼저 선택해야 합니다. 그리고 무한히 많은 임의의 선택은 불가능합니다. 우리가 선택하는 규칙, 즉 선택자인 관계를 찾을 수 없는 한, 우리는 선택이 이론적으로도 가능하다는 것을 알지 못합니다.

    그런 다음 러셀은 각 양말의 질량 중심의 위치를 선택기로 사용할 것을 제안합니다.

  39. ^ Mycielski, Jan (2006), "A system of axioms of set theory for the rationalists" (PDF), Notices of the American Mathematical Society, 53 (2): 206–213, MR 2208445.

참고문헌

번역: Jean van Heijenoort, 2002. 프레게에서 괴델까지: 수학 논리학의 원천 책, 1879–1931. 신판. 하버드 대학 출판부. ISBN0-674-32449-8
  • 1904. "모든 세트가 잘 정렬될 수 있음을 증명합니다." 139-41.
  • 1908. "집합론 I의 기초에 대한 조사", 199-215.

외부 링크