[ZFC Set Theory] VI. 전순서 집합 Well-Ordered Sets

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

$\def\dom{\operatorname{dom}}$$\def\ran{\operatorname{ran}}$

[lang-en]As of the previous post, we've covered the most fundamental parts of the ZFC set theory. As commented in the previous post, we're going to talk about ordinals as of this post. To deal with the ordinals, we need to deal with the well-ordered sets first. Hence, we're going to talk about well-ordered sets in this post. First of all, let's look at the below:[/lang-en]

[lang-ko]이전 글까지 우리는 ZFC 집합론에서 가장 기초적인 내용들을 다뤄왔습니다. 저번 글에서 언급했듯이, 이번 글부터는 서수라는 개념에 대해 다루게 될 것입니다. 서수를 다루기 위해서는 전순서 집합에 대해 알아야 할 필요가 있습니다. 따라서, 이번 글에서는 전순서 집합에 대해 다룰 예정입니다. 일단 제일 먼저 아래의 정의를 보시죠.[/lang-ko]

 

[def]{1.}[lang-en]A binary relation $\leq$ on a set $P$ is called a $partial \; ordering$ of $P$ if it is antisymmetric, reflextive, and transitive. Further, $\left( P , \leq \right)$ is called a $partially \; ordered \; set$. A partial ordering $\leq$ of $P$ is called a $total \; ordering$ or $linear \; ordering$ if moreover $p \leq q$ or $q \leq p$ for any $p,q \in P$. In this case, $\left( P , \leq \right)$ is called a $totally \; ordered \; set$, obviously.[/lang-en][lang-ko]집합 $P$ 위에서 정의된 이항 관계 $\leq$가 반대칭적이고 반사적이고 추이적이면 $\leq$를 $P$ 위에서 정의된 부분 순서라고 부른다. 또한, $\left( P , \leq \right)$를 부분 순서 집합이라고 부른다. 만약 집합 $P$에서 정의된 부분 순서 $\leq$에 대해, 임의의 두 원소 $p,q \in P$에 대해 항상 $p \leq q$ 또는 $q \leq p$가 성립한다면 이러한 $\leq$를 전순서라고 부른다. 당연하지만, $\leq$가 전순서인 경우, $\left( P , \leq \right)$를 전순서 집합이라고 부른다.[/lang-ko][/def]

 

[lang-en]Let an ordered set be given. Then, we can consider concepts like maximal, greatest, etc. Look at the below:[/lang-en]

[lang-ko]순서 집합이 주어졌다고 해봅시다. 그러면 최대 또는 극대와 같은 개념들을 고려해볼 수 있을 것입니다. 아래의 정의를 보죠.[/lang-ko]

 

[def]{2.}[lang-en]Let $\left( P , \leq \right)$ be a partially ordered set, $X$ be a subset of $P$, and $a \in P$. Then:
$\bullet$ $a$ is a $maximal$ element of $X$ if $a \in X$ and $\forall x \in X, \; a \leq x \Rightarrow a = x$;
$\bullet$ $a$ is a $minimal$ element of $X$ if $a \in X$ and $\forall x \in X, \; x \leq a \Rightarrow a = x$;
$\bullet$ $a$ is the $greatest$ element of $X$ if $a \in X$ and $\forall x \in X, \; x \leq a$;
$\bullet$ $a$ is the $least$ element of $X$ if $a \in X$ and $\forall x \in X, \; a \leq x$;
$\bullet$ $a$ is an $upperbound$ of $X$ if $\forall x \in X, \; x \leq a$;
$\bullet$ $a$ is a $lowerbound$ of $X$ if $\forall x \in X, \; a \leq x$;
$\bullet$ $a$ is the $supremum$ of $X$ if $a$ is the least upperbound of $X$;
$\bullet$ $a$ is the $infimum$ of $X$ if $a$ is the greatest lowerbound of $X$.[/lang-en][lang-ko]부분 순서 집합 $\left( P , \leq \right)$와 $P$의 부분집합 $X$, $P$의 원소 $a \in P$가 주어졌다고 하자.
$\bullet$ $a \in X$이고 $\forall x \in X, \; a \leq x \Rightarrow a = x$이면 $a$를 $X$의 극대 원소라고 한다.
$\bullet$ $a \in X$이고 $\forall x \in X, \; x \leq a \Rightarrow a = x$이면 $a$를 $X$의 극소 원소라고 한다.
$\bullet$ $a \in X$이고 $\forall x \in X, \; x \leq a$이면 $a$를 $X$의 최대 원소라고 한다.
$\bullet$ $a \in X$이고 $\forall x \in X, \; a \leq x$이면 $a$를 $X$의 최소 원소라고 한다.
$\bullet$ $\forall x \in X, \; x \leq a$이면 $a$를 $X$의 상계라고 한다.
$\bullet$ $\forall x \in X, \; a \leq x$이면 $a$를 $X$의 하계라고 한다.
$\bullet$ $a$가 최소 상계라면 $a$를 상한이라고 한다.
$\bullet$ $a$가 최대 하계라면 $a$를 하한이라고 한다.[/lang-ko][/def]

 

