Set

Proposition✔

• 예시

  "\(5\) 는 자연수이다." 는 명제이다.

• 명제의 부정을 \(\neg p\) 로 표기한다.

• 예시

  명제 \(p\) "\(5\) 는 자연수이다." 의 부정 \(\neg p\) 은 "\(5\) 는 자연수가 아니다." 이다.

• 예시

  명제 \(p\) 가 참이면 부정 \(\neg p\) 은 거짓이 되고, 거짓이면 참이 되는데 이것을 표로 정리하면 다음과 같다.

  \(p\)	\(\neg p\)	\(\neg (\neg p)\)
  \(T\)	\(F\)	\(T\)
  \(F\)	\(T\)	\(F\)

  진리표를 통하여 \(p\) 와 \(\neg (\neg p)\) 의 옳고 그름이 같다는 것을 알 수 있다.

• "\(p \lor q\)" 는 \(p\)와 \(q\) 중 하나만 참이어도 \(p \lor q\) 가 참이 된다.

• 예시

  명제 "\(18\)은 \(4\)의 배수이거나 \(6\)의 배수이다." 는 명제 "[\(18\)은 \(4\)의 배수이다.] \(\lor\) [\(18\)은 \(6\) 의 배수이다.]" 이다.

• \(p \lor q\), 즉 "\(p\) 또는 \(q\)" 의 부정은 "\(p\)도 아니고 \(q\)도 아니다.", 즉 \((\neg p) \land (\neg q)\) 이다.

  • 예시

    "그곳에 풀이나 나무 중 적어도 한 가지가 있었다." 의 부정은 "그곳에 풀도 없었고 나무도 없었다." 가 된다.

  • 위 예시로 \(\neg (p \lor q) \equiv (\neg p) \land (\neg q)\) 임을 알 수 있다.

• 그러므로 진리표는 다음과 같다.

  \(p\)	\(q\)	\(p \lor q\)	\(\neg (p \lor q)\)	\((\neg p) \land (\neg q)\)
  \(T\)	\(T\)	\(T\)	\(F\)	\(F\)
  \(T\)	\(F\)	\(T\)	\(F\)	\(F\)
  \(F\)	\(T\)	\(T\)	\(F\)	\(F\)
  \(F\)	\(F\)	\(F\)	\(T\)	\(T\)

• "\(p \land q\)" 는 \(p\)와 \(q\) 가 둘 다 참이어야 \(p \land q\) 가 참이 된다.

• 진리표는 다음과 같다.

  \(p\)	\(q\)	\(p \land q\)	\(\neg (p \land q)\)	\((\neg p) \lor (\neg q)\)
  \(T\)	\(T\)	\(T\)	\(F\)	\(F\)
  \(T\)	\(F\)	\(F\)	\(T\)	\(T\)
  \(F\)	\(T\)	\(F\)	\(T\)	\(T\)
  \(F\)	\(F\)	\(F\)	\(T\)	\(T\)

• "\(p\) 이면 \(q\) 이다" 로 읽는다. 이 명제의 부정은 \(p\)는 성립하지만 \(q\) 는 성립하지 않는 것이다. 그러므로 다음이 성립한다.

  \[ \neg (p \implies q) \equiv p \land (\neg q) \]

  이것을 다시 쓰면 다음과 같다.

  \[ p \implies q \equiv \neg p \lor q \]

  그러므로 진리표는 다음과 같다.

  \(p\)	\(q\)	\(\neg p \lor q\)	\(p \implies q\)
  \(T\)	\(T\)	\(T\)	\(T\)
  \(T\)	\(F\)	\(F\)	\(F\)
  \(F\)	\(T\)	\(T\)	\(T\)
  \(F\)	\(F\)	\(T\)	\(T\)

  그러므로 \(p\) 가 거짓이면 \(p \implies q\) 는 항상 참이다. 이것을 공진리라고 한다.

• \(p \implies q\) 이고 \(q \implies p\) 일 때, \(p \iff q\) 라고 한다.

• 예시

  \(x \in \R\) 에 대하여 명제 \(x ^{2} < 0 \implies x = 23\) 은 항상 참이다.

• 증명

  이는 \(x \in \varnothing\) 이면 \(x \in A\) 임을 증명하는 것과 같다. 가정이 거짓이므로 공진리다. ■

• 예시

  변수 \(x\) 를 포함하는 문장 "\(x\) 는 \(6\) 의 약수이다." 는 \(x\) 가 초기화됨에 따라 명제가 되므로 조건이다.

Set✔

• 어떤 대상이 특정 집합에 속해있으면 그 대상을 집합의 원소라고 한다.

• 원소 \(a\) 가 집합 \(A\) 에 속해있으면

  \[ a \in A \]

  로 표현하고 원소 \(a\) 가 집합 \(A\) 에 속해있지 않으면

  \[ a \not \in A \]

  로 표현한다.

• 1895년 칸토어가 집합론을 처음 발표했을 때 그가 내린 집합의 정의는 "직관이나 사고를 통해 명확히 구별할 수 있는 대상을 하나의 전체로 묶어 놓은 것"이다.

• 예시

  키가 \(160\)cm 이상인 학생들의 모임

  대한민국 국적을 가진 사람들의 모임

• 집합은 다음 \(3\) 가지 방법으로 표현할 수 있다.

  1. 원소나열법 : \(\{ \}\) 안에 집합의 모든 원소를 나열하는 것이다. 가령, \(A = \{ \text{재석, 명수, 준하}\}\).

  2. 조건제시법 : \(\{x:x \text{의 조건}\}\) 과 같이 모든 원소들의 공통된 성질을 제시하는 방법이다. 원소나열법으로 집합을 나타내기 어려운 경우 자주 사용된다. 가령, \(A = \{x:x \text{ 는 대한민국 국적을 가진 사람 }\}\).

  3. 벤다이어그램 : 도형을 통하여 집합을 나타내는 방법이다.

• 집합은 다음과 같이 분류된다.

  • 유한집합 : 원소의 개수가 유한한 집합이다.

  • 무한집합 : 원소의 개수가 무한한 집합이다.

  • 공집합 : 원소가 하나도 없는 집합 \(\varnothing\) 이다.

• 예시

  변수 \(x\) 에 대한 조건 "\(x\) 는 \(6\) 의 약수이다." 의 진리집합은

  \[ P = \{x:x\text{는 6 의 약수} \} \]

  이다. 이때 "\(x \in P\)" 와 "\(x\) 는 \(6\) 의 약수" 는 같다.

• 조건은 이미 존재하는 집합을 상정하고 그 집합에 특정 조건을 가하여 얻은 부분집합으로 구성하는 경우가 많다.

  만약 전체집합을 \(U\) 로 가정하는 경우 조건 \(p(x)\) 를 집합 \(U\) 에서 정의했다고 한다.

• 예시

  변수 \(x\) 에 대한 조건 "\(x\) 는 \(6\) 의 약수이다." 은 자연수 집합 \(\Bbb{N}\) 을 상정하고 정의된 것이므로 진리집합을 더 엄밀하게 쓰면

  \[ P = \{x \in \Bbb{N}:x\text{는 6 의 약수} \} = \{1,2,3,6\}\]

  이 된다.

• 두 집합이 서로 같다는 것은 서로가 서로의 부분집합이라는 것이다. 임의의 두 집합 \(A, B\) 가 서로 같다는 것은 \(A \subset B\) 와 \(B \subset A\) 를 만족한다는 것이고 \(A = B\) 로 표현한다.

• \(x \in A\) 는 조건 \(p\) 를 참이되게 하는 \(A\) 의 원소 \(x\) 에 대한 것이므로 참이 된 조건 \(p\) 를 뜻한다.

  그러므로 \(x \in A\) 라는 표기는 참과 거짓이 정해졌으므로 더 이상 조건이 아니라 명제를 뜻한다.

• 조건 \(p(x)\) 의 진리집합 \(P\) 에 대하여 명제 "어떤 \(x\) 에 대하여 \(p(x)\) 이다." 는 어떤 \(x\) 에 대하여 \(p(x)\) 가 참이되게 하는 \(x\) 가 하나 이상 있다는 뜻이다. 그러므로 이 명제는

  \[ P \neq \varnothing \]

  와 같다. 이것을 부정하면 \(P = \varnothing\) 인데, 이것은 곧 \(P ^{c} = U\) 이므로

  \[ U = P ^{c} = \{x|\neg p(x)\} \]

  이고, 이것을 말로 설명하면 "임의의 \(x\) 에 대하여 \(\neg p(x)\) 이다." 이다.

  그러므로 \(\neg [\text{어떤 x 에 대하여 p(x)}] \equiv \text{임의의 x 에 대하여} \neg \text{p(x)}\) 즉,

  \[ \neg [\exists x, p(x)] \equiv [\forall x, \neg p(x)] \]

  이다. 마찬가지로

  \[ \neg [\forall x, p(x)] \equiv [\exists x, \neg p(x)] \]

  이다.

• 예시

  "임의의 \(a < 0\) 에 대하여 \(x \geq a\) 이다." 는 변수 \(x\) 에 관한 조건인데, 이것의 대우명제는 "\(x<a\) 인 음수 \(a<0\) 이 존재한다." 이다.

• \(A\) 가 \(B\) 의 부분집합이라는 것을 \(A \subset B\) 라고 표기한다.

• 집합 \(A\) 의 모든 원소가 집합 \(B\) 에 속하면 집합 \(A\) 는 집합 \(B\) 의 부분집합이다. 따라서 모든 집합은 자기 자신의 부분집합이다. 이것은 \(A \subset A\) 로 표현된다.

• 공집합은 모든 집합의 부분집합이다. 이것은 \(\varnothing \subset A\) 로 표현된다.

• \(A\) 가 \(B\) 의 부분집합이 아니라는 것을 \(A \not \subset B\) 이라고 표현한다.

• 예시

  세 집합 \(A, B, C\) 가 \(A = \{a, b, c\}, B = \{a, b, c, d, e\}, C = \{d, e, f, g\}\) 일 때 집합 \(A\) 의 원소가 모두 \(B\) 에 속하지만 \(C\) 의 원소가 \(B\) 에 속하지는 않는다. 따라서 다음이 성립한다.

  \[ A \subset B \]
  \[ C \not \subset B \]

