(번역) Transfinite induction

Original article: w:Transfinite induction

 

초월-유한 귀납법(Transfinite induction)은 예를 들어 순서-숫자(ordinal numbers) 또는 세는-숫자(cardinal numbers)의 집합과 같은 바른-순서화된 집합(well-ordered sets)에 대한 수학적 귀납법(mathematical induction)의 확장입니다. 그 정확성은 ZFC의 정리입니다.

Induction by cases

$P(\alpha )$를 모든 세는-숫자 $\alpha$에 대해 정의된 속성(property)이라고 놓습니다. $P(\beta )$가 모든 $\beta <\alpha$에 대해 참일 때마다 $P(\alpha )$도 참이라고 가정합니다. 그런-다음 초월-유한 귀납법은 $P$가 모든 순서-숫자에 대해 참이라고 말합니다.

보통 증명은 세 가지 경우로 나뉩니다:

• 영 경우(Zero case): $P(0)$가 참임을 입증합니다.
• 다음 경우(Successor case): 임의의 다음 순서-숫자(successor ordinal) $\alpha +1$에 대해 $P(\alpha +1)$이 $P(\alpha )$를 따름을 입증합니다 (그리고 필요하다면, 임의의 $\beta <\alpha$에 대해 $P(\beta )$를 따름을 입증합니다).
• 극한 경우(Limit case): 모든 극한 순서-숫자(limit ordinal) $\lambda$에 대해, $P(\lambda )$가 모든 $\beta <\lambda$에 대해 $P(\beta )$를 따름을 입증합니다.

모든 세 가지 경우는 고려되는 순서-숫자의 유형을 제외하고 동일합니다. 그것들은 형식적으로 별도로 고려될 필요는 없지만, 실제로 증명은 전형적으로 별도의 표시가 필요할 정도로 다릅니다. 영은 때때로 극한 순서-숫자(limit ordinal)로 고려되고 때때로 극한 순서-숫자와 같은 경우에 증명에서 취급될 수 있습니다.

Transfinite recursion

초월-유한 재귀(Transfinite recursion)는 초월-유한 귀납법과 유사합니다; 어쨌든, 어떤 것이 모든 순서-숫자에 대해 유지된다는 것을 입증하는 대신, 우리는 각 순서-숫자에 대해 하나씩 대상의 수열을 구성합니다.

하나의 예제로서, 벡터 공간(vector space, 아마도 무한-차원)에 대해 기저(basis)는 벡터 $v_0$를 선택하고 각 순서-숫자 $\alpha$에 대해 벡터 $\{v_{\beta }\mid \beta <\alpha \}$의 스팬(span)에 있지 않은 벡터를 선택함으로써 만들 수 있습니다. 이 과정은 벡터가 선택될 수 없을 때 중지합니다.

보다 형식적으로, 우리는 다음과 같이 초월-유한 재귀 정리(Transfinite Recursion Theorem)를 말할 수 있습니다:

Transfinite Recursion Theorem (version 1). 클래스 함수 G: V → V 가 주어지면 (여기서 V는 모든 집합의 클래스), 다음을 만족하는 고유한 초월-유한 수열(transfinite sequence) F: Ord → V가 존재합니다 (여기서 Ord는 모든 순서-숫자의 클래스):

• 모든 $\alpha$에 대해, $F(\alpha )=G(F\upharpoonright \alpha )$, 여기서 $\upharpoonright$ 는 순서-숫자 < $\alpha$에 대한 F의 도메인의 제한을 나타냅니다.

Transfinite Recursion Theorem (version 2). 집합 $g_1$, 및 클래스 함수 $G_2,G_3$가 주어지면, 다음을 만족하는 고유한 함수 F: Ord → V가 존재합니다

• $F(0)=g_1$,
• $F(\alpha +1)=G_2(F(\alpha ))$, for all α ∈ Ord,
• $F(\lambda )=G_3(F\upharpoonright \lambda )$, for all limit λ ≠ 0.

우리는 위의 속성을 의미 있게 만들기 위해 $G_2,G_3$의 도메인이 충분히 넓어야 함을 주목하십시오. 이들 속성을 만족시키는 수열의 고유성은 초월-유한 귀납법을 사용하여 입증될 수 있습니다.

