Zorn's lemma

Zorn's lemma
홀리스 프램튼의 영화는 존스 렘마를 참고하세요.
존의 보조정리를 사용하여 연결된 모든 그래프에 신장 트리가 있음을 보여줄 수 있습니다. 트리인 모든 부분 그래프의 집합은 포함에 의해 순서가 정해지며, 사슬의 결합은 상한입니다. 존의 보조정리는 그래프가 연결되어 있기 때문에 신장 트리인 최대 트리가 존재해야 한다고 말합니다.[1] 여기 있는 그림과 같은 유한 그래프에는 존의 보조정리가 필요하지 않습니다.

Kuratowski-Zorn 보조정리라고도 알려진 Zorn의 보조정리는 집합론의 명제입니다. 모든 체인에 대한 상한을 포함하는 부분 순서 집합(즉, 모든 완전 순서 부분 집합)은 반드시 최소 하나의 최대 요소를 포함한다고 말합니다.

보조정리는 1922년 Kazimierz Kuratowski에 의해 증명되었고 1935년 Max Zorn에 의해 독립적으로 증명되었습니다.[2] 함수 분석에서 한-바나흐 정리, 모든 벡터 공간은 기초를 가지고 있다는 정리,[3] 위상수학에서 콤팩트 공간의 모든 곱은 콤팩트하다는 타이코노프 정리 등과 같이 매우 중요한 여러 정리들의 증명에서 나타납니다. 그리고 추상대수학에서의 정리들은 항등식을 갖는 환에서 모든 고유한 이상은 최대 이상에 포함되며 모든 분야는 대수적 종결을 갖는다는 것입니다.[4]

ZF(선택 공리가 없는 저멜로-프랑켈 집합 이론) 내에서 세 가지 중 하나가 나머지 두 가지를 증명하기에 충분하다는 점에서 조른의 보조정리는 잘 정렬된 정리와 선택 공리와 동등합니다.[5] 조른 보조정리의 초기 공식은 주어진 부분 순서 집합의 모든 완전 순서 부분 집합이 부분 순서 집합의 최대 완전 순서 부분 집합에 포함된다는 하우스도르프의 최대 원리입니다.[6]

동기

어떤 식으로든 부분적으로 질서 있는 집합에서 극대 원소로 볼 수 있는 수학적 대상의 존재를 증명하기 위해서는 극대 원소가 없다고 가정하고 초극성 귀납법과 상황의 가정을 이용하여 모순을 얻음으로써 그러한 대상의 존재를 증명해 볼 수 있습니다. 존의 보조정리는 그러한 논증이 작동하기 위해 상황이 만족해야 하는 조건을 정리하고 수학자들이 매번 손으로 초미세 유도 논증을 반복할 필요가 없고, 단지 존의 보조정리의 조건을 확인할 수 있게 합니다.

만약 여러분이 수학적 대상을 단계적으로 만들고 있고, (i) 무한히 많은 단계를 거쳐도 완성하지 못했고, (ii) 여러분이 계속해서 만드는 것을 막을 것이 없어 보인다면, 조른의 보조정리가 여러분을 도울 수 있을 것입니다.

— William Timothy Gowers, "How to use Zorn’s lemma"[7]

보조정리표