• 조건 \(p\) 의 진리집합이 \(P\) 이면 그 부정 \(\neg p\) 의 진리집합은 \(P ^{c}\) 이다.

• 증명

  \[ x \in (A ^{c})^{c} \iff \neg (x \in A ^{c}) \iff \neg (\neg x \in A) \iff x \in A \]

• 전체집합 \(U\) 에 대하여 다음이 성립한다.

  • \(\varnothing ^{c} = U, U ^{c} = \varnothing\)

  • \(A \cup A ^{c} = U, A \cap A ^{c} = \varnothing\)

• 집합 \(X\) 속의 집합족이란 \(X\) 의 부분집합으로 이루어진 집합이다.

  즉, \(X\) 속의 집합족은 \(X\) 의 멱집합 \(\mathcal{P}(X)\) 의 부분집합 \(\mathcal{F} \subseteq \mathcal{P}(X)\) 이다.

• 예시

  집합 \(\{\{2, \{3\}\}, \{1\}, \{5,6\}\}\) 은 모든 원소가 집합이므로 집합족이다.

  임의의 집합 \(X\) 에 대하여 공집합 \(\varnothing\) 과 \(X\) 의 멱집합 \(\mathcal{P}(X)\) 은 \(X\) 속의 집합족이다.

Union✔

• 정의에 따라 조건 \(p, q\) 의 진리집합 \(P, Q\) 에 대하여 조건 \(p \lor q\) 의 진리집합은 \(P \cup Q\) 이다.

• 예시

  \[ \{1,2,3\}\cup \{3,4\}=\{1,2,3,4\} \]
  \[ A \cup B \cup C = \{x : x \in A \lor x \in B \lor x \in C\} \]

• 가산 개의 집합의 합집합

  자연수 개수만큼 무한히 많은 집합을 다음과 같이 일렬로 나열 가능하다면,

  \[ A, B, C, D , \dots \]

  다음과 같이 이들에게 자연수를 매길 수 있다.

  \[ A_1, A_2, A_3, A_4, \dots \]

  이때 이것들의 합집합을 다음과 같이 표기한다.

  \[ A_1 \cup A_2 \cup \dots = \bigcup_{i=0}^{\infty}A_i =\bigcup_{i \in \Bbb{N}}^{}A_i = \{x: \exists i \in \Bbb{N}, x \in A_i\} \]

• 임의의 첨수족의 합집합

  자연수 \(\Bbb{N}\) 으로 번호를 매기는 것은 과하거나(유한 개의 집합들), 적당하거나(자연수 개수만큼 많은 집합들), 부족(비가산 개의 집합들)할 수 있다.

  그러므로 적당한 첨수 \(i \in I\) 를 부여받은 집합 \(A_i\) 들의 합집합(적어도 한 집합의 원소인 대상들의 집합)을 다음과 같이 표기할 수 있다.

  \[ \bigcup_{i \in I}^{}A_i := \{x : \exists i \in I, x \in A_i\} \]

• 예시

  만일 \(I = \{1,2\}\) 이면 집합족은 \(\mathcal{A} = \{A_1, A_2\} = \{A_i : i \in \{1,2\}\}\) 이고 합집합은

  \[ \bigcup_{i \in I}^{} A_i = \bigcup_{}^{}\{A_i : i \in I\} = \bigcup_{}^{}\mathcal{A} = \bigcup_{}^{}\{A \in \mathcal{A}\} = \bigcup_{}^{}\{X \in \mathcal{A}\} = A_1 \cup A_2 \]

  이다.

• 임의의 합집합

  집합족 \(\mathcal{M}\) 의 합집합은 그에 속하는 집합들의 모든 원소를 합쳐놓은 집합

  \[ \bigcup_{}^{}\mathcal{M} = \bigcup_{A \in \mathcal{M}}^{} A := \{x : \exists A \in \mathcal{M}, x \in A\} \]

  이다. 이는 가산 개의 집합의 합집합과 임의의 첨수족의 합집합을 모두 포함하는 일반적인 정의이다.

• 예시

  각 양수 \(r>0\) 에 대하여 \(A_r = \{x \in \R : x \geq r\}\) 이라 두면

  \[ \bigcup_{r>0}^{} A_r = \{x \in \R : x > 0\} \]

  이 된다. \(A = \{x \in \R : x > 0\}\) 라 두면 각 \(r>0\) 에 대하여 \(A_r \subset A\) 이므로 \(\bigcup_{r>0}^{}A_r \subset A\) 이다. 역으로 \(A \subset \bigcup_{r>0}^{}A_r\) 을 증명하는 것은

  \[ x>0 \implies \exists r > 0 \text{ s.t. } x \geq r \]

  을 증명하는 것이다. \(r = x\) 라 두면 \(0 < r \leq x\) 이므로 \(A \subset \bigcup_{r>0}^{}A_r\) 이 성립하므로 \(A = \bigcup_{r>0}^{}A_r\) 이다.

  사실 양수 전체의 집합을 \(P\) 로 두고 \(\bigcup_{r \in P}^{}A_r\) 와 같이 표현해야 하지만, 관례상 \(\bigcup_{r>0}^{}A_r\) 와 같이 쓴다.

Intersection✔

• 정의에 따라 조건 \(p, q\) 의 진리집합 \(P, Q\) 에 대하여 조건 \(p \land q\) 의 진리집합은 \(P \cap Q\) 이다.

• 집합 \(A_1,A_2,A_3,A_4,A_5\) 의 교집합은 \(A_1 \cap A_2 \cap A_3 \cap A_4 \cap A_5\) 으로 나타낼 수 있는데, 이것을 다음과 같이 나타낼 수 있다.

  \[ \bigcap_{i=1}^{5}A_i \]

  이때 다음이 성립한다.

  \[ x \in \bigcap_{i \in I}^{}A_i \iff \forall i \in I, x \in A_i \]

• 집합족 \(\mathcal{A}\) 의 교집합은 \(\mathcal{A}\) 의 모든 원소에 동시에 속하는 대상으로 이루어진 다음과 같은 집합이다.

  \[ x \in \bigcap_{}^{}\mathcal{A} \iff \forall A \in \mathcal{A}, x \in A \]

• 증명 6)

  \[ x \in (A \cup B) ^{c} \iff \neg (x \in A \lor x \in B) \]
  \[ \iff (x \not \in A) \land (x \not \in B) \iff (x \in A ^{c}) \land (x \in B ^{c}) \]
  \[ \iff x \in A ^{c} \cap B ^{c} \]

• 증명 1)

  \[\displaystyle \bigg (\bigcup_{i \in I}^{}A_i\bigg ) ^{c} = \bigcap_{i \in I}^{} A_i ^{c} \iff x \not \in \bigcup_{i \in I}^{} A_i\]
  \[ \iff \neg (\exists i \in I, x \in A_i) \iff \forall i \in I, x \not \in A_i\]
  \[ \iff \forall i \in I, x \in A_i ^{c} \iff x \in \bigcap_{i \in I}^{} A_i ^{c} \]

Difference✔

• 집합의 뺄셈을 \(A - B\) 로도 표기하고 \(A \setminus B\) 로도 표기한다.

Disjoint✔

• 서로소인 집합족의 합집합을 다음과 같이 표현한다.

  \[ \bigsqcup_{i \in I}^{}A_i \]

Rules of Set Theory✔

• \(I\) 가 비가산 집합이어도 된다.

Tuple✔

• 두 원소 \(a,b\) 로 이루어진 집합은 \(\{a,b\}=\{b,a\}\) 이지만, 순서쌍은 \(a \neq b\) 일 때 \((a,b) \neq (b,a)\) 이다.

• 곱집합, 함수, 이항관계 등이 순서쌍을 이용해 정의된다.

• 순서쌍의 성분은 스칼라, 벡터, 다른 순서쌍일 수도 있다.

• 순서쌍으로 n-tuple 을 귀납적으로 정의할 수 있다. 가령, 3-튜플 순서쌍을 \((a,b,c) := (a, (b, c))\) 로 정의할 수 있다.

• 순서쌍의 가장 기본적인 성질은 두 순서쌍이 같을 필요충분조건이 두 성분이 각각 같은 것이라는 것이다. 즉,

  \[ (a,b) = (c,d) \iff (a = c) \land (b = d) \]

• 보통 순서쌍을 \((a,b)\) 로 표현하지만 열린구간과 혼동하지 않기 위하여 \(\big <a, b\big >\) 또는 \(a \times b\) 로 나타내기도 한다.

• 증명

  \(a=b\) 인 경우

  \[\{\{a\}\} = (a, b) = (c,d) = \{\{c\},\{c,d\}\}\]

  에서 \(\{a\}=\{c\}=\{c,d\}\) 이므로 \(a=b=c=d\) 이다.

  \(a \neq b\) 인 경우 \(\{a,b\}\) 는 두 원소의 집합이므로 한 원소의 집합이 아니다. 그러므로

  \[ \{c\} \in \{\{c\},\{c,d\}\} = \{\{a\}, \{a,b\}\} \]

  에서 명백하게 \(\{c\} \neq \{a,b\}\) 이다. 그러므로 당연히

  \[ \{c\}=\{a\} \implies a = c \]

  이다. 마찬가지로

  \[ \{a,b\} \in \{\{a\}, \{a,b\}\} = \{\{c\}, \{c,d\}\} \]

  에서 명백하게 \(\{a,b\}\neq \{c\}\) 이다. 그러므로 당연히

  \[ \{a,b\} = \{c,d\} \]

  인데 \(b \in \{c,d\} = \{a,b\}\) 로부터 \(b=c\) 또는 \(b=d\) 이다.

  그런데 \(b=c\) 이면 \(a=c=b\) 이므로 모순이다. 그러므로 \(b=d\) 이다.

Product Set✔

