집합

Relation✔

• 증명

  동치관계 \(\ssim\) 에 대한 동치류 \(E = [x], E' = [x']\) 에 대하여 \(E \cap E' \neq \varnothing\) 이면 \(y \in E \cap E'\) 인 \(y\) 가 존재한다. 그러면 \(y \ssim x, y \ssim x'\) 이다. 반사관계에 의하여 \(x \ssim y\) 이고 전이관계에 의하여 \(x \ssim y \ssim x' \implies x \ssim x'\) 이다. 어떤 \(w \in E\) 에 대하여 \(w \ssim x\) 이므로 전이관계에 의하여 \(w \ssim x \ssim x' \implies w \ssim x'\) 이다. 따라서 \(E \subset E'\) 이다. 그러면 반사관계에 의하여 \(E' \subset E\) 이다. 따라서 \(E = E'\) 이다. ■

Open Interval✔

• \((a, b) = \varnothing\) 이면 \(a\) 를 \(b\) 의 immediate predecessor 라 하고 \(b\) 를 \(a\) 의 immediate successor 라 한다.

• NBG 체계에서 정의한 순서형과 똑같이 정의된다.

• 예시

  열린구간 \((-1, 1)\) 과 \(\R\) 은 다음과 같이 정의된 함수 \(f: (-1, 1) \to \R\) 이 전단사이므로 같은 순서형을 가진다.

  \[ f(x) = \dfrac{x}{1-x ^{2}} \]

  

Bound Property✔

• 실수체는 이 성질을 지닌다.

• 증명

Real Number Field✔

• 집합론의 체와 선형대수학의 체에서 정의한 체를 완비순서체로 구체화시킨 것이 실수체이다.

• 1) 부터 5) 까지를 대수학의 법칙(laws of algebra)라 한다. 두 이항연산이 정의되어 1) 부터 5) 를 만족하는 집합을 체(field)라 한다. 6) 을 만족하는 순서관계까지 정의되면 순서체(ordered field) 라 한다. 7), 8) 은 위상수학적 성질인데 이 조건을 만족하는 집합을 위상수학적으로 선형 연속체(linear continuum)라 한다.

• 1) 부터 7) 이 만족되면 \(x < y \implies z = (x+y)/(1+1)\) 라는 식으로 8) 이 증명되어 정리가 되지만, 강조의 의미로 8) 을 공리로 표기한다.

• \(x>0\) 를 양수라 하고 \(x<0\) 를 음수라 한다. 양의 실수를 \(\R _{+}\) 라 표기하고 음이 아닌 실수를 \(\bar{\R }_{+}\) 라 표기한다.

Inductive Set✔

Integers✔

• \(\Bbb{Z}_{+} \subset \R _{+}\) 임은 쉽게 보일 수 있다. 또한 \(\min \Bbb{Z}_{+} = 1\) 도 쉽게 보일 수 있다.

• \(\Bbb{Z}_{+}\) 는 귀납적이다. \(A\) 가 양의 정수의 귀납적 집합이면 \(A = \Bbb{Z}_{+}\) 이다.

• 정수에는 합, 차, 곱이 정의되어있지만 나눗셈이 정의되어있지 않다. 정수 나눗셈에 의한 몫으로 유리수 \(\Bbb{Q}\) 를 정의한다.

Section✔

• \(S_1 = \varnothing\) 이다.

Well-Ordering Property✔

• 증명

  수론 정리 2.1.4에 의하여 증명된다. Munkres, Topology 에서는 또 다른 증명이 있다. ■

Strong Induction Principle✔

• 증명

  \(A \neq \Bbb{Z}_{+}\) 이면 \(A\) 에 속하지 않는 가장 작은 양의 정수 \(n\) 이 존재한다. 그러면 \(n\) 보다 작은 양의 정수는 모두 \(A\) 에 속한다. 즉, \(S_n \subset A\) 이다. 그러면 가정에 의하여 \(n \in A\) 이다. 이는 모순이다. ■

Product Set✔

• 집합 \(J\) 의 원소에 의하여 집합 \(A\) 의 원소가 라벨링되었다면 \(J\) 를 인덱스 집합이라 한다.

• 집합에 인덱스를 붙이면 집합을 편하게 표현할 수 있다. 가령 \(A = \{3, \varnothing, \{1, 2\}\}\) 같은 집합을 \(A = \{a_1, a_2, a_3\}\) 으로 표현할 수 있다. 이 인덱스 \(1, 2, 3\) 을 모아둔 집합 \(J = \{1, 2, 3\}\) 가 \(A\) 의 인덱스 집합이 된다. 이 인덱스 집합을 사용하여 집합 \(A\) 를 다음과 같이 편하게 표현할 수 있다.

  \[ A = \{a _{\alpha} : \alpha \in J\} \]

  이때 인덱스 집합이 \(J \subset \Bbb{Z}_{+}\) 이어야 할 필요는 없다. 인덱스 집합은 완전히 임의의 집합일 수 있다.

• 즉, \(\{A _{\alpha}\} _{\alpha \in J}\) 은 \(\alpha \in J\) 에 대한 모든 \(A _{\alpha}\) 의 모임이다.

