03wk - 카디널리티

Author

최규빈

Published

September 16, 2025

강의영상

Size와 Cardinality

- 집합 \(A\)의 cardinality는 집합에 들어있는 “원소의 수”를 좀 더 일반화한 개념이다. 집합 \(A\)가 유한집합일 경우는 우리에게 익숙한 size의 개념을 그대로 사용하면 된다. 예를들어 집합 \(A = \{2,3,4\}\) 일 경우는

\[\text{cardinal number of } A := |A| = 3\]

와 같이 사용하면된다. 만약에 집합 \(A\)가 무한집합이라면 그 동작원리가 조금 복잡하다.

- 오늘의 목표: 집합의 size개념을 일반화하자! (그래서 카디널리티라는 개념을 만들자)

  • 익숙한 개념: 두 집합 \(A\),\(B\)의 size 비교 (단, \(A\)와 \(B\)는 유한집합)
  • 파생되는 성질: 두 집합 \(A\), \(B\)사이에 전사, 단사, 전단사 함수가 존재할때 size 비교?
  • 개념의 확장: 두 집합 \(A\),\(B\)의 cardinality 비교 (이때 \(A\)와 \(B\)는 무한집합일수도있음)

전사/단사/전단사

- 용어 정리

  • injective = one-to-one = 단사 = 일대일 함수
  • surjective = onto = 전사 = 위로의 함수
  • bijective = one-to-one and onto, one-to-one correspondence = 전단사 = 일대일 대응

- ref: https://en.wikipedia.org/wiki/Bijection,_injection_and_surjection

Figure: 위키에 있는 단사,전사,전단사함수의 그림

- 따지는 방법

  • 단사: 함수 \(f\)는 \(X\)에서 \(Y\)로 향하는 단사함수이다. \(\Leftrightarrow\) \(\forall x_1,x_2 \in X\): \(x_1\neq x_2 \Rightarrow f(x_1)\neq f(x_2)\)
  • 전사: 함수 \(f\)는 \(X\)에서 \(Y\)로 향하는 전사함수이다. \(\Leftrightarrow\) \(\forall y \in Y ~\exists x \in X\) such that \(f(x)=y\).

- 성질1: 어떤함수가 전사함수 & 단사함수 \(\Leftrightarrow\) 전단사함수

- 성질2:

  • 집합 \(X\)에서 집합 \(Y\)로 가는 단사함수 \(f\)가 존재한다. \(\Rightarrow\) \(|X| \leq |Y|\)
  • 집합 \(X\)에서 집합 \(Y\)로 가는 전사함수 \(f\)가 존재한다. \(\Rightarrow\) \(|X| \geq |Y|\)

- 성질1~2로 유추하면 아래와 같은 사실을 주장 할 수 있지 않을까?

  • 집합 \(X\)에서 집합 \(Y\)로 향하는 전단사함수가 존재한다 \(\Rightarrow\) \(|X|=|Y|\)

- 확장된 정의: 두 집합 \(X\), \(Y\)를 고려하자.

  • \(|X|\leq |Y|\) \(\Leftrightarrow\) \(X\)에서 \(Y\)로 향하는 단사함수가 존재한다.
  • \(|X|\geq |Y|\) \(\Leftrightarrow\) \(X\)에서 \(Y\)로 향하는 전사함수가 존재한다.
  • \(|X|=|Y|\) \(\Leftrightarrow\) \(X\)에서 \(Y\)로 향하는 전단사함수가 존재한다.

두 집합의 카디널리티 비교

# 예제

집합 \(X=\{1,2,3\}\), \(Y=\{2,4,6\}\)을 생각하자. 적당한 함수 \(f\)를 아래와 같이 정의하자.

  • \(f(1)=2\)
  • \(f(2)=4\)
  • \(f(3)=6\)

함수 \(f\)의 성질을 체크해보자.

  1. (단사) \(\forall x_1,x_2 \in X\): \(x_1\neq x_2\) \(\Rightarrow\) \(f(x_1)\neq f(x_2)\).
  2. (전사) \(\forall y \in Y~ \exists x \in X\) such that \(f(x)=y\).