• 예시

  집합 \(X\) 와 \(\forall A \in 2 ^{X}\) 에 대하여 \(\Phi (A) \in \{0,1\}^{X}\) 를

  \[ \Phi (A)(x) = \begin{cases} 1 &x \in A\\ 0 &x \not \in A\\ \end{cases} \]

  로 정의하자. 또 임의의 함수 \(f \in \{0,1\}^{X}\) 에 대하여 \(X\) 의 부분집합 \(\Psi (f) \in 2 ^{X}\) 를

  \[ \Psi (f) = \{x \in X : f(x) = 1\} \]

  라 정의하자. ▲

  그러면 임의의 \(f: X \to \{0,1\}\) 에 대하여

  \[ \Phi (\Psi (f))(x) = 1 \iff x \in \Psi (f) \iff f(x) = 1 \]

  이므로 \(\Phi (\Psi (f)) = f\) 이다. 또한 임의의 \(A \in 2 ^{X}\) 에 대하여

  \[ x \in \Psi (\Phi (A)) \iff \Phi (A)(x) = 1 \iff x \in A \]

  이므로 \(\Psi (\Phi (A))=A\) 이다. (\(\Psi(f)\) 는 \(f\) 가 \(1\) 이 되게 하는 정의역 집합인데, \(\Psi (\Phi (A))\) 이므로 \(\Phi (A)\) 가 \(1\) 이 되게 하는 정의역 집합이다. 근데 \(\Phi (A)\) 란 \(x\) 가 \(A\) 에 속하면 \(1\) 이므로 결국 \(A\) 의 원소들로 구성된다.)

  그러므로 두 함수

  \[ \Psi : 2 ^{X} \to \{0,1\} ^{X}, \quad \Psi : \{0,1\}^{X}\to 2 ^{X} \]

  는 서로 역함수이다.

• 물론 어느 함수 \(f\) 는 실제로는 곱집합 \(I \times \bigcup_{i \in I}^{}X_i\) 의 부분집합으로써

  \[ \{(i_1, x_1), (i_2, x_2), \dots, (i_n, x_n), \dots\} \]

  와 같은 \(I\) 에서 \(\bigcup_{i \in I}^{}X_i\) 로 가는 함수지만, 이것을

  \[ (x_1, x_2, \dots, x_n, \dots) \]

  으로 표기하자고 약속하는 것이다.

• 위 정의에서 \((\bigcup_{i \in I}^{}X_i) ^{I}\) 는 \(I\) 에서 \(\bigcup_{i \in I}^{}X_i\) 로 가는 함수 전체의 집합을 뜻한다.

• 임의의 \(i \in I\) 에 대하여 \(X_i = X\) 이면 \(\prod_{i \in I}^{}X_i = X ^{I}\) 이다.

• 예시

  \(\R\) 을 \(n \in \N\) 개 곱한 곱집합 \(\R ^{n}\) 에서 \(n = \{0,1,2, \dots, n-1\}\) 이므로 \(\R ^{n}\) 는 \(n \to \R\) 인 함수 전체의 집합

  \[ \prod_{i=1}^{n}\R = \{f \in \R ^{n} : f(i) \in \R, i \in n \} \]

  이다. 그리고 \(n = \{0,1,2,\dots,n-1\}\) 을 \(\R\) 로 대응시키는 어느 함수

  \[ i \mapsto a_i, \quad i = 0,1,2,\dots,n-1 \]

  는 실제로

  \[ \{(0, a_0), (1, a_1), (2, a_2), \dots, (n-1, a _{n-1})\} \]

  와 같은 곱집합 \(n \times X\) 의 부분집합이지만,

  \[ (a_0, a_1, a_2, \dots, a _{n-1}) \]

  라고 표시한다.

• 유한개의 집합 \(A_1, A_2, \dots, A_n\) 의 곱집합 \(A_1 \times A_2 \times \dots \times A_n\) 은

  \[ A_1 \times A_2 \times \dots \times A_n = \{(a_1, a_2, \dots, a_n) : a_i \in A_i\} \]

  이다. 이것을 간단하게 표기하여 집합 \(A, I\) 에 대하여 \(A\) 의 \(I\) 번 곱집합 \(A ^{I}\) 는

  \[ A ^{I} = \{(a_i) _{i \in I} : a_i \in A\} \]

  이다.

• 예시

  우리에게 익숙한 데카르트 공간 \(\Bbb{R} ^{2}\), 즉 직교좌표계는

  \[ \R ^{2} = \Bbb{R} \times \Bbb{R} = \{(x,y) : x, y \in \R \}\]

  로써 곱집합이다. 또한 공간좌표계는

  \[ \R ^{3} = \Bbb{R} \times \Bbb{R} \times \R = \{(x,y, z) : x, y, z \in \R \}\]

  이다.

• 증명

Power set✔

• 즉, 집합 \(S\) 의 멱집합 \(\mathcal{P}(S)\) 또는 \(2 ^{S}\) 는

  \[ \mathcal{P}(S) = 2 ^{S} := \{A: A \subseteq S\} \]

  이다.

• 예시

  집합 {x,y,z} 의 멱집합 원소들의 부분 집합 관계는 다음과 같은 헤세 도형으로도 표현할 수 있다.

  

Function✔

• 함수란 \(X\) 의 원소를 \(Y\) 로 대응시키는 규칙, 또는 법이다.

• \((x,y) \in f\) 일 때 \(f(x) = y\) 또는 \(f: x \mapsto y\) 라고 쓴다. 집합 \(X\) 를 \(f\) 의 정의역, \(Y\) 를 \(f\) 의 공역이라고 하고, \(f: X \to Y\) 라고 쓴다. \(f: x \mapsto y, X \to Y\) 는 \(f: X \to Y\) 가 함수이고 \((x, y) \in f\) 라는 뜻이다.

• \(X_0 \subset X\) 에 대하여 \(f(X_0)\) 은 \(X_0\) 의 모든 원소의 상의 집합이다. \(Y_0 \subset Y\) 에 대하여 \(f ^{-1}(Y_0) = \{x \in X: f(x) \in Y_0\}\) 를 역상(inverse image) 또는 원상(preimage) 라 한다.

• 정의역과 공역은 공집합이 아니라고 간주하자.

• 1830년대 독일 수학자 디리클레가 함수의 이론적 기반을 정립하는데 크게 기여했다. 그가 함수의 기반을 정립하려 애쓴 것은 푸리에 급수의 수렴성에 대한 문제 때문이었다.

• 예시

  데카르트 공간 \(\Bbb{R} ^{2}\), 즉 직교좌표계의 부분집합 \(x ^{2}+y ^{2} = 4\) 는 함수가 아니다. \((0, -2), (0, +2)\) 가 이 관계에 속하는데 이는 함수의 두번째 조건을 위배하기 때문이다.

Function Equality✔

• 증명

  \(f = g\) 이면 임의의 \(x \in X\) 에 대하여

  \[ y = f(x) \iff (x, y) \in f \iff (x, y) \in g \iff y = g(x) \]

  이므로 \(f(x) = g(x)\) 이다. ▲

  반대로 임의의 \(x \in X\) 에 대하여 \(f(x) = g(x)\) 이면

  \[ (x,y) \in f \iff y = f(x) \iff y = g(x) \iff (x,y) \in g \]

  이므로 \(f=g\) 이다. ■

Identity Function✔

• 즉, 항등함수는 \(x \in X\) 에 대하여

  \[ 1 _{X}(x) = x \]

  이다.

• 항등함수를 \(1_X\) 로도 표기하고 \(\text{ id }_X\) 로도 표기한다.

Inclusion Function✔

• 포함함수를 보통 \(\iota _{A}:A \hookrightarrow X\) 와 같이 표기한다.

• 즉 포함 함수란 정의역이 공역의 부분 집합이며, 정의역의 모든 원소를 자신으로 대응시키는 함수이다.

• 모든 포함함수는 단사 함수이다.

• 모든 단사 함수는 전단사 함수와 포함 함수의 합성이다.

• 즉, 두 함수 \(f,g\) 가 같은 함수일 필요충분조건이 \(x \in X\) 에 대하여 \(f(x)=g(x)\) 라는 것이다.

• 증명

  \(f = g\) 이면 (이는 곱집합의 부분집합으로써의 \(f\) 와 \(g\) 가 서로 같다는 것이다. 즉, 단지 두 집합이 서로 같다는 것이다.) \(\forall x \in X\) 에 대하여

  \[ y = f(x) \iff (x,y) \in f \iff (x,y) \in g \iff y = g(x) \]

  이므로 \(f(x) = g(x)\) 이다.

  역으로 \(\forall x \in X\) 에 대하여 \(f(x) = g(x)\) 이면 (이는 두 함수 \(f, g\) 의 상이 서로 같다는 것이다. 즉, 두 함수의 함숫값이 같다는 거지.)

  \[ (x, y) \in f \iff y = f(x) \iff y = g(x) \iff (x, y) \in g \]

  이므로 \(f = g\) 이다.

Restriction✔

• 그냥 \(f\) 의 대응 규칙을 유지한 채 정의역만 \(A\) 로 줄인 함수이다.

Composite Function✔

• \(f\) 와 \(g\) 는 각각 곱집합 \(X \in Y\) 와 \(Y \times Z\) 의 부분집합이므로

  \[ g \circ f = \{(x, z) \in X \times Z: (\exists y) ((x, y) \in f, (y, z) \in g)\} \]

  와 같이 정의할 수도 있다. 이는 \((x, y) \in f, (y, z) \in g\) 인 \(y\) 가 존재한다는 말이다.

Composite Function satisfies Associativity✔

• 증명

  합성함수의 정의에 의하여 각 \(x \in X\) 에 대하여

  \[ h \circ (g \circ f)(x) = h(g \circ f(x)) = h(g(f(x))) = h \circ g(f(x)) = (h \circ g) \circ f(x) \]

  이다. 그러므로

  \[ h \circ (g \circ f) = (h \circ g) \circ f \]

  이다. ■

Injection✔

• 즉, 단사 함수는 다음과 같이 정의역의 서로 다른 원소를 공역의 서로 다른 원소로 대응시키는 함수이다.

  

• 즉, 이 정리는 \(x\) 를 \(y\) 로 보내면 그 \(y\) 를 다시 \(x\) 로 보낼 수 있음을 말하고 있다. 전사함수라면 이렇게 할 수 없을 수도 있는데, \(y\) 에 대응되는 \(x\) 가 유일하지 않을 수도 있기 때문이다.