• 인덱스 함수 \(f\) 는 단사가 아니어도 된다. 즉, \(\alpha \neq \beta\) 이어도 \(A _{\alpha} = A _{\beta }\) 일 수 있다.

• 예시

  집합족 \(\mathcal{A}\) 에 대한 인덱스 함수 \(f: J \to \mathcal{A}\) 의 상 \(f(\alpha)\) 를 \(A _{\alpha}\) 로 표기하면 다음이 성립한다.

  \[ \bigcup_{\alpha \in J}^{}A _{\alpha} = \{x : \exists \alpha \in J : x \in A _{\alpha}\} \]
  \[ \bigcap_{\alpha \in J}^{}A _{\alpha} = \{x : \forall \alpha \in J : x \in A _{\alpha}\} \]

Sequence✔

• 집합족 \(\{A_1, \dots ,A_m\}\) 의 집합들이 모두 \(X\) 로 같을 경우 곱집합은 단순히 \(X ^{m}\) 이 된다.

  집합족 \(\{A_1, A_2, \dots \}\) 의 집합들이 모두 \(X\) 로 같을 경우 곱집합은 \(X ^{\omega }\) 이 된다.

• 예시

  \(\R ^{m}\) 을 유클리드 \(m\)-공간이라 한다.

  \(\R ^{\omega }\) 를 무한차원 유클리드 공간이라 한다. 이것은 실수로 이루어진 \(\omega\)-튜플 \((x_1, x_2, \dots )\) 을 모두 모은 집합이다.

Cartesian Product✔

• 이 정의가 \(m\)-튜플과 다른 점은 인덱스 집합 \(\{1, 2, \dots , m\}\) 을 완전히 임의의 집합 \(J\) 로 바꿨다는 것이다.

• 예시

  \(J = 2 \in \N\) 이면 \(X ^{2}\) 는 \(X\) 의 모든 \(2\)-튜플 집합이다.

  또한 \(2 = \{0, 1\}\) 이므로 \(X ^{2}\) 는 \(\{0, 1\}\) 에서 \(X\) 로 가는 모든 함수의 집합이다.

• 이 곱집합 정의는 집합론의 곱집합 정의와 같다.

• 문맥이 명확할 경우 곱집합을 \(\prod_{}^{}A _{\alpha}\) 로 간단하게 표기한다.

• 모든 집합 \(A _{\alpha}\) 들이 한 집합 \(X\) 일 경우 \(\prod A _{\alpha} = X ^{J}\) 이다.

Finite Set✔

• 집합론의 유한집합 정의와 똑같다.

• 증명

  전단사 \(g: A - \{a_0\} \to \{1, \dots ,n\}\) 의 존재성을 가정하면 함수 \(f: A \to \{1,\dots ,n+1\}\) 를 다음과 같이 정의하면 \(f\) 가 전단사임을 바로 알 수 있다.

  \[ f(x) = \begin{cases} g(x) & x \in A - \{a_0\}\\ n+1 & x = a_0 \\ \end{cases} \]

  ▲

  전단사 \(f: A \to \{1, \dots , n+1\}\) 의 존재성을 가정하자. \(f(a_0) = n+1\) 일 경우 제한 \(f|_{A - \{a_0\}}\) 이 우리가 찾던 전단사 사상이다. \(f(a_0) \neq n + 1\) 일 경우 다음과 같은 함수 \(h: A \to \{1, \dots , n+1\}\) 를 정의하자.

  \[ h(x) = \begin{cases} n+1 & x = a_0\\ m & x = a_1\\ f(x) & x \in A - \{a_0, a_1\}\\ \end{cases} \]

  그러면 제한 \(h| _{A - \{a_0\}}\) 이 우리가 찾는 전단사 사상이다. ■

• 증명

  \(B = \varnothing\) 인 경우 자명하다. ▲

  \(n = 1\) 인 경우 \(A = \{a\}\) 의 진부분집합은 \(B = \varnothing\) 이므로 자명하다. ▲

  정리가 \(n (> 1)\) 에 대하여 성립함을 가정하고 \(n + 1\) 에 대하여 성립함을 보이자. \(f:A \to \{1, 2, \dots , n+1\}\) 가 전단사이고 \(B \subsetneq A\) 가 \(B \neq \varnothing\) 임을 가정하자. 이제 \(a_0 \in B\) 와 \(a_1 \in A - B\) 를 선택하자.

  Lemma 6.1 에 의하여 전단사 사상 \(g: A - \{a_0\} \to \{1, \dots , n\}\) 이 존재한다. 정리가 \(n\) 에 대하여 성립하므로 다음이 성립한다.

  1. 전단사 사상 \(h : B - \{a_0\} \to \{1, 2, \dots , n\}\) 가 존재하지 않는다.

  2. \(B - \{a_0\} = \varnothing\) 이거나 \(p < n\) 에 대하여 다음과 같은 전단사 사상이 존재한다.

     \[ k : B - \{a_0\} \to \{1, 2, \dots , p\} \]

  Lemma 6.1 과 1) 에 의하여 \(B \to \{1, 2, \dots , n+1\}\) 로 가는 전단사 사상이 존재하지 않는다. 이로써 \(n+1\) 에 대하여 1) 이 성립한다. ▲

  \(B - \{a_0\} = \varnothing\) 일 경우 \(B \to \{1\}\) 로 가는 전단사 사상이 존재한다. \(B - \{a_0\} \neq \varnothing\) 일 경우 Lemma 6.1 과 2) 에 의하여 \(B \to \{1, 2, \dots , p +1\}\) 로 가는 전단사 사상이 존재한다. 즉, 어느 경우에든 \(m < n+1\) 에 대하여 \(B \to \{1, 2, \dots , m\}\) 로 가는 전단사 사상이 존재한다. 이로써 \(n + 1\) 에 대하여 2) 가 성립한다. ▲

  그러면 수학적 귀납법에 의하여 정리가 모든 \(n \in \Bbb{Z}_{+}\) 에 대하여 성립한다. ■

