[ZFC Set Theory] VIII. 초한 귀납법 Transfinite Induction

[lang-en]To see the previous post[/lang-en][lang-ko]이전 글 보러가기[/lang-ko]

$\def\Ord{\operatorname{Ord}}\def\ran{\operatorname{ran}}$

[lang-en]In the previous post, we discussed what ordinal numbers are and what their properties are. In this post, we are going to talk about the transfinite induction. The transfinite induction is a kind of extension of the mathematical induction. Now, let's take a moment to explain what mathematical induction is. Mathematical induction is a recursive proof technique used to prove statements that depend on a natural number or an integer. It involves proving a base case and then proving that if the statement holds for some natural number or integer, then it also holds for the next natural number or integer.[/lang-en]

[lang-ko]이전 글에서 우리는 서수의 정의와 그의 성질에 대해 다뤘습니다. 이번 글에서는 초한 귀납법에 대해 다룰 예정입니다. 초한 귀납법은 수학적 귀납법의 확장 중 하나입니다. 그러니 일단 수학적 귀납법에 대해 설명하도록 하겠습니다. 수학적 귀납법은 자연수나 정수 등에 의존하는 명제를 증명하는 데에 사용할 수 있는 재귀적인 증명 기법입니다. 이는 기저 사례에 대해 증명하고, 어떤 자연수나 정수에 대해 참이면 그 다음 수에 대해서도 참임을 보여서 모든 수에 대해서도 성립함을 보이는 기법입니다.[/lang-ko]

 

[thm]{1. ([lang-en]Mathematical Induction[/lang-en][lang-ko]수학적 귀납법[/lang-ko])}[lang-en]Let $T$ be a set satisfying the following properties:
(i) $0 \in T$;
(ii) $n \in T \Rightarrow n \cup \{ n \} \in T$.
Then, $\mathbb{N} \subseteq T$.[/lang-en][lang-ko]집합 $T$가 다음 두 명제를 만족한다고 하자.
(i) $0 \in T$.
(ii) $n \in T \Rightarrow n \cup \{ n \} \in T$.
그러면, $\mathbb{N} \subseteq T$이다.[/lang-ko][/thm]

 

Proof.

[lang-en]Suppose not, i.e., let $\mathbb{N}$ be not a subset of $T$. Then, the set $S := \mathbb{N} \setminus T$ is nonempty. Since $\mathbb{N}$ is well-ordered by $\subseteq$, there is the least element of $S$, and let's call it $m$. $m$ is clearly not $0$ because $0 \in T$. Hence, by the definition of $\mathbb{N}$, there is $m' \in \mathbb{N}$ such that $m' \cup \{ m' \} = m$. Then $m' \notin S$ since $m$ is the least element of $S$. Thus, we can conclude that $m' \in T$ and by the condition (ii), this implies that $m \in T$ , which contradicts $m \in S$. Therefore, $\mathbb{N}$ is a subset of $T$.[/lang-en]

[lang-ko]정리가 성립하지 않는다고 가정하자. 즉, $\mathbb{N}$이 $T$의 부분 집합이 아니라고 하자. 그러면 $S := \mathbb{N} \setminus T$는 공집합이 아니다. $\mathbb{N}$이 $\subseteq$를 정렬 순서로 가지므로 $S$는 최소 원소를 가지며, 그 최소 원소를 $m$이라고 하자. 그러면 $0 \in T$로부터 $m$이 $0$이 아니라는 것은 명확하다. 그러므로 $\mathbb{N}$의 정의에 의해, $m' \cup \{ m' \} = m$이 성립하도록 하는 $m' \in \mathbb{N}$이 존재한다. 그러면 $m$이 $S$의 최소 원소라는 사실로부터 $m' \notin S$라는 사실을 알 수 있으며, 이는 곧 $m' \in T$를 의미한다. 따라서 조건 (ii)에 의해 $m \in T$를 얻으며, 이는 $m \in S$에 모순이다. 따라서 $\mathbb{N}$은 $T$의 부분 집합임을 알 수 있다.[/lang-ko]

$\blacksquare$

 

[lang-en]Now that you know what mathematical induction is, let's learn about transfinite induction. Transfinite induction is a method of proof used to establish a statement that holds for all ordinal numbers. Transfinite induction also involves proving a base case and then proving the successor cases and the limit cases.[/lang-en]

