[ZFC Set Theory] Appendix A. 공리적 집합론 Axiomatic Set Theory

[lang-en]This post deals with random things related with axiomatic set theory, which were not covered in the series posts. One day, this post might be quite long. No one knows for sure. :-)$\renewcommand{\emptyset}{\varnothing}$[/lang-en]

[lang-ko]이 포스트는 공리적 집합론과 관련이 있으나 시리즈 글들에서 다루지 못한 내용들을 다루는 글입니다. 언젠가는 글이 상당히 길어질지도 모르죠. 확실한 건 아무도 모릅니다. :-)$\renewcommand{\emptyset}{\varnothing}$[/lang-ko]

i. [lang-ko]시리즈 글들[/lang-ko][lang-en]List of Series Posts[/lang-en]

• Introduction
• I. 집합의 연산 Operations On Sets
• II. 집합 $X \in X$의 비존재성 Nonexistence of A Set $X \in X$
• III. 튜플과 곱집합 Tuples and Cartesian Products
• IV. 이항 관계와 함수 Binary Relations & Functions
• V. 동치 관계와 동치류 Equivalence Relations & Equivalence Classes

ii. [lang-ko]목차[/lang-ko][lang-en]Table of Contents[/lang-en]

i. [lang-ko]시리즈 글들[/lang-ko][lang-en]List of Series Posts[/lang-en]

ii. [lang-ko]목차[/lang-ko][lang-en]Table of Contents[/lang-en]

1. [lang-ko]타르스키 유한[/lang-ko][lang-en]Tarski-Finite[/lang-en]

• Definition 1.1.
• Lemma 1.2.
• Proposition 1.3.
• Theorem 1.4.

2. [lang-ko]짝 공리[/lang-ko][lang-en]Axiom of Pairing[/lang-en]

• Theorem 2.1.

1. [lang-ko]타르스키 유한[/lang-ko][lang-en]Tarski-Finite[/lang-en]

[lang-en]The concept of finiteness is very important in set theory. As a rule, in set theory, the finiteness is defined using the concept of natural numbers. However, cannot we define the finiteness without the concept of natural numbers? The answer is.. YES! We can define the finiteness without natural numbers! Alfred Tarski(1901-1983), the Polish-American mathematician, introduced the concept of Tarski-finiteness. Look at the below:[/lang-en]

[lang-ko]유한의 개념은 집합론에서 매우 중요합니다. 일반적으로, 집합론에서는 유한성의 개념을 자연수를 이용하여 정의합니다. 하지만, 자연수의 개념을 사용하지 않고 유한성을 정의할 수는 없을까요? 이에 대한 대답은 "가능하다"입니다. 폴란드계 미국인 수학자인 알프레드 타르스키 (Alfred Tarski, 1901-1983)는 타르스키-유한이라는 개념을 도입하여 자연수의 개념 없이 유한성을 정의하였습니다. 아래는 그에 대한 내용을 담고 있습니다.[/lang-ko]

 

