집합론, 그 아홉 번째 이야기 | 집합의 농도 ( Cardinality of Sets )

집합의 농도에 대해 이야기 하기에 앞서 유한집합과 무한집합에 대해 얘기하도록 하겠다. 우리는 보통 유한집합을 유한한 원소를 가지는 집합, 무한집합을 무한히 많은 원소를 가지는 집합이라고 생각하지만, 이렇게 말하면 무한히 많은 것이 무엇인지에 대한 질문에 제대로 된 답을 할 수 없게 된다. 따라서 우리는 무한집합을 먼저 정의할 것이다. 무한집합은 다음과 같이 정의한다.

 

집합 $X$와 $Y$ 사이의 전단사함수 $f:X\to Y$가 존재하도록 하는 집합 $X$의 진부분집합 $Y$가 존재할 때, $X$를 무한집합이라고 한다.

 

위의 정의를 통해 무한집합을 명확하게 정의할 수 있으며, 유한집합은 무한집합이 아닌 집합으로 정의한다.

 

만약 두 집합의 크기를 비교하고 싶다면 어떻게 해야 할까? 물론 유한집합이라면 그냥 원소의 개수를 세어본다면 될 것이다. 또한, 유한집합보다 무한집합이 더 크다고 생각하는 것은 자연스럽다. 그렇다면 두 무한집합의 크기는 어떻게 비교해야 할까? 다시 유한집합으로 돌아와서 생각해보자. 만약 두 유한집합의 크기가 같다면 두 집합 사이에는 전단사함수가 존재할 것임은 틀림없다. 이런 성질을 무한집합에서도 생각할 수 있음은 자연스러워 보인다. 따라서 두 집합의 크기를 비교하는 개념인 집합의 농도는 다음과 같이 정의한다.

 

1. 두 집합 $A$와 $B$가 주어졌을 때, 전단사함수 $f:A\to B$가 존재하면 $A$와 $B$의 농도가 같다고 하며 $|A|=|B|$와 같이 나타낸다. 2. 두 집합 $A$와 $B$가 주어졌을 때, 단사함수 $f:A\to B$가 존재하면 $A$의 농도는 $B$의 농도와 같거나 그보다 작다고 하며 $|A|\leq|B|$와 같이 나타낸다. 3. 두 집합 $A$와 $B$가 주어졌을 때, 두 집합 사이에 전단사함수는 존재하지 않지만 단사함수 $f:A\to B$가 존재한다면 $A$의 농도는 $B$의 농도보다 작다고 하며 $|A|<|B|$와 같이 나타낸다.

 

위의 정의로부터 두 집합 간의 크기를 비교할 때에는 전단사함수의 존재 여부를 통해 두 집합의 크기가 같음 또는 다름을 증명한다. 또한, 임의의 집합 $A$, $B$, $C$에 대해 다음이 성립한다.

 

1. 등호의 반사성 : 

$$|A|=|A|$$

이는 항등함수 $I:A\to A$를 잡음으로써 증명할 수 있다.

 

2. 등호의 대칭성 :

$$|A|=|B|\Rightarrow |B|=|A|$$

$|A|=|B|$이면 전단사함수 $f:A\to B$를 잡을 수 있으며, $f$가 전단사함수이므로 그의 역함수 $f^{-1}:B\to A$ 역시 전단사함수이다. 따라서 $|B|=|A|$가 성립한다.

 

3. 등호의 추이성 :

$$|A|=|B|\land|B|=|C|\Rightarrow|A|=|C|$$

$|A|=|B|\land|B|=|C|$로부터 두 전단사함수 $f:A\to B$와 $g:B\to C$를 잡을 수 있으며, 이 두 함수의 합성함수 $g\circ f:A\to C$도 전단사함수이므로 $|A|=|C|$가 성립한다.

 

4. 등호를 포함한 부등호의 반사성 :

$$|A|\leq|A|$$

$|A|=|A|$이므로 전단사함수 $f:A\to A$가 존재하며, 전단사함수는 단사함수이다. 따라서 $|A|\leq|A|$가 성립한다.

 

5. 칸토어-베른슈타인 정리 :

$$|A|\leq|B|\land|B|\leq|A|\Leftrightarrow|A|=|B|$$

이 명제에 대한 증명은 따로 포스팅하였다.

 

6. 등호를 포함한 부등호의 추이성 :

$$|A|\leq|B|\land|B|\leq|C|\Rightarrow|A|\leq|C|$$

$|A|\leq|B|\land|B|\leq|C|$이므로 두 단사함수 $f:A\to B$와 $g:B\to C$를 잡을 수 있으며, 두 함수의 합성함수인 $g\circ f:A\to C$ 역시 단사함수이므로 $|A|\leq|C|$이다.

 

7. 전사함수의 존재성 :

집합 $A$가 공집합이 아닐 때 다음이 성립한다.

$$\exists f:B\to A\;s.t.\;f(B)=A\Leftrightarrow|A|\leq|B|$$

 

Part 1. $\exists f:B\to A\;s.t.\;f(B)=A\Rightarrow|A|\leq|B|$

선택공리에 의해 $A$의 모든 원소 $a$에 대해 $f(b)=a$가 되도록 하는 $b\in B$를 하나씩 선택하는 함수 $g:A\to B$를 잡을 수 있으며, $f$가 함수라는 것에 의해 $g$가 단사함수임은 보장된다. 따라서 $|A|\leq|B|$이다.

 

Part 2. $|A|\leq|B|\Rightarrow\exists f:B\to A\;s.t.\;f(B)=A$

$|A|\leq|B|$이므로 단사함수 $g:A\to B$가 존재한다. 이때, 함수 $f:B\to A$를 고정된 $x\in A$에 대해 다음과 같이 정의하면 $f$가 전사함수가 된다.

$$f(b)=\begin{cases} a&\mbox{if }\exists a\in A\;s.t.\;g(a)=b\\x&\mbox{otherwise}\end{cases}$$

 

8. 부등호와 등호 그리고 등호를 포함한 부등호의 관계 :

$$|A|<|B|\lor|A|=|B|\Leftrightarrow|A|\leq|B|$$

 

Part 1. $|A|<|B|\lor|A|=|B|\Rightarrow|A|\leq|B|$

만약 $|A|<|B|$라면 단사함수 $f:A\to B$가 존재하므로 $|A|\leq|B|$이고, $|A|=|B|$라면 전단사함수 $g:A\to B$가 존재하는데, 전단사함수는 단사함수이므로 $|A|\leq|B|$이다. 따라서 $|A|<|B|\lor|A|=|B|\Rightarrow|A|\leq|B|$이다.

 

Part 2. $|A|\leq|B|\Rightarrow|A|<|B|\lor|A|=|B|$

만약 전단사함수 $f:A\to B$가 존재한다면 $|A|=|B|$이고, 그렇지 않다면 $|A|\leq|B|$로부터 단사함수 $g:A\to B$를 잡을 수 있다. 전단사함수가 존재하지 않으면서 $g$가 단사함수이므로 $|A|<|B|$이다. 따라서 $|A|\leq|B|\Rightarrow|A|<|B|\lor|A|=|B|$이다.

 

9. 삼분성 : 무조건 다음 세 가지 조건 중 한 가지만을 만족한다.

$$|A|<|B|, |A|=|B|, |A|>|B|$$