• 증명

  전단사 사상 \(f: A \to B\) 가 존재한다고 가정하자. \(A\) 가 유한집합이므로 어떤 \(n\) 에 대하여 전단사 사상 \(g: A \to \{1, 2, \dots , n\}\) 가 존재한다. 그러면 합성함수 \(g \circ f ^{-1}\) 는 \(B \to \{1, 2, \dots , n\}\) 로 가는 전단사 사상이다. 이는 Theorem 6.2 에 의하여 모순이다. ■

• 증명

  함수 \(f: \Bbb{Z}_{+}\to \Bbb{Z}_{+}-\{1\}\) 를 \(f(n) = n + 1\) 로 정의하면 전단사 사상이고, \(\Bbb{Z}_{+} - \{1\} \subsetneq \Bbb{Z}_{+}\) 이다. \(\Bbb{Z}_{+}\) 가 유한집합이면 Corollary 6.3 에 의하여 모순이다. ■

Uniqueness of Cardinality✔

• 이 정리가 이 절의 가장 중요한 결론이다. 이 정리가 두 집합 \(\{1, 2, \dots , n\}, \{1, 2, \dots ,m\}\) 이 서로 다르면, 두 집합의 원소의 개수(기수)가 다르다는 것을 보장해준다.

• 증명

  \(m < n\) 에 대하여 다음과 같은 전단사 사상을 가정하자.

  \[ f: A \to \{1, 2, \dots , n\} \]
  \[ g: A \to \{1, 2, \dots , m\} \]

  이제 다음과 같은 전단사 합성함수를 만들 수 있다.

  \[ g \circ f ^{-1}: \{1, 2, \dots , n\} \to \{1, 2, \dots , m\} \]

  공역이 정의역의 진부분집합이므로 Corollary 6.3 에 의하여 이것이 전단사라는 것은 모순이다. ■

Criterion for Finiteness✔

• 증명

  \(1 \implies 2\):

  \(B\) 가 유한집합이면 어떤 \(n\) 에 대한 전단사 함수 \(f: \{1, 2, \dots , n\}\to B\) 가 존재한다. ■

  \(2 \implies 3\):

  전사 함수 \(f: \{1, 2, \dots , n\} \to B\) 가 존재하면 함수 \(g: B \to \{1, 2, \dots , n\}\) 를 다음과 같이 정의할 수 있다.

  \[ g(b) = \min f ^{-1}(\{b\}) \]

  \(f\) 가 전사이므로 집합 \(f ^{-1}(\{b\})\) 은 공집합이 아니다. well-ordering property 에 의하여 \(g(b)\) 는 유일하게 결정된다. 또한 \(b \neq b'\) 이면 두 집합 \(f ^{-1}(\{b\}), f ^{-1}(\{b'\})\) 은 서로소이므로 \(g\) 는 단사이다. ■

  \(3 \implies 1\):

  단사 함수 \(g: B \to \{1, 2, \dots , n\}\) 의 치역을 바꿔서 전단사함수로 만들 수 있다. 유한집합의 정의에 의하여 \(B\) 는 유한집합이다. ■

• \(2 \implies 3\) 의 증명에서 전사함수 \(f\) 에 대한 역함수 \(f ^{-1}\) 를 다뤘다. 그러나 오직 전단사함수만이 역함수를 가진다. 따라서 \(f\) 가 단사라는 조건이 필요하다. 그냥 엄청 엄밀하게 증명하려 하지 않고, 조금 융통성있게 표기한듯.