[lang-ko]이제 수학적 귀납법이 무엇인지 알았으니 초한 귀납법에 대해 알아보도록 합시다. 초한 귀납법은 서수에 대한 명제를 증명하는 데에 사용되는 증명 기법입니다. 초한 귀납법은 기저 사례와 따름 사례, 극한 사례를 증명하여 모든 서수에 대해 성립함을 증명하는 방법입니다.[/lang-ko]

 

[thm]{2. ([lang-en]Transfinite Induction[/lang-en][lang-ko]초한 귀납법[/lang-ko])}[lang-en]Let $C$ be a class of ordinals and assume that:
(i) $0 \in C$;
(ii) if $\alpha \in C$, then $\alpha + 1 \in C$;
(iii) if $\alpha$ is a nonzero limit ordinal and $\beta \in C$ for all $\beta < \alpha$, then $\alpha \in C$.
Then, $C$ is the class of all ordinals.[/lang-en][lang-ko]서수를 원소로 가지는 모임 $C$가 다음 세 명제를 만족한다고 하자.
(i) $0 \in C$.
(ii) $\alpha \in C$이면 $\alpha + 1 \in C$이다.
(iii) $\alpha$가 $0$이 아닌 극한 서수이고 모든 $\beta < \alpha$에 대해 $\beta \in C$라면 $\alpha \in C$이다.
그러면 $C$는 모든 서수의 모임이다.[/lang-ko][/thm]

 

Proof.

[lang-en]Suppose not and let $\alpha$ be the least ordinal such that $\alpha \notin C$. It is clear that $\alpha \neq 0$. If $\alpha$ is a successor ordinal, there is an ordinal $\beta$ such that $\beta + 1 = \alpha$. By the minimality of $\alpha$, $\beta \in C$ and makes a contradiction to the condition (ii). If $\alpha$ is a limit ordinal, by the minimality of $\alpha$, $\beta \in C$ for every $\beta < \alpha$. Hence, by the condition (iii), $\alpha \in C$ and makes a contradiction. Therefore, every ordinal is an element of $C$ and the proof is complete.[/lang-en]

[lang-ko]정리가 성립하지 않는다고 가정하고 $\alpha$가 $\alpha \notin C$인 가장 작은 서수라고 합시다. 그러면 $\alpha \neq 0$인 것은 명확합니다. 만약 $\alpha$가 따름 서수라면, $\beta + 1 = \alpha$인 서수 $\beta$가 존재합니다. 그러면 $\alpha$의 최소성으로부터 $\beta \in C$임을 알 수 있으며, 이는 조건 (ii)에 모순입니다. 만약 $\alpha$가 극한 서수라면, $\alpha$의 최소성에 의해 모든 $\beta < \alpha$에 대해 $\beta \in C$가 성립합니다. 따라서 조건 (iii)에 의해 $\alpha \in C$임을 알 수 있으며 모순이 발생합니다. 따라서 모든 서수는 $C$의 원소가 되며, 증명이 완성됩니다.[/lang-ko]

$\blacksquare$

 

[lang-en]As this is a bit short to conclude the post, I would like to introduce the transfinite recursion. Transfinite recursion is a technique used to define a function on the class of all ordinal numbers. The idea behind transfinite recursion is to define the function step by step, starting with the value at 0 and then defining its values for each successor and limit ordinal. Before describing about transfinite recursion, we should talk about sequences.[/lang-en]

[lang-ko]이렇게 글을 끝내기엔 좀 짧기 때문에 초한 재귀에 대해 설명하려 합니다. 초한 재귀는 모든 서수의 모임을 정의역으로 하는 함수를 정의하는 기법입니다. 초한 재귀의 가장 핵심적인 아이디어는 함숫값을 $0$부터 하나씩 차근차근 정의하는 것입니다. 초한 재귀에 대해 서술하기 전에 수열에 대해 먼저 설명하도록 하겠습니다.[/lang-ko]

 

