[ZFC Set Theory] III. 튜플과 곱집합 Tuples and Cartesian Products

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

 

[lang-en]By axiom of extensionality, $\{ x , y \}$ and $\{ y , x \}$ are the same sets. But commonly, we often consider an ordered pair, and we need the concept of ordered pair to describe more things. Hence, we should define ordered pair, but how can we do that? First of all, let's think about properties that ordered pairs have to have. Intuitively, an ordered pair $\left< a , b \right>$ and an ordered pair $\left< c , d \right>$ are equal if and only if $a = c$ and $b = d$, isn't it? So, we aim to make ordered pairs satisfy this property. To achieve this, we define an ordered pair $\left< x , y \right>$ as follows:[/lang-en]

[lang-ko]외연 공리에 의해 집합 $\{ x,y \}$와 집합 $\{ y,x \}$가 같은 집합임을 알 수 있습니다. 하지만 일반적으로 우리는 순서쌍을 고려하곤 하며, 더 다양한 논의를 위해 순서쌍의 개념이 필요합니다. 따라서 우리는 순서쌍의 개념을 정의할 필요가 있습니다. 그러나, 순서쌍을 어떻게 정의할 수 있을까요? 가장 먼저, 우리가 정의하려는 순서쌍이 꼭 가져야만 하는 성질들에 대해 생각해봅시다. 직관적으로, 순서쌍 $\left< a,b \right>$와 순서쌍 $\left< c,d \right>$가 같은 것은 $a=c$이고 $b=d$인 것과 동치명제여야 할 것입니다. 그러므로, 우리는 순서쌍이 이러한 성질을 만족할 수 있도록 하는 것을 목표로 하여 순서쌍을 정의할 것입니다. 이 목표를 완수하기 위해, 우리는 순서쌍을 다음과 같이 정의합니다.[/lang-ko]

 

[def]{1.}[lang-en]Let $x$ and $y$ be sets. Then we define an $ordered \; pair$ $\left< x , y \right>$ as a set as follows:[/lang-en][lang-ko]$x$와 $y$가 집합이라고 하자. 그러면 집합으로서의 순서쌍 $\left< x,y \right>$는 다음과 같이 정의된다.[/lang-ko] $$ \left< x , y \right> := \{ \{ x \} , \{ x , y \} \} $$[/def]

 

[lang-en]Now, we have to check whether the ordered pairs defined above satisfy the desired property. Look at Theorem 2.[/lang-en]

[lang-ko]이제, 우리는 위와 같이 정의된 순서쌍이 우리가 처음에 의도한 성질을 만족하는지 확인할 필요가 있습니다. 아래의 Theorem 2.를 봅시다.[/lang-ko]

 

[thm]{2.}[lang-en]For any four sets $a$, $b$, $c$, and $d$, $\left< a , b \right> = \left< c , d \right>$ if and only if $a = c \land b = d$.[/lang-en][lang-ko]임의의 네 집합 $a$, $b$, $c$, $d$에 대하여, $\left< a,b \right> = \left< c,d \right>$인 것은 $a=c \land b=d$인 것과 필요충분조건이다.[/lang-ko][/thm]

 

Proof.

