[암호학] 4. 집합론 1

원소의 개수를 세자

어떤 집합의 원소의 개수를 Cardinality라고 하고 기호는 $|A|$로 나타낸다. (앞으로 크기라고도 표현할 것이다.)

Cardinality에 관해 두가지 성질이 있다.

• $|A| < |B| < |C|$ 이면 $|A| < |C|$이다.
• $|A| = |A|$이다.

당연해보이지만 일단 짚고 넘어가자.

 

유한집합에서 Cardinality는 그냥 원소의 개수를 세면 되기 때문에 생각하기 쉽다.

하지만 집합이 무한집합이라면 어떨까?

일반적으로 생각하기 힘들다.

 

자연수 집합 $\mathbb{N}$이 있다.

$\mathbb{N}$는 무한함이 자명하다.

자연수에 0을 추가해 새로운 집합 $\mathbb{N}^+ = \mathbb{N}  \cup \{0\} $을 정의하자. (범자연수 집합이 된다.)

$|\mathbb{N}| + 1 = |\mathbb{N}^+|$라고 할 수 있나?

그럴 수 없다.

무한한 크기에 연산을 한다는 것이 안되기 때문이다.

그래서 무한집합에서의 Cardinality를 다르게 정의한다.

무한집합 $A, B$ 에서 $|A|=|B|$가 성립하려면 $A, B$ 사이에 일대일 대응이 존재해야 한다.

$n \in \mathbb{N}$에서 $n-1$이라는 함수를 생각하면 $\mathbb{N}^+$가 된다.

이렇게 일대일 대응이 있기 때문에 두 집합의 Cardinality는 같다.

무한개념이기 때문에 직관적으로 이해는 힘들 수 있지만 정의를 따라가자.

 

그럼 정수와 자연수는?

정수에 번호를 붙이는 식으로 접근하자.

$1 \rightarrow 0$

$n \rightarrow (-1)^n \lfloor\frac{n}{2}\rfloor$

으로 정의하면 일대일 대응이 된다.

그래서 정수집합과 자연수집합의 Cardinality는 같다.

즉 $|\mathbb{N}| = |\mathbb{Z}|$

 

설마 자연수와 유리수도?

정수와 자연수의 크기가 같아졌으니 자연수와 유리수의 크기가 같아지면 정수와 유리수의 크기도 같아지는 것이다.

유리수는 서로소인 두 자연수 $p, q$가 있을 때 $\frac{p}{q}$로 표현할 수 있다.

즉 자연수 쌍으로 나타낼 수 있다.

정확하진 않지만 $\mathbb{Q} = \mathbb{N} \times \mathbb{N}$으로 나타낼 수 있다. (여기서 $\times$는 Cartesian Product)

유리수집합도 번호를 붙이자.

$1 \rightarrow 0$

$2 \rightarrow \frac{1}{1}$

$3 \rightarrow \frac{2}{1}$

$4 \rightarrow \frac{1}{2}$

...

이런식으로 매기다보면 또 번호가 다 매겨진다. (음수도 적절히 섞어가며 매긴다.)

결국 $|\mathbb{N}| = |\mathbb{Z}| = |\mathbb{Q}|$까지 성립한다.

 

그렇다면 실수도?

안타깝게도 $|\mathbb{N}| \neq |\mathbb{R}|$이다.

여기에 유명한 증명이 있다.

 

Cantor's proof

귀류법을 사용한다.

실수를 축소해 0~1범위만 존재하는 $\mathbb{R}_{01}$이 있다고 하자.

$\mathbb{N}$와 $\mathbb{R}_{01}$사이에 일대일 대응이 존재한다.

위와 같이 번호를 매기자.

$1 \rightarrow 0.d_{11}d_{12}d_{13}...$

$2 \rightarrow 0.d_{21}d_{22}d_{23}...$

$3 \rightarrow 0.d_{31}d_{32}d_{33}...$

...

그리고 새로운 실수 $x = 0.D_1D_2D_3...$를 정의할 것이다.

여기서 $D_i = (d_{ii}+1) \mod 10 $ (mod는 나머지연산)

그럼 이 수는 위의 대응에 존재하지 않는 수가 된다.

$x$는 $i$번째 수와 비교하면 소수점 아래 $i$번째 수가 다르기 때문이다.

$D_i$를 정하는 규칙에 따라 새로운 $x$는 계속 만들어진다.

따라서 일대일 대응은 존재하지 않는다.$\Box$

 

$|\mathbb{R_{01}}| = |\mathbb{R}|$임을 보이는건 연습문제로 남겨놓는다...

 

결론

실수집합은 자연수집합보다 크기가 크다는 것을 알았다.

$|\mathbb{N}| = |\mathbb{Z}| = |\mathbb{Q}| < |\mathbb{R}|$이 된다.

 

집합개념이 많아 다음에 이어가려고 한다.