[해석학](6)[집합의 크기]

 

집합의 크기

• 집합의 크기가 같다 (|A| = |B|)
  $\Leftrightarrow$ 전단사함수인 f: A -> B가 존재

참고) 전단사(bijective)
    단사(injective): $f(a)=f(b) \Rightarrow a=b$
    $\Leftrightarrow a \neq b \Rightarrow f(a) \neq f(b)$
    전사(surjective): $\forall b \in B, \ \exists a\in A, f(a)=b$

• countable: |A| = |ℕ|인 집합 A
• uncountable: not countable
• at most countable: 유한 집합 & countable

예) 짝수집합?
    $f: \ \mathbb{N}->2\mathbb{N}$인 f(n) = 2n을 잡으면
    f는 단사이고 전사이므로,
    $|\mathbb{N}| = |2\mathbb{N}|$
예) 정수집합?
    $f: \ \mathbb{N} -> \mathbb{Z}$인 함수
    $f(n) = \begin{cases} n/2 & \text{if } n = even \ -(n-1)/2 & \text{if } n = odd \end{cases}$
    f는 전단사이므로, $|\mathbb{N}| = |\mathbb{Z}|$
예) $\mathbb{N} \times \mathbb{N}$?
    $(a, b) \in \mathbb{N}$인 (a, b)를 2차원 평면에 나타내보자
    이 평면 위의 점을 지그재그로 세면 자연수와 대응시킬 수 있다
    $f: \ \mathbb{N} \times \mathbb{N} -> \mathbb{N}$
    $f(a, b) = \frac{(a+b-1)(a+b-2)}{2}+a$
예) $\mathbb{Q}$?
    Q = 기약분수의 집합 = m/n (gcd(m, n) = 1)
    따라서 $\mathbb{N} \times \mathbb{N}$와 매우 흡사한 방식으로 증명 가능하다
    단, $\mathbb{N} \times \mathbb{N}$와 달리 기약분수가 아닐 떄는 pass한다고 하면 된다

 

Countability에 대한 도구

1. countable의 부분집합은 at most countable이다
   즉, 셀 수 있는 집합의 부분집합은 유한집합 아니면 countable이다
2. $A_1, A_2,... \text{가 countable} \Rightarrow \bigcap\limits^{\infty}_{n=1}A_n \text{ 도 countable}$

• 증명
  \bigcap\limits^{\infty}_{n=1}A_n \subseteq \text{countable} 이므로,
  \bigcap\limits^{\infty}_{n=1}A_n는 countable이거나 유한집합이다.

   3. A, B \text{가 countable이면, } A \times B \text{도 countable이다}

• 증명
  A, B의 원소를 2차원 격자에 나열한 다음 지그재그로 세는 방법도 있는데,
  소인수분해를 이용한 다른 방법도 소개하겠다
  
  A, B가 countable이므로, 자연수와 일대일대응인 함수 f_A, f_B가 존재한다.
  f: A\times B \to \mathbb{N}인 함수 f를 다음과 같이 잡아보자
  f = \{2^{f_A(a)} \cdot 3^{f_B(b)} \ | \ a \in A, \ b \in B\}
  이떄, f는 산술의 기본정리에 의해 단사함수가 된다 (정수론 정리 5 참고)
  a, b가 하나라도 다르면 다른 값이 나옴
  임의의 집합 A, B가 있을 때,
  f: A \to B인 단사함수가 존재하면 |A| \le |B|이다
  따라서 A\times B는 at most countable이 된다.
  그러나, B의 원소를 고정한 A\times B의 부분집합 S = \{(a, b_0)\ \ | \ a \in A\}는
  f_A를 통해 자연수와 일대일대응이 되므로
  |S|=|\mathbb{N}| \le |A\times B| \le |\mathbb{N}|이므로
  A \times B \text{도 countable이다}

예) $ℝ \backslash ℚ$는 uncountable이다
    $ℝ = (ℝ \backslash ℚ) \cap ℚ$ 이고,
    각각 ℝ = uncountable, ℚ = countable이므로,
    만약 $ℝ \backslash ℚ$가 countable이라면
    countable $\cup$ countable = countable $\neq \mathbb{R}$이므로 모순
    -> 따라서 $ℝ \backslash ℚ$ = uncountable

 

$\mathbb{R}$의 크기

