1.1 Baby Set Theory
"아가 Set Theory"
Set(집합)이란 물건(member 또는 element(원소))들의 모임.
\[t \in A : t \textrm{ is an element of }A\] \[t \notin A : t \textrm{ is not an element of }A\]
Example 1.1.1
$A$ = 10 이하의 소수들의 set이라고 하면, \[A = \{ 2,3,5,7 \} \]
$B$ = 다항식 $x^{4}-17x^{3}+101x^{2}-247+210=0 $의 모든 해들의 set이라고 하면,
\[B= \{2,3,5,7\}\]
Principle 1.1.2 [Extensionality]
두 set이 정확히 같은 원소를 가지면, 두 set은 같다.
만약 두 set $A$, $B$가 모든 object $t$에 대해, \[t \in A \quad \textrm{iff}\quad t \in B\]이면, \[A=B \]이다.
Example 1.1.3
Empty set(공집합) $\varnothing$은 member를 갖지 않는 set을 말한다. Extensionality에 의해, empty set은 유일.
임의의 object $x$, $y$에 대해, pair set \[\{x, y\}\]를 만들 수 있다. 이때
\[\{x, y\} = \{y, x\}\]
이다. 둘은 같은 원소를 갖기 때문.
만일 $x=y$인 특별한 경우, $\{ x, x\} = \{x\}$.
비슷하게, 임의의 object $x$, $y$, $z$에 대해 \[\{x, y, z\}\]를 만들 수 있다. 일반적으로 set $\{x_{1}, x_{2}, \cdots, x_{n}\}$은 정확히 $x_{1}, x_{2}, \cdots, x_{n}$를 원소로 같는 set.
Example 1.1.4
$\varnothing$을 원소로 갖는 set $\{\varnothing\}$을 만들 수 있다.
$\{\varnothing\} \not= \varnothing$인데, $\varnothing \in \{\varnothing\}$이나 $\varnothing \notin \varnothing$이기 때문. 그러면 $\{\{\varnothing\}\}$, $\{\{\{\varnothing\}\}\}$도 만들 수 있을 거고…
Exercise 1.1.5
세 set $\varnothing$, $\{\varnothing\}$, $\{\{\varnothing\}\}$를 생각. 이들은 모두 서로 다르다는 것을 보여라.
Proof.
Extensionality에 따르면, 한쪽에는 포함되나 다른쪽에는 포함되지 않는 element가 존재함을 보이면 된다.
$\varnothing \in \{\varnothing\}$이나 $\varnothing \notin \varnothing$이므로 $\varnothing \not= \{\varnothing\}$ [Example 1.1.4]. $\{\varnothing\} \in \{\{\varnothing\}\}$이나 $\{\varnothing\} \notin \varnothing$이므로 $\varnothing \not= \{\{\varnothing\}\}$. $\varnothing \in \{\varnothing\}$이나 $\varnothing \notin \{\{\varnothing\}\}$이므로 $\{\varnothing\} \not= \{\{\varnothing\}\}$. $\square$
Set $A$, $B$의 union(합집합) $A \cup B$는 $A$ 또는 $B$에 속하는 모든 element들의 set.
Set $A$, $B$의 intersection(교집합) $A \cap B$는 $A$와 $B$ 둘 다에 속하는 모든 element들의 set.
$A \cap B = \varnothing$이면, set $A$와 $B$는 disjoint(서로소)하다고 한다.
Set $A$가 set $B$의 subset(부분집합)이라는 것은 $A$의 모든 element가 $B$의 element이기도 하다는 말과 동치. 이를 $A \subseteq B$로 나타낸다.
만약 $A \subseteq B$이면, A가 B에 포함된다(included) 또는 B가 A를 포함한다(includes)고 말한다.
$\varnothing$은 모든 set들의 subset1.
Example 1.1.6
-
$\varnothing \subseteq \varnothing$ 그러나 $\varnothing \notin \varnothing$.
-
$\{\varnothing\} \in \{\{\varnothing\}\}$ 그러나 $\{\varnothing\} \not\subseteq \{\{\varnothing\}\}$.
-
$U_{K}$를 대한민국을 이루는 3요소들의 set,2,
$U_{p}$를 대한민국의 모든 국민들의 set이라고 하자. 그러면 \[ \textrm{박지훈} \in U_{p} \in U_{K} \] 그러나 \[ \textrm{박지훈} \notin U_{K} \]이므로, $U_{p} \not\subseteq U_{K}$.
임의의 set $A$는 하나 이상의 subset들을 가질 수 있다.
$A$의 power set(멱집합) $\mathcal{P}(A)$는 $A$의 모든 subset들을 모아 놓은 set.
\[\begin{align*} \mathcal{P}(\varnothing) &= \{\varnothing\}\\ \mathcal{P}(\{\varnothing\}) &= \{\varnothing, \{\varnothing\} \}\\ \mathcal{P}(\{0, 1\}) &= \{\varnothing, \{0\}, \{1\}, \{0, 1\} \} \end{align*}\]Exercise 1.1.7
$B \subseteq C$이면, $\mathcal{P}(B) \subseteq \mathcal{P}(C)$이다.
Proof.
$A \in \mathcal{P}(B)$라고 가정하자. 그러면 $\mathcal{P}(B)$는 $B$의 모든 subset들을 모아놓은 set이고, $A$는 그 중 하나이므로 $A \subseteq B$이다. 따라서 $A \subseteq C$이고, $A \in \mathcal{P}(C)$. $\square$
Principle 1.1.8 [Abstraction]
조건을 줌으로써 set을 specify할 수 있다. 어떤 조건 $\underline{ }x\underline{ }$를 만족하는 모든 object $x$의 set을 다음과 같이 쓸 수 있다.
\[\{x | \underline{ }x\underline{ }\}\]Example 1.1.9
-
$\mathcal{P}(A) = \{x|x \textrm{ is a subset of }A\} = \{x|x \subseteq A \}$
-
$A \cap B = \{y|y\in A \textrm{ and } y \in B \}$
-
$\{z|z \not= z\} = \varnothing$
-
$\{n|n \textrm{ is an even prime}\} = \{2\}$
그러나 조건을 이상하게 설정한다면…
Example 1.1.10 [Berry’s Paradox]
Set $A$를 다음과 같이 정의하자.
\[A=\{x|x \textrm{ is a positive integer definable in one line of type}\}\]‘definable’? 한 줄 안에 정의내릴 수 있는 양의 정수들의 예시:
\[\begin{align*} & 12317 \\ & \textrm{백만번째 소수} \\ & 2^{2^{n}}+1 \textrm{형태의 소수가 아닌 가장 작은 자연수} \\ & \textrm{23번째 완전수} \end{align*}\]이 포스팅에서 “한 줄” 안에 들어갈 수 있는 문자의 개수는 유한하게 정해져 있고, “한 줄”을 이룰 수 있는 글자들의 종류 역시 유한하므로, $A$는 정수들의 finite set(유한집합).
이제 $A$에 포함되지 않는 가장 작은 양의 정수를 생각하자. 다음과 같이 쓸 수 있을 것이다:
\[\textrm{The least positive integer not definable in one line}\]이 정수는 $A$에 포함되지 않으므로 한 줄로 정의되어서는 안되는데, 위처럼 한 줄로 정의된 양의 정수이다!
Example 1.1.11 [Russell’s Paradox]
다음 set $A$를 생각.
\[A=\{x | x \notin x \}\]즉 $A$는 스스로가 자기 자신의 member가 되지 않는 모든 object들의 set.
그렇다면 $A$는 자기 자신의 member일까?
- $A \notin A$이면, $A$는 자기 자신의 member가 아니므로 $A$의 조건을 만족한다. 따라서 $A \in A$여야 한다.
- $A \in A$이면, $A$는 $A$의 조건을 만족하지 못하므로 $A \notin A$이다.
어느쪽이든 모순된 결과를 낳는다!
왜 이런 문제가 발생했을까?
Berry’s paradox의 경우 ‘definable’이라는 개념이 모호했기 때문.
Russell’s paradox는… 결론에 모순이 등장했다는 것은 전제에 문제가 있기 때문인데, 애초에 $A$가 set이 아니었던 걸까?3
위 역설들의 해결은 Ch. 2에서 이루어진다.