집합과 순서쌍 · Sets & Ordered Pairs
문제. $x$와 $y$가 원소이고 $x \neq y$라 가정하자. $(x, y) \neq (y, x)$임을 증명하라.
증명. Kuratowski 정의에 의해 순서쌍은 다음과 같이 정의된다:
$(x, y) = (y, x)$라 가정하면, $\{\{x\}, \{x, y\}\} = \{\{y\}, \{y, x\}\}$이다.
$\{x\} \in \{\{y\}, \{y, x\}\}$이므로, $\{x\} = \{y\}$ 또는 $\{x\} = \{y, x\}$이다.
$\{x\} = \{y\}$이면 $x = y$이므로 $x \neq y$에 모순이다.
$\{x\} = \{y, x\}$이면 $y \in \{x\}$이므로 $y = x$이고, 역시 모순이다.
따라서 $(x, y) \neq (y, x)$이다.
Problem. Let $x$ and $y$ be elements and assume that $x \neq y$. Prove that $(x, y) \neq (y, x)$.
Proof. By Kuratowski's definition:
Suppose $(x,y) = (y,x)$. Then $\{\{x\},\{x,y\}\} = \{\{y\},\{y,x\}\}$.
Since $\{x\} \in \{\{y\},\{y,x\}\}$, either $\{x\} = \{y\}$ or $\{x\} = \{y,x\}$.
If $\{x\} = \{y\}$, then $x = y$, contradicting $x \neq y$.
If $\{x\} = \{y,x\}$, then $y \in \{x\}$, so $y = x$, again a contradiction.
Therefore $(x,y) \neq (y,x)$. $\square$
문제. $n$을 양의 정수(자연수)라 하자. 순서 $n$-tuple을 정의하라.
증명. 순서 $n$-tuple을 귀납적으로 정의한다.
기저: $n = 1$일 때, 순서 $1$-tuple $(x_1)$은 그냥 $x_1$ 자체이다.
귀납 단계: 순서 $(n-1)$-tuple이 정의되었다고 가정하자. 순서 $n$-tuple은 다음과 같이 정의한다:
즉, 순서 $n$-tuple은 순서 $(n-1)$-tuple과 $x_n$의 순서쌍으로 정의된다.
Problem. Let $n$ be a positive integer (natural number). Define ordered $n$-tuples.
Proof. Define ordered $n$-tuples inductively.
Base case: For $n = 1$, the ordered $1$-tuple $(x_1)$ is simply $x_1$ itself.
Inductive step: Assuming ordered $(n{-}1)$-tuples are defined, set:
That is, an ordered $n$-tuple is the ordered pair of the ordered $(n{-}1)$-tuple $(x_1,\ldots,x_{n-1})$ and the element $x_n$. $\square$
문제. $S$와 $T$를 집합이라 하자. $S$와 $T$ 사이의 관계를 수학적으로 어떻게 정의할 수 있는가?
증명. $S$와 $T$ 사이의 관계(relation)란 카르테시안 곱 $S \times T$의 부분집합 $R$을 말한다:
$(s, t) \in R$일 때 "$s$는 $t$와 관계 $R$에 있다"고 말하며, $sRt$로 표기한다.
특별한 경우로 $S = T$이면 $R$을 $S$ 위의 관계라 한다. 순서 관계, 동치 관계 등이 이 정의의 특수한 경우이다.
Problem. Let $S$ and $T$ be sets. How can we define a relation between $S$ and $T$ mathematically?
Proof. A relation between $S$ and $T$ is a subset $R$ of the Cartesian product $S \times T$:
When $(s,t) \in R$, we say "$s$ is related to $t$ by $R$" and write $sRt$.
When $S = T$, we call $R$ a relation on $S$. Order relations and equivalence relations are special cases of this definition. $\square$
상한과 하한 · Supremum & Infimum
문제. $\sup E$가 존재하면 유일함을 보여라. 아래로 유계인 집합 $E$의 최대하계(infimum)도 같은 방법으로 유일하게 정의됨을 보여라.
증명. $\alpha$와 $\beta$가 모두 $\sup E$라 가정하자.
$\alpha$는 $E$의 상계이고 $\beta$는 최소상계이므로, $\beta \leq \alpha$이다.
반대로, $\beta$는 $E$의 상계이고 $\alpha$는 최소상계이므로, $\alpha \leq \beta$이다.
따라서 $\alpha = \beta$이다.
$\inf E$의 유일성도 동일하다: $\gamma, \delta$가 모두 $\inf E$이면, $\gamma$는 하계이고 $\delta$는 최대하계이므로 $\gamma \leq \delta$이다. 마찬가지로 $\delta \leq \gamma$이므로 $\gamma = \delta$이다.
Problem. Show that $\sup E$ is unique. The greatest lower bound, or infimum, of a set $E$ which is bounded below is defined in the same manner.
Proof. Suppose $\alpha$ and $\beta$ are both suprema of $E$.
Since $\alpha$ is an upper bound and $\beta$ is the least upper bound, $\beta \leq \alpha$.
Since $\beta$ is an upper bound and $\alpha$ is the least upper bound, $\alpha \leq \beta$.
Therefore $\alpha = \beta$.
Uniqueness of $\inf E$ follows identically: if $\gamma, \delta$ are both infima, then $\gamma \leq \delta$ and $\delta \leq \gamma$, so $\gamma = \delta$. $\square$
문제 (a). $A = \{p \in \mathbb{Q} : p > 0 \text{ and } p^2 < 2\}$, $B = \{p \in \mathbb{Q} : p > 0 \text{ and } p^2 > 2\}$로 놓자. $A$와 $B$의 상한·하한 성질을 $\mathbb{Q}$ 안에서 논하라.
문제 (b). $\alpha = \sup E$이면 $\alpha$가 $E$의 원소일 수도, 아닐 수도 있음을 보여라.
증명 (a). $A$는 상계를 가진다. 사실, $B$의 모든 원소가 $A$의 상계이다. $B$는 공집합이 아닌 원소를 가지므로(예: $2 \in B$), $A$는 위로 유계이다.
그러나 $A$에는 가장 큰 원소가 없다: 임의의 $p \in A$에 대해, Rudin의 구성에 의해 $p < q$이고 $q \in A$인 유리수 $q$가 항상 존재한다.
마찬가지로 $B$에는 가장 작은 원소가 없다.
핵심: $A$는 $\mathbb{Q}$ 안에서 최소상계를 갖지 않는다. $\sup A = \sqrt{2}$이지만 $\sqrt{2} \notin \mathbb{Q}$이기 때문이다. 이것이 $\mathbb{Q}$가 최소상계 성질을 갖지 않는 이유이다.
증명 (b). $E_1 = \{r \in \mathbb{Q} : r < 0\}$, $E_2 = \{r \in \mathbb{Q} : r \leq 0\}$으로 놓으면, $\sup E_1 = \sup E_2 = 0$이다. $0 \notin E_1$이지만 $0 \in E_2$이다.
Problem (a). Let $A = \{p \in \mathbb{Q} : p > 0 \text{ and } p^2 < 2\}$ and $B = \{p \in \mathbb{Q} : p > 0 \text{ and } p^2 > 2\}$. Discuss the sup/inf properties of $A$ and $B$ within $\mathbb{Q}$.
Problem (b). If $\alpha = \sup E$ exists, then $\alpha$ may or may not be a member of $E$. Give examples.
Proof (a). Since $A$ has upper bounds (every member of $B$ is an upper bound of $A$, and $B$ is nonempty since $2 \in B$), $A$ is bounded above.
But $A$ contains no largest member: for any $p \in A$, by Rudin's construction, there exists $q \in A$ with $q > p$. Similarly, $B$ contains no smallest member.
The key point: $A$ has no least upper bound in $\mathbb{Q}$. We have $\sup A = \sqrt{2}$, but $\sqrt{2} \notin \mathbb{Q}$. This shows $\mathbb{Q}$ does not have the least-upper-bound property.
Proof (b). Let $E_1 = \{r \in \mathbb{Q} : r < 0\}$ and $E_2 = \{r \in \mathbb{Q} : r \leq 0\}$. Then $\sup E_1 = \sup E_2 = 0$, but $0 \notin E_1$ while $0 \in E_2$. $\square$
최소상계·최대하계 성질 · LUB & GLB Properties
문제. 최대하계 성질(greatest-lower-bound property)을 정의하라.
정의. 순서 집합 $S$가 최대하계 성질(greatest-lower-bound property)을 가진다는 것은 다음을 의미한다:
$S$의 공집합이 아닌 부분집합 $E$가 아래로 유계이면, $\inf E$가 $S$ 안에 존재한다.
즉, 아래로 유계인 모든 비어있지 않은 부분집합이 $S$ 안에서 최대하계를 가진다.
비고. Theorem 1.18에 의해, 최소상계 성질을 가진 순서 집합은 자동으로 최대하계 성질도 가진다.
Problem. Define the greatest-lower-bound property.
Definition. An ordered set $S$ has the greatest-lower-bound property if:
Every nonempty subset $E \subset S$ that is bounded below has $\inf E \in S$.
Remark. By Theorem 1.18, an ordered set with the least-upper-bound property automatically has the greatest-lower-bound property. $\square$
문제. 최대하계 성질이 최소상계 성질을 함의함을 증명하라.
증명. $S$가 최대하계 성질을 가지는 순서 집합이라 하자. $E \subset S$가 공집합이 아니고 위로 유계임을 가정한다. $\sup E$가 $S$ 안에 존재함을 보여야 한다.
$U$를 $E$의 모든 상계의 집합이라 하자. $E$가 위로 유계이므로 $U \neq \emptyset$이다.
임의의 $x \in E$에 대해, $x \leq u$가 모든 $u \in U$에 대해 성립한다. 따라서 $U$는 아래로 유계이다($E$의 모든 원소가 $U$의 하계).
$S$가 최대하계 성질을 가지므로, $\alpha = \inf U$가 $S$ 안에 존재한다.
$\alpha$가 $\sup E$임을 보이자:
(i) 임의의 $x \in E$에 대해, $x$는 $U$의 하계이므로 $x \leq \alpha = \inf U$이다. 따라서 $\alpha$는 $E$의 상계이다.
(ii) $\gamma < \alpha$이면, $\gamma$는 $U$의 하계가 아니다($\alpha$가 최대하계이므로). 따라서 $\gamma < u$인 $u \in U$가 존재하므로, $\gamma$는 $E$의 상계가 아니다... 이것은 올바르지 않다. 더 정확히:
$\gamma$가 $E$의 상계이면 $\gamma \in U$이므로 $\alpha = \inf U \leq \gamma$이다. 따라서 $\alpha$보다 작은 어떤 수도 $E$의 상계가 될 수 없으므로, $\alpha = \sup E$이다.
Problem. Prove that the greatest-lower-bound property implies the least-upper-bound property.
Proof. Suppose $S$ has the greatest-lower-bound property. Let $E \subset S$ be nonempty and bounded above. We show $\sup E$ exists in $S$.
Let $U$ be the set of all upper bounds of $E$. Since $E$ is bounded above, $U \neq \emptyset$. Every $x \in E$ satisfies $x \leq u$ for all $u \in U$, so $U$ is bounded below.
By the GLB property, $\alpha = \inf U$ exists in $S$.
We claim $\alpha = \sup E$:
(i) $\alpha$ is an upper bound of $E$: for any $x \in E$, $x$ is a lower bound of $U$, so $x \leq \inf U = \alpha$.
(ii) $\alpha$ is the least upper bound: if $\gamma$ is any upper bound of $E$, then $\gamma \in U$, so $\alpha = \inf U \leq \gamma$.
Therefore $\alpha = \sup E \in S$. $\square$
순서체와 실수의 유일성 · Ordered Fields & Uniqueness of $\mathbb{R}$
문제. $\mathbb{R}_1$과 $\mathbb{R}_2$가 최소상계 성질을 가지고 $\mathbb{Q}$를 포함하는 순서체라 하자. $\mathbb{R}_1$과 $\mathbb{R}_2$를 어떤 의미에서 동일시할 수 있음을 보여라. 즉, $\mathbb{R}$은 최소상계 성질을 가지고 $\mathbb{Q}$를 포함하는 유일한 순서체임을 보여라.
증명 스케치. $\varphi: \mathbb{R}_1 \to \mathbb{R}_2$를 다음과 같이 정의한다: 각 $x \in \mathbb{R}_1$에 대해,
즉, $\mathbb{R}_1$에서 $x$보다 작은 유리수들의 집합을 $\mathbb{R}_2$에서의 상한으로 보낸다.
잘 정의됨: $\mathbb{Q}$의 아르키메데스 성질에 의해, 위 집합은 공집합이 아니고 위로 유계이다. $\mathbb{R}_2$가 최소상계 성질을 가지므로 $\sup$이 존재한다.
$\varphi$가 순서체 동형사상임을 보인다:
(1) $\varphi$는 단사(injective): $x < y$이면 $\{q \in \mathbb{Q} : q < x\} \subsetneq \{q \in \mathbb{Q} : q < y\}$이므로 $\varphi(x) < \varphi(y)$.
(2) $\varphi$는 전사(surjective): 임의의 $y \in \mathbb{R}_2$에 대해, $x = \sup_{\mathbb{R}_1}\{q \in \mathbb{Q} : q < y\}$로 놓으면 $\varphi(x) = y$.
(3) $\varphi$는 체 연산을 보존: $\varphi(x + y) = \varphi(x) + \varphi(y)$, $\varphi(xy) = \varphi(x)\varphi(y)$.
따라서 $\mathbb{R}_1 \cong \mathbb{R}_2$이다.
Problem (Difficult). Let $\mathbb{R}_1$ and $\mathbb{R}_2$ be ordered fields which have the least-upper-bound property and contain $\mathbb{Q}$. Show that we can identify $\mathbb{R}_1$ and $\mathbb{R}_2$ in a certain sense. In other words, show that $\mathbb{R}$ is the unique ordered field which has the least-upper-bound property and contains $\mathbb{Q}$ in a certain sense.
Proof sketch. Define $\varphi: \mathbb{R}_1 \to \mathbb{R}_2$ by:
Well-defined: By the Archimedean property, the set above is nonempty and bounded above, so the supremum exists in $\mathbb{R}_2$.
$\varphi$ is an ordered field isomorphism:
(1) Injective: $x < y$ implies the Dedekind cuts are strictly nested, so $\varphi(x) < \varphi(y)$.
(2) Surjective: for any $y \in \mathbb{R}_2$, set $x = \sup_{\mathbb{R}_1}\{q \in \mathbb{Q} : q < y\}$; then $\varphi(x) = y$.
(3) Preserves field operations: $\varphi(x+y) = \varphi(x)+\varphi(y)$ and $\varphi(xy) = \varphi(x)\varphi(y)$.
Therefore $\mathbb{R}_1 \cong \mathbb{R}_2$. $\square$
확장된 실수 체계 · Extended Real Number System
문제. $\inf \emptyset = \infty$로 정의하는 것이 자연스러운가?
증명. 자연스럽다. 그 이유는 다음과 같다:
$\inf E$의 정의는 "$E$의 하계 중 가장 큰 것"이다. $\emptyset$의 경우, 모든 실수가 $\emptyset$의 하계이다 (공허하게 참이므로).
확장된 실수 $\overline{\mathbb{R}} = \mathbb{R} \cup \{-\infty, +\infty\}$에서, 모든 원소 $x$에 대해 $x \leq +\infty$이므로 $+\infty$도 $\emptyset$의 하계이다.
하계 중 가장 큰 것은 $+\infty$이므로, $\inf \emptyset = +\infty$로 정의하는 것이 자연스럽다.
직관적으로: 집합에 원소가 없으면 "아래에서 제한하는 것이 없으므로" 하한이 가능한 한 가장 큰 값을 가진다.
Problem. Is it natural to define $\inf \emptyset = \infty$?
Proof. Yes. By definition, $\inf E$ is the greatest lower bound of $E$. For $E = \emptyset$, every real number is vacuously a lower bound of $\emptyset$.
In $\overline{\mathbb{R}} = \mathbb{R} \cup \{-\infty, +\infty\}$, $+\infty$ is also a lower bound (vacuously). The greatest lower bound is therefore $+\infty$.
Intuitively: with no elements to constrain from below, the infimum is as large as possible. $\square$
문제. $\inf \emptyset = \infty$, $\sup \emptyset = -\infty$로 정의하자. $\overline{\mathbb{R}}$의 모든 부분집합이 최대하계를 가짐을 보여라.
증명. $E \subset \overline{\mathbb{R}}$를 임의의 부분집합이라 하자. 다음 경우를 나누어 증명한다:
경우 1: $E = \emptyset$이면, 정의에 의해 $\inf E = +\infty \in \overline{\mathbb{R}}$이다.
경우 2: $E \neq \emptyset$이고 $E$가 $\mathbb{R}$에서 아래로 유계이면 (즉, 어떤 실수 $m$이 모든 $x \in E \cap \mathbb{R}$에 대해 $m \leq x$를 만족), $-\infty \in E$이면 $\inf E = -\infty$이다. $-\infty \notin E$이면 $\mathbb{R}$의 최대하계 성질에 의해 $\inf E \in \mathbb{R} \subset \overline{\mathbb{R}}$이다.
경우 3: $E$가 아래로 유계가 아니면, $-\infty \in E$이거나 $E$가 임의로 작은 실수를 포함하므로, $\inf E = -\infty \in \overline{\mathbb{R}}$이다.
모든 경우에 $\inf E \in \overline{\mathbb{R}}$이므로, $\overline{\mathbb{R}}$의 모든 부분집합은 최대하계를 가진다.
Problem. Define $\inf \emptyset = \infty$ and $\sup \emptyset = -\infty$. Show that every subset of $\overline{\mathbb{R}}$ has a greatest lower bound.
Proof. Let $E \subset \overline{\mathbb{R}}$ be arbitrary.
Case 1: $E = \emptyset$. By definition, $\inf E = +\infty \in \overline{\mathbb{R}}$.
Case 2: $E \neq \emptyset$ and $E$ is bounded below in $\mathbb{R}$. If $-\infty \in E$, then $\inf E = -\infty$. Otherwise, by the GLB property of $\mathbb{R}$, $\inf E \in \mathbb{R} \subset \overline{\mathbb{R}}$.
Case 3: $E$ is not bounded below. Then either $-\infty \in E$ or $E$ contains arbitrarily small reals, so $\inf E = -\infty \in \overline{\mathbb{R}}$.
In all cases $\inf E \in \overline{\mathbb{R}}$. $\square$
문제 (a). $\mathbb{R}^2$에 순서를 줄 수 있는가?
문제 (b). $\mathbb{R}^2$를 순서체로 만들 수 있는가?
증명 (a). 가능하다. 사전식 순서(lexicographic order)를 정의하면 된다:
이것이 전순서(total order)임을 확인할 수 있다: 임의의 두 원소 $(a_1, a_2)$와 $(b_1, b_2)$에 대해, 세 관계 $<$, $=$, $>$ 중 정확히 하나가 성립한다.
증명 (b). 불가능하다. $\mathbb{R}^2$를 순서체로 만들 수 없다.
귀류법: $\mathbb{R}^2$가 순서체라 가정하자. 순서체에서 $x^2 \geq 0$이 모든 원소에 대해 성립해야 한다.
$i = (0, 1)$로 놓으면, $i^2 = i \cdot i$가 정의되어야 한다. 순서체의 성질에 의해 $i^2 > 0$이거나 $i^2 = 0$이거나 $i = 0$이어야 한다.
그런데 $\mathbb{R}^2$의 어떤 곱셈 구조를 주더라도, $\mathbb{R}^2$가 체가 되려면 $\mathbb{C}$와 동형이어야 한다. $\mathbb{C}$에서 $i^2 = -1 < 0$이므로 순서체의 조건 $x^2 \geq 0$에 모순이다.
더 일반적으로, $\mathbb{R}^2$를 체로 만들면 $x^2 + 1 = 0$의 해가 존재하게 되어 순서체가 될 수 없다.
Problem (Difficult). (a) Can we give an order on $\mathbb{R}^2$?
(b) Can we make $\mathbb{R}^2$ an ordered field?
Proof (a). Yes. Define the lexicographic order:
This is a total order on $\mathbb{R}^2$.
Proof (b). No. Suppose $\mathbb{R}^2$ is an ordered field. In any ordered field, $x^2 \geq 0$ for all $x$.
Any field structure on $\mathbb{R}^2$ (as a 2-dimensional $\mathbb{R}$-algebra that is a field) is isomorphic to $\mathbb{C}$. In $\mathbb{C}$, $i^2 = -1 < 0$, contradicting $x^2 \geq 0$.
More generally, any field containing $\mathbb{R}$ as a subfield with $[\mathbb{R}^2:\mathbb{R}] = 2$ must have a root of $x^2 + 1 = 0$, making it impossible to be an ordered field. $\square$