[def]{3.}[lang-en]A function whose domain is $\mathbb{N}$ is called an (infinite) $sequence$. A sequence in $X$ means a function of $\mathbb{N}$ into $X$. The standard notation for a sequence is $$ \left< a_n : n < \omega \right> $$ or variants thereof. Some authors simply write as $\{ a_n \}$. A finite sequence is a function $s$ whose domain is a natural number $n \in \mathbb{N}$; then $s$ is a sequence of length $n$.
A transfinite sequence is a function whose domain is an ordinal: $$ \left< a_\xi : \xi < \alpha \right> . $$ It is also called an $\alpha$-sequence or a sequence of length $\alpha$. We also say that a sequence $\left< a_\xi : \xi < \alpha \right>$ is an $enumeration$ of its range $\{ a_\xi : \xi < \alpha \}$. Somtimes we shall call a "sequence" $$ \left< a_\alpha : \alpha \in \Ord \right> $$ a function (a proper class) on $\Ord$.[/lang-en][lang-ko]정의역이 $\mathbb{N}$인 함수를 (무한) 수열이라고 한다. $X$ 위의 수열은 $\mathbb{N}$에서 $X$로 가는 함수를 말한다. 수열의 가장 일반적인 표기는 $$ \left< a_n : n < \omega \right> $$ 또는 이의 변형들이다. 저자에 따라 간단하게 $\{ a_n \}$과 같이 쓰기도 한다. 유한 수열은 정의역이 자연수 $n \in \mathbb{N}$인 함수 $s$를 말하며, 이 경우, $s$를 길이 $n$짜리 수열이라고 한다. 초한 수열은 정의역이 서수인 함수로, $$ \left< a_\xi : \xi < \alpha \right> $$와 같이 나타낸다. 이는 $\alpha$-수열 또는 길이 $\alpha$짜리 수열이라고 불린다. 또한 수열 $\left< a_\xi : \xi < \alpha \right>$를 이의 치역 $\{ a_\xi : \xi < \alpha \}$의 열거라고 부르기도 한다. 때때로 $\Ord$ 위의 함수 $$ \left< a_\alpha : \alpha \in \Ord \right> $$를 "수열"이라고 부르기도 한다.[/lang-ko][/def]

 