[lang-en]Further, the supremum and the infimum of $X$ is denoted by $\sup X$ and $\inf X$, respectively. Also, note that if $X$ is totally ordered by $\leq$, then a maximal element of $X$ is its greatest element and this is similar for a minimal element. Moreover, if $\left( P , \leq \right)$ and $\left( Q , \leq \right)$ are partially ordered sets and $f : P \to Q$ is given, then $f$ is $order$-$preserving$ if $x \leq y$ implies that $f(x) \leq f(y)$. If $P$ and $Q$ are totally ordered, then an order-preserving function is called $increasing$. If an order-preserving function $f : P \to Q$ is bijective and if its inverse $f^{-1}$ is order-preserving, then $f$ is called an $order \; isomorphism$, and we say that $\left( P , \leq \right)$ is $order \; isomorphic$ to $\left( Q , \leq \right)$. Clearly, order isomorphic is an equivalence relation on the class of the partially ordered sets. Finally, an order isomorphism of $P$ onto itself is an $order \; automorphism$ of $\left( P , \leq \right)$.[/lang-en]

[lang-ko]또한, $X$의 상한과 하한은 각각 $\sup X$, $\inf X$와 같이 나타냅니다. 만약 $\left( X , \leq \right)$가 전순서 집합이라면 $X$의 극대 원소는 언제나 $X$의 최대 원소가 되며, 이는 극소 원소의 경우에도 비슷하다는 것을 알아두세요. 추가로, $\left( P , \leq \right)$와 $\left( Q , \leq \right)$가 부분 순서 집합이고 함수 $f : P \to Q$에 대하여 $x \leq y$가 $f(x) \leq f(y)$를 함의한다면, 이러한 함수 $f$가 순서를 보존한다고 말하며, 만약 $P$와 $Q$가 전순서 집합이었을 경우, 순서를 보존하는 함수를 증가 함수라고 말합니다. 만약 순서를 보존하는 함수 $f : P \to Q$가 전단사 함수이고 역함수 $f^{-1}$ 역시 순서를 보존한다면, $f$를 순서 동형 사상이라고 말하며, 부분 순서 집합 $\left( P , \leq \right)$가 부분 순서 집합 $\left( Q , \leq \right)$와 순서 동형이라고 말합니다. 당연하게도, 순서 동형 관계는 모든 부분 순서 집합의 모임 위의 동치 관계가 됩니다. 마지막으로, $P$에서 자기 자신으로 가는 순서 동형 사상을 $\left( P , \leq \right)$의 순서 자기동형 사상이라고 합니다.[/lang-ko]

 

[lang-en]If you think about the number system that we usually deal with, you can see that these are all preorder sets. For example, the set of the real numbers is obviously a totally ordered set. Hence, so are the cases of rational numbers, integers, natural numbers. Of these, the natural numbers have a slightly more unusual property. A nonempty subset of $\mathbb{N}$ always has the least element. This property is quite special, so it has a name, of course. Look at the below:[/lang-en]

[lang-ko]우리가 흔히 다루는 수 체계들을 떠올려 보면, 그들은 모두 전순서 집합이라는 사실을 알 수 있습니다. 예를 들어, 실수 집합이 전순서 집합이 된다는 것은 직관적으로 당연해 보입니다. 이는 유리수, 정수, 자연수의 경우도 마찬가지입니다. 그런데, 이 중 자연수는 조금 더 특별한 성질을 가지고 있습니다. 자연수 집합 $\mathbb{N}$의 공집합이 아닌 부분집합은 항상 최소 원소를 가진다는 것입니다. 이 성질은 상당히 특별한 성질이며, 그렇기 때문에 이름을 가지고 있습니다. 아래의 정의를 한번 봅시다.[/lang-ko]

 