[lang-en]The if part is very obvious so it suffices to show only the only if part. To prove the only if part, consider two cases. If $a = b$, then $\left< a , b \right> = \{ \{ a \} , \{ a , a \} \}$, which means $\left< a , b \right> = \{ \{ a \} \}$. This can be easily shown by axiom of extensionality. Thus, $\left< a , b \right> = \left< c , d \right>$ implies that $\{ \{ c \} , \{ c , d \} \} = \{ \{ a \} \}$. Hence, it has to be $\{ c \} = \{ a \}$ and $\{ c , d \} = \{ a \}$ and this is an evidence for the fact that $c = a$ and $d = a$. Thus, $a = c$ and $b = a = d$ if $a = b$. Now, consider a case $a \neq b$. If $a \neq b$, then $\{ \{ a \} , \{ a , b \} \} = \{ \{ c \} , \{ c , d \} \}$. By axiom of extensionality, $\{ a \}$ must be equal to $\{ c \}$ or $\{ c, d \}$. If $\{ a \}$ is the same set with $\{ c , d \}$, then it has to be $c = a$ and $d = a$ by axiom of extensionality. And this means that $\left< c , d \right> = \{ \{ c \} \}$ and thus $\{ a, b \} = \{ c \}$, which implies that $b = c = a$ and induces a contradiction. Hence, $\{ a \} \neq \{ c , d \}$ and this forces that $\{ a \} = \{ c \}$. Consequently, $a = c$ by axiom of extenstionality, and this concludes $\{ a , b \} = \{ c , d \}$. The fact that $a = c$ forces that $b = d$ since $\{ a , b \} = \{ c , d \}$. Therefore, $a = c$ and $b = d$ in the case of $a \neq b$ and, hece, $\left< a , b \right> = \left< c , d \right>$ only if $a = c \land b = d$.[/lang-en]

[lang-ko]먼저, $a=c \land b=d$가 $\left< a,b \right> = \left< c,d \right>$를 함의함은 매우 당연하므로 그 역만 보이면 충분합니다. 이를 증명하기 위해 두 가지 경우로 쪼개어 생각해봅시다. 만약 $a=b$라면, $\left< a,b \right> = \{ \{ a \} , \{ a , a \} \}$이며, 이는 곧 $\left< a,b \right> = \{ \{ a \} \}$임을 의미합니다. 이는 외연 공리를 통해 쉽게 보일 수 있습니다. 그러므로, $\left< a,b \right> = \left< c,d \right>$인 것은 $\{ \{ c \} , \{ c , d \} \} = \{ \{ a \} \}$임을 함의합니다. 따라서, 외연 공리를 통해 $\{ c \} = \{ a \}$이면서 동시에 $\{ c , d \} = \{ a \}$이어야만 한다는 것을 알 수 있습니다. 이때, $\{ c , d \} = \{ a \}$인 것은 $a = c = d$를 함의하므로, $a=c \land b=d$임을 알 수 있습니다. 이제 $a \neq b$인 경우를 살펴봅시다. 이 경우, $\{ \{ a \} , \{ a , b \} \} = \{ \{ c \} , \{ c , d \} \}$임을 알 수 있습니다. 이때, 외연 공리에 의해, $\{ a \}$는 $\{ c \}$나 $\{ c , d \}$ 둘 중 하나와 같은 집합이어야만 합니다. 만약 $\{ a \} = \{ c , d \}$라면, 외연 공리에 의해 $a = c$이면서 동시에 $a = d$여야만 하며, $a=b$인 경우와 같은 방식의 논의를 통해 $a = b = c = d$를 얻을 수 있고, 이는 $a \neq b$라는 가정에 모순임을 알 수 있습니다. 따라서 $\{ a \} \neq \{ c , d \}$임을 알 수 있으며, 이는 $\{ a \} = \{ c \}$임을 의미합니다. 따라서 외연 공리를 통해 $a = c$임을 알 수 있으며, 동시에 $\{ a , b \} = \{ c , d \}$임을 알 수 있습니다. 이제 기계적인 과정을 통해 $b = d$임을 얻을 수 있으므로, 이 경우 역시 $a = c \land b = d$임을 알 수 있습니다. 따라서, $a = b$인 경우와 $a \neq b$인 경우 모두 $\left< a , b \right> = \left< c , d \right>$가 $a = c \land b = d$를 함의한다는 사실을 알 수 있으며, 이는 곧 정리를 증명합니다.[/lang-ko]

$\blacksquare$

[lang-en]By Theorem 2., we have a definition of ordered pair which satisfies the desired property. Then, can we extract each component in an ordered pair? In other words, can we represent $x$ and $y$ in terms of $\left< x , y \right>$? To answer this, we define two operators as follows:[/lang-en]