더 일반적으로, 임의의 바른-토대된 관계(well-founded relation) R 위에 초월-유한 재귀에 의한 대상을 정의할 수 있습니다. (R은 집합일 필요도 없습니다; 그것은 적절한 클래스가 될 수 있으며, 그것이 집합-같은 관계(set-like relation)라는 조건에서 그렇습니다; 즉, 임의의 x에 대해, yRx가 집합임을 만족하는 모든 y의 모음입니다.)

Relationship to the axiom of choice

귀납법과 재귀를 사용하는 증명 또는 구성은 종종 초월-유한 귀납법에 의해 처리될 수 있는 바른-순서화된 관계를 생성하기 위해 선택의 공리(axiom of choice)를 사용합니다. 어쨌든, 만약 문제에서 관계가 이미 바른-순서화된 것이면, 우리는 종종 선택의 공리 호출 없이 초월-유한 귀납법을 사용할 수 있습니다. 예를 들어, 보렐 집합(Borel set)에 대한 많은 결과는 집합의 순서-숫자 랭크 위에 초월-유한 귀납법에 의해 입증됩니다; 이들 랭크는 이미 바른-순서화된 것이므로, 선택의 공리가 그것들을 바른-순서화하기 위해 필요하지 않습니다.

비탈리 집합(Vitali set)의 다음 구성은 선택의 공리가 초월-유한 귀납법에 의한 증명에서 사용될 수 있는 한 가지 방법을 보여줍니다:

• 먼저, 실수를 바른-순서화하여 (이것이 선택의 공리가 바른-순서화 정리(well-ordering theorem)를 통해 들어가는 곳임), 수열 $⟨r_{\alpha }|\alpha <\beta ⟩$을 제공하며, 여기서 $\beta$는 연속체의 카디널리티(cardinality of the continuum)를 갖는 순서-숫자입니다. $v_0$을 $r_0$와 같다고 놓습니다. 그런-다음 $v_1$을 $r_{{\alpha }_1}$과 같다고 놓으며, 여기서 ${\alpha }_1$은 $r_{{\alpha }_1}-v_0$가 유리수가 아님을 만족하는 최솟값입니다. 계속하십시오; 각 단계에서 지금까지 v 수열에서 구성된 임의의 원소와 유리수 차이가 없는 r 수열의 최소 실수를 사용합니다. r 수열에서 모든 실수가 소진될 때까지 계속하십시오. 마지막 v 수열은 비탈리 수열을 열거할 것입니다.

위의 논증은 실수를 바른-순서화하기 위해 처음부터 본질적인 방법으로 선택의 공리를 사용합니다. 그 단계 후에, 선택의 공리는 다시 사용되지 않습니다.

선택 공리의 다른 용도는 더 미묘합니다. 예를 들어, 초월-유한 재귀에 의한 구성은 자주 α까지 수열이 주어지면, $A_{\alpha +1}$에 대한 고유한 값을 지정하지 않을 것이지만, $A_{\alpha +1}$이 만족시켜야 하는 조건만 지정하고, 이 조건을 만족시키는 적어도 하나의 집합이 있다고 주장합니다. 만약 각 단계에서 그러한 집합의 고유한 예를 정의하는 것이 가능하지 않으면, 각 단계에서 그러한 집합을 선택하기 위해 선택의 공리(의 어떤 형식)를(을) 호출해야 할 수 있습니다. 셀-수-있는 길이의 귀납법과 재귀에 대해, 더 약한 종속 선택의 공리(axiom of dependent choice)가 충분합니다. 종속 선택의 공리를 만족시키지만 완전한 선택의 공리를 만족시키지 않는 집합 이론가들에게 관심 있는 체르멜로–프렝켈 집합 이론(Zermelo–Fraenkel set theory)의 모델이 있기 때문에, 특정한 증명이 오직 종속 선택을 필요로 한다는 지식이 유용할 수 있습니다.

See also

 

• Mathematical induction
• Transfinite number

 

References

• Suppes, Patrick (1972), "Section 7.1", Axiomatic set theory, Dover Publications, ISBN 0-486-61630-4

External links

 

• Emerson, Jonathan; Lezama, Mark & Weisstein, Eric W. "Transfinite Induction". MathWorld.