[def]{3.}[lang-en]A total ordering $\leq$ of a set $P$ is a $well$-$ordering$ if every nonempty subset of $P$ has a least element.[/lang-en][lang-ko]집합 $P$ 위의 전순서 $\leq$가 주어졌다고 하자. 만약 $P$의 공집합이 아닌 부분집합이 항상 최소 원소를 가진다면, 전순서 $\leq$를 정렬 순서라고 한다.[/lang-ko][/def]

 

[lang-en]The concept of well-ordering is of fundamental importance. Well-ordered sets can be compared by their "lengths". The ordinal numbers, which will be covered in the next post, represent this "lengths". By the way, the below explain how we compare the well-ordered sets. Look at the below:[/lang-en]

[lang-ko]정렬 순서의 개념은 근본적으로 매우 중요합니다. 정렬 집합들은 그들의 '길이'를 이용하여 비교할 수 있으며, 다음 글에서 다루게 될 서수가 바로 이 '길이'의 역할을 하게 됩니다. 아래의 내용은 우리가 어떻게 정렬 집합들을 비교할 수 있을지를 설명하는 내용입니다. 아래를 보죠.[/lang-ko]

 

[lem]{4.}[lang-en]If $\left( W , \leq \right)$ is a well-ordered set and $f : W \to W$ is an increasing function, then $f(x) \geq x$ for each $x \in W$.[/lang-en][lang-ko]만약 $\left( W , \leq \right)$가 정렬 집합이고 $f : W \to W$가 증가 함수라면, 각 $x \in W$에 대하여 언제나 $f(x) \geq x$가 성립한다.[/lang-ko][/lem]

 

Proof.

[lang-en]Assume that the set $X = \{ x \in W \mid f(x) < x \}$ is nonempty and let $z$ be the least element of $X$. The existence of such $z$ is implied by the fact that $\left( W , \leq \right)$ is a well-ordered set. If $w = f(z)$, then since $f$ is an increasing function, $f(w) < w$, and this makes a contradiction the minimality of $z$. Hence, the assumption is false and the proof is complete.[/lang-en]

[lang-ko]집합 $X = \{ x \in W \mid f(x) < x \}$가 공집합이 아니라고 가정하고 $z$를 $X$의 최소 원소라고 합시다. 이러한 $z$의 존재성은 $\leq$가 정렬 순서라는 것으로부터 자명합니다. 만약 $w = f(z)$라면, $f$가 증가 함수라는 사실로부터 $f(w) < w$가 성립함을 알 수 있으며, 이는 $z$가 $X$의 최소 원소라는 사실에 모순입니다. 따라서 $\forall x \in W, \; f(x) \geq x$가 성립함을 알 수 있습니다.[/lang-ko]

$\blacksquare$

 

[cor]{4.1.}[lang-en]The only automorphism of a well-ordered set is the identity.[/lang-en][lang-ko]정렬 집합의 순서 자기 동형 사상은 항등 사상 뿐이다.[/lang-ko][/cor]

 

Proof.

[lang-en]Let $\left( W , \leq \right)$ be a well-ordered set and $f : W \to W$ be an order automorphism. Then, by the Lemma 4, $f(x) \geq x$ for all $x \in W$ and $f^{-1}(x) \geq x$ for all $x \in W$. Hence, $f(x) \geq x = f^{-1}(f(x)) \geq f(x)$ and therefore $f(x) = x$.[/lang-en]

[lang-ko]$\left( W , \leq \right)$가 정렬 집합이고 $f : W \to W$가 순서 자기 동형 사상이라고 합시다. 그러면, Lemma 4에 의해 모든 $x \in W$에 대해 $f(x) \geq x$이면서 동시에 $f^{-1}(x) \geq x$입니다. 따라서, $f(x) \geq x = f^{-1}(f(x)) \geq f(x)$가 성립하며, 따름정리가 증명됩니다.[/lang-ko]

$\blacksquare$

 

[cor]{4.2.}[lang-en]If two well-ordered sets $\left( W_1 , \leq \right)$ and $\left( W_2 , \leq \right)$ are order isomorphic to each other, then the order isomorphism of $W_1$ onto $W_2$ is unique.[/lang-en][lang-ko]만약 두 정렬 집합 $\left( W_1 , \leq \right)$와 $\left( W_2 , \leq \right)$가 순서 동형이라면, $W_1$에서 $W_2$로 가는 순서 동형 사상은 유일하다.[/lang-ko][/cor]

 

Proof.

[lang-en]Let $f_1 : W_1 \to W_2$ and $f_2 : W_1 \to W_2$ be order isomorphisms. Then, $f_1 \circ f_2^{-1}$ and $f_2^{-1} \circ f_1$ are order automorphisms. Hence, by the Corollary 4.1, $f_1 \circ f_2^{-1}$ and $f_2^{-1} \circ f_1$ are identities. Thus, $f_1^{-1} = f_2^{-1}$ and therefore $f_1 = f_2$.[/lang-en]