• 증명

  유한집합의 유한한 합집합은 유한집합이다:

  유한 집합 \(A, B\) 에 대하여 \(A \cup B\) 가 유한집합임을 증명하자. \(A = \varnothing \lor B = \varnothing\) 이면 자명하다. ▲

  그렇지 않을 경우 \(n, m\) 에 대한 전단사 사상 \(f: \{1, 2, \dots ,m\} \to A\) 와 \(g : \{1, 2, \dots , n\} \to B\) 이 존재한다. 함수 \(h: \{1, 2, \dots ,m + n\} \to A \cup B\) 을 다음과 같이 정의하자.

  \[ h(i) = \begin{cases} f(i) & i \in \{1, 2, \dots , m\}\\ g(i - m) & i \in \{m + 1, \dots , m + n\}\\ \end{cases} \]

  그러면 \(h\) 가 전사임을 보이는 것은 쉽다. 즉, \(h\) 는 전단사이다. 유한집합의 정의에 따라서 \(A \cup B\) 는 유한집합이다. ▲

  유한집합 \(A_1, \dots , A_n\) 에 대하여 \(n = 1\) 일 때 \(\displaystyle \bigcup_{i=1}^{n}A_i\) 은 자명하게 유한집합이다. ▲

  \(n (> 1)\) 일 때 \(\displaystyle \bigcup_{i=1}^{n-1}A_i\) 이 유한집합이라고 가정하자. \(\displaystyle \bigcup_{i=1}^{n}A_i = \bigcup_{i=1}^{n-1}A_i \cup A_n\) 인데, 이것은 위에서 증명한 바에 의하여 유한집합이다. ▲

  수학적 귀납법에 의하여 유한집합의 유한한 합집합은 유한집합이다. ■

  유한집합의 유한한 곱집합은 유한집합이다:

  유한집합 \(A, B\) 에 대하여 \(A \times B\) 가 유한집합임을 보이자. \(a \in A\) 에 대하여 \(\{a\} \times B\) 는 \(B\) 와 전단사 사상을 가지므로 유한집합이다. \(A \times B\) 는 이러한 집합들의 유한한 합집합이므로 유한집합이다. ▲

  이를 기반으로 유한집합 \(A_1, A_2, \dots, A_n\) 에 대하여 \(\displaystyle \prod_{i=1}^{n}A_i\) 가 유한집합임을 위와 같이 수학적 귀납법으로 쉽게 보일 수 있다. ■

Countable and Uncountable Sets✔

• 증명

  \(1 \implies 2\):

  \(B\) 가 가산 무한집합이면 전단사 함수 \(f:\Bbb{Z}_{+}\to B\) 가 존재한다. ▲

  \(B\) 가 유한집합이면 \(n \geq 1\) 에 대한 전단사 \(h:\{1, 2, \dots , n\}\to B\) 가 존재한다. \(h\) 를 다음과 같이 전사함수 \(f: \Bbb{Z}_{+}\to B\) 로 확장할 수 있다.

  \[ f(i) = \begin{cases} h(i) & 1 \leq i \leq n\\ h(1) & n < i\\ \end{cases} \]

  ■

  \(2 \implies 3\):

  \(f: \Bbb{Z}_{+}\to B\) 가 전사이면 함수 \(g: B \to \Bbb{Z}_{+}\) 를 다음과 같이 정의할 수 있다.

  \[ g(b) = \min f ^{-1}(\{b\}) \]

  \(f\) 가 전사이므로 \(f ^{-1}(\{b\}) \neq \varnothing\) 이므로 well-ordering property 에 의하여 \(g\) 가 잘 정의된다. \(b \neq b'\) 일 때 두 집합 \(f ^{-1}(\{b\}), f ^{-1}(\{b'\})\) 은 서로소이므로 \(g\) 는 단사이다. ■

  \(3 \implies 1\):

  단사함수 \(g : B \to \Bbb{Z}_{+}\) 에 대하여 \(B\) 가 가산집합임을 보이자. \(g\) 의 공역을 바꿔서 \(g\) 를 전단사로 만들자. 그러면 \(\Bbb{Z}_{+}\) 의 모든 부분집합이 가산집합임을 보이면 된다.

  \(C \subset \Bbb{Z}_{+}\) 에 대하여 \(C\) 가 유한집합이면 가산집합이다. \(C\) 가 무한집합일 경우는 다음의 Lemme 7.2 에서 증명한다. ■

• 증명

  함수 \(h : \Bbb{Z}_{+}\to C\) 가 전단사가 되도록 정의하자. 먼저 \(h(1) = \min C\) 로 정의하자. \(h(1),\dots ,h(n-1)\) 이 정의되어 있을 때 \(h(n)\) 을 다음과 같이 정의하자.

  \[ h(n) = \min [C - h(\{1, 2, \dots , n -1\})] \]

  이렇게 정의하는 것이 가능한 이유는 항상 \(C - h(\{1, 2, \dots , n -1\}) \neq \varnothing\) 이기 때문이다. 만약 이것이 공집합이면 \(h:\{1, \dots , n -1\}\to C\) 가 전사가 되어 Corollary 6.7 에 의하여 \(C\) 가 유한집합이 된다. 즉, \(h\) 는 모든 \(n \in \Bbb{Z}_{+}\) 에 대하여 잘 정의된다. ▲

  임의의 \(m < n\) 에 대하여 \(h(m) \in h(\{1, 2, \dots , n -1\})\) 인 반면 \(h(n) \not\in h( \{ 1, 2, \dots , n- 1\})\) 이므로 \(h(n) \neq h(m)\) 이다. 따라서 \(h\) 는 단사이다. ▲

  임의의 \(c \in C\) 가 \(h\) 의 상임을 보이면 \(h\) 가 전사임이 증명되고, 모든 증명이 끝난다. 먼저 \(h\) 는 단사이므로 \(h(\Bbb{Z}_{+})\) 는 유한집합 \(\{1, 2, \dots , c\}\) 에 포함되지 않는다. 따라서 \(h(n) > c\) 인 \(n \in \Bbb{Z}_{+}\) 이 존재한다. \(m \in \Bbb{Z}_{+}\) 을 \(h(m) \geq c\) 를 만족하는 가장 작은 \(\Bbb{Z}_{+}\) 의 원소라고 하자.

  그러면 \(\forall i < m : h(i) < c\) 이고, 이에 따라 \(c \not\in h(\{1, 2, \dots , m -1\})\) 이다. 그렇다면 \(c \in C - h(\{1, 2, \dots , m - 1\})\) 인데 \(h(m) = \min [ C - h(\{1, 2, \dots , m - 1\})]\) 이므로 \(h(m) \leq c\) 이다.

  그러므로 \(h(m) = c\) 이다. ■

