[계산이론](23)[집합의 크기&대각선 논법]

non-TR에 대해 알기 위해선 무한집합의 크기에 대해 정확히 따져볼 필요가 있다!

 

집합의 크기

(자세한건 집합론에서 다루겠다.)

 

단사: 하나의 input에 하나의 output이 대응됨
    $f: \ X\rightarrow Y$에 대해,
    $x_1 \neq x_2 \Rightarrow f(x_1) \neq f(x_2)$
    $\Leftrightarrow f(x_1) = f(x_2) \Rightarrow x_1 = x_2$
전사: output에 적어도 1개의 input이 대응됨 (치역 = 공역)
    $f: \ X\rightarrow Y$에 대해,
    $\forall y \in Y ,\ \exists x \in X, \ y = f(x)$
전단사: 전사이며 단사
예) y = 4x는 전단사함수이다.
    - 단사
        a, b ∈ X, a != b일떄,
        f(a) = 4a != 4b = f(b)
        즉, f(a) != f(b)이므로, f는 단사이다
    - 전사
        임의의 y ∈ Y에 대해
        대응되는 x = y/4가 있으므로, (이떄 x = y/4 ∈ X)
        f는 전사이다
    따라서 y = 4x는 전단사함수이다

 

집합의 크기가 같다 ⇔ 집합 간 전단사함수가 존재한다.
예) x={1, 2, 3}과 y={3, 6, 9}의 크기는 같은가?
    전단사함수 y = 3x가 존재하므로,
    x, y는 크기가 같은 집합이다.
    (y=3x가 전단사임을 증명하는건 생략)
예) 자연수 전체 집합 N과 짝수 집합 E의 크기는 같은가?
    f: N -> E 인 함수를 생각해 보자.
    전단사함수 f: y = 2x가 존재하므로,
    N, E는 크기가 같은 집합이다.

 

countable과 uncountable

• countable: 집합의 크기가 유한하거나 자연수와 같음
  countable한 집합의 크기 = |N| = $\aleph_0$
• uncountable: 집합의 크기가 countable이 아님
  예) 양의 유리수 집합은 countable하다

 

대각선 논법

실수 집합(ℝ)의 크기를 알기 위해 고안된 방법

1. 실수 집합이 countable하다 가정한다
   즉, 자연수와 일대일대응하다
2. 실수 집합 안에 있는 원소를 자연수와 짝을 맞춰 늘어놓는다

n	f(n)
1	0.120200202020...
2	2.321313213213...
3	0.799432131313...
4	1.542489586986...
...	...

3. 새로운 x를 잡아보자.
   x = {n번째 자리 수는 f(n)의 n번째 자리 수와 같지 않다.}
   즉, 앞의 예제에서는
   x = 0.0111...처럼 잡을 수 있다.
4. x는 ℝ안에 들어가는 실수이나, f(n)의 원소와 n번째 자리에서 차이가 나기 때문에 f(n)엔 없는 원소이다.
   -> 즉, f의 전사에 위배되므로, (ℝ != f(n)) ℝ는 자연수 집합과 크기가 같지 않다.
   따라서 ℝ는 uncountable하다

참고) 집합의 대소비교에서
    A -> B 단사함수는 있으나 전단사 함수가 없을 때
    |A| < |B| 라고 할 수 있다.
    따라서 앞에서 ℝ는 ℕ보다 집합의 크기가 크다고 할 수 있다