[lang-ko]$f_1 : W_1 \to W_2$와 $f_2 : W_1 \to W_2$가 순서 동형 사상이라고 합시다. 그러면, $f_1 \circ f_2^{-1}$와 $f_2^{-1} \circ f_1$이 순서 자기 동형 사상이 되므로 Corollary 4.1에 의해 $f_1 \circ f_2^{-1}$와 $f_2^{-1} \circ f_1$이 항등 사상임을 알 수 있습니다. 따라서, $f_1^{-1} = f_2^{-1}$임을 알 수 있으며, 이로부터 $f_1 = f_2$를 얻을 수 있습니다.[/lang-ko]

$\blacksquare$

 

[lang-en]Before developing the content, we will introduce one concept; if $\left( W , \leq \right)$ is a well-ordered set and $u \in W$, then $\{ x \in W \mid x < u \}$ is an $initial \; segment$ of $W$ given by $u$. So let's continue, look at the below.[/lang-en]

[lang-ko]내용을 더 전개하기에 앞서, 한 가지 개념을 먼저 소개하도록 하겠습니다. $\left( W , \leq \right)$가 정렬 집합이고 $u \in W$라고 할 때, 집합 $\{ x \in W \mid x < u \}$를 $u$에 의해 주어진 $W$의 절편 (initial segment of $W$ given by $u$)이라고 합니다. 그럼 내용을 계속해서 전개하도록 하겠습니다. 아래를 보죠.[/lang-ko]

 

[lem]{5.}[lang-en]No well-ordered set is order isomorphic to an initial segment of itself.[/lang-en][lang-ko]그 어떤 정렬 집합도 자기 자신의 절편과 순서 동형이 될 수 없다.[/lang-ko][/lem]

 

Proof.

[lang-en]Suppose not, i.e., there is a well-ordered set $\left( W , \leq \right)$ and $u \in W$ such that $W$ is order isomorphic to $S_u = \{ x \in W \mid x < u \}$. Let $f : W \to S_u$ be an order isomorphism. Since $S_i \subseteq W$, the extension $f : W \to W$ is an increasing function. Then, by the Lemma 4, $f(u) \geq u$ and this means that $f(u) \notin S_u$ and thus makes a contradiction. Therefore, the proof is complete.[/lang-en]

[lang-ko]보조정리가 성립하지 않는다고 가정합시다. 즉, $W$가 $S_u = \{ x \in W \mid x < u \}$와 순서 동형이도록 하는 정렬 집합 $\left( W , \leq \right)$와 $u \in W$가 존재한다고 가정합시다. 그러면 순서 동형 사상 $f : W \to S_u$가 존재합니다. 이때, $S_u \subseteq W$이므로 $f : W \to S_u$의 확장 $f : W \to W$는 증가 함수임을 알 수 있습니다. 따라서 Lemma 4에 의해, $f(u) \geq u$가 성립하며, 이는 $f(u) \notin S_u$를 함의하므로 모순이 발생합니다. 따라서 보조정리가 성립합니다.[/lang-ko]

$\blacksquare$

 

[thm]{6.}[lang-en]If $\left( W_1 , \leq \right)$ and $\left( W_2 , \leq \right)$ are well-ordered sets, then exactly one of the following three cases holds:
(i) $W_1$ is order isomorphic to $W_2$;
(ii) $W_1$ is order isomorphic to an initial segment of $W_2$;
(iii) $W_2$ is order isomorphic to an initial segment of $W_1$.[/lang-en][lang-ko]만약 $\left( W_1 , \leq \right)$와 $\left( W_2 , \leq \right)$가 정렬 집합이라면, 다음 세 경우 중 정확히 하나만이 성립한다.
(i) $W_1$과 $W_2$가 순서 동형이다.
(ii) $W_1$이 $W_2$의 절편과 순서 동형이다.
(iii) $W_2$가 $W_1$의 절편과 순서 동형이다.[/lang-ko][/thm]

 

Proof.