[def]{1.1.}[lang-en]A set $S$ is said to be $Tarski$-$finite$ if every nonempty $X \subset \href{https://susiljob.tistory.com/62}{\mathscr{P}(S)}$ has a $\subset$-maximal element, i.e., $u \in X$ such that there is no $v \in X$ with $u \subset v$ and $u \neq v$. $S$ is said to be $Tarski$-$infinite$ if it is not Tarski-finite.[/lang-en][lang-ko]모든 비어있지 않은 $X \subset \href{https://susiljob.tistory.com/62}{\mathscr{P}(S)}$가 $\subset$-극대 원소를 가진다면, 즉 $u \subset v$이면서 $u \neq v$인 $v \in X$가 존재하지 않는 $u \in X$가 존재한다면, 그러한 $S$를 타르스키 유한 집합이라고 한다. 또한, 타르스키 유한이 아닌 집합을 타르스키 무한 집합이라고 한다.[/lang-ko][/def]

 

[lem]{1.2.}[lang-en]Each $n \in \NN$ is Tarski-finite.[/lang-en][lang-ko]각 $n \in \NN$은 타르스키 유한이다.[/lang-ko][/lem]

 

Proof.

[lang-en]First, since $\mathscr{P}(0) = \{ \varnothing \}$, there is only one nonempty subset of $\mathscr{P}(0)$, namely, $\{ \varnothing \}$. Also, it is quite obvious that $\emptyset$ is a $\subset$-maximal element of $\{ \varnothing \}$. Hence, $0$ is Tarski-finite.[/lang-en]

[lang-ko]가장 먼저, $\mathscr{P}(0) = \{ \varnothing \}$이므로 $\mathscr{P}(0)$의 비어있지 않은 부분집합은 $\{ \varnothing \}$이 유일합니다. 따라서 $\emptyset$이 $\{ \varnothing \}$의 $\subset$-극대 원소임은 매우 명확합니다.[/lang-ko]

[lang-en]Now, let $n \in \NN$ be Tarski-finite and consider a nonempty $X \subset \mathscr{P}(n+1)$. Then, we can define $X' = \{ x \in X \mid n \notin x \}$ and this is a set by the axiom schema of specification. If $X'$ is nonempty, then we can take a $\subset$-maximal element $Y$ in $X'$ by the induction hypothesis. If $Y \cup \{ n \} \in X$, $Y \cup \{ n \}$ is a $\subset$-maximal element in $X$, obviously. If $Y \cup \{ n \} \notin X$, then $Y$ itself is a $\subset$-maximal element in $X$, clearly.[/lang-en]

[lang-ko]이제 $n \in \NN$이 타르스키 유한이라고 가정한 후, 비어있지 않은 $X \subset \mathscr{P}(n+1)$을 생각합시다. 그러면 모임 $X' = \{ x \in X \mid n \notin x \}$을 고려할 수 있으며, 이는 분류 공리꼴에 의해 집합임이 보장됩니다. 만약 $X'$이 공집합이 아니라면, 귀납 가정에 의해 $X'$의 $\subset$-극대 원소 $Y$를 잡을 수 있습니다. 만일 $Y \cup \{ n \} \in X$라면 $Y \cup \{ n \}$은 $X$의 $\subset$-극대 원소가 될 것입니다. 만일 $Y \cup \{ n \} \notin X$라면, $Y$ 자체로도 $X$의 $\subset$-극대 원소가 될 것입니다.[/lang-ko]

[lang-en]If $X'$ is empty, then we can take a set $X'' = \{ x \setminus \{ n \} \mid x \in X \}$. Then, obviously, $X'' \subset \mathscr{P}(n)$ and $X''$ is nonempty. Since $n$ is Tarski-finite, $X''$ has a $\subset$-maximal element $Y''$. Hence, $X$ has a $\subset$-maximal element $Y'' \cup \{ n \}$ and thus $n+1$ is also Tarski-finite.[/lang-en]

[lang-ko]만약 $X'$이 공집합이라면, 새로운 집합 $X'' = \{ x \setminus \{ n \} \mid x \in X \}$을 고려할 수 있을 것입니다. 그러면, $X'' \subset \mathscr{P}(n)$이고 $X''$이 비어있지 않으므로 귀납 가정에 의해 $X''$은 $\subset$-극대 원소 $Y''$을 가집니다. 따라서 $X$는 $\subset$-극대 원소 $Y'' \cup \{ n \}$을 가지며, 따라서 $n+1$ 역시 타르스키 유한입니다.[/lang-ko]

[lang-en]Therefore, by the principle of mathematical induction (Theorem VIII.1), every $n \in \NN$ is Tarski-finite.[/lang-en]

[lang-ko]따라서, 수학적 귀납법 (Theorem VIII.1)에 의해 임의의 $n \in \NN$은 타르스키 유한입니다.[/lang-ko]

$\blacksquare$

 

[prop]{1.3.}[lang-en]$\NN$ is Tarski-infinite.[/lang-en][lang-ko]$\NN$은 타르스키 무한이다.[/lang-ko][/prop]

 

Proof.

[lang-en]By the definition of $\NN$ (Definition VII.4), $\NN \in \mathscr{P}(\NN)$. Now let $n \in \NN$. Then, $n \cup \{ n \} \in \NN$ and thus $n$ is not a $\subset$-maximal element of $\NN$. Therefore, $\NN$ has no $\subset$-maximal element and, hence, $\NN$ is Tarski-infinite.[/lang-en]

[lang-ko]$\NN$의 정의 (Definition VII.4)에 의해 $\NN \in \mathscr{P}(\NN)$입니다. 이제 아무 자연수 $n \in \NN$을 생각합시다. 그러면 $n \cup \{ n \} \in \NN$이므로 $n$은 $\NN$의 $\subset$-극대 원소가 될 수 없습니다. 따라서 $\NN$은 $\subset$-극대 원소를 가지지 않으며, $\NN$이 타르스키 무한임이 증명됩니다.[/lang-ko]

$\blacksquare$

 

[thm]{1.4.}[lang-en]A set $X$ is infinite if and only if $X$ is Tarski-infinite.[/lang-en][lang-ko]집합 $X$가 무한 집합인 것과 $X$가 타르스키 무한인 것은 필요충분조건이다.[/lang-ko][/thm]

 

Proof.

[lang-en]We shall show the forward one, first. Let $X$ be an infinite set and consider the set $S = \{ u \subset X \mid u \text{ is finite} \}$. If there is a $\subset$-maximal element $u$ of $S$, then by the definition of $S$, $u$ is finite and thus $X \setminus u$ is nonempty. Hence, we can consider a set $u \cup \{ x \}$ for some $x \in X \setminus u$. Since $u$ is finite, $u \cup \{ x \}$ is also finite and this contradicts the maximality of $u$. Hence, there is no $\subset$-maximal element of $S$, and therefore $X$ is Tarski-infinite.[/lang-en]

[lang-en]Now aim for the proof of the backward one. Since the direct proof can be quite difficult, we shall prove the contrapositive. Suppose that $X$ is a finite set. Then, there is a natural number $n \in \NN$ such that there exists a bijection $f : n \to X$. Now consider a nonempty $S \subset \mathscr{P}(X)$. Then, since $f$ is bijective, there exists nonempty $T \subset \mathscr{P}(n)$ such that $S = \{ f(t) \mid t \in T \}$. By Lemma 1.2, $n$ is Tarski-finite so there exists a $\subset$-maximal element of $T$ and this means that there is a $\subset$-maximal element of $S$ since $f$ is bijective. Therefore, by the arbitrariness of the choice of $S$, $X$ is Tarski-finite.[/lang-en]

[lang-ko]먼저, 집합 $X$가 무한 집합이면 $X$가 타르스키 무한임을 보이겠습니다. 집합 $X$가 무한 집합이라 하고, 집합 $S = \{ u \subset X \mid u \text{는 유한 집합} \}$을 생각합시다. 만일 $S$의 $\subset$-극대 원소 $u$가 존재한다면, $S$의 정의에 의해 $u$는 유한 집합이 될 것이며, 따라서 $X \setminus u$는 비어있지 않게 됩니다. 따라서 어떤 $x \in X \setminus u$에 대하여 집합 $u \cup \{ x \}$를 생각할 수 있으며, $u$가 유한이므로 $u \cup \{ x \}$ 역시 유한이 되어 $u$의 극대성에 모순입니다. 따라서, $S$는 $\subset$-극대 원소를 가지지 않으며, $X$가 타르스키 무한임을 알 수 있습니다.[/lang-ko]

[lang-ko]이제 집합 $X$가 타르스키 무한이면 $X$가 무한 집합임을 보입시다. 이 명제를 직접 증명하는 것은 까다로울 수 있으므로, 그 대우명제를 증명하도록 하겠습니다. 집합 $X$가 유한이라고 합시다. 그러면, 전단사 함수 $f : n \to X$가 존재하도록 하는 자연수 $n \in \NN$이 존재합니다. 이제 비어있지 않은 $S \subset \mathscr{P}(X)$를 고려하면, $f$가 전단사 함수라는 것으로부터, $S = \{ f(t) \mid t \in T \}$를 만족하는 비어있지 않은 $T \subset \mathscr{P}(n)$이 존재함을 알 수 있습니다. Lemma 1.2에 의해 $n$이 타르스키 유한이므로, $T$는 $\subset$-극대 원소를 가집니다. 따라서, $f$가 전단사 함수라는 사실은 곧 $S$ 역시 $\subset$-극대 원소를 가짐을 함의합니다. $S$의 선택이 임의적이었으므로, $X$가 타르스키 유한임을 알 수 있으며, 정리가 증명됩니다.[/lang-ko]

$\blacksquare$

2. [lang-ko]짝 공리[/lang-ko][lang-en]Axiom of Pairing[/lang-en]

[lang-en]Several axioms of the ZFC set theory are not independent of each other. The axiom of pairing is one such example. The axiom of pairing can be derived from the axiom of power, the axiom schema of specification, and the axiom schema of replacement through the following process:[/lang-en]

[lang-ko]ZFC 집합론의 몇몇 공리들은 서로 독립적이지 않습니다. 짝 공리는 그러한 예시 중 하나입니다. 짝 공리는 멱집합 공리, 분류 공리꼴, 치환 공리꼴로부터 다음과 같은 과정을 통해 유도될 수 있습니다.[/lang-ko]

 

[thm]{2.1.}[lang-en]Let $\mathrm T \supseteq \mathrm{Power} + \mathrm{Spec} + \mathrm{Replace}$ be a theory, where $\mathrm{Power}$, $\mathrm{Spec}$, and $\mathrm{Replace}$ denote the axiom of power, the axiom schema of specification, and the axiom schema of replacement, respectively. Then, $\mathrm T \vdash \mathrm{Pair}$, where $\mathrm{Pair}$ denotes the axiom of pairing.[/lang-en][lang-ko]이론 $T$가 이론 $\mathrm{Power} + \mathrm{Spec} + \mathrm{Replace}$를 포함한다고 하자. 그러면 $\mathrm T \vdash \mathrm{Pair}$가 성립한다. 여기서 $\mathrm{Power}$, $\mathrm{Spec}$, $\mathrm{Replace}$, $\mathrm{Pair}$는 각각 멱집합 공리, 분류 공리꼴, 치환 공리꼴, 짝 공리를 나타낸다.[/lang-ko][/thm]

 

Proof.

[lang-en]Let $x$ and $y$ be sets. By the axiom schema of specification, there exists an empty set $\varnothing$. Also, by applying the axiom of power and then axiom schema of specification, we can obtaine a set $\left\{ \varnothing \right\}$. Applying the axiom of power again, we deduce that a set $\left\{ \varnothing, \left\{ \varnothing \right\} \right\}$ exists. Now, replacing $\varnothing$ and $\left\{ \varnothing \right\}$ to $x$ and $y$, respectively, we obtain a set $\left\{ x, y \right\}$ through the axiom schema of replacement. Therefore, the axiom of pair is proved.[/lang-en]

[lang-ko]$x$와 $y$가 집합이라고 합시다. 그러면 분류 공리꼴에 의해 공집합 $\varnothing$이 존재합니다. 또한, 멱집합 공리와 분류 공리꼴에 의해 집합 $\left\{ \varnothing \right\}$ 역시 존재하며, 이 집합에 같은 과정을 다시 적용하면 집합 $\left\{ \varnothing, \left\{ \varnothing \right\} \right\}$이 존재함을 알 수 있습니다. 이제 $\varnothing$과 $\left\{ \varnothing \right\}$을 각각 $x$와 $y$로 치환하면, 치환 공리꼴에 의해 집합 $\left\{ x, y \right\}$가 존재하며, 따라서 짝 공리가 증명됩니다.[/lang-ko]

$\blacksquare$

[lang-en]And always, thanks for reading.[/lang-en]

[lang-ko]언제나 그렇듯이, 읽어주셔서 감사합니다.[/lang-ko]