예비 개념:

  • 반사적인(x마다 x ≤ x), 반대칭적인(x ≤ y와 y ≤ x가 모두 유지되면 x = y), 과도적인(x ≤ y와 y ≤ z이면 x ≤ z이면 x ≤ z)의 이진 관계 ≤를 가진 집합 P를 ≤만큼 순서화한다고 합니다. x ≤ y인 P의 두 원소 x와 y가 주어졌을 때, y는 x보다 크거나 같다고 합니다. "부분적"이라는 단어는 부분적으로 정렬된 집합의 모든 원소 쌍이 순서 관계 하에서 비교될 필요가 없다는 것을 의미합니다. 즉, 순서 관계가 ≤인 부분적으로 정렬된 집합 P에는 x ≤ y도 y ≤ x도 없는 원소 x와 y가 있을 수 있습니다. 모든 원소 쌍이 비슷한 순서 집합을 완전 순서 집합이라고 합니다.
  • 부분 순서 집합 P의 모든 부분 집합 S는 P에서 S로 상속되는 순서 관계를 제한함으로써 그 자체로 부분 순서화된 것으로 볼 수 있습니다. 부분 순서 집합 P의 부분 집합 S가 상속 순서로 완전히 순서화되면 사슬(P)이라고 합니다.
  • 순서 관계가 ≤인 부분 순서 집합 P의 원소 m은 m보다 큰 P의 다른 원소가 없는 경우, 즉 s ≠ m 및 m ≤ s인 P에 s가 없는 경우 최대(≤에 대하여)입니다. 순서 관계에 따라 부분 순서 집합은 임의의 수의 최대 요소를 가질 수 있습니다. 그러나 완전 순서 집합은 최대 하나의 최대 요소를 가질 수 있습니다.
  • 부분 순서 집합 P의 부분집합 S가 주어졌을 때, P의 원소 u는 S의 모든 원소보다 크거나 같으면 S의 상한입니다. 여기서 S는 사슬일 필요는 없으며, u는 S의 모든 원소와 비슷해야 하지만 그 자체가 S의 원소일 필요는 없습니다.

존의 보조정리는 다음과 같이 기술할 수 있습니다.

조른 보조정리 - 부분 순서 집합 P가 P의 모든 사슬이 P에서 상한을 갖는 성질을 갖는다고 가정하자. 그러면 집합 P는 적어도 하나의 최대 원소를 포함합니다.

집합 P와 사슬이 비어 있지 않아야 하는 것과 같은 이 공식의 변형이 사용되기도 합니다.[8]

존의 보조정리(비공집합의 경우)—비공집합 P가 아닌 부분순서 집합 P가 모든 비공사슬이 P에서 상한을 갖는 성질을 갖는다고 가정하자. 그러면 집합 P는 적어도 하나의 최대 원소를 포함합니다.

비록 이 공식이 공식적으로 더 약한 것처럼 보이지만(비워지지 않는다는 추가 조건을 P에 두지만 P에 대해 동일한 결론을 얻기 때문에), 사실 두 공식은 동등합니다. 이를 검증하기 위해서 먼저 P가 P의 모든 사슬이 P에서 상한을 갖는다는 조건을 만족시킨다고 가정합니다. 그러면 P의 빈 부분 집합은 정의를 공백으로 만족하므로 사슬입니다. 따라서 이 부분 집합은 P에서 상한을 가져야 한다는 것을 의미하며, 이 상한은 P가 실제로 비어 있지 않음을 보여줍니다. 반대로, P가 비어 있지 않다고 가정하고 모든 비어 있지 않은 사슬이 P에서 상한을 갖는다는 가설을 만족시킨다면, P의 임의의 요소가 빈 사슬(즉, 사슬로 보이는 빈 부분 집합)에 대한 상한 역할을 하기 때문에 P는 또한 모든 사슬이 상한을 갖는다는 조건을 만족시킵니다.

그 차이는 미묘해 보일 수 있지만, 존의 보조정리를 사용하는 많은 증명에서 어떤 종류의 결합을 사용하여 상한을 생성하므로 빈 사슬의 경우를 간과할 수 있습니다. 즉, 모든 사슬이 상한을 가지고 있다는 검증은 빈 사슬과 비어 있지 않은 사슬을 별도로 처리해야 할 수 있습니다. 그래서 많은 저자들은 일반적인 논법에서 빈 사슬을 다루는 것보다 집합 P의 비공허성을 검증하는 것을 선호합니다.[9]

예제 응용프로그램

모든 벡터 공간에는 기저가 있습니다.

존의 보조정리는 모든 벡터공간 V가 기저를 갖는다는 것을 보여주는 데 사용될 수 있습니다.[10]

V = {0}인 경우 빈 집합은 V의 기준이 됩니다. 이제 V가 ≠ {0}이라고 가정합니다. P를 V의 모든 일차독립 부분집합들로 이루어진 집합이라 하자. V는 영벡터 공간이 아니므로 V의 영이 아닌 요소 v가 존재하므로 P는 선형적으로 독립적인 부분 집합 {v}을(를) 포함합니다. 또한 P는 집합 포함에 의해 부분적으로 순서가 정해집니다(포함 순서 참조). V의 최대 선형 독립 부분 집합을 찾는 것은 P에서 최대 원소를 찾는 것과 같습니다.