• 증명

  \(g \circ f = 1 _{X}\) 를 만족하는 \(g\) 가 있으면

  \[ f(x_1) = f(x_2) \implies x_1 = (g \circ f)(x_1) = (g \circ f)(x_2) = x_2 \]

  이므로 \(f\) 가 단사함수의 조건을 만족하여 단사함수가 된다.

  이제 역으로 \(f\) 가 단사함수라면 \(g \circ f = 1 _{X}\) 인 함수 \(g: Y \to X\) 가 존재함을 보이기 위하여

  \[ B = \{y \in Y: f(x) = y \text{ 를 만족하는 } x \in X \text{ 가 존재한다}\} \]

  라고 두자. 즉, \(B = \operatorname{ran} f\) 이다. \(y \in B\) 이면 \(f\) 가 단사함수라는 가정에 의하여 \(f(x) = y\) 를 만족하는 \(x \in X\) 가 유일하게 존재하는데, 이때 함수 \(g\) 를 \(g(y) = x\) 라고 정의하자. 만약 \(y \not \in B\) 이면 \(g(y)\) 는 아무렇게나 정의하자.

  가령 \(X\) 의 한 원소 \(x_0 \in X\) 에 대하여

  \[ g(y) = \begin{cases} x, &y \in B, y = f(x) \\ x_0,& y \not \in B\\ \end{cases} \]

  라고 정의하는 것이다. 그러면

  \[ g \circ f = 1 _{X} \]

  임이 바로 확인된다. 왜냐하면 어차피 정의역의 원소 \(x_0\) 에 대응되는 치역의 원소 \(y\) 가 존재하지 않는다면 이 원소 \(x_0\) 에 대한 함수 \(f\) 는 정의되지 않기 때문에 결국 우리는 \(g(y) = x\) 만 생각하면 되기 때문이다. 그렇다면 \(g(f(x)) = x\) 이므로 \(g \circ f\) 는 항등함수 \(1 _{X}\) 가 된다. ■

Surjection✔

• 예시

  

• 즉, 이 정리는 \(y\) 를 \(x\) 로 보내면 그 \(x\) 를 다시 \(y\) 로 보낼 수 있음을 말하고 있다. 단사함수라면 이렇게 할 수 없을 수도 있는데, \(y\) 에 대응되는 \(x\) 가 존재하지 않을 수도 있기 때문이다.

• 증명

  먼저 \(f \circ g = 1 _{Y}\) 를 만족하는 함수 \(g: Y \to X\) 가 존재한다고 가정하자. 각 \(y \in Y\) 에 대하여 \(x=g(y)\) 라 두면 \(f \circ g\) 이 항등함수라고 하였으므로

  \[ f(x) = f(g(y)) = y \]

  이다. 그러면 이 관계에 의하여 임의의 \(y \in Y\) 가 함수 \(g\) 와 \(f\) 를 통하여, 즉 정의역의 원소 \(x\) 를 통하여 다시 \(y\) 로 대응되므로 전사함수의 조건이 성립하여 \(f\) 가 전사함수가 된다.

  이제 역으로 \(f\) 가 전사함수이면 \(f \circ g = 1 _{Y}\) 인 \(g\) 가 존재함을 보이기 위하여

  \[ A_y = \{x \in X: f(x) = y\} \]

  라고 두면 \(A_y \neq \varnothing\) 이다. 왜냐하면 \(f\) 가 전사함수이므로 \(Y\) 의 모든 원소가 \(X\) 의 적당한 원소로 대응되기 때문이다. 이때 각 \(y \in Y\) 에 대하여 \(A_y\) 의 원소 \(x\) 를 택하여 이 \(x\) 를 \(x = g(y) \in X\) 라 두면

  \[ f(g(y)) = y \]

  이다. ■

• 위 증명에서 \(A_y\) 의 원소를 하나 택한다고 하였는데 이렇게 하나씩 택하는 것이 가능한가에 대한 문제는 좀더 신중한 접근이 필요하다. 한편 이것이 가능하다고 가정하는 것이 선택공리이다.

Bijection✔

• \(\exists !\) 는 유일한 존재성을 표현한다.

• 즉, 전사이면서 동시에 단사인 함수를 전단사함수라 한다.

• 예시

  

Inverse Function✔

• \(f\) 의 역함수 \(g\) 를 \(f ^{-1} : Y \to X\) 로 표기한다.

• 예시

  함수 \(f: \N \to \Bbb{Z}\) 를

  \[f(2n) = -n, \qquad f(2n-1) = n\]

  이라 정의하면 그 역함수 \(g: \Bbb{Z} \to \N\) 는

  \[ g(n) = 2n-1, g(-n) = 2n \]

  가 된다.

• \(X_0 \subset X, Y_0 \subset Y\) 에 대하여 \(f ^{-1}(f(X_0)) = X_0, f(f ^{-1}(Y_0)) = Y_0\) 이 일반적으로 성립하지 않는다. 일반적으로 다음이 성립한다.

  \[ X_0 \subset f ^{-1}(f(X_0)) \]
  \[ f(f ^{-1}(Y_0)) \subset Y_0 \]

  \(f\) 가 단사이면 첫번째 포함관계가 등식이 된다. \(f\) 가 전사면 두번째 포함관계가 등식이 된다.

• 증명

  \(g\) 와 \(h\) 가 \(f\) 의 역함수라면

  \[ g = 1 _{X} \circ g = (h \circ f) \circ g = h \circ (f \circ g) = h \circ 1 _{Y} = h \tag{1} \]

  가 된다.

• 증명

  정리 1.2.2 와 정리 1.2.3 에 의하여 증명이 된다.

• 함수 \(f: X \to Y\) 가 전단사 함수이면 \(h \circ f = 1 _{X}\) 인 \(h: Y \to X\) 와 \(f \circ g = 1 _{Y}\) 인 \(g: Y \to X\) 가 존재하는데, \((1)\) 에 의하여 \(g = h\) 가 되어 \(f\) 의 역함수가 된다.

• 함수 \(f: X \to Y\) 와 \(A \subset X, B \subset Y\) 에 대하여

  \[ f ^{-1}(B) = \{x \in X:f(x) \in B\} \]
  \[ f (A) = \{f(x) \in Y:x \in A\} \]

  라 정의하자. 집합 \(f ^{-1}(B)\) 를 \(B\) 의 역상이라 하고 \(f(A)\) 를 \(A\) 의 상이라 한다.

  이때 \(f\) 가 전사일 필요충분조건은 \(f(X)=Y\) 이다.

• 한편 정의역이나 공역을 축소하여 전단사함수가 되게 한 후 역함수를 정의할 수도 있다. 삼각함수의 역함수가 이런 식으로 정의된다.

• 증명

Binary Operation✔

• 자연수의 덧셈이나 곱셈 등은 모두 이항연산이다.

Characteristic Function✔

• 특정 집합에 특정 값이 속하는지 표시하는 함수이다. 특정 값이 집합에 속하면 \(1\), 속하지 않으면 \(0\) 의 값을 가진다.

Projection✔

• 이 정의에서 \(f\) 란 곱집합의 정의에서의 \(f\) 를 뜻한다.

• 즉, \(i \in I\) 에 대한 사영은 집합족 \(\{X_i : i \in I\}\) 의 곱집합 \(\prod_{i \in I}^{}X_i\) 에 존재하는 함수들 중 어느 함수를 입력하면, 그것을 그 함수의 \(i\) 번째 사상으로 대응시킨다.

• 예시

  \(\R ^{n}\) 의 사영 \(\pi _i\) 는 \(a_i \in \R\) 에 대한 곱집합 \(\R ^{n}\) 의 어느 한 원소 \((a_1, a_2, \dots, a_n)\) 를 입력하면 \(i\) 번째 원소 \(a_i\) 를 출력하는 함수이다.

Equivalence Relation✔

• 이를 통해 순서수 \(\alpha\) 에 대하여 집합 \(X\) 위의 \(\alpha\)항 관계를 다음과 같은 거듭제곱 집합의 부분집합으로 정의한다.

  \[ R \subseteq X ^{\alpha } \]

• 예시

  집합 \(X\) 위의 영항관계(nullary relation) 은 \(R \subseteq \{\cdot \}\) 즉, \(R = \varnothing\) 이다.

  집합 \(X\) 위의 단항관계(unary relation) 은 \(R \subseteq X\) 이다.

  집합 \(X\) 위의 이항관계(binary relation) 은 \(R \subseteq X \times X\) 이다. 특히 이항관계에서 \((x, y) \in R\) 일 경우 \(xRy\) 와 같이 자주 표기한다.

  • 가령 집합 \(\Bbb{N}\) 위의 이항관계 \(+ \subseteq \Bbb{N} \times \Bbb{N}\) 에서 \((1, 2) \in \Bbb{N}\) 을 \(1 + 2\) 로 표기한다.

  집합 \(X\) 위의 삼항관계(ternary relation) 은 \(R \subseteq X \times X \times X\) 이다.

  • 프로그래밍 언어에서 x = (condition) ? a : b; 와 같이 사용되기도 한다.

  집합 \(X\) 위의 \(n\)항관계(n-ary relation) 은 \(R \subseteq X ^{n}\) 이다. 이때 \((x_1, \dots, x_n) \in R\) 을 \(R(x_1, \dots, x_n)\) 와 같이 표기한다.

• 두 집합 \(X, Y\) 의 곱집합 \(X \times Y\) 의 부분집합이다.

• 집합 \(X\) 에 관계가 주어졌다는 것은 곱집합 \(X \times X\) 의 부분집합이 주어졌다는 것이다.

• 예시

  데카르트 공간 \(\Bbb{R} ^{2}\), 즉 직교좌표계의 다음과 같은 부분집합은 관계이다.

  \[ x \in X, y \in Y, x ^{2}+y ^{2} = 4 \]

• 동치관계 \(R \subset X \times X\) 의 원소 \((x, y) \in R\) 을 다음과 같이 쓴다.

  \[ x \sim y \]

• 동치관계의 조건을 다시 열거하면 다음과 같이 된다.

  \[ x \in X \to x \sim x \]
  \[ x \sim y \to y \sim x \]
  \[ x \sim y, y \sim z \to x \sim z \]

• 예시

  "같다" 는 동치관계의 예시이다.

  "서로 평행이다", "서로 닮음이다" 도 동치관계의 예시이다.

