[암호학] 5. 집합론 2

Countable vs Uncountable

위 용어를 의미로 해석하면 "셀 수 있는"과 "셀 수 없는"이다.

셀 수 있다는 의미로 접근하면 Countable Set은 유한집합을 의미할 것 같다.

하지만 유한집합은 Finite Set이라는 용어가 있고 이는 Countable Set과 구분되고 심지어 위 두 용어는 모두 무한집합(Infinite Set)에서 정의한다.

Countable Set은 자연수집합과 대응되는 집합이다.

자연수가 개수를 세는데 사용되니 이런 의미를 가지게 된 것 같다.

앞에서 보였듯이 $|\mathbb{N}|=|\mathbb{Z}|=|\mathbb{Q}|$이므로 $\mathbb{N},\mathbb{Z},\mathbb{Q}$는 모두 Countable Set이 된다.

반면 $\mathbb{R}$은 Uncountable이 된다.

 

Power Set

Power Set이란 어떤 집합의 모든 부분집합을 원소로 하는 집합이다.

예를 들면 $A = \{1,2\}$이 있을 때 $A$의 Power Set을 $2^A$로 나타내고 $2^A = \{\varnothing,\{1\},\{2\},\{1,2\} \}$가 된다.

어떤 집합 $A$의 부분집합의 개수는 $2^{|A|}$개이기 때문에 위와 같은 표기를 사용하는 것 같다.

 

Theorem) 모든 집합 $X$에서 $|X| \neq |2^X|$이다.

proof

$X = \varnothing$인 경우 $|X| = 0$, $|2^X| = 1$이므로 참이다.

$|X| = |2^X|$라는 것은 두 집합 사이에 일대일 대응이 존재한다라는 것이다.

그러한 대응을 $f$라고 하자.

$a \in X \rightarrow f(a) \in 2^X$이고 $f(a) \subset X$가 된다. ($2^X$의 원소는 $X$의 부분집합이기 때문)

새로운 집합 $P = \{a|a \in X, a \notin f(a) \}$에서 $b \in X, f(b) = P$인 $b$가 존재하는지 알아보자.

즉 $P$는 $X$의 부분집합이지만 $a$라는 원소가 $f(a)$에 없는 원소들을 모은 집합이다.

이러한 $P$가 존재함을 보이면 일대일 대응이 존재함을 보인 것이다.

 

case 1) $b \in P$

그러면 가정에 의해 $b \in f(b)$가 된다.

하지만 $P$집합의 정의에 의해 $b \notin P$가 된다. ($P$집합은 $b \notin f(b)$만 원소로 가짐)

 

case 2) $b \notin P$

그러면 가정에 의해 $b \notin f(b)$가 되고 $P$집합의 정의에 의해 $b \in P$가 된다.

 

모든 case에서 모순을 보이므로 그런 집합 $P$는 존재하지 않는다. $\Box$

 

$|\mathbb{R}| = |2^{\mathbb{N}}|$

또 다시 $|\mathbb{R_{01}}|$와 $|2^{\mathbb{N}}|$과 비교해보자.

그런데 이번엔 특별히 실수집합을 이진수로 바라볼 것이다.

예를들면 $0.0101001, 0.101001000...$같이 표현할 것이다.

그럼 비트마스킹을 하는 것처럼 자연수 $i$를실수에서 소숫점 아래 $i$번째 자리가 $1$이면 집합에 포함시키고 $0$이면 포함시키지 않으면 $\mathbb{N}$의 모든 부분집합을 만들 수 있다.

따라서 $|\mathbb{R_{01}}| = |2^{\mathbb{N}}|$가 되고 $2^{\mathbb{N}}$는 Uncountable Set임을 알 수 있다.

 

또한 Countable Set의 Power Set은 Uncountable Set이다.

 

정리

집합론을 가볍게 살펴본 것 같은데 간략하게 요약하면 아래와 같다.

$|A| < |\mathbb{N}| = |\mathbb{Z}| = |\mathbb{Q}| < |\mathbb{R}| = |2^{\mathbb{N}}| < |2^{\mathbb{R}}| < ...$

여기서 $A$는 Finite Set

$|\mathbb{N}| < |\mathbb{R}|$사이에 존재하는 집합이 있는지는 밝혀지지 않았다고 한다.

없다고는 예상하지만 그런 증명이 없다고 한다.

이를 Continuum Hypothesis라고 한다.