조른의 보조정리를 적용하려면 P의 사슬 T를 취합니다(즉, T는 완전 순서 P의 부분집합). T가 빈 집합이면 {v}는 P의 T에 대한 상한입니다. 그렇다면 T가 비어 있지 않다고 가정합니다. 우리는 T가 상한을 갖는다는 것, 즉 T의 모든 구성원을 포함하는 V의 선독립 부분집합 B가 존재한다는 것을 보여주어야 합니다.

B를 T의 모든 집합들의 합집합으로 삼자. 우리는 B가 P에서 T의 상한임을 보여주고자 합니다. 이를 위해서는 B가 V의 선형 독립적인 부분집합임을 보여주면 됩니다.

그렇지 않으면 B가 선형 독립적이지 않다고 가정합니다. 그런 다음 벡터 v, v, ..., v ∈ B와 스칼라 a, a, a, ..., a, 모두 0은 아닙니다.

B는 T의 모든 집합들의 합이므로, 모든 i = 1, 2, ..., k에 대하여 v ∈ S인 집합 S, S, ..., S ∈ T가 있습니다. T가 완전 순서이므로 집합 S, S, ..., S 중 하나는 다른 집합을 포함해야 하므로 v, v, ..., v를 모두 포함하는 집합 S가 있습니다. 이것은 S에i 선형 의존적인 벡터 집합이 있다는 것을 알려주며, S가i 선형 독립적이라는 것과 모순됩니다(P의 구성원이기 때문에).

Zorn의 보조정리에 대한 가설이 확인되었고, 따라서 P에는 최대 원소가 존재하며, 즉 V의 최대 선형 독립 부분 집합 B가 존재합니다.

마지막으로, 우리는 B가 실제로 V의 기초임을 보여줍니다. B가 V의 스패닝 집합이라는 것을 보여주면 충분합니다. 모순을 위해 B가 스패닝되지 않는다고 가정합니다. 그러면 B의 스팬에 포함되지 않은 v ∈ V가 있습니다. 이는 B ∪ {v}이(가) B보다 큰 V의 선형 독립적인 부분 집합이며, 이는 B의 최대값과 모순됨을 나타냅니다. 따라서 B는 V의 스패닝 집합이며, 따라서 V의 기저입니다.

통일성이 있는 사소한 모든 고리에는 최대의 이상이 포함되어 있습니다.

존의 보조정리는 통일성을 갖는 모든 자명하지 않은 고리 R이 최대 이상을 포함한다는 것을 보여주는 데 사용될 수 있습니다.

P를 R의 모든 고유 아이디얼(즉, R 자체를 제외한 R의 모든 아이디얼)로 구성된 집합이라 하자. R은 사소하지 않으므로 집합 P는 사소 아이디얼 {0}을(를) 포함합니다. 또한 P는 세트 포함에 의해 부분적으로 주문됩니다. R에서 극대 아이디얼을 찾는 것은 P에서 극대 원소를 찾는 것과 같습니다.

조른의 보조정리를 적용하려면 P에서 사슬 T를 취합니다. T가 비어 있으면 사소한 아이디얼 {0}은 P에서 T의 상한입니다. 그러면 T가 비어 있지 않다고 가정합니다. T가 상한을 가지고 있다는 것, 즉 T의 모든 구성원을 포함하지만 여전히 R보다 작은 이상 I ⊆ R이 존재한다는 것을 보여주는 것이 필요합니다(그렇지 않으면 적절한 이상이 되지 않으므로 P에 있지 않습니다).

내가 T에 있는 모든 이상들의 연합체가 된다고 생각해 보세요. 우리는 내가 P에서 T의 상한이라는 것을 보여주고 싶습니다. 먼저 제가 R의 이상형이라는 것을 보여드리겠습니다. 제가 이상적인 사람이 되려면 세 가지 조건을 만족시켜야 합니다.

  1. 나는 R의 비어 있지 않은 부분집합이고,
  2. 모든 x, y ∈ I에 대하여, 합 x + y는 I 안에 있습니다.
  3. 모든 ∈ R과 모든 x ∈ I에 대하여, 곱 rx는 I 안에 있습니다.

#1 - 나는 R의 비어 있지 않은 부분 집합입니다.