Equivalence Class✔

• 예시

  집합 \(X = \{a,b,c\}\) 에

  \[ R = \{(a,a), (b,b), (c,c), (a,b), (b,a)\} \]

  와 같은 동치 관계가 주어져있다고 하자. 그러면

  \[ [a]=\{a,b\}, \qquad [b]=\{a,b\}, \qquad [c]=\{c\} \]

  이므로 집합 \(X=\{a,b,c\}\) 가 집합족

  \[ \{\{a,b\}, \{c\}\} \]

  으로 분할된다.

• 증명

  \(x \sim y\) 이면 동치관계의 성질 2), 3) 에 의하여

  \[ z \in [x] \iff z \sim x \iff z \sim y \iff z \in [y] \]

  이다. 역으로 \([x] = [y]\) 이면 \(x \sim x\) 이므로 \(x \in [x] = [y]\) 가 되고 따라서 \(x \sim y\) 임을 알 수 있다.

  두번째 성질을 증명하기 위하여

  \[ [x] \cap [y] \neq \varnothing \implies [x] = [y] \]

  임을 보이자. 만약 \(z \in [x] \cap [y]\) 이면 \(z \sim x, z \sim y\) 가 성립하고 따라서 \(x \sim y\) 이다. \(\forall x \in X, x \in [x]\) 이므로 성질 \((1)\) 에 의해 집합 \(X\) 는 집합족

  \[ \{[x]:x \in X\} \]

  으로 분할됨을 알 수 있다.

Partition✔

• 집합 \(X\) 에 동치관계 \(\sim\) 가 주어지면 Munkres Topology, Lemma 3.1에 의하여 자동적으로 \(X\) 의 분할이 생김을 알 수 있는데, 이러한 분할을

  \[ X/\sim \]

  라고 표시한다. 이 집합족을 몫집합이라고 한다.

• 만약 각 집합 \([x]\) 의 원소를 하나 택하여 \(r_x\) 라 두고 \(I = \{r_x:x \in X\}\) 라 두면 \(\{[r]:r \in I\}\) 는 서로소인 집합족이 되고, 따라서

  \[ X = \bigcup_{}^{}\{[r]:r \in I\} \]

  임을 알 수 있다.

• 이제 거꾸로 집합 \(X\) 의 분할 \(\mathcal{P} = \{X_i : i \in I\}\) 가 주어졌을 때 동치관계를 이끌어내보자. \(\forall x, y \in X\) 가 "\(x, y \in X_i\) 인 \(i \in I\) 가 존재한다" 를 만족할 때 \(x \sim y\) 라고 정의하자. 그러면 \(\sim\) 이 동치관계임을 바로 알 수 있다.

  실제로 \(x \in X\) 이면 분할의 정의 1) \(X = \bigcup_{i \in I}^{}X_i\) 에 의하여 \(x \in X_i\) 인 \(i \in I\) 를 찾을 수 있고, 이에 따라 \(x \sim x\) 가 성립하며, 이로써 동치관계의 조건 1) 반사성이 성립한다.

  동치관계의 조건 2) 대칭성은 \(x \sim y\) 로부터 \(y \sim x\) 를 이끌어내면 증명되는데, \(x, y \in X_i\) 인 \(i \in I\) 가 존재하면, \(y, x \in X_i\) 인 \(i \in I\) 가 존재함은 자명하다.

  그러면 이제 동치관계의 조건 3) 추이성을 보이기 위하여 \(x \sim y, y \sim z\) 라 가정하자. 그러면 \(x, y \in X_i\) 인 \(i \in I\) 와 \(y,z \in X_j\) 인 \(j \in I\) 가 존재한다. 그런데 \(y \in X_i \cap X_j\) 이므로 \(X_i = X_j\) 이고, 이에따라 \(x \sim z\) 이다.

• 예시

  정수 집합 \(\Bbb{Z}\) 에 관계

  \[ m \sim n \iff \exists k \in \N, m - n = 2k \]

  를 정의하면 동치관계가 됨을 바로 알 수 있다.

  이때 \(m\) 이 짝수면 \([m] = \{2n \in \N : n \in \N\}\) 가 되고, \(m\) 이 홀수면 \([m] = \{2n+1 \in \N : n \in \N\}\) 가 된다. 따라서

  \[ \Bbb{Z}/\sim\ = \{[x]:m \in \Bbb{Z}\} = \{[m]:m = 0, 1\} = \{[0], [1]\} \]

  가 되고, \(\Bbb{Z} = [0] \cup [1]\) 이 된다. 이때 \(0, 1\) 대신 \(8, 5\) 를 택하여 \(\Bbb{Z} = [8] \cup [5]\) 라고 써도 마찬가지이다.

• 예시

  집합 \(\N \times \N = \{(m,n):m,n \in \N\}\) 에 관계 \(\sim\) 를

  \[ (m,n) \sim (m',n') \iff m+n' = n+m' \]

  와 같이 부여하면 동치관계가 된다. 반사성, 대칭성이 성립함은 자명하고, 추이성이 성립함을 보이자. 이는 \(x \sim y, y \sim z \to x \sim z\) 를 보임으로써 완성된다.

  만약 \((m,n) \sim (m',n') \land (m', n') \sim (m'', n'')\) 라면 \(m+n'=n+m' \land m'+n''=n'+m''\) 이므로

  \[ (m+n'')+(m'+n') = (m+n')+(m'+n'') \]
  \[ = (n+m') + (n'+m'')=n+m''+(m'+n') \]

  이 성립한다. 따라서 \(m+n''=n+m''\) 이고, 이에따라

  \[ \therefore (m,n) \sim (m'',n'') \]

  이다. ■

  한편 이 경우

  \[ \N \times \N / \sim = \{[(0, 0)], [(n, 0)], [(0, n)] : n \in \N \setminus \{0\} \} \]

  이 성립함을 금방 알 수 있는데, 이것이 정수 체계의 정의로 곧바로 연결된다. 왜냐하면, 사실 이렇게 이해하는 게 더 편하다. 동치 관계

  \[ (m,n) \sim (m',n') \iff m+n' = n+m' \]

  를

  \[ (m,n) \sim (m',n') \iff m-n = m'-n' \]

  로 생각하면 이는 \(a \in \N \times \N\) 의 첫번째 원소와 두번째 원소의 차이값이다.

• 이 정리는 동치관계와 동치관계로 생성된 분할이 서로 같고, 분할과 분할로 생성된 동치관계가 서로 같음을 말해준다. 즉, 분할과 동치관계가 본질적으로 서로 같다는 것을 말해준다.

• 첫번째 명제의 증명

  먼저 \(x \sim y\) 이면 \(x \in [x], y \in [x]\) 이고 \([x] \in X/\sim\) 이므로 \(x \sim _{(X/\sim )}y\) 가 성립한다. 역으로 \(x \sim _{(X/\sim )}y\) 이면 \(x \in [z], y \in [z]\) 인 \([z] \in X/\sim\) 이 존재한다. 그러면 \(x \sim z, y \sim z\) 이므로 \(x \sim y\) 이다.

• 두번째 명제의 증명

  \(A \in \mathcal{P}\) 라고 가정하고, \(a \in A\) 를 택하자. 만약 \(x \in A\) 이면 정의에 의하여 \(x \sim _{\mathcal{P}} a\) 이다. 만약 \(x \sim _{\mathcal{P}}a\) 이면 \(x \in B, a \in B\) 인 \(B \in \mathcal{P}\) 가 존재하는데 \(a \in A \cap B\) 이므로 \(A=B\) 이고, 따라서 \(x \in A\) 이다. 그러므로

  \[ A = \{x \in X:x \sim _{\mathcal{P}}a\} \in X/\sim _{\mathcal{P}} \]

  이다.

  역으로 \(A \in X / \sim _{\mathcal{P}}\) 이면 적절한 \(a \in X\) 에 대하여 \(A = \{x \in X:x \sim _{\mathcal{P}}a\}\) 이다. 한편 분할 \(\mathcal{P}\) 에서 \(a \in X\) 가 포함되는 것을 \(B \in \mathcal{P}\) 라 하자. 그러면 방금 증명한 바에 의하여 \(A=B\) 이고, 따라서 \(A \in \mathcal{P}\) 이다.

• 예시

  홀수 전체 집합을 \(O\), 짝수 전체 집합을 \(E\) 라 두면 \(\mathcal{P} = \{O, E\}\) 는 정수 전체 집합 \(\Bbb{Z}\) 의 분할이다. 그러면 동치관게 \(\sim _{\mathcal{P}}\) 의 정의에 의하여

  \[ m \sim _{\mathcal{P}} n \iff \exists a, b \in \N, (m = 2a-2, n = 2b-2) \lor (m = 2a - 1, n = 2b - 1) \]
  \[ \iff \exists c \in \N, m - n = 2c \]

  이다. 그러므로 동치관계 \(\sim _{\mathcal{P}}\) 는 "분할" 의 예시에서 정의한 \(\Bbb{Z}/\sim\) 과 같은 것이 된다.

• "분할" 의 예시에서는 정수 집합 \(\Bbb{Z}\) 에 관계

  \[ m \sim n \iff \exists k \in \N, m - n = 2k \]

  를 정의하여 \(\Bbb{Z}/\sim\) 가 짝수와 홀수의 집합으로 구성된다는 사실을 이끌어 내었고,

  이 예시는 역으로 정수 집합 \(\Bbb{Z}\) 를 짝수와 홀수로 분할한 집합 \(\mathcal{P} = \{O,E\}\) 에 대한 동치관계 \(m \sim _{\mathcal{P}} n\) 로부터 이 동치관계가

  \[ m \sim _{\mathcal{P}} n \iff \exists c \in \N, m - n = 2c \]

  를 뜻함을 이끌어 냄으로써

  동치관계의 정의로부터 도출된 분할과 분할의 정의로부터 도출된 동치관계가 서로 동일함을 보여주고 있는 것이다.

Quotient Set✔

• 목사상은 전사사상이다.