[lang-ko]Theorem 2. 덕분에 우리는 처음에 목표로 한 성질을 가지는 순서쌍의 정의를 얻었음을 알 수 있습니다. 이제, 순서쌍으로부터 각 성분을 뽑아낼 수 있을까요? 다시 말해서, 집합 $x$와 $y$를 각각 순서쌍 $\left< x , y \right>$에 대한 식으로 나타낼 수 있을까요? 이에 대해 답하기 위해 다음과 같은 두 연산을 정의합니다.[/lang-ko]

 

[def]{3.}[lang-en]Let a set $P$ be an ordered pair of two sets. Then we define a set $\operatorname{first} P$ and a set $\operatorname{second} P$ as follows:[/lang-en][lang-ko]$P$를 두 집합의 순서쌍이라고 하자. 그러면 우리는 두 집합 $\operatorname{first} P$와 $\operatorname{second} P$를 다음과 같이 정의한다.[/lang-ko] $$ \operatorname{first} P = \bigcup \bigcap P $$ $$ \operatorname{second} P = \begin{cases} \bigcup \bigcap P & \mbox{if } \left( \bigcup P \right) \setminus \left( \bigcap P \right) = \varnothing \\ \bigcup \left( \left( \bigcup P \right) \setminus \left( \bigcap P \right) \right) & \mbox{otherwise} \end{cases} $$[/def]

 

[lang-en]It is easily calculated that $P = \left< \operatorname{first} P , \operatorname{second} P \right>$ for any ordered pairs $P$.[/lang-en]

[lang-ko]$P = \left< \operatorname{first} P , \operatorname{second} P \right>$가 성립함은 간단한 계산으로 보일 수 있으므로 이는 독자에게 맡기겠습니다.[/lang-ko]

 

[lang-en]Now then we have the definition of ordered pairs, we are ready to define a tuple, which is a finite ordered list. As in the case of ordered pairs, $n$-tuples $\left( a_1, a_2, \cdots, a_n \right)$ and $\left( b_1, b_2, \cdots, b_n \right)$ are equal if and only if the corresponding components are the same. In other words, $\left( a_1, a_2, \cdots, a_n \right) = \left( b_1, b_2, \cdots, b_n \right)$ if and only if $a_i = b_i$ for $i = 1 , 2 , \cdots , n$. To keep this property, we define $n$-tuple as follows:[/lang-en]

[lang-ko]이제 순서쌍을 정의하였으니, 순서가 부여된 유한한 수의 집합의 나열인, 튜플을 정의하기 위한 준비가 끝났다고 할 수 있습니다. 순서쌍의 경우와 같이, $n$-튜플 $\left( a_1, a_2, \cdots, a_n \right)$와 $\left( b_1, b_2, \cdots, b_n \right)$가 같은 것은 같은 위치의 성분들이 각각 같은 것과 필요충분조건이 되어야 할 것입니다. 다른 말로 하면, $\left( a_1, a_2, \cdots, a_n \right) = \left( b_1, b_2, \cdots, b_n \right)$인 것과 $i = 1,2,\cdots,n$에 대하여 $a_i = b_i$가 성립하는 것이 동치조건이 되어야 할 것입니다. 이 성질을 그대로 유지하기 위해, 우리는 $n$-튜플을 다음과 같이 정의합니다.[/lang-ko]

 

[def]{4.}[lang-en]Let $a_1$, $a_2$, $\cdots$, $a_n$ be $n$ sets. Then we define an $n$-$tuple$ $\left( a_1, a_2, \cdots, a_n \right)$ as a set satisfying the following property:[/lang-en][lang-ko]$a_1$, $a_2$, $\cdots$, $a_n$이 $n$개의 집합이라고 하자. 그러면 $n$-튜플 $\left( a_1, a_2, \cdots, a_n \right)$는 다음과 같이 정의된다.[/lang-ko] $$ \begin{array}{c} \left( \right) := \varnothing \\ \left( a_1, a_2, \cdots, a_n \right) := \left< a_1, \left( a_2, \cdots, a_n \right) \right> \end{array} $$ [/def]

 