함수 \(f\)는 전단사 함수이다. 집합 \(X\)에서 집합 \(Y\)로 가는 전단사 함수가 존재하므로 집합 \(X\)와 집합 \(Y\)의 카디널리티는 동일하다.

#

# 예제

집합 \(X=\{1,2,3,\dots \}\), \(Y=\{0,1,2,\dots \}\)을 생각하자. 함수 \(f\)를 아래와 같이 정의하자.

  • \(f(1)=0\)
  • \(f(2)=1\)
  • \(f(3)=2\)
  • \(\dots\)

함수 \(f\)의 성질을 체크해보자.

  1. (단사) \(\forall x_1,x_2 \in X\): \(x_1\neq x_2\) \(\Rightarrow\) \(f(x_1)\neq f(x_2)\)
  2. (전사) \(\forall y \in Y~ \exists x \in X\) such that \(f(x)=y\).

함수 \(f\)는 전단사함수이다. 집합 \(X\)에서 집합 \(Y\)로 가는 전단사 함수가 존재하므로 집합 \(X\)와 집합 \(Y\)의 카디널리티는 동일하다.1

#

- \(\aleph_0\)의 정의: 자연수 집합의 카디널리티 (최소의 무한 기수)를 \(\aleph_0\)이라고 정의한다. 즉

\[|\mathbb{N}|=\aleph_0\]

이다.

- 놀라운 사실1:

  • 음이 아닌 정수의 집합 \(\mathbb{N} \cup \{0\}\)의 카디널리티 역시 \(\aleph_0\)이다.

- 놀라운 사실2:

  • 자연수집합은 음이 아는 정수집합의 진 부분집합인데, 카디널리티가 같다. 즉 \(A \subsetneq B\) 인데, \(|A|=|B|\) 인 상황.
  • 즉 무한집합의 경우, 본인과 카디널넘버가 같은 진 부분집합이 존재할 수 있다. (유한집합에서는 불가능하겠지)
Note

깨알같이 소개하는 무한집합의 정의:

집합 \(A\)가 무한집합이다. \(\Leftrightarrow\) \(A\)와 동일한 카디널리티를 가지는 \(A\)의 진 부분집합이 존재한다.

# 예제

집합 \(X=\{1,2,3,\dots \}\), \(Y=\{2,4,6,\dots \}\)을 생각하자. 함수 \(f\)를 아래와 같이 정의하자.

  • \(f(1)=2\)
  • \(f(2)=4\)
  • \(f(3)=6\)
  • \(\dots\)

함수 \(f\)의 성질을 체크해보자.

  1. (단사) \(\forall x_1,x_2 \in X\), \(x_1\neq x_2\) \(\Rightarrow\) \(f(x_1)\neq f(x_2)\)?
  2. (전사) \(\forall y \in Y~ \exists x \in X\) such that \(f(x)=y\).

1의 질문과 2의 질문이 모두 맞으므로 함수 \(f\)는 전단사함수이다. 집합 \(X\)에서 집합 \(Y\)로 가는 전단사 함수가 존재하므로 집합 \(X\)와 집합 \(Y\)의 카디널리티는 동일하다.

#

- 약간 생각해보면 우리는 “\(\aleph_0\)에 1,2,3을 더해도.. 그리고 \(\aleph_0\)를 2배,3배,4배 하여도 \(\aleph_0\)이다” 란 사실을 알 수 있다.

  • \(\aleph_0 + 1 = \aleph_0\)
  • \(\aleph_0 + 2 = \aleph_0\)
  • \(...\)
  • \(\aleph_0 \times 2 = \aleph_0\)
  • \(\aleph_0 \times 3 = \aleph_0\)
  • \(...\)

- 자연수/홀수/짝수/정수의 카디널리티

  • 자연수집합 \(\mathbb{N}\)의 카디널리티는 \(\aleph_0\)이다.
  • 짝수인 자연수 집합의 카디널리티는 \(\aleph_0\)이고, 홀수인 자연수 집합의 카디널리티도 \(\aleph_0\)이다.
  • 정수집합 \(\mathbb{Z}\)의 카디널리티 역시 \(\aleph_0\)이다.

카디널리티의 유용한개념