• 증명

  \(2 \implies 1\):

  2) 를 가정하면 함수 \(\tilde{f}:X/ \sim \to Y:[x] \to f(x)\) 가 존재한다. 이때 이 정의가 잘 정의되어 있는지 살펴봐야 하는데, 왜냐하면 \([x]\) 의 함수값을 정의하기 위하여 \(x\) 를 사용하였는데 \([x]\) 를 대표하는 원소가 \(x\) 이외에 더 있을 수 있기 때문이다. 즉, 다른 원소 \(y\) 에 대하여 \([x]=[y]\) 라면 \(y\) 도 \([x]\) 를 대표하게 되는데 이런 때에도 \(f(x)=f(y)\) 가 성립하여야 \(\tilde{f}\) 가 함수가 될 수 있다. 이것을 2) 가 보장해준다.

  이제 \(\tilde{f}\) 의 유일성을 보이면 된다. 즉, 두 함수 \(\tilde{f}_{1}, \tilde{f}_{2}: X/\sim \to Y\) 가 \(\tilde{f}_{1} \circ q = \tilde{f}_{2} \circ q = f\) 이면 서로 같음을 보이자. 2) 를 가정했으므로 임의의 \(A \in X/ \sim\) 에 대하여 다음이 성립한다.

  \[ x, y \in A \implies f(x) = f(y) \]

  따라서 다음이 성립한다.

  \[ \tilde{f}_1(q(x)) = \tilde{f}_2(q(x)) \iff \tilde{f}_1(A) = \tilde{f}_2(A) \]

  즉, 정의역의 임의의 원소에서 \(\tilde{f}_1\) 와 \(\tilde{f}_2\) 의 상이 같다. 함수의 상등의 정의에 의하여 \(\tilde{f}_1 = \tilde{f}_2\) 이다. ▲

  \(1 \implies 2\):

  역으로 \(\tilde{f}\circ q = f\) 가 성립하는 함수 \(\tilde{f}:X/\sim \to Y\) 가 존재하면 조건 2) 가 성립하는 것은 자명하다. ■

• 예시

  좌표평면 \(\R ^{2}\) 의 한 점 \(A = (a_1, a_2)\) 에서 출발하여 \(B = (b_1, b_2)\) 로 가는 화살표 \(\overrightarrow{AB}\) 전체의 집합을 \(X\) 라 하고, \(X\) 에 관계

  \[ \overrightarrow{AB} \sim \overrightarrow{CD} \iff B-A = D-C \]

  를 정의하자. 그러면 이 관계는 동치관계가 된다.

  이때 \(\forall \overrightarrow{AB} \in X\) 에 대하여 \(A+C=B\) 인 \(C = \in \R ^{2}\) 를 잡으면 \(O = (0, 0)\) 에 대하여 \(\bigg [\overrightarrow{AB}\bigg ] = \bigg [\overrightarrow{OC}\bigg ]\) 이다. 따라서

  \[ X/\sim = \bigg \{\bigg [\overrightarrow{OC}\bigg ] : C \in \R ^{2} \bigg \} \]

  이다. 이때 함수

  \[ C \mapsto \bigg [\overrightarrow{OC}\bigg ] : \R ^{2} \to X/\sim \]

  은 전단사함수이다. 즉, 좌표평면 위의 모든 벡터는 한 점에 의하여 결정되므로 점 \((a_1, a_2) \in \R ^{2}\) 을 벡터라 부른다. 이는 원점에서 그 점으로 가는 화살표로 이해하려는 것이다.

• 예시

  실수체 \(\R\) 위의 벡터공간 \(V\) 와 그 부분공간 \(W\) 에 대하여

  \[ x \sim _{W} y \iff x - y \in W \]

  라고 정의하면 동치관계가 된다. 이때 \(\forall x \in V\) 에 대하여

  \[ [x] = \{y : x-y \in W\} = \{x+z:z \in W\} \]

  가 되는데, \(V / \sim _{W}\) 에 \(x, y \in V, a \in \R\) 에 대한 연산

  \[ [x]+[y]=[x+y], \qquad a[x]=[ax] \]

  를 정의하자. 그러면 \(V/ \sim _{W}\) 는 벡터공간이 되는데, 이것을 \(V/W\) 라고 쓰고 몫공간이라고 한다.

  그런데 \([x+y]\) 를 정의하기 위하여 \(x\) 를 사용했는데 \([x]\) 를 대표하는 원소가 \(x\) 만 있는 것이 아니기 때문에 이것이 잘 정의되었는가 검증해야 한다. 즉,

  \[ [x_1] = [x_2], [y_1] = [y_2] \implies [x_1+y_1] = [x_2+y_2], [ax_1] = [ax_2] \]

  임을 증명해야 한다. 먼저 \([x_1] = [x_2], [y_1] = [y_2]\) 이면 \(x_1 \sim x_2, y_1 \sim y_2\) 이므로 \(x_1 - x_2, y_1 - y_2 \in W\) 이고, 이로부터

  \[ (x_1+y_1) - (x_2+y_2) = (x_1-x_2)+(y_1-y_2)\in W \]
  \[ ax_1-ax_2=a(x_1-x_2) \in W \]

  임을 알 수 있다.

Order✔

집합과 수의 체계는 부분순서를 "순서" 라고 표현하고 있다. Munkres, Topology 에서는 절대 전순서 관계를 "순서" 라고 표현한다.

• 원순서 관계에 반대칭성 \(a \leq b \land b \leq a \implies a = b\) 을 추가하면 부분 순서가 된다.

• 원순서 관계는 두 원소를 추이적으로 비교할 수 있는 관계이다.

• 원순서 관계를 만족하는 집합을 원순서 집합(preordered set, proset) 이라 한다. 원순서 집합은 두 원소를 추이적으로 비교할 수 있는 집합이다.

• 만약 \(x \leq y\) 이면서 \(x \neq y\) 이면 \(x < y\) 라고 표기한다.

• 부분 순서관계가 정의되어 있는 집합을 부분 순서집합(partially ordered set) 이라 한다.

• 예시

  집합 \(X = \{a,b,c\}\) 에 관계

  \[ R = \{(a,a),(b,b),(c,c),(a,b),(a,c)\}\subset X \times X \]

  를 정의하면 \(R\) 은 순서관계가 된다. 이때 원소 \(a,b,c\) 사이에 다음의 순서

  \[ a \leq a, b \leq b, c \leq c, a \leq b, a \leq c \]

  가 있게 된다.

• 비반사성와 추이성이 다음 조건 비대칭성(asymmetry)을 함의한다.

  \[x < y \implies y \not < x\]

  따라서 보통 비대칭성이 생략되지만 저자에 따라서 강조의 의미로 비대칭성을 쓸 때도 있다.

• 부분 순서 \(\leq \subseteq X ^{2}\) 가 존재할 때 \(x, y \in X\) 에 대하여 다음을 만족하는 이항 관계 \(< \subseteq X ^{2}\) 는 절대 부분순서이다.

  \[x < y \iff x \leq y \neq x\]

• 절대 부분 순서 \(< \subseteq X ^{2}\) 가 존재할 때 \(x, y \in X\) 에 대하여 다음을 만족하는 이항 관계 \(\leq \subseteq X ^{2}\) 는 부분순서이다.

  \[x \leq y \iff x < y \lor x = y\]

• 원전순서 관계는 두 원소가 항상 비교 가능한 원순서 관계이다. 준순서에 비교가능서을 추가한 것이 준전순서이다.

• 절대 부분 순서 관계가 부여된 집합의 두 원소가 항상 비교 가능하면 절대 전순서 관계라 한다. 절대 부분 순서 관계에 비교가능성 조건만 추가하면 절대 전순서 관계가 되는 것이다.

• Munkres, Topology 에서는 절대 전순서 관계 \(<\) 를 simple order 라고 말한다. 또한 \(x \leq y \iff x < y \lor x = y\) 라고 정의한다.

• 부분순서관계에 비교가능성을 추가하면 전순서 관계가 된다. 즉, 전순서 관계는 두 원소가 항상 비교가능한 부분순서관계이다.

• 위 조건들이 다음 조건 반사성을 함의하므로 보통 생략되나 저자에 따라 강조의 의미로 포함시킬 때도 있다.

  \[a \leq a\]

• 전순서는 두 원소가 항상 비교가능한 부분순서이다.

• 도약이 없는 전순서를 조밀 순서라 한다.

• 조밀 순서는 비교 가능한 서로 다른 두 원소 사이에 항상 제 3의 원소가 존재하는 부분순서이다.

Bounded Set✔

Supremum✔

• 상계 중 가장 작은 원소를 최소상계(least upper bound) 또는 상한(supremum)이라 한다.

• 집합 \(S\) 가 상한을 가지면 두번째 조건에 의하여 상한이 오직 하나밖에 없음을 쉽게 알 수 있다. 그 상한을 \(\sup S\) 라고 쓴다.

• 어느 집합의 상한은 그 집합의 원소일 수도 있고, 아닐 수도 있다.

  만약 \(\sup A\) 가 \(A\) 의 원소가 되면, \(\sup A\) 는 자명하게 \(A\) 에서 가장 큰 원소이다.

• 예시

  실수집합 \(\Bbb{R}\) 의 부분집합을 취하고 순서를 부여하여 열린구간

  \[ (0, 1) = \{x \in \Bbb{R}: 0 < x < 1\} \]

  을 얻으면, 이것의 상계 전체 집합은

  \[ \{x \in \Bbb{R} : x \geq 1\} \]

  이다. 이 집합의 최소원소는 \(1\) 이므로

  \[ \sup (0, 1) = 1 \]

  이다.

  마찬가지로 실수집합 \(\Bbb{R}\) 의 부분집합을 취하고 순서를 부여하여 닫힌구간

  \[ [0, 1] = \{x \in \Bbb{R}: 0 \leq x \leq 1\} \]

  을 얻으면, 이것의 상한은

  \[ \sup [0, 1] = 1 \]

  이다.