• 증명

  가산집합 \(B\) 에 대한 \(A \subset B\) 를 잡자. Theorem 7.1 에 의하여 단사 \(f: B \to \Bbb{Z}_{+}\) 가 존재한다. \(f\) 를 \(A\) 로 제한하면 단사이므로 Theorem 7.1 에 의하여 \(A\) 는 가산이다. ■

• 증명

  집합론의 정리 \(\N \times \N \approx \N\)에서도 증명된다. Munkres, Topology 에는 또 다른 증명이 있다. ■

• 증명

  \(\{1, 2, \dots , N\}\) 또는 \(\Bbb{Z}_{+}\) 인 인덱스 집합 \(J\) 에 대한 인덱스된 가산 집합족 \(\{A_n\}_{n \in J}\) 를 잡자. 편의상 \(A_n \neq \varnothing\) 을 가정하자. 이 가정은 아무런 영향력이 없다.

  \(A_n\) 이 가산이므로 각 \(n\) 마다 전사함수 \(f_n : \Bbb{Z}_{+}\to A_n\) 이 존재한다. 마찬가지로 전사함수 \(g: \Bbb{Z}_{+}\to J\) 가 존재한다. 이를 통해 다음과 같은 함수를 정의하자.

  \[ h: \Bbb{Z}_{+}\times \Bbb{Z}_{+} \to \bigcup_{n \in J}^{}A_n, (k, m) \mapsto f _{g(k)}(m) \]

  그러면 \(h\) 는 전사이다. \(\Bbb{Z}_{+} \times \Bbb{Z}_{+} \approx \Bbb{Z}_{+}\) 이므로 Theorem 7.1 에 의하여 \(\displaystyle \bigcup_{n \in J}^{}A_n\) 은 가산이다. ■

• 이 정리를 보면 가산집합의 가산 곱집합도 가산이라고 생각하고 싶지만, 그렇지 않다. Theorem 7.7 을 보자.

• 증명

  두 가산집합 \(A,B\) 의 곱집합이 가산임을 먼저 보이자. \(A\) 또는 \(B\) 가 공집합이면 자명하다. 둘 다 공집합이 아닐 때 Theorem 7.1 에 의하여 전사함수 \(f:\Bbb{Z}_{+}\to A, g:\Bbb{Z}_{+}\to B\) 가 존재한다. 이를 기반으로 함수 \(h(n,m) = (f(n), g(m))\) 를 만들면 이는 전사이다. 따라서 \(A \times B\) 는 가산이다. ▲

  이제 가산집합 \(A_i\) 에 대하여 \(A_1 \times \dots \times A _{n-1}\) 이 가산집합임을 가정하자. 그리고 전단사 함수

  \[ g: A_1 \times \dots \times A_n \to (A_1 \times \dots \times A _{n-1}) \times A_n \]

  을 다음과 같이 정의하자.

  \[ g(x_1, \dots ,x_n) = ((x_1, \dots ,x _{n-1}), x_n) \]

  \(A_1 \times \dots \times A _{n-1}\) 이 가산이고 두 가산집합의 곱집합이 가산이므로 \(A_1 \times \dots \times A_n\) 도 가산이다. ■

• 다음 증명이 유명한 대각선 논법이다.

• 증명

  함수 \(g: \Bbb{Z}_{+}\to X ^{\omega }\) 가 전사가 아님을 보이면 된다. \(g(n)\) 을 \(x _{ij} \in \{0, 1\}\) 에 대하여 다음과 같이 표기하자.

  \[ g(n) = (x _{n1}, x _{n2}, x _{n3}, \dots , x _{nm}, \dots ) \]

  이제 \(y = (y_1, y_2, \dots, y_n, \dots ) \in X ^{\omega }\) 를 다음과 같이 정의하자.

  \[ y_n = \begin{cases} 0 &x _{nn} = 1 \\ 1 & x _{nn} = 0\\ \end{cases} \]

  그러면 어떠한 정의역의 원소에 대한 상이라도 \(y\) 와 같지 않다. 즉, \(y\) 를 상으로 갖는 정의역의 원소는 존재하지 않는다. 따라서 \(g\) 는 전사가 아니다. ■