# 개념1 – 어떠한 집합 \(A\)의 cardinality가 \(\aleph_0\) 이라면, 집합 \(A\)를 아래와 같이 쓸 수 있다.

\[ A = \{a_1,a_2,a_3,\dots \}\]

즉 어떠한 집합 \(A\)의 cardinality가 \(\aleph_0\) 이라면 그 집합은 “셀 수 있다.”

이 개념을 이용하여 아래를 풀어보자.

  • \(\{0\} \cup \mathbb{N}\)의 카디널리티는?
  • 짝수집합의 카디널리티는?
  • 홀수집합의 카디널리티는?
  • 정수집합의 카디널리티는?
  • \(\{3n-2: n=1,2,3,\dots\}\)의 카디널리티는?

#

# 개념2 – \(A \subset B\) 라면, 항상 \(A\)에서 \(B\)로 가는 단사함수가 존재한다. 즉 \(|A| \leq |B|\) 가 성립한다.

# 개념3 – 어떠한 집합 \(A\)의 cardinality가 \(\aleph_0\) 이라고 하자. 그리고 또 다른 집합 \(B\)의 cardinality는 \(\aleph_0\) 이라고 하자. 그러면 \(A\cup B\) 의 cardinality는 \(\aleph_0\) 이다.

유리수의 카디널리티

# 예제 – \(|\mathbb{N}| = |\mathbb{Q}|\) 임을 보여라. (https://en.wikipedia.org/wiki/Rational_number)

- 전략: 자연수집합 \(\mathbb{N}\)에서 양의유리수 \(\mathbb{Q}^+\)로 가는 전단사함수가 존재함을 보이자. (그러면 아래의 2-4가 자동으로 보여진다.)

  1. \(|\mathbb{N}| = |\mathbb{Q}^+|\)
  2. \(|\mathbb{Q}^+| = |\mathbb{Q}^-| \Rightarrow |\mathbb{N}| = |\mathbb{Q}^-|\)
  3. \(|\mathbb{N}| = |\mathbb{Q}^+ \cup \mathbb{Q}^-|\)
  4. \(|\mathbb{N}| = |\mathbb{Q}|\)

- 단사: \(\mathbb{N} \subset \mathbb{Q}^+\) 이므로, \(\mathbb{N} \to \mathbb{Q}^+\) 인 단사함수가 존재한다. 즉 \(|\mathbb{N}| \leq |\mathbb{Q}^+|\) 이다.

- 전사: 이제 \(\mathbb{N} \to \mathbb{Q}^+\)인 전사함수가 존재함을 보이면 된다. 아래의 그림을 보면 직관적으로 \(\mathbb{N} \to \mathbb{Q}^+\)인 전사함수가 존재함을 알 수 있음. (모든 양의유리수 \(q \in \mathbb{Q}^+\)에 대하여 대응하는 \(n \in \mathbb{N}\)이 적어도 하나는 존재함)

Figure: 자연수와 양의유리수의 카디널넘버가 동일함을 보여주는 그림 (출처: 위키))

#

- 결론: 유리수집합 \(\mathbb{Q}\)의 카디널넘버는 \(\aleph_0\)이다. 좀 더 자극적으로 말하면 “자연수의 갯수와 유리수의 갯수는 같다” 라고 말할 수 있다.

- 아래와 같이 쓸 수 있다.

  • \(\aleph_0 \times \aleph_0 = \aleph_0^2 = \aleph_0\)

실수의 카디널리티

# 예제 – \(|\mathbb{R}| > |\mathbb{Q}|\) 임을 보여라.

- 단순화1: \(|\mathbb{Q}|=|\mathbb{N}|\) 이므로, \(|\mathbb{R}| > |\mathbb{N}|\) 임을 보여도 충분하다.

  • \(\mathbb{N} \to \mathbb{R}\) 인 단사함수는 존재하지만, 전사함수는 존재할 수 없음을 보이자.
  • 그런데 \(\mathbb{N} \to \mathbb{R}\) 인 단사함수의 존재성은 쉽게 논의할 수 있다. (자연수는 실수의 부분집합이니까)

그러면 “\(\mathbb{N} \to \mathbb{R}\) 인 전사함수는 존재할 수 없음”만을 보이면 끝나네?