• 증명

  \(S\) 가 위로 유계이므로 \(\exists M \in \Z: \forall s \in S: s \leq M\) 이다. 즉, 모든 \(S\) 의 원소 \(s\) 에 대하여 적당한 정수 \(M\) 이 존재하여 항상 \(s \leq M\) 라는 것이다.

  그러므로 \(\forall s \in S: 0 \leq M - s\) 이다. 그러면 집합 \(T\) 를 이렇게 정의해보자.

  \[ T = \{M - s : s \in S\} \subseteq \Bbb{N} \]

  그러면 Well-Ordering Principle 에 의하여 \(T\) 는 가장 작은 원소를 갖는다. 그것을 \(b _{T} \in T\) 라고 하자.

  그렇다면

  \[ (\forall s \in S: b _{T} \leq M - s) \land (\exists g _{S} \in S:b _{T} = M - g _{S}) \]

  이다. 즉, \(S\) 의 모든 원소 \(s\) 에 대하여 \(M-s\) 는 \(b _{T}\) 와 같거나 크고, \(S\) 의 원소 \(g _{S}\) 가 존재하여 \(b _{T} = M - g _{S}\) 가 된다는 것이다.

  그러므로

  \[ \forall s \in S : b _{T} \leq M - s \]
  \[ \iff \forall s \in S : M - g _{S} \leq M - s \]
  \[ \iff \forall s \in S : - g _{S} \leq - s \]
  \[ \iff \forall s \in S : g _{S} \geq s \]
  \[ \iff g _{S} \in S \land (\forall s \in S : g _{S} \geq s ) \]

  이다. 즉, \(S\) 의 모든 원소 \(s\) 보다 큰 원소 \(g _{S}\) 가 존재한다는 것이다.

  그러므로 \(S\) 의 가장 큰 원소 \(g _{S}\) 가 존재한다.

• 증명

  \(S\) 가 위로 유계라고 하자. 그러면 \(S\) 는 상한 \(B = \sup S\) 를 갖는다.

  \(x > 1\) 이므로 \(\dfrac{x}{B} > \dfrac{1}{B}\) 에서 \(\dfrac{B}{x} < B\) 이다.

  \(B\) 가 최소상계, 즉 상한인데도 \(\dfrac{B}{x} < B\) 이므로 \(\dfrac{B}{x}\) 는 상계가 될 수 없다. 그러므로

  \[ \exists n \in \Bbb{N}: x ^{n} > \dfrac{B}{x} \implies x ^{n+1} > B \]

  이다. 즉, \(\dfrac{B}{x}\) 가 상계가 아니므로 와 적당한 자연수 \(n\) 에 대한 \(x ^{n}\) 이 존재하여 \(x ^{n} > \dfrac{B}{x}\) 인데, 이는 곧 \(x ^{n+1} > B\) 이 된다. 그런데 \(B\) 를 최소상계라고 했으므로 이는 모순이다.

  그러므로 \(B\) 는 상계가 아니다.

  이로써 \(S\) 가 위로 유계라는 가정 또한 모순이다. 그러므로 \(S\) 는 위로 무계 집합이다.

Backwards Induction✔

• 증명

  적당한 자연수 \(\exists k \in \Bbb{N}\) 가 존재하여 \(P(k)\) 가 거짓이 된다고 하자.

  그러면 정리 "\(x \in \Bbb{R}\) 이 \(x > 1\) 일 때 집합 \(S = \{x ^{n}:n \in \Bbb{N}\}\) 은 위로 무계 집합이다." 에 의하여 \(\{2 ^{n} : n \in \Bbb{N}\}\) 은 위로 무계이다.

  쉽게 말해서 \(2\) 의 제곱수는 상계가 없다. 그러므로 \(k \in \Bbb{N}\) 가 아무리 크더라도

  \[ M = 2 ^{N} > k \]

  를 만족하는 \(N, M \in \Bbb{N}\) 이 존재한다. 그러면 이제 집합 \(S\) 를 다음과 같이 만들어보자.

  \[ S = \{n \in \Bbb{N} : n < M, P(n) \text{ is false}\} \]

  쉽게 말해 \(M\) 보다 작은 자연수 \(n\) 중에서 명제함수 \(P(n)\) 가 거짓이 되는 자연수 \(n\) 의 모임으로 집합 \(S\) 를 정의하는 것이다. 그러면 \(k\) 는 반드시 \(S\) 의 원소이므로 \(S \neq \varnothing\) 이다. (\(\because k < M , P(k) \text{ is false}\))

  그리고 \(S\) 는 \(\forall x \in S: x < M\) 이므로 위로 유계이다.

  그렇다면 정리 "정수집합 \(\Z\) 과 \(\Z\) 의 순서관계 \(\leq\) 에 대하여 \(\varnothing \subset S \subseteq \Z\) 인 집합 \(S\) 가 \((\Z, \leq )\) 에서 위로 유계라면 \(S\) 는 가장 큰 원소를 갖는다." 에 의하여 \(S\) 는 가장 큰 원소 \(g _{S}\) 를 갖는다.

  그러면 \(S\) 의 가장 큰 원소 \(g _{S}\) 보다 큰 자연수 \(m\) 에 대하여 \(m < n \leq M\) 인 자연수 \(n\) 이 존재하여 \(P(n)\) 을 참이 되게 한다. 그리고 그러므로 \(P(m+1)\) 도 참이다.

  그런데 명제함수 \(P\) 의 두번째 성질

  2. \(P(n) \implies P(n-1)\)

  에 의하여 \(P(m+1) \implies P(m)\) 이다. 즉, \(P(m+1)\) 이 참이면 \(P(m)\) 도 참이다. 이에따라 \(P(m-1)\) 도 참이고, \(P(m-2)\) 도 참이고, \(\dots\), \(P(1)\) 도 참이다.

  그러므로 \(S\) 의 가장 큰 원소 \(g _{S}\) 가 존재하지 않으며, 이에따라 \(S = \varnothing\) 이라는 결론을 얻는다. 이는 모순이다.

  그러므로 \(P(k)\) 가 거짓이 되게 하는 \(k \in \Bbb{N}\) 는 존재하지 않는다. ■

Infimum✔

• 하계 중 가장 작은 원소를 최대하계(greatest lower bound) 또는 하한(infimum)이라 한다.

• 하한도 집합 \(S\) 에 대하여 오직 하나밖에 없는데 그 하한을 \(\inf S\) 라고 한다.

• 예시

  집합 \(X\) 의 멱집합 \(2 ^{X}\) 에 포함관계에 의한 순서를 부여하자. 즉, \(A \subset B \to A \leq B\) 로 정의한다는 것이다. 이 관계가 순서관계를 만족한다는 것은 자명하다.

  이때 집합족 \(\mathcal{A} \subset 2 ^{X}\) 이 주어지면

  \[ \sup \mathcal{A} = \bigcup_{}^{}\mathcal{A}, \inf \mathcal{A} = \bigcap_{}^{}\mathcal{A} \]

  이다. 이것을 증명해보자.

  먼저 \(\forall A \in \mathcal{A} \to A \leq \bigcup_{}^{}\mathcal{A}\) 이므로 \(\bigcup_{}^{}\mathcal{A}\) 은 \(\mathcal{A}\) 의 상계이다. 만약 \(S \in 2 ^{X}\) 가 \(\mathcal{A}\) 의 상계라면, 임의의 \(A \in \mathcal{A}\) 에 대하여 \(A \subset S\) 이므로

  \[ x \in \bigcup_{}^{}\mathcal{A} \implies \exists A \in \mathcal{A}, x \in A \implies x \in S \]

  이다. 그러므로 \(\bigcup_{}^{}\mathcal{A} \leq S\) 이고,

  \[ \sup \mathcal{A} = \bigcup_{}^{}\mathcal{A} \]

  이다.

Convex Set✔

• 쉽게 말해 유클리드 공간 속의 집합에서 임의의 두 점을 골랐을 때 둘을 연결하는 선분이 그 집합에 포함되면 볼록집합이다.

  볼록 집합:

  

  볼록 집합이 아닌 예:

  

• 블록집합 \(C\) 의 볼록부분집합 \(F\) 가 다음을 만족하면 \(F\) 를 \(C\) 의 면이라고 한다.

  \(\exists t \in (0, 1) \text{ s.t. } x,y \in C, tx + (1-t)y \in F \implies x,y \in F\)

• 한 점으로 이루어진 볼록집합의 면을 꼭짓점이라 하다.

Lattice✔

• 이 정의에서 주의할 점은 \(x \lor y = \sup \{x, y\}\) 와 \(x \land y = \inf \{x, y\}\) 로 정의한다는 것이다.

• 위에서 말한 상한의 정의를 다시 반복하면 \(x \lor y\) 은

  \[ x \leq x \lor y, \quad y \leq x \lor y \]
  \[ x \leq z, y \leq z \to x \lor y \leq z \]

  를 만족한다. 이때

  \[ (x, y) \mapsto x \lor y, \quad (x, y) \mapsto x \land y \]

  은 이항연산이다.

• 증명

  1), 2) 는 자명하다. \(\lor\) 의 결합법칙을 보이기 위하여

  \[ (x \lor y) \lor z \leq x \lor (y \lor z) \tag{1} \]

  를 보이자. 먼저 \(x \leq x \lor (y \lor z)\) 와 \(y \leq y \lor z \leq x \lor (y \lor z)\) 에서

  \[ x \lor y \leq x \lor (y \lor z) \]

  가 성립한다. 또한 \(z \leq y \lor z \leq x \lor (y \lor z)\) 을 함께 생각하면 \((1)\) 이 성립함을 알 수 있다. 반대 부등식도 같은 방식으로 증명되고 \(\land\) 의 결합법칙도 같은 방식으로 증명된다.

  마지막 명제 \((x \lor y) \land x = x\) 를 보이기 위해서

  \[ x \leq x, \quad x \leq x \lor y \]
  \[ z \leq x, z \leq x \lor y \to z \leq x \]

  를 보이면 되는데 이는 자명하다. ■

