이상엽/ 집합의 크기

집합의 분류

유한, 무한집합

동등

두 집합 X, Y 에 대하여 전단사함수 f : X \to Y 가 존재하면 X, Y 는 동등이다. (X \approx Y 또는 f : X \approx Y )

유한, 무한집합

집합 X 의 적당한 진부분집합 Y X 와 동등하면 X 는 무한집합이다.

무한집합이 아닌 집합을 유한집합이라 한다.

ex) (0, 1) \approx \mathbb{R} \therefore \mathbb{R} 은 무한집합이다.

여러가지 정리

  • 공집합 \emptyset 은 유한집합이다.
  • 무한집합을 포함하는 집합은 무한이다.
  • 유한집합의 모든 부분집합은 유한이다.
  • 전단사함수 f : X \to Y 에 대하여
    • X 가 무한집합이면 Y 도 무한집합이고
    • X 가 유한집합이면 Y 도 유한집합이다.
  • 무한집합 X 의 부분집합 Y 가 유한이면 X - Y 는 무한집합이다.

가부번, 비가부번 집합

가부번집합

집합 X X \approx \mathbb{N} 일 때 X 를 가부번집합이라 한다.

  • 가부번집합은 번호를 붙일 수 있는 집합을 의미함.
    • 자연수 집합은 번호를 붙일 수 있으므로 가부번 집합이다. –1 다음은 2 그 다음 3이므로
    • 실수 집합은 번호를 붙일 수 없으므로 비가부번 집합이 된다. –1 다음 수를 어떤 것으로 정의할 수가 없음.

가산집합

유한집합이나 가부번집합을 가산집합이라 한다.

여러가지 정리

  • 가산집합의 부분집합은 가산집합이다.
  • 가부번집합들의 합집합은 가부번이다.
  • \mathbb{N} \times \mathbb{N} 은 가부번집합이다.
  • \mathbb{Q} 은 가부번집합이다.
    • 가부번 집합을 합하거나 곱해도 가부번 집합이다. –지수로 올리면 얘기가 달라짐.
  • \mathbb{R} 의 부분집합 (0, 1) 은 비가부번이다.
  • 모든 무리수의 집합은 비가부번집합이다.
    • 비가부번 집합인 실수 집합은 유리수와 무리수 집합의 합집합인데, 유리수 집합은 가부번 집합이므로 무리수 집합이 비가부번 집합이어야 한다.
  • \mathbb{C} 은 비가부번집합이다. (복소수 집합)

기수

기수의 개념

기수

집합의 크기를 나타내는 수. card A 또는 \# A

  • 각 집합 A 에 대해 \# A 는 유일하다.
  • \# A 에 해당하는 집합 A 는 항상 있다.
  • A = \emptyset \Leftrightarrow \# A = 0
  • A ~ \{ 1, 2, ... , k \} 이면 \# A = k ( k \in \mathbb{N})
  • A \approx B \Leftrightarrow \# A = \#B
  • (배열의 길이라고 생각하면 편하다)

유한기수, 초한기수

유한기수는 유한집합의 기수이고, 초한기수는 무한집합의 기수

  • 대표적인 초한기수
    • \# \mathbb{N} = \aleph_{0} 가부번집합의 기수 (알레프 제로라고 읽음)
    • \# \mathbb{R} = \varsigma 연속체의 기수 (시그마라고 읽음)

#A < #B

A B 의 한 부분집합과 동등이고, B A 의 어떠한 부분집합과도 동등이지 않다.

  • \# A \leq \# A
  • A B 의 부분집합과 동등이고, B A 의 부분집합과 동등이면 A B 는 동등이다. (\# A = \# B ) – 칸토어-번슈타인 정리
  • \# A \leq \# B 이고 \# B \leq \# C 이면 \# A \leq \# C 이다.

기수의 연산

기수 합

서로소인 두 집합 A, B 의 기수를 각각 a, b 라고할 때, a + b = \# (A \cup B)

기수 곱

집합 A, B 의 기수를 각각 a, b 라고할 때, ab = \# (A \times B)

연산 법칙

임의의 기수 x, y, z 에 대하여 다음이 성립한다.

  • 교환법칙
    • x + y = y + x
    • xy = yx
  • 결합법칙
    • (x + y) + z = x + (y + z)
    • (xy)z = x(yz)
  • 분배법칙
    • x(y+z) = xy + xz
  • (기수 자체는 숫자인데, 기수의 연산은 그 숫자의 값이 위의 결과를 만족한다고 보는게 아니라, 그 기수가 대응되는 집합과의 관계가 위 조건을 만족한다는 의미)

여러가지 정리

  • \aleph_{0} + \aleph_{0} = \aleph_{0}
  • \varsigma + \varsigma = \varsigma
  • \aleph_{0} + \varsigma = \varsigma
  • \aleph_{0} \aleph_{0} = \aleph_{0}
  • \varsigma \varsigma = \varsigma
  • \aleph_{0} \varsigma = \varsigma

기수의 지수

집합 A, B 에 대하여 \# A = m, \# B = n 일 때

  • B^{A} = \{ f | f : A \to B \}
    • A에서 B로 가는 함수를 끌어 모은 집합. 지수에서 밑으로 가는 모습
    • ex) A = \{ 1, 2, 3 \}, B = \{ 4, 5 \} 일 때, f : A \to B 의 총 개수
      • 2 \times 2 \times 2 = 8 = 2^{3} = \#B^{\#A}
  • \# (B^{A}) = n^{m}
  • B = \{ 0, 1 \} 일 때, B^{A} = \{ 0, 1 \}^{A} = 2^{A}

여러가지 정리

  • 집합 X 에 대하여 \# X = x 일 때 \# P(X) = 2^{x}
    • ex) X = \{ 1, 2, 3 \} 일때
      • P(X) = \{ \emptyset, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\} \}
      • \# P(X) = 8
  • 기수 x, y, z 에 대하여
    • x^{y} x^{z} = x^{y+z}
    • (x^{y})^{z} = x^{yz}
    • (xy)^{z} = x^{z} y^{z}
  • \varsigma = \aleph_{0}^{\aleph_{0}} = \varsigma^{\aleph_{0}}
    • \aleph_{0} 끼리의 합이나 곱은 여전히 \aleph_{0} 지만, 지수로 올리면 \varsigma 가 된다.
    • \varsigma \aleph_{0} 를 지수로 올려도 \varsigma 가 된다.
  • 2^{c} = \aleph_{0}^{c} = \varsigma^{c}
    • 2^{c} 는 실수집합의 멱집합
[ssba]

The author

지성을 추구하는 사람/ suyeongpark@abyne.com

댓글 남기기

This site uses Akismet to reduce spam. Learn how your comment data is processed.