03wk-1: 카디널리티 (2)

Author

최규빈

Published

September 16, 2025

강의영상

03wk-2주차에 뒷부분 보충한내용 추가 업로드했습니다.

카디널리티의 유용한개념

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

\[ A = \{a_1,a_2,a_3,\dots \} =\bigcup_{n \in \mathbb{N}} \{a_n\}\]

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

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

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

#

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

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

유리수의 카디널리티

# 예제1 – \(|\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\)

실수의 카디널리티

# 예제2 – \(|\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]\)로 향하는 전사가 존재할 수 없음을 보여도 충분하다.1

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

(증명)

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

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

Note

함수 \(a:\mathbb{N} \to [0,1]\)의 예시 중 하나는 아래와 같은 형태일 것임.

  • \(a(1)=a_1= 0.1\) (유리수)
  • \(a(2)=a_2= 0.3141592\cdots\) (무리수, \(\frac{\pi}{10}\))
  • \(a(3)=a_3=0.14142135\cdots\) (무리수, \(\frac{\sqrt{2}}{10}\))
  • \(\dots\)

그 가상의 인물의 주장이 맞다면 모든 \(y \in [0,1]\)에 대하여, \(a(x)=y\)를 만족하는 적당한 \(x \in \mathbb{N}\)이 존재한다는 의미이므로

\[[0,1]=\{a_1,a_2,a_3,\dots\}\]

꼴로 표현가능하다는 의미임. 다시 말하면 \([0,1]\) 사이의 모든 실수는 “셀 수 있다”는 의미.

2. 전사함수의 정의에 의하여 아래가 성립해야 함

\(\forall y\in [0,1] ~\exists x \in \mathbb{N}\) such that \(a(x)=y\)

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

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

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

#

무리수의 카디널리티

# 예제3 – \(|\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}|\) 임을 귀류법을 이용하여 보이자.

(증명)

…

#

# 예제4 – \(|\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\) 사실상 전단사가 존재한다고 가정하는셈) 앞의 수업시간과 같은 논리로 보일 수 있음.

르벡메저

이제 누군가가 아래와 같은 방식으로 길이를 잰다고 해도 비웃을 수 없다.

  • 한 점의 길이는 \(0\)이다.
  • \([0,2\pi)\)의 모든 유리수의 길이는 \(0\)이다.
  • \([0,2\pi)\)의 모든 무리수의 길이는 \(2\pi\)이다.

Footnotes

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