• 증명

  집합론 따름정리 1.2.5에 의하여 \(g: A \to \mathcal{P}(A)\) 가 전사가 아님을 보이면 충분하다.

  \(a \in A\) 에 대한 \(g(a)\) 는 \(A\) 의 부분집합이다. \(A\) 의 부분집합 \(B = \{a : a \in A - g(a)\}\) 를 정의하자. 어떤 \(a_0 \in A\) 에 대하여 \(g(a_0) = B\) 라고 가정하자. \(a_0 \in B\) 인 경우 \(B\) 의 정의에 의하여 \(a_0 \not\in B\) 이고, \(a_0 \not\in B\) 인 경우 \(B\) 의 정의에 의하여 \(a_0 \in B\) 이다. 즉, 모순이다. 따라서 \(B\) 는 \(g\) 의 상이 아니다. ■

Infinite Sets✔

• 증명

  \(1 \implies 2\):

  단사함수 \(f: \Bbb{Z}_{+}\to A\) 를 가정하자. \(f(n) = a_n\) 로 표기하고, 함수 \(g:A \to A - \{a_1\}\) 를 다음과 같이 정의하자.

  \[ a_n \in f(\Bbb{Z}_{+}) \implies g(a_n) = a _{n+1} \]
  \[ x \in A - f(\Bbb{Z}_{+}) \implies g(x) = x \]

  그러면 \(g\) 는 전단사이다. ■

  \(2 \implies 3\):

  Corollary 6.3 의 대우를 취하면 바로 나온다. ■

  \(3 \implies 1\):

  집합론 도움정리 3.4.4 에 의하여 바로 증명된다. Munkres, Topology 에는 또 다른 증명이 있다. ■

Axiom of Choice✔

• 집합론의 선택공리는 좀 더 형식적으로 정의된다.

• 즉, 집합 \(C\) 에 집합족 \(\mathcal{A}\) 에 속한 각각의 집합에서 원소를 하나씩 선택하여 포함시킨다. 선택공리는 이러한 방식으로 만들어진 집합이 존재한다는 것을 보장해준다.

  집합론의 공리에 의하여 집합을 만드는 합법적인 방법은 다음과 같다.

  1. 원소를 리스팅하여 집합을 정의한다. 또는 집합 \(A\) 의 어떤 특성을 만족하는 부분집합 \(B\) 를 정의한다.
  2. 주어진 집합족의 교집합이나 합집합을 취하거나, 두 집합의 차를 취하여 집합을 만든다.
  3. 주어진 집합의 모든 부분집합의 집합을 만든다.
  4. 집합의 곱집합을 취한다.

  그러나 가령 \(f: \Bbb{Z}_{+}\times A\) 와 같이 정의된 함수는 \(\Bbb{Z}_{+}\times A\) 의 부분집합인데, 이 집합을 만들기 위해서는 \(\Bbb{Z}_{+}\times A\) 의 적절한 부분집합을 취해야 한다. 그런데 함수라는 곱집합의 부분집합을 취하는 방법은 위의 4가지 방법 어느 것에도 해당되지 않는다. 따라서 함수의 존재성을 보장하기 위하여 집합을 만드는 새로운 합법적인 방법을 구축할 필요가 있다. 그 방법이 바로 이 선택공리이다.

• 이 공리는 대부분의 수학자들이 오늘날에 받아들였고 그들의 수학의 기반으로 삼고 있다. 그러나 역사적으로 선택공리을 받아들일 것인지에 대한 많은 논쟁이 있었다. 왜냐하면 선택공리를 가정하면 몇몇 수학자들이 받아들이기 힘들어하는 사실들이 증명되었기 때문이다. 그러한 정리 중 하나가 아래에서 살펴볼 well-ordering theorem 이다.

• \(c\) 를 집합족 \(\mathcal{B}\) 에 대한 선택함수라 한다. 선택공리와 이 정리의 차이점은 이 정리에는 서로소라는 조건이 없다는 것이다.