T는 적어도 하나의 원소를 포함하고, 그 원소는 적어도 0을 포함하므로, 결합 I은 적어도 0을 포함하고 비어 있지 않습니다. T의 모든 원소는 R의 부분 집합이므로, 결합 I은 R의 원소들로만 구성됩니다.

#2 - 모든 x, y ∈ I에 대하여, 합 x + y는 I 안에 있습니다.

x와 y가 I의 원소라고 가정합니다. 그렇다면 x는 J의 원소이고 y는 K의 원소인 두 개의 이상 J, K ∈ T가 존재합니다. T는 완전 순서이므로, 우리는 J ⊆ K 또는 K ⊆ J임을 알고 있습니다. 일반성을 잃지 않고 첫 번째 경우를 가정하십시오. x와 y는 둘 다 이상적인 K의 구성원이므로 이들의 합 x + y는 K의 구성원이며, 이는 x + y가 I의 구성원임을 보여줍니다.

#3 - 모든 ∈ R과 모든 x ∈ I에 대하여, 곱 rx는 I에 있습니다.

x가 I의 원소라고 가정해 보겠습니다. 그렇다면 x가 J 안에 있는 이상적인 J ∈ T가 존재합니다. r ∈ R이면 rx는 J의 원소이고 따라서 I의 원소입니다. 그래서 저는 R에서 이상적인 사람입니다.

이제, 우리는 제가 올바른 이상이라는 것을 보여줍니다. 아이디얼은 1을 포함하는 경우에만 R과 같습니다. (R이면 1을 포함하고, 반대로 1을 포함하고 r이 R의 임의의 원소라면 r1 = r은 아이디얼의 원소이므로 아이디얼은 R과 같습니다.) 따라서 만약 내가 R과 같다면, 아이디얼은 1을 포함하고, 이는 T의 구성원 중 하나가 1을 포함하므로 R과 같음을 의미하지만 R은 P에서 명시적으로 제외됩니다.

Zorn의 보조정리에 대한 가설이 확인되었고, 따라서 P에는 최대 원소가 존재하며, 즉 R에는 최대 이상이 존재합니다.

증명스케치

선택의 공리를 가정한 조른의 보조정리 증명의 밑그림이 그 뒤를 이룹니다. 보조정리가 거짓이라고 가정해 보겠습니다. 그러면 부분 순서 집합, 즉 포셋 P가 존재하여 모든 부분 집합이 상한을 가지며, P의 모든 원소에 대하여 그보다 더 큰 다른 원소가 존재합니다. 모든 완전 순서 부분 집합 T에 대하여, T는 상한을 가지며, 그 상한은 더 큰 원소를 가지므로, 더 큰 원소 b(T)를 정의할 수 있습니다. 함수 b를 실제로 정의하기 위해서는 선택 공리를 사용해야 합니다.

함수 b를 사용하여 원소 a0 < a1 < a2 < a3 < ...를 정의할 것입니다. < aω+1 < aω < …, P로 표시됨. 셀 수 없이 무한한 이 수열은 정말로 깁니다. 지수는 단지 자연수가 아니라 모든 순서입니다. 사실, 순서가 집합 P에 비해 너무 길고, 너무 많은 순서수(적절한 클래스)가 있으며, 어떤 집합에 원소가 있는 것보다 더 많습니다(즉, 어떤 순서수 집합이 주어지면 더 큰 순서수가 존재함). 집합 P는 곧 소진되어 원하는 모순에 부딪힐 것입니다.