- 단순화2: \(\mathbb{N} \to \mathbb{R}\) 인 전사함수는 존재할 수 없음을 보이고 싶다. 그런데 이는 \(\mathbb{N} \to [0,1]\)로 향하는 전사가 존재할 수 없음을 보여도 충분하다.2

- 전략: \(\mathbb{N} \to [0,1]\) 인 전사함수가 존재한다고 가정하고 모순을 이끌어 내자.

(증명)

1. 아래와 같은 주장을 하는 가상의 인물을 세움:

\(\mathbb{N} \to [0,1]\)인 전사함수 \(a(n)\) 이 존재한다.

2. 그런데 \(\mathbb{N} \to [0,1]\)인 단사가 존재함은 당연하므로 (\(f(x)=\frac{1}{x}\)) 이 인물은 사실상 \(\mathbb{N} \to [0,1]\) 인 전단사 함수가 존재한다고 주장하는 꼴임. 즉 아래를 주장하는 꼴임.

\([0,1]=\{a_1,a_2,a_3,\dots\}\) 와 같이 표현할 수 있다.

아래의 원리에 따라서 \(y=0.c_1c_2c_3\cdots\)를 뽑는다면?

  • \(y\)의 첫번째 소수점의 값 \(c_1\)은 \(a(1)=a_1\)의 첫번째 소수점과 다르게 한다. \(\Rightarrow\) \(y\neq a(1)\) \(\Rightarrow\) \(y \notin \{a_1\}\)
  • \(y\)의 두번째 소수점의 값 \(c_2\)은 \(a(2)=a_2\)의 두번째 소수점과 다르게 한다. \(\Rightarrow\) \(y\neq a(1)\) and \(y\neq a(2)\) \(\Rightarrow\) \(y \notin \{a_1, a_2\}\)
  • \(\dots\)

\(y\)는 분명히 \([0,1]\) 사이의 실수이지만 \(y \notin \{a_1,a_2,a_3,\dots,\}\) 이다. (모순)

Warning

제가 영상에서 설명하다가 보니까.. 다른 방식으로 설명하고 싶어서요.. 강의노트를 좀 더 알기쉽게 바꿨습니다.

#

무리수의 카디널리티

# 예제 – \(|\mathbb{R}-\mathbb{Q}| > |\mathbb{Q}|\) 임을 보여라.

- 유리수의 집합 \(\mathbb{Q}\) 에서 무리수의 집합 \(\mathbb{R}-\mathbb{Q}\) 로의 단사함수가 존재하므로 \(|\mathbb{Q}| \leq |\mathbb{R}-\mathbb{Q}|\) 가 성립함은 자명하다. (왜?)

- 이제 \(|\mathbb{Q}| \neq |\mathbb{R}-\mathbb{Q}|\) 임을 귀류법을 이용하여 보이자.

(증명)

…

#

# 예제 – \(|\mathbb{R} - \mathbb{Q}| = |\mathbb{R}|\) 임을 보여라.

이건 제 실력으로는 증명할 수 없어요.. 연속체가설을 믿으세요..

#

정리하면 \(|\mathbb{N}|:=\aleph_0 =|\mathbb{Q}| < |\mathbb{R}-\mathbb{Q}| = |\mathbb{R}|:=\aleph_1\) 와 같이 된다.

# 예제 – \(|\mathbb{Q}| < |\mathbb{R}|\) 임을 보여라. <– 한반더

(증명)

\(|\mathbb{N}| < |[0,1]|\) 임을 보여도 충분하다. 따라서 \(\mathbb{N} \to [0,1]\) 인 단사는 존재하지만 전사가 존재할수 없음을 보이면 된다. 단사가 존재함은 \(f(x)=\frac{1}{x}\)로 보일 수 있다. 전사가 존재하지 않음은 귀류법을 이용하여 (즉 전사가 존재한다고 가정 \(\to\) 사실상 전단사가 존재한다고 가정하는셈) 앞의 수업시간과 같은 논리로 보일 수 있음.

Footnotes

  1. 살짝 어질어질하죠?↩︎

  2. \(\mathbb{R}\)은 커녕 \([0,1]\)도 꽉 채우지 못한다는 의미니까..↩︎