• 증명

  집합 \(B \in \mathcal{B}\) 에 대한 집합 \(B'\) 을 다음과 같이 정의하자.

  \[ B' = \{(B, x) : x \in B\} \]

  그러면 \(B' \displaystyle \subset \mathcal{B}\times \bigcup_{B \in \mathcal{B}}B\) 이다. \(B \neq \varnothing\) 이므로 \(B' \neq \varnothing\) 이다. 또한 서로 다른 \(B_1, B_2 \in \mathcal{B}\) 에 대하여 \(B'_1\) 와 \(B'_2\) 가 서로소임은 자명하다. 이제 다음과 같은 모임을 정의하자.

  \[ \mathcal{C} = \{B' : B \in \mathcal{B}\} \]

  선택공리에 의하여 \(\mathcal{C}\) 의 원소 \(B'\) 에서 원소를 하나만 선택하여 집합 \(c\) 에 포함시키는 방식으로 \(c\) 를 만들 수 있다. ▲

  이제 이 \(c\) 가 함수임을 보이려 한다. \(c\) 의 원소는 \(B'\) 에서 가져왔으므로 \(c \subset \mathcal{B} \times \displaystyle \bigcup_{B \in \mathcal{B}}^{}B\) 이다. 또한 \(c\) 는 \(B'\) 에서 오직 하나의 원소를 가져왔다. 따라서 함수의 정의에 의하여 \(c: \mathcal{B}\to \displaystyle \bigcup_{B \in \mathcal{B}}^{}B\) 이다. ▲

  \(c\) 가 함수임을 보였으니 \(c\) 가 선택함수임을 보이려 한다. \((B, x) \in c\) 이면 \(x \in B\) 이므로 \(C(B) \in B\) 이다. ■

• 이제 Theorem 9.1 의 \(3 \implies 1\) 을 선택함수를 사용하여 엄밀하게 증명해보자.

  • Theorem 9.1 의 \(3 \implies 1\) 증명(선택함수 사용)

    무한집합 \(A\) 에 대하여 단사함수 \(f:\Bbb{Z}_{+}\to A\) 의 존재성을 보이자. \(\mathcal{B} = \mathcal{P}(A) \setminus \varnothing\) 에 대하여 Lemma 9.2 는 다음과 같은 선택함수의 존재성을 보장한다.

    \[ c: \mathcal{B} \to \bigcup_{B \in \mathcal{B}}^{}B = A \]
    \[ \forall B \in \mathcal{B} : c(B) \in B \]

    이제 함수 \(f:\Bbb{Z}_{+}\to A\) 를 다음과 같이 정의하자.

    \[ f(1) = c(A) \]
    \[ i > 1 : f(i) = c(A - f(\{1, 2, \dots ,i-1\})) \]

    \(A\) 가 무한집합이므로 항상 \(A - f(\{1, 2, \dots ,i-1\}) \neq \varnothing\) 이고, 위와 같은 정의는 잘 정의되며 각 \(f(i)\) 들이 유일하게 정의된다. 따라서 \(f\) 는 단사함수이다. ■

  이렇게 Theorem 9.1 을 선택함수를 구체적으로 사용하여 엄밀하게 증명해보았다. 그러나 실제로 대다수의 수학자들은 구체적인 선택함수를 정의하여 사용하는 위와같은 엄밀한 증명을 하지는 않고, 다음과 같이 무한번의 임의의 선택을 하는 것으로 증명을 한다. 수학자들도 실제로 선택공리를 사용해야 한다는 것을 알고 있지만, 귀찮게 그렇게까지 엄밀하게 하지는 않는다. 그러나 수학자들은 선택함수를 꼭 언급해야 하는 상황이라면 선택공리를 사용하여 엄밀한 증명을 할 수 있다. 가령 선택함수를 구체적으로 정의하지 않으면 혼란이나 모호함이 발생하는 경우에서.

  • Theorem 9.1 의 \(3 \implies 1\) 증명(일반적인 방법)

    무한집합 \(A\) 에 대하여 단사함수 \(f:\Bbb{Z}_{+}\to A\) 의 존재성을 보이자. \(A \neq \varnothing\) 이므로 \(A\) 에서 원소 \(a_1\) 을 택하여 \(f(1) = a_1\) 으로 정의하자. 이미 정의된 \(f(1),\dots ,f(n-1)\) 에 대하여 \(A - f(\{1, 2, \dots , n -1\})\) 의 한 원소 \(a_n\) 를 택하여 \(f(n) = a_n\) 으로 정의하자. \(A\) 가 무한집합이므로 \(A - f(\{1, 2, \dots , n -1\}) \neq \varnothing\) 이다. 그러면 \(m < n\) 에 대하여 \(f(m) \in f(\{1, 2, \dots ,n -1\})\) 이지만 \(f(n) \not\in f(\{1, 2, \dots ,n -1\})\) 이다. 따라서 \(f(n) \neq f(m)\) 이다. ■

Well-Ordered Sets✔

• 집합론에서의 정렬집합의 정의도 있다.

• Well-ordering property 는 \(\Bbb{Z}_{+}\) 의 공집합이 아닌 부분집합이 최소원소를 가진다는 성질이다. 이 성질을 일반화시킨 개념이 well-ordered set 이다.

• 예시

  사전순서가 부여된 곱집합 \(\{1, 2\} \times \Bbb{Z}_{+}\) 는 다음과 같은 무한 수열이다.

  \[ \{1, 1\}, \{1, 2\}, \{1, 3\}, \dots ; \{2, 1\}, \{2, 2\}, \{2, 3\}, \dots \]

  이 집합의 임의의 부분집합에 최소원소가 있음은 자명하다. 즉, 이 곱집합은 정렬집합이다.

• 정렬집합을 만드는 방법은 다음과 같고, 이것들을 증명하는 것은 쉽다.

  1. 기존의 정렬집합의 순서관계를 보존한 부분집합은 정렬집합이다.

  2. 두 정렬집합 \(A, B\) 에 대하여 사전순서가 부여된 \(A \times B\) 는 정렬집합이다.

• 순서관계가 없는 유한집합 \(A\) 를 정렬집합으로 만드는 방법은 전단사 함수 \(f:A \to \{1, 2, \dots , n\}\) 를 사용하는 것이다. 전단사 \(f\) 를 통하여 \(A\) 에 \(\{1, 2, \dots , n\}\) 가 갖는 순서관계를 부여할 수 있다.

• 증명

Well-ordering theorem✔

• 이 정리는 집합론의 체르멜로 정렬정리에서도 소개했었고, 여기에 증명이 있다.

• 두번째 방법으로 정렬집합 \(\Bbb{Z}_{+}\) 에 대하여 \(\Bbb{Z}_{+}^{n}\) 이 정렬집합임을 보일 수 있다. 그러나 \(\Bbb{Z}_{+}\) 의 무한곱 \((\Bbb{Z}_{+})^{\omega }\) 도 정렬집합임을 보일 수 있을까? 이것은 어렵다. 실제로 누구도 \((\Bbb{Z}_{+})^{\omega }\) 에 구체적인 정렬순서를 부여할 수 없었다. 일반적으로 말하면, 가산 집합에 정렬순서를 부여하는 것은 쉽지만 비가산 집합에 정렬순서를 부여하는 것은 어려웠다. 그러나 체르멜로 정렬정리는 어찌되었든 그러한 정렬순서가 존재한다는 것을 보장해준다.

  선택공리를 가정했을 때 몇몇 수학자들이 받아들이기 힘든 사실들이 참이 된다고 말했었는데, 그 중 하나가 이 체르멜로 정렬정리이다. 체르멜로가 1904년 이 정리를 발표하자 수학계가 발칵 뒤집혔고, 이 정리의 증명이 올바른지에 대한 상당한 토론이 있었다. 또한 비가산 집합의 정렬 순서에 대한 구성적인 절차는 소개되지 않았기 때문에 회의감에 사로잡힌 수학자들도 있었다. 이 정리의 증명을 잘 살펴보면 무한번의 임의의 선택을 할 수 있다는 선택공리가 사용된다.

  그러나 몇몇 수학자들은 선택공리를 탐탁치 않아 했기에 이후 몇년간 새로운 정리가 소개될 때마다 "여기에 선택공리가 사용되었는가?" 라는 질문을 하곤 했다. 또한 선택공리 위에 증명된 정리는 흔들리는 땅 위에 세워진 정리라고 여겨졌다. 그러나 오늘날의 대다수의 수학자들은 선택공리를 의심하지 않는다. 선택공리는 이미 집합론의 공리로 인정되어 사용되고 있고, 이 체르멜로 정렬정리도 마찬가지로 잘 사용되고 있다.

• 그러나 앞으로의 논의에서 체르멜로 정렬정리의 모든 파워가 다 필요한 경우는 많지 않다. 좀 더 약한 정리인 이 정리를 사용하는 경우가 많을 것이다.

Section of Well-ordered Set✔

Minimal Uncountable Well-ordered Set✔

• \(S _{\Omega}\) 는 비가산 정렬 집합이며, 이것의 절편은 모두 가산이다. 이것의 순서관계는 조건에 따라서 유일하게 결정된다. 이것을 최소 비가산 정렬집합(minimal uncountable well-ordered set)이라고 부를 것이다. 또한 정렬집합 \(A = S _{\Omega} \cup \{\Omega\}\) 을 \(\bar{S}_{\Omega}\) 라고 표기한다.

• 증명

  가령 비가산 정렬 집합 \(B\) 에 대하여 사전순서가 부여된 정렬집합 \(C = \{1,2\}\times B\) 를 정의할 수 있다. 그러면 \(b \in B\) 에 대한 임의의 \(2 \times b\) 의 원소에 의한 \(C\) 의 절편은 비가산이다.

  \(C\) 의 절편이 비가산이 되게 하는 가장 작은 원소를 \(\Omega\) 라고 하자. 그러면 \(\Omega\) 에 의한 \(C\) 의 모든 절편으로 집합 \(A\) 를 만들 수 있다. 이 \(A\) 가 존재성을 증명하고자 하는 집합이다. ■

• 최소 비가산 정렬집합 \(S _{\Omega}\) 란 비가산 정렬 집합이고, 이것의 절편은 모두 가산임을 뜻한다.

• 최소 비가산 정렬집합의 가장 유용한 성질이 이 정리이다.

• 증명

  각 \(a \in A\) 에 대한 \(S_a\) 는 가산이므로 \(B = \bigcup_{a \in A}^{}S_a\) 도 가산이다. \(S _{\Omega}\) 는 비가산이므로 \(B \subsetneq S _{\Omega}\) 이다. 그러면 어떤 \(x \in S _{\Omega} \setminus B\) 가 존재하고 이 \(x\) 는 \(A\) 의 상계이다. 왜냐하면 만약 \(\exists a \in A:x < a\) 이면 \(x \in S_a \implies x \in B\) 이므로 모순이기 때문이다. ■