a는 트랜스피니트 재귀에 의해 정의됩니다. P에서 임의로 a를 선택합니다(P는 빈 집합에 대한 상한을 포함하므로 비어 있지 않으므로 가능합니다). 그리고 다른 순서 w에 대해 = b ({a : v < w}를 설정합니다. a는v 완전히 주문되었기 때문에, 이것은 충분한 근거가 있는 정의입니다.

위 증명은 초기 세그먼트 {av:v < w}를 P의 부분 집합으로 간주하여 명시적으로 순서형을 참조하지 않고 공식화할 수 있습니다. 이러한 집합은 각 x ∈ S가 x = b ({리 ∈ S : y < x})를 만족하는 순서가 잘 정렬된 사슬 S ⊆ P로 쉽게 특징지을 수 있습니다. 모순은 모든 S의 결합(한계 서수 경우에 해당)을 취하거나 b(S)를 "마지막" S에 추가(후수 서수 경우에 해당)함으로써 항상 "다음" 초기 세그먼트를 찾을 수 있다는 것에 주목함으로써 달성됩니다.[11]

이 증명은 존의 보조개가 실제로 약간 더 강한 버전이라는 것을 보여줍니다.

보조정리 - P가 모든 잘 정렬된 부분집합이 상한을 갖는 집합이고, x가 P의 임의의 원소라면, P는 x보다 크거나 같은 최대 원소를 갖습니다. 즉, x에 필적하는 최대 원소가 있습니다.

역사

하우스도르프 최대 원리는 조른의 보조정리와 유사한 초기 진술입니다.

Kazimierz Kuratowski는 1922년에[12] 현대 공식에 가까운 보조정리의 버전을 증명했습니다. (그것은 포함에 의해 순서화되고 잘 정돈된 사슬들의 결합 아래 닫힌 집합에 적용됩니다.) 본질적으로 동일한 공식(단순하게 정렬된 것이 아니라 임의의 사슬을 사용함으로써 약화됨)이 1935년 막스 존에 의해 독립적으로 주어졌으며,[13] 그는 그것을 잘 정렬된 정리를 대체하는 집합론의 새로운 공리로 제안했고, 대수학에서 그 응용의 일부를 보여주었고, 또 다른 논문에서 선택 공리와 동등성을 보여줄 것을 약속했습니다. 한 번도 나타나지 않았던.

"존의 보조제"라는 이름은 1940년 존 투키(John Tukey)가 그의 저서 "위상학의 수렴과 균일성"에서 사용했기 때문인 것으로 보입니다. 1939년 부르바키의 테오리에 데 앙상블은 "Le Théorème de Zorn"과 유사한 최대 원리를 언급합니다.[14] "쿠라토프스키–존 보조개"라는 이름은 폴란드와 러시아에서 널리 퍼져 있습니다.

조른 보조정리의 동등한 형태

참고 항목: 선택 공리 § 등가물

존의 보조정리는 (ZF에서) 세 가지 주요 결과와 동등합니다.

  1. 하우스도르프 최대원리
  2. 선택의 공리
  3. 순서 정리.

(인간의 직관을 거스를 수도 있는) 이 동등성을 암시하는 잘 알려진 농담은 제리 보나에게 기인합니다: "선택의 공리는 분명히 사실이고, 질서정연한 원칙은 분명히 거짓이며, 누가 존의 보조정리에 대해 말할 수 있습니까?"[15]

존의 보조정리는 또한 1차 논리의 강력한 완전성 정리와 동등합니다.[16]

게다가, 존의 보조정리(또는 그와 동등한 형태 중 하나)는 다른 수학 영역에서 몇 가지 주요한 결과를 암시합니다. 예를들면,

  1. 함수해석학에서 가장 기본적인 결과 중 하나인 한-바나흐 정리를 증명하는 데 사용되는 바나흐의 확장 정리
  2. 모든 벡터 공간에는 선형[17] 대수의 결과인 기저가 있습니다. 특히 실수는 유리수 위의 벡터 공간으로서 하멜 기저를 가지고 있습니다.
  3. 모든 교환적인 단위환은 최대 이상을 가지며, 이는 크룰 정리로 알려진 환 이론의 결과이며, 조른의 보조환은 다음과 같습니다[18].
  4. 위상수학에서의 타이코노프 정리 (또한[19] 동치인)
  5. 모든 적절한 필터는 1차 논리의[20] 완전성 정리를 산출하는 한외 필터에 포함됩니다.

이러한 의미에서 우리는 존의 보조정리가 수학의 많은 영역에 적용할 수 있는 강력한 도구로 보일 수 있는 방법을 봅니다.

선택 공리의 약화에 따른 아날로그

참고 항목: 종속선택의 공리

ZF + DC(선택 공리가 종속 선택 공리로 대체된 저멜로-프란켈 집합 이론)에서 Zorn의 보조정리의 약화된 형태가 입증될 수 있습니다. 존의 보조정리는 최대 요소가 없는 집합이 집합의 순서 관계가 전체가 된다는 것을 언급하는 것과 동일할 것이며, 이를 통해 셀 수 있는 사슬을 구성하기 위해 종속 선택의 공리를 적용할 수 있다는 것을 관찰함으로써 간단히 표현할 수 있습니다. 따라서 부분적으로 순서가 매겨진 집합 중에서 유일하게 유한개의 사슬을 가진 집합은 최대 원소를 가져야 합니다.[21]

좀 더 일반적으로, 의존적 선택의 공리를 상위 순서로 강화하는 것은 앞 단락의 진술을 상위 순서로 일반화할 수 있게 해줍니다.[21] 임의로 큰 서수를 허용하는 한계에서, 우리는 앞 절의 선택 공리를 사용하여 완전한 존 보조정리의 증명을 복구합니다.

대중문화에서는

1970년 영화 조른스 보조제는 보조제의 이름을 따서 지어졌습니다.

보조정리는 "바트의 새로운 친구" 에피소드에서 심슨 가족에 언급되었습니다.[22]

참고 항목

메모들

  1. ^ Serre, Jean-Pierre (2003), Trees, Springer Monographs in Mathematics, Springer, p. 23
  2. ^ Moore 2013, 168페이지
  3. ^ Wilansky, Albert (1964). Functional Analysis. New York: Blaisdell. pp. 16–17.
  4. ^ Jech 2008, ch. 2, §2 수학에서 선택의 공리의 일부 적용
  5. ^ Jech 2008, 9페이지
  6. ^ Moore 2013, 168페이지
  7. ^ William Timothy Gowers (12 August 2008). "How to use Zorn's lemma".
  8. ^ 예를 들면 , , , , .
  9. ^ Bergman, George M (2015). An Invitation to General Algebra and Universal Constructions. Universitext (Second ed.). Springer-Verlag. p. 164. ISBN 978-3-319-11477-4.
  10. ^ Smits, Tim. "A Proof that every Vector Space has a Basis" (PDF). Retrieved 14 August 2022.
  11. ^ Lewin, Jonathan W. (1991). "A simple proof of Zorn's lemma". The American Mathematical Monthly. 98 (4): 353–354. doi:10.1080/00029890.1991.12000768.
  12. ^ Kuratowski, Casimir (1922). "Une méthode d'élimination des nombres transfinis des raisonnements mathématiques" [A method of disposing of transfinite numbers of mathematical reasoning] (PDF). Fundamenta Mathematicae (in French). 3: 76–108. doi:10.4064/fm-3-1-76-108. Retrieved 24 April 2013.
  13. ^ Zorn, Max (1935). "A remark on method in transfinite algebra". Bulletin of the American Mathematical Society. 41 (10): 667–670. doi:10.1090/S0002-9904-1935-06166-X.
  14. ^ 캠벨 1978, 페이지 82.
  15. ^ 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.
  16. ^ J.L. Bell & A.B. Slomson (1969). 모델 및 울트라 제품. 노스홀랜드 출판사. 5장 정리 4.3장 103쪽
  17. ^ Blass, Andreas (1984). "Existence of bases implies the Axiom of Choice". Axiomatic Set Theory. Contemporary Mathematics. Vol. 31. pp. 31–33. doi:10.1090/conm/031/763890. ISBN 9780821850268. {{cite book}}: journal= 무시됨(도움말)
  18. ^ Hodges, W. (1979). "Krull implies Zorn". Journal of the London Mathematical Society. s2-19 (2): 285–287. doi:10.1112/jlms/s2-19.2.285.
  19. ^ Kelley, John L. (1950). "The Tychonoff product theorem implies the axiom of choice". Fundamenta Mathematicae. 37: 75–76. doi:10.4064/fm-37-1-75-76.
  20. ^ J.L. Bell & A.B. Slomson (1969). 모델 및 울트라 제품. 노스홀랜드 출판사.
  21. ^ a b Wolk, Elliot S. (1983), "On the principle of dependent choices and some forms of Zorn's lemma", Canadian Mathematical Bulletin, 26 (3): 365–367, doi:10.4153/CMB-1983-062-5
  22. ^ "Zorn's Lemma The Simpsons and their Mathematical Secrets".

참고문헌

외부 링크