[lang-en]For $u \in W_i$, ($i = 1, \; 2$), let $W_i(u)$ denote the initial segment of $W_i$ given by $u$. Let $$ f = \{ (x,y) \in W_1 \times W_2 \mid W_1(x) \text{ is order isomorphic to } W_2(y) \}. $$ Using the Lemma 5, it is easy to check that $f$ is a one-to-one function. If $h$ is an order isomorphism of $W_1(x)$ onto $W_2(y)$, and $x' < x$, then $W_1(x')$ and $W_2(h(x'))$ are order isomorphic to each other since the restriction of $h$ is an order isomorphism between $W_1(x')$ and $W_2(h(x'))$. If follows that $f$ is increasing.[/lang-en]

[lang-ko]각 $u \in W_i$ ($i = 1, \; 2$)에 대하여, $W_i(u)$가 $u$에 의해 주어진 $W_i$의 절편을 나타낸다고 합시다. 이제 $$ f = \{ (x,y) \in W_1 \times W_2 \mid W_1(x) \text{가 } W_2(y) \text{와 순서 동형이다.} \} $$ 라고 합시다. 그러면 Lemma 5로부터 $f$가 일대일 함수가 됨을 매우 쉽게 확인할 수 있습니다. 만약 $h$가 $W_1(x)$와 $W_2(y)$ 사이의 순서 동형 사상이고 $x' < x$라면, $h$의 정의역을 축소하여 $W_1(x')$와 $W_2(h(x'))$ 사이의 순서 동형 사상을 얻을 수 있으므로 이 둘은 순서 동형입니다. 따라서 $f$가 증가 함수가 됨을 알 수 있습니다.[/lang-ko]

[lang-en]If $\dom(f) = W_1$ and $\ran(f) = W_2$, then the case (i) holds.[/lang-en]

[lang-ko]만약 $\dom(f) = W_1$이고 $\ran(f) = W_2$라면 (i)가 성립합니다.[/lang-ko]

[lang-en]If $y_1 < y_2$ and $y_2 \in \ran(f)$, then $y_1 \in \ran(f)$, obviously. Thus if $\ran(f) \neq W_2$ and $y_0$ is the least element of $W_2 \setminus \ran(f)$, then we have $\ran(f) = W_2(y_0)$. Necessarily, $\dom(f) = W_1$, for otherwise we would have $(x_0,y_0) \in f$, where $x_0$ is the least element of $W_1 \setminus \dom(f)$. Thus the case (ii) holds.[/lang-en]

[lang-ko]만약 $y_1 < y_2$이고 $y_2 \in \ran(f)$라면, $y_1 \in \ran(f)$임이 매우 자명합니다. 따라서 $\ran(f) \neq W_2$이고 $y_0$이 $W_2 \setminus \ran(f)$의 최소 원소라면 $\ran(f) = W_2(y_0)$임을 알 수 있습니다. 만약 $\dom(f) \neq W_1$이라면 $W_1 \setminus \dom(f)$의 최소 원소 $x_0$에 대하여 $(x_0,y_0) \in f$임이 자명하므로 $\dom(f) = W_1$임을 알 수 있습니다. 따라서 $\ran(f) \neq W_2$이면 (ii)가 성립합니다.[/lang-ko]

[lang-en]Similarly, if $\dom(f) \neq W_1$, then the case (iii) holds.[/lang-en]

[lang-ko]비슷하게, 만약 $\dom(f) \neq W_1$이라면 (iii)가 성립함을 알 수 있습니다.[/lang-ko]

[lang-en]In view of the Lemma 5, the three cases are mutually exclusive.[/lang-en]

[lang-ko]Lemma 5에 의하여, 세 경우 중 어느 하나가 성립하면 나머지는 성립하지 않음을 알 수 있으며, 따라서 정리가 증명됩니다.[/lang-ko]

$\blacksquare$

 

[lang-en]If two well-ordered sets are order isomorphic, we say that they have the same $order$-$type$. Informally, an ordinal number is the order-type of a well-ordered set. In the next post, we shall give a formal definition of ordinal numbers. Using the concept of ordinal numbers, we can state the transfinite induction, which is an extension of the mathematical induction. Of course, in many other ways, we're going to use the idea of ordinal numbers. And always, thanks for reading.[/lang-en]

[lang-ko]만약 두 정렬 집합이 순서 동형이라면, 그 둘이 같은 순서형을 가진다고 말합니다. 비형식적으로는, 서수는 정렬 집합의 순서형을 말합니다. 다음 글에서는 이러한 서수의 형식적인 정의를 보게 될 것입니다. 서수의 개념을 이용하여 수학적 귀납법의 확장인 초한 귀납법을 형식화할 수 있으며, 이 외에도 다양한 부분에서 서수의 개념을 이용할 수 있습니다. 또한, 늘 그렇듯이, 읽어주셔서 감사합니다.[/lang-ko]

 

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