[thm]{4. ([lang-en]Transfinite Recursion[/lang-en][lang-ko]초한 재귀[/lang-ko])}[lang-en]Let $G$ be a function (on the class $V$ of all sets). Then there uniquely exists a function $F$ on $\Ord$ such that $$ F(\alpha) = G(\href{https://susiljob.tistory.com/107}{F \upharpoonright \alpha}) $$ for each $\alpha$.[/lang-en][lang-ko]$G$를 (모든 집합의 모임 $V$ 위의) 함수라고 하자. 그러면 각 $\alpha$에 대해 $$ F(\alpha) = G(\href{https://susiljob.tistory.com/107}{F \upharpoonright \alpha}) $$가 성립하는 $\Ord$를 정의역으로 가지는 함수 $F$가 유일하게 존재한다.[/lang-ko][/thm]

 

Proof.

[lang-en]Let $F(\alpha) = x$ if and only if there is a sequence $\left< a_\xi : \xi < \alpha \right>$ such that: $$ \begin{array}{rl} (i) & \forall \xi < \alpha , \; a_\xi = G( \left< a_\eta : \eta < \xi \right> ); \\ (ii) & x = G( \left< a_\xi : \xi < \alpha \right> ). \end{array} $$ For every $\alpha$, if there exists a sequence of length $\alpha$ satisfying the condition (i), then such a sequence is unique. For otherwise, if $\left< a_\xi : \xi < \alpha \right>$ and $\left< b_\xi : \xi < \alpha \right>$ are two sequences of length $\alpha$ satisfying the condition (i), one shows $a_\xi = b_\xi$ by induction on $\xi$. Thus $F(\alpha)$ is determined uniquely by the condition (ii), and therefore $F$ is a function. It follows, again by induction, that for each $\alpha$ there is a sequence of length $\alpha$ satisfying the condition (i) (at limit steps, we use replacement to get the sequence of length $\alpha$ as the union of all the sequence of length $\xi$, $\xi < \alpha$). Thus $F$ is well-defined for all $\alpha \in \Ord$. It obviously satisfies $F(\alpha) = G(F \upharpoonright \alpha)$. If $F'$ is any function on $\Ord$ satisfying $F'(\alpha) = G(F' \upharpoonright \alpha)$ then it follows by induction that $F'(\alpha) = F(\alpha)$ for all $\alpha$.[/lang-en]

[lang-ko]각 $\alpha$에 대해 함숫값 $F(\alpha) = x$인 것과 다음 두 명제를 만족하는 수열 $\left< a_\xi : \xi < \alpha \right>$가 존재하는 것이 필요충분조건이 되도록 함수 $F$를 정의합시다. $$ \begin{array}{rl} (i) & \forall \xi < \alpha , \; a_\xi = G( \left< a_eta : \eta < \xi \right> ) \\ (ii) & x = G( \left< a_\xi : \xi < \alpha \right> ) \end{array} $$ 서수 $\alpha$에 대해, 조건 (i)를 만족하는 길이 $\alpha$짜리 수열이 존재한다면, 그러한 수열은 유일합니다. 만약 그렇지 않다면, 조건 (i)를 만족하는 길이 $\alpha$짜리 두 수열 $\left< a_\xi : \xi < \alpha \right>$와 $\left< b_\xi : \xi < \alpha \right>$에 대해 $a_\xi = b_\xi$임을 $\xi$에 대한 귀납법으로 보일 수 있습니다. 따라서 조건 (ii)에 의해 $F(\alpha)$는 유일하게 존재하며, $F$가 함수임을 알 수 있습니다. 이제 다시 귀납법을 사용하면, 각 $\alpha$에 대하여 조건 (i)를 만족하는 길이 $\alpha$짜리 수열이 언제나 존재합니다. (극한 사례의 경우, 치환 공리꼴을 사용하여 길이 $\xi < \alpha$인 수열의 합집합으로 길이 $\alpha$인 수열을 얻을 수 있습니다.) 따라서 $F$는 모든 $\alpha \in \Ord$에 대해 잘 정의됩니다. 이렇게 정의한 함수 $F$에 대하여 $F(\alpha) = G(F \upharpoonright \alpha)$가 성립함은 매우 당연합니다. 만약 $\Ord$를 정의역으로 하는 또다른 함수 $F'$가 $F'(\alpha) = G(F' \upharpoonright \alpha)$를 만족한다면 초한 귀납법을 이용하여 모든 서수 $\alpha$에 대해 $F'(\alpha) = F(\alpha)$임을 보일 수 있습니다.[/lang-ko]

$\blacksquare$

 

[cor]{4.1.}[lang-en]Let $X$ be a set and $\theta$ an ordinal. For every function $G$ of the set of all transfinite sequences in $X$ of length $< \theta$ such that $\ran(G) \subseteq X$, there exists unique $\theta$-sequence $\left< a_\alpha : \alpha < \theta \right>$ in $X$ such that $a_\alpha = G( \left< a_\xi : \xi < \alpha \right> )$ for every $\alpha < \theta$.[/lang-en][lang-ko]$X$를 집합이라 하고 $\theta$를 서수라고 하자. $X$ 위의 길이 $<\theta$인 모든 초한 수열들의 집합을 정의역으로 하고 $\ran(G) \subseteq X$인 함수 $G$에 대해, 모든 $\alpha < \theta$에 대해 $a_\alpha = G( \left< a_\xi : \xi < \alpha \right> )$를 만족하는 $X$ 위의 $\theta$-수열 $\left< a_\alpha : \alpha < \theta \right>$가 유일하게 존재한다.[/lang-ko][/cor]

 

[lang-en]The proof of Corollary 4.1 is quite routine so the proof is ommitted. If you cannot derive the corollary from Theorem 4 immediately, try to prove the corollary by yourself.[/lang-en]

[lang-ko]Corollary 4.1의 증명은 상당히 기계적이므로 증명을 생략하도록 하겠습니다. 만약 이 따름정리를 Theorem 4로부터 즉시 얻어내지 못하였다면 스스로 증명해보는 것도 좋을 것 같습니다.[/lang-ko]

 

[lang-en]In the next post, as commented on the last post, we'll deal with the arithmetic of ordinals. And always, thanks for reading.[/lang-en]

[lang-ko]다음 글에서는 이전 글에서 언급했듯이 서수의 산술연산을 다룰 예정입니다. 늘 그랬듯이, 읽어주셔서 감사합니다.[/lang-ko]

 

[lang-en]To see the next post[/lang-en][lang-ko]다음 글 보러가기[/lang-ko]