[lang-en]Now, we have to check whether the tuples defined above satisfy the desired property. Look at Theorem 5.[/lang-en]

[lang-ko]이제 위와 같이 정의된 튜플이 우리가 원했던 그 성질을 만족하는지 확인해야 합니다. Theorem 5.를 봅시다.[/lang-ko]

 

[thm]{5.}[lang-en]Let $a_1, a_2, \cdots, a_n, b_1, b_2, \cdots, b_n$ be sets. Then the $n$-tuples $\left( a_1, a_2, \cdots, a_n \right)$ and $\left( b_1, b_2, \cdots, b_n \right)$ are equal if and only if $a_i = b_i$ for $i = 1 , 2 , \cdots, n$.[/lang-en][lang-ko]$a_1, a_2, \cdots, a_n, b_1, b_2, \cdots, b_n$이 모두 집합이라고 하자. 그러면 $n$-튜플 $\left( a_1, a_2, \cdots, a_n \right)$와 $\left( b_1, b_2, \cdots, b_n \right)$가 같은 것은 각 $i = 1,2,\cdots,n$에 대하여 $a_i = b_i$인 것과 동치이다.[/lang-ko][/thm]

 

Proof.

[lang-en]If $n=0$, then the theorem holds vacuously. Now assume that the theorem holds if $n=k$. Then, by Theorem 2., and by Definition 1., it also holds when $n=k+1$. Therefore, by the mathematical induction, the thoerem holds for any natural numbers $n$.[/lang-en]

[lang-ko]만약 $n=0$이라면, 정리는 공허하게 참입니다. 이제 정리가 $n=k$에 대해 성립한다고 가정합시다. 그러면, Theorem 2.와 Definition 1.에 의해, 정리가 $n=k+1$에 대해서도 성립함을 알 수 있습니다. 따라서, 수학적 귀납법에 의해, 임의의 자연수 $n$에 대하여 정리가 성립함을 알 수 있습니다.[/lang-ko]

$\blacksquare$

 

[lang-en]Now then, we can consider a set containing the tuples defined above. We call the set of the $n$-tuples the Cartesian product. Formally, it is defined as follows:[/lang-en]

[lang-ko]그럼 이제, 우리는 위와 같이 정의된 튜플들의 집합을 고려할 수 있습니다. 이러한 집합을 우리는 데카르트 곱이라고 부릅니다. 형식적으로는, 이는 다음과 같이 정의됩니다.[/lang-ko]

 

[def]{6.}[lang-en]Let $A_1, A_2, \cdots, A_n$ be $n$ sets. Then the $Cartesian \; product$ of these sets is defined as:[/lang-en][lang-ko]$A_1, A_2, \cdots, A_n$을 $n$개의 집합이라고 하자. 그러면 이 집합들의 데카르트 곱은 다음과 같이 정의된다.[/lang-ko] $$ \prod_{i=1}^{n} A_i = A_1 \times A_2 \times \cdots \times A_n := \{ \left( a_1, a_2, \cdots, a_n \right) \mid a_i \in A_i ; i = 1,2,\cdots,n \} $$[/def]

 

[lang-en]In this post, we do not consider infinite Cartesian products because we do not prepare to consider infinite Cartesian products—in more detail, we need the concept of set-functions to consider an infinite Cartesian product but set-functions are not defined in this series, [ZFC Set Theory]. And always, thanks for reading.[/lang-en]

[lang-ko]이번 글에서는 무한 개의 집합의 데카르트 곱을 고려하지 않을 것입니다. 왜냐하면, 이에 대한 논의를 하기 위해서는 함수의 개념이 도입되어야 하는데, 아직 [ZFC Set Theory] 시리즈에서는 이를 정의하지 않았기 때문입니다. 늘 그렇듯이, 읽어주셔서 감사합니다.[/lang-ko]

 

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