$(0, 1) \subseteq \mathbb{R}$인 (0, 1)이 uncountable이므로 $\mathbb{R}$도 uncountable이다

• 증명 (NIP를 이용해보자)
  (0, 1)이 countable이라 가정하자. (0, 1) = {x1, x2, ...}
  어떤 원소 x1에 대해
  $I_1 = [a_1, b_1] \subseteq (0, 1)$ (단, $x_1 \notin I_1$)인 구간을 잡을 수 있을 것이다.
  그 다음 $x_2 \in I_1$인 어떤 원소 x2에 대해
  $I_2 = [a_2, b_2] \subseteq I_1$ (단, $x_2 \notin I_2$)인 구간을 잡을 수 있을 것이다.
  이걸 계속 반복하면...
  $\forall n \in \mathbb{N}, \ \exists I_n \subseteq I_{n-1}$ (단, $x_n \notin I_n$)
  따라서 I1, I2, ...은 nested interval이므로 NIP를 사용하면
  $\exists x \in I_n \subseteq (0, 1)$ 그러나 $x_n \notin I_n \Rightarrow \forall n \in \mathbb{N}, \ x \neq x_n$
  따라서 x는 (0, 1)안에 들어가지만, {x1, x2, ...}안에는 없음 -> 모순
  따라서 (0, 1) is uncountable

• 참고) 실수의 diagonal 증명
  계산이론 정리 24에선 임의의 수열에 대해서 대각선 논법을 사용해 증명하였다.
  실수에서도 비슷하게 임의의 (0, 1)사이의 수의 순서집합을 정의하고
  n번째 자리와 새로운 수 x의 n번째 자리와 비교해서
  x가 순서집합 내에 포함되지 않는다는 것으로 uncountability를 증명한다.
  그러나 실수에서는 수의 표기법이 유일하지가 않다
      예) 0.199999.... = 0.2
  따라서 단순히 n번째 자리의 숫자만 다르다는 것으로 판별하면
      x = 0.1999...., x3 = 0.200000.... 일떄 자릿수는 각자 9, 0으로 다르나,
      x = x3이다
  x가 경우에 따라선 순서집합 내에 속할수도 있다는 것이다
  -> 따라서 x를 만들 때 9, 0을 쓰지 않게 조건을 추가하면 된다
      예) x의 n번쨰 원소를 정할 떄 n번째 원소의 n번째 자릿수가 1이라면 2, 아니면 1

 

칸토어의 정리

멱집합 (power set) (P(A)): A의 모든 부분집합을 포함하는 집합
멱집합의 크기 = $2^{|A|}$
    집합 A의 원소가 들어가 있느냐(1) 없느냐(0)의 경우가 나눠짐

 

칸토어의 정리: 임의의 집합 A에 대해, |P(A)| > A이다

• 증명
  f: A -> P(A)인 전사함수 f가 존재한다고 하자.
  B = {$a \in A \ | \ a \notin f(a)$}인 집합 B를 정의할 때
      B는 A의 부분집합 -> B \in P(A)
  f가 전사함수이므로, f(b) = B인 b가 A에 존재한다
  만약 $b \in B$?
      B의 정의에 의해, b \notin f(b) = B
      즉, b는 B에 포함되면 안됨
      -> 모순
  만약 $b \notin B$?
      b \notin B = f(b)이므로, B의 정의에 의해
      b \in B여야 한다
      -> 모순
  -> 모든 경우에서 모순이므로 전사함수 f는 존재하지 않는다
  --> 따라서, A -> P(A)인 전단사함수가 존재하지 않으므로, $A \neq P(A)$
  
  그리고, f: A->P(A)인 단사함수 f(a) = {a}가 있으므로,
  |A| \le |P(A)|이다

 

연속체 가설

|ℕ| < |S| < |ℝ|인 S는 없다
    즉, 자연수와 실수의 크기 사이엔 아무것도 없다

 

참고) |P(A)| = |ℝ|
    수업은 안나감

무한의 위계
    모든 무한은 그것보다 더 큰 무한이 있다
    (멱집합 사용하면 됨)
    $|\mathbb{N}| = \aleph_0$
    $|\mathbb{R}| = 2^{\aleph_0} = \aleph_1$
    $|P(\mathbb{R})| = 2^{aleph_1} = aleph_2$
    ...