Transfinite induction

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

Induction by cases

$P(\alpha )$ 를 모든 세는-숫자 $\alpha$ 에 대해 정의된 속성(property)이라고 놓습니다. $P(\beta )$ 가 모든 $\beta <\alpha$ 에 대해 참일 때마다 $P(\alpha )$ 도 참이라고 가정합니다.^[2] 그런-다음 초월-유한 귀납법은 $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는 모든 집합의 클래스),^[3] 다음을 만족하는 고유한 초월-유한 수열(transfinite sequence) F: Ord → V가 존재합니다 (여기서 Ord는 모든 순서-숫자의 클래스):

모든

\alpha

에 대해,

F(\alpha )=G(F\upharpoonright \alpha )

, 여기서

\upharpoonright

는 순서-숫자 <

\alpha

에 대한 F의 도메인의 제한을 나타냅니다.

귀납법에서 경우에서 처럼, 우리는 서로 다른 유형의 순서-숫자를 개별적으로 취급할 수 있습니다: 초월-유한 재귀의 또 다른 형식화는 다음과 같습니다:

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

F(0) = g₁,
F(α + 1) = G₂(F(α)), for all α ∈ Ord,
$F(\lambda )=G_{3}(F\upharpoonright \lambda )$ , for all limit λ ≠ 0.

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

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

Relationship to the axiom of choice

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

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

먼저, 실수를 바른-순서화하여 (이것이 선택의 공리가 바른-순서화 정리(well-ordering theorem)를 통해 들어가는 곳임), 수열

\langle r_{\alpha }|\alpha <\beta \rangle

을 제공하며, 여기서

\beta

는 연속체의 카디널리티(cardinality of the continuum)를 갖는 순서-숫자입니다. v₀을 r₀와 같다고 놓습니다. 그런-다음 v₁을 r_α₁과 같다고 놓으며, 여기서

\alpha _{1}

은 r_α₁ − v₀가 유리수가 아님을 만족하는 최솟값입니다. 계속하십시오; 각 단계에서 지금까지 v 수열에서 구성된 임의의 원소와 유리수 차이가 없는 r 수열의 최소 실수를 사용합니다. r 수열에서 모든 실수가 소진될 때까지 계속하십시오. 마지막 v 수열은 비탈리 수열을 열거할 것입니다.

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

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

Notes

^ J. Schlöder, Ordinal Arithmetic. Accessed 2022-03-24.
^ It is not necessary here to assume separately that $P(0)$ is true. As there is no $\beta$ less than 0, it is vacuously true that for all $\beta <0$ , $P(\beta )$ is true.
^ A class function is a rule (specifically, a logical formula) assigning each element in the lefthand class to an element in the righthand class. It is not a function because its domain and codomain are not sets.
^ In fact, the domain of the relation does not even need to be a set. It can be a proper class, provided that the relation R is set-like: for any x, the collection of all y such that y R x must be a set.

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.

[1] J. Schlöder, Ordinal Arithmetic. Accessed 2022-03-24.

[2] It is not necessary here to assume separately that $P(0)$ is true. As there is no $\beta$ less than 0, it is vacuously true that for all $\beta <0$ , $P(\beta )$ is true.

[3] A class function is a rule (specifically, a logical formula) assigning each element in the lefthand class to an element in the righthand class. It is not a function because its domain and codomain are not sets.

[4] In fact, the domain of the relation does not even need to be a set. It can be a proper class, provided that the relation R is set-like: for any x, the collection of all y such that y R x must be a set.

[1]

[2]

[3]

[4]