• 증명

  첫째 명제는 위에서 이미 증명하였고, \(x \leq x\) 는 1.22 의 첫째 성질에서 나온다. \(x \leq y, y \leq x\) 이면 \(x \lor y = y\) 이고 \(y \lor x = x\) 이다. 이때 \(\lor\) 이 교환법칙을 만족하므로 \(x=y\) 이다. 만약 \(x \leq y, y \leq z\) 이면

  \[ x \lor z = x \lor (y \lor z) = (x \lor y) \lor z = y \lor z = z \]

  이므로 \(x \leq z\) 가 성립한다. 이제 \(\sup \{x, y\} = x \lor y\) 임을 보이자. 먼저

  \[ x \lor (x \lor y) = (x \lor x) \lor y = x \lor y \]

  이므로 \(x \leq x \lor y\) 가 성립하고 \(x\) 와 \(y\) 의 역할을 바꾸면

  \[ y \leq y \lor x = x \lor y \]

  이다. 마지막으로 \(x \leq z, y \leq z\) 이면

  \[ (x \lor y) \lor z = x \lor (y \lor z) = x \lor z = z \]

  이다. 따라서 \(x \lor y \leq z\) 이다. 그러므로 \(\sup \{x, y\} = x \lor y\) 이다. ■

ZFC✔

이렇게 집합을 초보적인 수준에서 알아보았다. 하지만 집합을 막연하게 사용하자 다음과 같은 모순이 발견되기 시작했다.

• \(S \in S\) 이면 정의에 의하여 \(S \not\in S\) 이다. 한편 \(S \not\in S\) 이면 \(S \in S\) 을 얻는다. 이 역설은 기존의 집합론에 모순이 있음을 말해주었고, 수학 학계에 수학의 엄밀한 기초를 세워야한다는 사실을 알려주었다.

이 역설은 함부로 집합을 만들면 모순이 생긴다는 것을 알려주었고, 수학자들은 다음 공리계를 세워서 어느때 집합을 만들면 올바른지 엄밀하게 정의하였다.

• 러셀의 역설 외에서 여러가지 역설이 발견되었었는데, 이러한 역설을 해결하기 위하여 먼저 중의적인 뜻을 항상 내포할 수 있는 자연어를 수학에서 배제하고, 다음의 기호만 쓰기로 했다. 실제로 모든 수학 체계의 내용은 다음의 단어들의 조합이다. 즉, 모든 수학을 다음의 단어만으로 전개할 수 있다.

  \[ \land \quad \lor \quad \neg \quad \to \quad \iff \quad \exists \quad \forall \]

  그런데 \(\iff\) 는 \(\to\) 와 \(\gets\) 의 조합으로 정의될 수 있으므로 제외하고, \(\dots \to \dots\) 도 \(\lnot \dots \lor \dots\) 의 조합으로 정의될 수 있으므로 제외하고, \(\lnot\) 도 사실은 의미론적 관점에서 명제를 만족시키는 여집합으로 해석될 수 있으므로 제외될 수 있고, \(\forall\) 는 \(\land\) 의 조합으로, \(\exists\) 도 \(\lor\) 의 조합으로 해석될 수 있어서 제외될 수 있다. 그렇다면 결국 \(\lor\) 와 \(\land\) 만으로도 수학을 구성해낼 수 있다.

  또한 "원소", "집합", "\(x \in X\)" 같은 단어는 무정의 술어로 남겨서, 공리계 내부에서 자연스럽게 의미를 얻도록 했다.

  • 무한공리에서 사용된 비형식적 술어 \(\varnothing\) 는 공집합을 뜻한다.

  • 선택공리에서 \(\bigcup_{}^{}\) 은 합집합을 뜻하는 비형식적 술어이며, 물론 공리계의 올바른 형식적 술어로 정의된다.

• 분류공리꼴로 인하여 이미 존재하는 집합에 어떤 조건을 가하여 부분 집합을 취할 수 있다. 이때 어떤 성질 \(\phi (a)\) 를 만족하는 집합이 바로 존재한다는 것이 아니라 이미 구성된 집합의 부분집합으로써 조건을 만족시키게 하는 것은 러셀의 역설을 피하기 위해서이다.

• 치환공리꼴로 인하여 어떤 논리식이 두 집합의 함수 관계라면, 함수의 상의 집합을 취할 수 있다.

• 무한공리에서 자연수를 정의할 때 쓰이는 성질

  \[ \varnothing \in \mathcal{A}, A \in \mathcal{A} \implies A ^{+} \in \mathcal{A} \]

  에 의하여 자연수가 정의된다. 그러므로 무한공리는 자연수의 존재성을 말하고 있다.

• 무한공리와 분류공리에 의하여 \(\varnothing = \{x \in \N : x \neq x\}\) 이므로 존재공리가 유도되어, 존재공리는 공리가 아니게 되지만 그 의미가 너무 커서 그냥 "공리" 라고 부른다.

  또한 짝공리도 합집합공리에서 도출되지만, 관행상 공리라고 부른다.

• 치환공리를 쉽게 말하면 다음과 같다.

  임의의 \(x\) 에 대하여 성질 \(P(x, y)\) 가 성립하는 \(y\) 가 유일하게 존재한다고 하면, 임의의 집합 \(X\) 에 대하여

  "임의의 \(x \in X\) 에 대하여 \(P(x,y)\) 가 성립하는 \(y \in Y\) 가 존재한다."

  를 만족하는 집합 \(Y\) 가 존재한다.

• 수학의 거의 모든 분야가 ZFC 를 표준적인 공리계로 사용한다. 즉, 현대 수학의 표준적인 수학기초론으로써 ZFC 공리계가 사용된다는 것이다.

  굳이 예외를 들자면 카테고리 이론을 들 수 있다.

  • 선택공리를 제외한 것을 ZF 공리계라고 하는데, ZF 도 표준적인 공리계로 사용된다.

• ZFC 공리계에서 존재공리는 다른 공리로부터 유도되지만 그 중요성 때문에 관례상 공리라고 부른다.

• 괴델의 완전성 정리는 1차 술어 논리가 완전하다는 것을 말해준다.

• 세 개의 명제 \(P_1, P_2, P_3\) 에 대하여 이 세 명제를 모두 만족하는 모델이 있으면 세 명제 사이에 모순이 없음을 알 수 있다. 이 경우 \(P_1, P_2\) 로부터 \(\neg P_3\) 을 증명하는 것은 불가능하다.

  또한 \(P_1, P_2, \neg P_3\) 을 만족하는 모델이 있으면 \(P_1, P_2\) 로부터 \(P_3\) 을 증명하는 것은 불가능하다.

  • 예시

    집합 \(X\) 와 이 집합에 정의된 관계 \(<\) 에 대한 명제

    \(P_1\): \(\forall x, y \in X\) 에 대하여 \(x<y\) 와 \(y<x\) 가 동시에 성립하지 않는다.

    \(P_2\): \(\forall x, y, z \in X\) 에 대하여 \(x<y \land y < z \implies x < z\) 이다.

    \(P_3\): \(\forall x, y \in X\) 에 대하여 \(x<y, x=y, y<x\) 중 하나가 성립한다.

    를 생각하자. 모델 \((2 ^{\{0,1\}}, \subsetneq )\) 은 \(P_1, P_2\) 을 만족하지만 \(P_3\) 은 만족하지 않는다. 따라서 \(P_1, P_2\) 에서 \(P_3\) 을 증명할 수 없다.

    한편 모델 \((2 ^{\{0\}}, \subsetneq )\) 은 \(P_1, P_2\) 을 만족하지만 \(\neg P_3\) 을 만족하지 않으므로 \(P_1, P_2\) 로부터 \(\neg P_3\) 을 증명할 수 없다. 따라서 \(P_3\) 은 공리계 \(\{P_1, P_2\}\) 안에서 결정불가능한 명제이다.

• 불완전성 정리의 증명

• 힐베르트는 산술 체계의 무모순성을 묻는 문제를 공표하면서 산술 체계의 무모순성을 증명함으로써 집합론의 무모순성과 더 나아가 수학의 무모순성을 증명할 수 있을 것이라고 믿었다. 하지만 괴델이 이 정리를 발표하여 산술 체계의 무모순성과 완전성이 양립 불가능함을 보였다.

  그렇다면 페아노 공리계에 다른 공리를 추가하여 무모순성을 해결하면 되지 않은가 라고 생각할 수 있으나 그 추가된 공리로 인하여 또 다른 결정불가능 명제가 자동으로 생성된다. 즉, 불완전성 정리란 아무리 공리를 추가하여도 무모순성과 완전성을 동시에 만족시킬 수 없음을 말한다.

• 이 정리도 괴델이 보였다.

• 이 정리는 ZF 공리계가 선택공리를 받아들이는 것이 안전하다는 것을 말해준다. 또한 괴델은 연속체 가설을 ZF 공리계에 받아들이는 것이 안전함을 보였다. 연속체 가설은 \(\mathfrak{c} = \aleph _1\) 임을 묻는데, 칸토어는 이를 증명하려고 무던히 노력했지만 실패했다.

• 이 정리가 연속체 가설이 안전하다는 괴델의 정리이다.

• 지금까지는 ZF 공리계 안에서 \(\mathfrak{c} = \aleph _1\) 을 증명할 수 있는지 알 수 없었다. 즉, \(\mathfrak{c} = \aleph _1\) 이 ZF 공리계로부터 독립적인지 알 수 없었다. 그러나 1963년 코헨이 다음의 정리를 증명했다.

• 이 정리는 ZF 공리계에서

  \[ \mathfrak{c} = \aleph _1, \enspace \mathfrak{c} = \aleph _2, \enspace \mathfrak{c} = \aleph _3, \dots \]

  중 어떤 것을 공리로 택해도 안전함을 말해준다. 또 이는 \(\mathfrak{c} = \aleph _1\) 이 ZF 공리계에서 증명될 수 없음을 말해주고, \(\mathfrak{c} \neq \aleph _1\) 도 증명될 수 없음을 말해준다. 즉 \(\mathfrak{c} = \aleph _1\) 는 ZFC 공리계에서 결정불가능한 명제였다.

• 즉, 괴델은 ZF 공리계가 무모순이라는 가정 하에 연속체 가설의 무모순을 보였고, 코헨은 연속체 가설의 독립성을 보였다.

• 유클리드 기하의 평행선 공리는 역사적으로 수학자들이 다른 공리로부터 도출하여 정리로 만드려고 무단히 노력했지만 실패했다. 그러나 결국 19세기 평행선 공리를 부정하면 비유클리드 기하학이 생성된다는 것이 발견되었다. 이는 평행선 공리가 유클리드 기하학의 다른 공리로부터 독립적임을 뜻했다.

  연속체 가설도 평행선 공리와 같은 위치에 있는 것이다.