Trichotomy and Completeness of Ordinals

21 Nov 2024

1. Basic Concepts

Definition. A set $(W, <)$ is called a well-ordered set if it satisfies the following conditions:

1. $(W, <)$ is a total order.
2. Every non-empty subset of $W$ has a least element.

Definition. If $(W, <)$ is a well-ordered set, a subset $S$ of $W$ such that $x < a \rightarrow x \in S$ for some $a \in S$ is called an initial segment.

Theorem. If $S$ is an initial segment of a well-ordered set $(W, <)$, then for some $a \in W$, the following holds:

\[S = W[a] := \{ x \in W : x < a \}\]

Proof. Let $a$ be the least element of $W \setminus S$.

2. Trichotomy of Order

Theorem.

1. A well-ordered set cannot be isomorphic to its initial segment.
2. The only order-preserving automorphism of a well-ordered set is the identity map.
3. The isomorphism between two well-ordered sets is unique.

Proof. We first prove the following lemma:

Lemma. If $f: (W, <) \to (W, <)$ is order-preserving, then for all $x \in W$, $x \leq f(x)$.

Proof of the Lemma. Assume for contradiction that $S = \lbrace x \in W : x > f(x) \rbrace$ is nonempty. Since $W$ is a well-ordered set, there exists a least element $c = \min S$. Since $c \in S$, we have $c > f(c)$, and since $f$ is order-preserving, it follows that $f(c) > f(f(c))$. On the other hand, since $c = \min S$, we have $f(c) \notin S$, and thus $f(f(c)) \geq f(c)$, leading to a contradiction. □

Proof of (1).

Assume $f: (W, <) \to (W[a], <)$ is an isomorphism. The inclusion map $j: W[a] \to W$ implies that $jf: (W, <) \to (W, <)$ is order-preserving. Therefore, $jf(a) \geq a$. However, since $a \notin \mathrm{im}f$, this leads to a contradiction. □

Proof of (2).

Assume $f: (W, <) \to (W, <)$ is an isomorphism. Since $f^{-1}$ is also an isomorphism, for all $x \in W$, we have $x \leq f(x)$ and $f(x) \leq f^{-1}(f(x)) = x$. Thus, $x = f(x)$. □

Proof of (3).

Assume $f, g: (W_1, <_1) \to (W_2, <_2)$ are isomorphisms. The composition $g^{-1}f: (W_1, <_1) \to (W_1, <_1)$ is an automorphism, and by (2), it must be the identity map. Therefore, $f = g$. ■

Trichotomy of Order. For well-ordered sets $(W_1, <_1)$ and $(W_2, <_2)$, exactly one of the following holds:

1. $(W_1, <_1) \sim (W_2, <_2)$
2. For some $a$, $(W_1[a], <_1) \sim (W_2, <_2)$
3. For some $b$, $(W_1, <_1) \sim (W_2[b], <_2)$

In each case, the isomorphism is unique, and in cases 2 and 3, $a$ and $b$ are unique.

Proof.

The preceding theorems guarantee that 1, 2, and 3 are mutually exclusive and establish the claim of uniqueness. Therefore, it suffices to show that any pair of well-ordered sets $(W_1, <_1)$ and $(W_2, <_2)$ falls into one of the three cases.

We define a partial function $f: W_1 \to W_2$ as follows:

\[f := \{ (x, y) \in (W_1, W_2) : (W_1[x], <_1) \sim (W_2[y], <_2) \}\]

It can be easily verified that $f$ is injective and order-preserving. We now consider two cases.

Case 1. $\mathrm{dom} f = W_1$

This corresponds to case 3 of the theorem, concluding the proof.

Case 2. $\mathrm{dom} f \subsetneq W_1$

First, we show that for some $a \in W$, $\mathrm{dom}f = W_1[a]$. If $x \in \mathrm{dom}f$, then $W_1[x] \sim W_2[f(x)]$. Let $\phi$ be the isomorphism of that isomorphism. For $x’ < x$, we have $W_1[x’] = W_2[\phi(x’)]$, thus $x’ \in \mathrm{dom}f$. Therefore, $\mathrm{dom} f$ is an initial segment.

Next, we show that $\mathrm{im} f = W_2$. Assume $\mathrm{dom}f = W_1[a]$. By a similar argument as above, we can show that $\mathrm{im}f$ is also an initial segment of $W_2$. If $\mathrm{im}f = W_2[b]$, then $(a, b) \in f$, which implies $a \in \mathrm{dom}f$, leading to a contradiction. ■

3. Completeness of Ordinals

Completeness of Ordinals. Every well-ordered set is order-isomorphic to some ordinal.

Proof. Let $(W, <)$ be a well-ordered set. We define $A$ and $S$ as follows:

\[\begin{gather} A = \{ a \in W : W[a] \sim \alpha_a \text{ where } \alpha_a \in \mathrm{Ord} \}\\ S = \{ \alpha_a \in \mathrm{Ord} : a \in A \} \end{gather}\]

It can be easily shown that $S$ is an ordinal and $A$ is an initial segment. Let $S = \beta$ and $A = W[c]$. The function $f: A \to S; a \mapsto \alpha_a$ is an order isomorphism between $(A, <)$ and $(S, \in)$. Thus, $W[c] \simeq \beta$, which implies $c \in A$, leading to a contradiction. Therefore, $A = W \sim \beta$. ■

4. Axiom of Replacement

The existence of $S$ in the above proof cannot be guaranteed without the Axiom of Replacement. This is because, due to Burali-Forti’s paradox, $\mathrm{Ord}$ is not a set, and thus the existence of $S$ cannot be guaranteed by the Axiom of Separation (see: List of ZFC Axioms).

Another example demonstrating the necessity of the Axiom of Replacement is that without it, we cannot guarantee the existence of $\omega + \omega$. For each $n \in \mathbb{N}$, the existence of $\omega + n$ can be shown using the Axiom of Pairing and the Axiom of Union, but the existence of $\omega + \omega := \bigcup_{n \in \mathbb{N}} (\omega + n)$ cannot be established. However, we cannot simply add an axiom allowing the union of arbitrary sets, as this would make “the set of all sets” a set, leading to Russell’s paradox.

In both cases, what we need is an axiom stating that “given a well-defined one-to-one correspondence $R(x,y)$ and a set $X$, the collection $\lbrace y : R(x, y), x \in X \rbrace$ is a set.” This axiom is the Axiom of Replacement. Using the Axiom of Replacement, we can show that given:

\[\begin{gather} \omega = \lbrace 0, 1, 2, ... \rbrace \\ R(x, y): y = \omega + x, \end{gather}\]

the image $\mathrm{im}R|_\omega = \lbrace \omega, \omega + 1, \omega + 2, … \rbrace$ exists, and thus $\omega \cup \mathrm{im}R|_\omega = \omega + \omega$ exists.

유리수와 실수의 집합론적 정의

20 Nov 2024

1. 칸토어의 동형성 정리

칸토어의 동형성 정리. 가산이고 양끝점이 없으며 조밀한 전순서 집합은 순서 동형에 대해 유일하다.

증명 1. (Back-and-Forth Argument)

$n$번째 단계에서 가장 인덱스가 작은 $a_k \in A \setminus \mathrm{dom} f_n$을 순서 동형성을 만족하게끔 임의의 $b \in B \setminus \mathrm{im} f_n$과 대응시키고, 가장 인덱스가 작은 $b_l \in B \setminus (\mathrm{im} f_n \cup \lbrace b \rbrace)$ 를 순서 동형성을 만족하게끔 임의의 $a \in A \setminus (\mathrm{dom}f_n \cup \lbrace a_k\rbrace)$ 와 대응시킨다. (그림의 파란색은 ‘가장 인덱스가 작은’으로 선택된 원소)

증명 2. (Only-Forth Argument)

$n$번째 단계에서 가장 인덱스가 작은 $a_k \in A \setminus \mathrm{dom} f_n$을 순서 동형성을 만족하게끔 가장 인덱스가 작은 $b_l \in B \setminus \mathrm{im}f_n$과 대응시킨다.

잘못된 증명. (Incorrect Only-Forth Argument)

$n$번째 단계에서 가장 인덱스가 작은 $a_k \in A \setminus \mathrm{dom} f_n$을 순서 동형성을 만족하게끔 임의의 $b \in B \setminus \mathrm{im}f_n$와 대응시킨다.

잘못된 이유. $\mathrm{im} \left[ \bigcup f_n \right]$이 $B$ 전체를 소진한다는 보장이 없다. 일례로 모든 경우 선택된 $b$의 인덱스가 짝수인 경우가 가능하다.

2. 데데킨트 절단

정의. 전순서 집합 $(P, <)$에 대하여 $P$의 부분집합 $A, B$가 다음을 만족할 때 $(A, B)$를 절단이라고 한다.

1. $A \sqcup B = P$
2. 임의의 $a \in A, b \in B$에 대해 $a < b$이다.

추가로 다음을 만족할 때 데데킨트 절단이라고 한다.

1. $A$는 최대 원소를 가지지 않는다.

추가로 다음까지 만족할 때 틈이라고 한다.

1. $B$는 최소 원소를 가지지 않는다.

Remark

1. $P$가 완비이다 ⇔ $P$는 틈을 가지지 않는다.
2. $P = \mathbb{Q}$일 때 틈은 무리수 집합을, 데데킨트 절단은 실수 집합을 나타낸다.

3. 완비화 정리

완비화 정리. $(P, <)$가 양끝점이 없는 조밀한 전순서라면 다음을 만족하는 완비 전순서 $(C, \prec)$가 순서 동형에 대해 유일하게 존재한다.

1. $P \subseteq C$
2. $\prec$는 $P$에서 $<$와 일치한다.
3. $P$는 $C$에서 조밀하다. 즉, $c_1 < c_2 \in C$에 대해 $c_1 < p < c_2$를 만족하는 $p \in P$가 언제나 존재한다.
4. $C$는 양끝점이 없다.

유일성 증명. $(C, \prec)$와 $(C^\ast, \prec^\ast)$가 조건을 만족하는 완비 전순서라고 하자. 다음과 같이 정의된 $\phi: C → C^\ast$는 순서 동형 사상이다.

1. $c \in P$라면 $\phi(c)=c$
2. $c \notin P$라면 $\phi(c) = \sup^\ast \lbrace p \in P : p \prec c \rbrace$

존재성 증명. 다음과 같이 정의한다.

\[\begin{gather} \mathcal{G} = \lbrace (A, B) : (A, B) \text{ is a gap of } P \rbrace \\ \mathcal{D} = \lbrace (A, B) : (A, B) \text{ is a Dedekind cut of } P \rbrace \\ \mathcal{P} = \mathcal{D} \setminus \mathcal{G} \end{gather}\]

라고 하자. 다음과 같이 $\mathcal{D}$에 순서를 준다.

\[(A_1, B_1) \prec (A_2, B_2) \iff A_1 \subset A_2\]

$(A, B) \in \mathcal{P}$라면 어떤 $p$에 대해 $B = \lbrace x \in P : x \geq p \rbrace$이며, 이때 $(A, B) = [p]$라고 적자. 즉,

\[\mathcal{P} = \lbrace [p] : p \in P \rbrace\]

$(\mathcal{P}, \prec) \sim (P, <)$임을 쉽게 확인할 수 있다. 이제 다음을 보인다.

Claim. $\mathcal{D}$는 $\mathcal{P}$에 대해 완비화 정리의 4가지 조건을 모두 만족하는 확장이다.

1, 2, 4는 자명하다. 3을 보인다.

$\mathfrak{d}_1 = (A_1, B_1), \mathfrak{d}_2 = (A_2, B_2) \in \mathcal{D}$에 대해 $\mathfrak{d_1} \prec \mathfrak{d}_2$, 즉 $A_1 \subset A_2$라고 하자. $p \in A_2 \setminus A_1$이며 $p$가 $B$의 최소 원소가 아닌 $p \in P$가 존재한다. 그러한 $p$에 대해 $\mathfrak{d}_1 \prec [p] \prec \mathfrak{d}_2$이다. □

마지막으로 다음을 보인다.

Claim. $(\mathcal{D}, \prec)$는 완비이다.

$\mathcal{S}$가 위로 유계인 $\mathcal{D}$의 공집합이 아닌 부분집합이라고 하자. 다음과 같이 정의한다.

\[\begin{gather} A_\mathcal{S} = \bigcup \lbrace A : (A, B) \in \mathcal{S} \rbrace\\ B_\mathcal{S} = \bigcap \lbrace B : (A, B) \in \mathcal{S} \rbrace \end{gather}\]

$(A_\mathcal{S}, B_\mathcal{S}) \in \mathcal{D}$이며, $\mathcal{S}$의 최소 상계임을 확인할 수 있다. ◾

집합론적 실수의 정의. 다음을 만족하는 집합 $(R, <)$은 순서 동형에 대해 유일하다.

1. 완비 전순서 집합이다.
2. 양끝점이 없다.
3. 분리 가능하다(separable). 즉, $Q \subset R$이 존재하여 $Q$는 가산집합이고 $R$에서 조밀하다.

증명. 칸토어의 동형성 정리와 완비화 정리로부터 따라 나온다.

Set-theoretic Definitions of Rational and Real Numbers

20 Nov 2024

1. Cantor’s Isomorphism Theorem

Cantor’s Isomorphism Theorem. Any countable, dense, linear order without endpoints is unique up to order isomorphism.

Proof 1. (Back-and-Forth Argument)

At the $n$-th step, map the least-indexed $a_k \in A \setminus \mathrm{dom} f_n$ to an arbitrary $b \in B \setminus \mathrm{im} f_n$ so that order isomorphism is preserved, and then map the least-indexed $b_l \in B \setminus (\mathrm{im} f_n \cup \lbrace b \rbrace)$ to an arbitrary $a \in A \setminus (\mathrm{dom}f_n \cup \lbrace a_k\rbrace)$ so that order isomorphism is preserved. (In the diagram, blue indicates the ‘least-indexed’ elements.)

Proof 2. (Only-Forth Argument)

At the $n$-th step, map the least-indexed $a_k \in A \setminus \mathrm{dom} f_n$ to the least-indexed $b_l \in B \setminus \mathrm{im}f_n$ so that order isomorphism is preserved.

Incorrect Proof. (Incorrect Only-Forth Argument)

At the $n$-th step, match the least-index $a_k \in A \setminus \mathrm{dom} f_n$ to an arbitrary $b \in B \setminus \mathrm{im}f_n$ so that order isomorphism is preserved.

Why this is incorrect: There is no guarantee that $\mathrm{im} \left[ \bigcup f_n \right]$ exhausts all of $B$. For example, it is possible that only $b$’s with even indices are chosen in every step.

2. Dedekind Cuts

Definition. For a linearly ordered set $(P, <)$, a pair of subsets $A, B$ of $P$ is called a cut if:

1. $A \sqcup B = P$
2. For any $a \in A, b \in B$, $a < b$.

Furthermore, it is a Dedekind cut if:

1. $A$ has no greatest element.

It is called a gap if, in addition:

1. $B$ has no least element.

Remark

1. $P$ is complete ⇔ $P$ has no gaps.
2. As will be seen, for $P = \mathbb{Q}$, gaps correspond to irrational numbers while Dedekind cuts correspond to real numbers.

3. Completion Theorem

Completion Theorem. If $(P, <)$ is a dense linear order without endpoints, then there exists a unique (up to order isomorphism) complete linear order $(C, \prec)$ satisfying:

1. $P \subseteq C$
2. $\prec$ coincides with $<$ on $P$
3. $P$ is dense in $C$: for any $c_1 < c_2 \in C$, there exists $p \in P$ with $c_1 < p < c_2$
4. $C$ has no endpoints.

Uniqueness Proof. Suppose $(C, \prec)$ and $(C^\ast, \prec^\ast)$ are complete linear orders satisfying the conditions. Define $\phi: C \to C^\ast$ as follows:

1. If $c \in P$, then $\phi(c)=c$
2. If $c \notin P$, then $\phi(c) = \sup^\ast \lbrace p \in P : p \prec c \rbrace$

This $\phi$ is an order isomorphism.

Existence Proof. Define:

\[\begin{gather} \mathcal{G} = \lbrace (A, B) : (A, B) \text{ is a gap of } P \rbrace \\ \mathcal{D} = \lbrace (A, B) : (A, B) \text{ is a Dedekind cut of } P \rbrace \\ \mathcal{P} = \mathcal{D} \setminus \mathcal{G} \end{gather}\]

Define an order on $\mathcal{D}$ by:

\[(A_1, B_1) \prec (A_2, B_2) \iff A_1 \subset A_2\]

If $(A, B) \in \mathcal{P}$, then for some $p$, $B = \lbrace x \in P : x \geq p \rbrace$, and we write $(A, B) = [p]$. That is,

\[\mathcal{P} = \lbrace [p] : p \in P \rbrace\]

It is easy to check that $(\mathcal{P}, \prec) \sim (P, <)$. Now, we show the following:

Claim. $\mathcal{D}$ is an extension of $\mathcal{P}$ satisfying all four conditions of the Completion Theorem.

Conditions 1, 2, and 4 are clear. We show 3.

Let $\mathfrak{d}_1 = (A_1, B_1), \mathfrak{d}_2 = (A_2, B_2) \in \mathcal{D}$ with $\mathfrak{d}_1 \prec \mathfrak{d}_2$, i.e., $A_1 \subset A_2$. There exists $p \in A_2 \setminus A_1$ such that $p$ is not the least element of $B$, i.e., $p \in P$. For such $p$, we have $\mathfrak{d}_1 \prec [p] \prec \mathfrak{d}_2$. □

Finally, we show:

Claim. $(\mathcal{D}, \prec)$ is complete.

Let $\mathcal{S}$ be a nonempty, upward-bounded subset of $\mathcal{D}$. Define:

\[\begin{gather} A_\mathcal{S} = \bigcup \lbrace A : (A, B) \in \mathcal{S} \rbrace\\ B_\mathcal{S} = \bigcap \lbrace B : (A, B) \in \mathcal{S} \rbrace \end{gather}\]

Then $(A_\mathcal{S}, B_\mathcal{S}) \in \mathcal{D}$ and is the least upper bound of $\mathcal{S}$. ◾

Set-theoretic Definition of the Real Numbers. A set $(R, <)$ satisfying the following is unique up to order isomorphism:

1. It is a complete linear order.
2. It has no endpoints.
3. It is separable; i.e., there exists $Q \subset R$ which is countable and dense in $R$.

Proof. This follows from Cantor’s Isomorphism Theorem and the Completion Theorem.

칸토어-슈뢰더-베른슈타인 정리

19 Nov 2024

정리. 두 집합 $X, Y$에 대해 $|X| \leq |Y|$, $|X| \geq |Y|$라면 $|X| = |Y|$이다.

매우 당연해 보이지만 $\leq$가 단사함수의 존재성으로, $=$가 전단사함수의 존재성으로 정의된다는 점에서 트리키한 함수 핸들링을 요구한다.

여담으로 “칸토어-베른슈타인 정리(위키피디아)” 또는 “슈뢰더-베른슈타인 정리(나무위키)”라고도 부르는데 “칸토어-슈뢰더 정리”라고 부르는 경우는 못 봤다. 홍대병에 취해 있다면 “칸토어-슈뢰더 정리”라고 불러보자.

첫 번째 증명

조건에 의해 단사함수 $f: X \to Y, g: Y \to X$가 존재한다. $Z := \mathrm{Im} f$가 $Y$와 같다면 증명이 끝나므로 $Z \subsetneq Y$라고 하자.

임의의 $y \in Z \setminus Y$ (그림에서 빈 점으로 표시) 에 대해,

• $x_1^y = g^{-1}(y)$
• $x_{n+1}^y = g(f(x_n))$

와 같이 두어, $h: X \to Y$를 다음과 같이 정의한다.

• $h_y(x_1^y) = y$
• $h_y(x_{n+1}^y) = f(x_n)$

다음이 성립함을 확인하라.

\[x^y_n = x^z_m \iff y = z, n = m\]

따라서 다음의 함수 $h: X → Y$는 well-defined이다.

\[h(x) = \begin{cases} h_y(x) &x = x^y_n \text{ for some } y, n \\\\ f(x) &\text{otherwise} \end{cases}\]

$h$가 전단사임을 확인하라. ◾

두 번째 증명

보조정리 (기수의 샌드위치 정리). $A_1 \supseteq B \supseteq A_2$에 대해 $|A_1| = |A_2|$라면 $|A_1| = |B| = |A_2|$이다.

증명. $f: A_1 → A_2$가 전단사라고 하자. $B_1 = B$로 둔다. 다음과 같이 $\lbrace A_n\rbrace , \lbrace B_n\rbrace , \lbrace C_n\rbrace $을 정의한다.

\[\begin{gather} A_{n+1} = f[A_n]\\ B_{n+1} = f[B_n]\\ C_n = A_n \setminus B_n \end{gather}\]

$C = \bigcup C_n$ (그림에서 색칠되지 않은 영역), $D = A_1 \setminus C$ (그림에서 색칠된 영역) 라고 하자. $f[C] \subset C, f[D] \subset D$임을 확인하라. 따라서 다음의 $g: B_1 → A_2$는 전단사이다. (화살표)

\[g(x) = \begin{cases} x & x \in C\\ f(x) & x \in D \end{cases}\]

본 정리의 증명. $f: X → Y, g: Y → X$가 전사일 때 $gf[X] \subseteq g[Y] \subseteq X$이고, $| gf[X] | = | X |$이므로, 보조정리에 의해 $|g[Y]| = |Y| = |X|$이다. ◾

잘 생각해 보면 두 증명은 사실 같다.

Cantor–Schröder–Bernstein Theorem

19 Nov 2024

Theorem. For two sets $X, Y$, if $|X| \leq |Y|$ and $|X| \geq |Y|$, then $|X| = |Y|$.

Although this may seem obvious, it requires some delicate function handling, since $\leq$ is defined by the existence of an injective function, while $=$ is defined by the existence of a bijective function.

As a side note, the theorem is often called the “Cantor–Bernstein theorem” or the “Schröder–Bernstein theorem”, but I’ve never seen it called the “Cantor–Schröder theorem.” If you’re feeling a bit pretentious, it’s an open option.

First Proof

By assumption there exists $f: X \to Y, g: Y \to X$ injective. If $Z := \mathrm{Im} f$ equals $Y$, the proof is done, so let us assume $Z \subsetneq Y$.

For any $y \in Z \setminus Y$ (represented as an empty dot in the diagram),

• let $x_1^y = g^{-1}(y)$
• let $x_{n+1}^y = g(f(x_n))$

Now define a function $h: X \to Y$ as follows:

• $h_y(x_1^y) = y$
• $h_y(x_{n+1}^y) = f(x_n)$

Check that the following holds:

\[x^y_n = x^z_m \iff y = z, n = m\]

Thus, the function $h: X \to Y$ defined by

\[h(x) = \begin{cases} h_y(x) &x = x^y_n \text{ for some } y, n \\\\ f(x) &\text{otherwise} \end{cases}\]

is well-defined. Verify that $h$ is bijective. ◾

Second Proof

Lemma (Sandwich Theorem for Cardinals). If $A_1 \supseteq B \supseteq A_2$ and $|A_1| = |A_2|$, then $|A_1| = |B| = |A_2|$.

Proof. Assume $f: A_1 \to A_2$ is bijective. Let $B_1 = B$. Define the sequences $\lbrace A_n\rbrace , \lbrace B_n\rbrace , \lbrace C_n\rbrace$ as follows:

\[\begin{gather} A_{n+1} = f[A_n]\\ B_{n+1} = f[B_n]\\ C_n = A_n \setminus B_n \end{gather}\]

Let $C = \bigcup C_n$ (the unshaded region in the diagram) and $D = A_1 \setminus C$ (the shaded region). Verify that $f[C] \subset C$ and $f[D] \subset D$. Then, define $g: B_1 \to A_2$ as follows (represented as arrows in the diagram).

\[g(x) = \begin{cases} x & x \in C\\ f(x) & x \in D \end{cases}\]

Then $g$ is bijective.

Proof of the main theorem. Given $f: X \to Y$ and $g: Y \to X$ are injective, we have $gf[X] \subseteq g[Y] \subseteq X$ and $| gf[X] | = | X |$. By the lemma, we obtain $|g[Y]| = |Y| = |X|$. ◾

Upon closer reflection, the two proofs are essentially the same.

ZFC 공리의 목록

18 Nov 2024

공리명	의미
외연 공리	집합은 원소의 모임이다.
공집합 공리*	공집합이 존재한다.
짝 공리*	$X, Y$로부터 $Z = \lbrace X, Y \rbrace$를 정의할 수 있다.
합집합 공리	$X = \lbrace Y_i \rbrace$로부터 $Z = \bigcup Y_i$를 정의할 수 있다.
멱집합 공리	$X$로부터 $\mathcal{P}(X)$를 정의할 수 있다.
분류 공리꼴**	$X$로부터 $Y = \lbrace y \in X : \phi(y) \rbrace$를 정의할 수 있다. ($\phi$는 1차 논리식)
무한 공리	모든 자연수를 포함하는 집합이 존재한다.
정칙 공리	$\in$은 정렬 순서이다.
치환 공리꼴	$X$로부터 $f[X]$를 정의할 수 있다. ($f$는 class function)
선택 공리	집합족 $\lbrace X_i \rbrace$에 대해 각 $X_i$의 원소를 하나씩 선택할 수 있다.

공리명	논리식(자유변수는 $\forall$로 양화)
외연 공리	$X = Y \leftrightarrow (z \in X \leftrightarrow z \in Y)$
공집합 공리*	$\exists Z : z \not\in Z$
짝 공리*	$\exists Z : z \in Z \leftrightarrow (z = X \lor z = Y)$
합집합 공리	$\exists Z : z \in Z \leftrightarrow \exists x \in X (z \in x)$
멱집합 공리	$\exists Z : z \in Z \leftrightarrow (w \in z \rightarrow w \in X)$
분류 공리꼴**	$\exists Z : z \in Z \leftrightarrow (z \in X \land \phi(z))$
무한 공리	$\exists Z : \varnothing \in Z \land (z \in Z \rightarrow z \cup \lbrace z \rbrace \in Z)$
정칙 공리	$\exists x \in X : \forall y \in X [ y \not\in x]$
치환 공리꼴	$\displaylines{[\forall x \in X \; \exists! y :\phi(x, y)] \rightarrow [\exists Y \; \forall x \in X \; \exists y \in Y : \phi(x, y)]}$
선택 공리	$\displaylines{\varnothing \notin X \rightarrow \exists f : X \rightarrow \bigcup X [ f(x) \in x ]}$

Remarks.

• 정칙 공리는 다음과 동치

\[\exists x \in X : x \cap X = \varnothing\]

• (*)로 표시된 공리는 분류 공리꼴로부터 유도할 수 있다.
• (**)로 표시된 공리는 치환 공리꼴로부터 유도할 수 있다.
  • 분류 공리꼴의 내용은 “X가 집합이다 → f[X]가 집합이다(f는 함수)”이라는 것이다. f가 함수임을(즉, f의 정의역이 집합임을) 선결적으로 요구함에 유의하라.

공리의 필요성

정리. 다음의 정리들은 선택 공리를 필요로 한다.

• $f: X → Y$가 전사일 때, 어떤 $X$의 부분집합 $Z$에 대해 $f\vert_Z$는 전단사이다.

• $\varnothing \not\in \lbrace X_i\rbrace$일 때 $\prod X_i \neq \varnothing$이다.

• 정렬 원리: 임의의 집합에 정렬 순서를 줄 수 있다.

• 초른의 보조정리: $(X, <)$의 임의의 체인이 $X$에서 상계를 가진다면, $X$는 극댓값_{maximal element}을 가진다.

정리. 다음의 정리들은 치환 공리꼴을 필요로 한다.

• $\omega + \omega$가 존재한다.

• 서수 완전성 정리. 모든 정렬 순서는 서수와 순서 동형이다.

List of ZFC Axioms

18 Nov 2024

Name	Meaning
Extensionality	Set is an unordered collection of elements.
Existence*	There exists the empty set.
Pairing*	From $X, Y$ follows $Z = \lbrace X, Y \rbrace$.
Union	From $X = \lbrace Y_i \rbrace$ follows $Z = \bigcup Y_i$.
Power Set	From $X$ follows $\mathcal{P}(X)$.
Separation Schema**	From $X$ follows $Y = \lbrace y \in X : \phi(y) \rbrace$, where $\phi$ is a first-order formula.
Infinity	There exists a set containing all the natural numbers.
Regularity	$\in$ is a well-ordering.
Replacement	From $X$ follows $f[X]$, where $f$ is a class function definable in first-order logic.
Choice	Every collection of nonempty sets $\lbrace X_i \rbrace$ has a choice function.

Name	Formula (Free variables are to be quantified by $\forall$)
Extensionality	$X = Y \leftrightarrow (z \in X \leftrightarrow z \in Y)$
Existence*	$\exists Z : z \not\in Z$
Pairing*	$\exists Z : z \in Z \leftrightarrow (z = X \lor z = Y)$
Union	$\exists Z : z \in Z \leftrightarrow \exists x \in X (z \in x)$
Power Set	$\exists Z : z \in Z \leftrightarrow (w \in z \rightarrow w \in X)$
Separation Schema**	$\exists Z : z \in Z \leftrightarrow (z \in X \land \phi(z))$
Infinity	$\exists Z : \varnothing \in Z \land (z \in Z \rightarrow z \cup \lbrace z \rbrace \in Z)$
Regularity	$\exists x \in X : \forall y \in X [ y \not\in x]$
Replacement	$\displaylines{[\forall x \in X \; \exists! y :\phi(x, y)] \rightarrow [\exists Y \; \forall x \in X \; \exists y \in Y : \phi(x, y)]}$
Choice	$\displaylines{\varnothing \notin X \rightarrow \exists f : X \rightarrow \bigcup X [ f(x) \in x ]}$

Remarks.

• Regularity is equivalent to the following:

\[\exists x \in X : x \cap X = \varnothing\]

• Those marked by (*) can be derived from the Separation.

• Those marked by (**) can be derived from the Replacement.

Replacement is strictly stronger than Separation:

• Separation can be stated as: If $X$ is a set and $f$ is a function, then $f[X]$ is a set.
• Replacement can be stated as: If $X$ is a set and $f$ is a class function, then $f[X]$ is a set.

The proof of following theorems require Choice.

• If $f: X → Y$ is surjective, there exists a subset $Z$ of $X$ such that $f\vert_Z$ is bijective.
• If $\varnothing \not\in \lbrace X_i\rbrace$, then $\prod X_i \neq \varnothing$.
• Well-ordering Principle. Every set can be well-ordered.
• Zorn’s Lemma. If every chain of $(X, <)$ is bounded in $X$, $X$ has a maximal element.

The proof of following theorems require Replacement.

• $\omega + \omega$ exists.
• Completeness of Ordinals. Every well-ordered set is order-isomorphic to a unique ordinal.

벨의 우주선 사고실험: 수동적 로렌츠 수축과 능동적 로렌츠 수축

17 Nov 2024

우주선 A, B가 가느다란 실로 연결된 채 관성 상태에 있다가 동시에 같은 가속도로 광속에 가깝게 운동하기 시작한다. A와 B를 연결하는 실은 어떻게 되는가?

1. 끊어진다.
2. 느슨해진다.
3. 변화가 없다.

이 문제는 드원과 베란이 1959년에 처음 고안했으나 1976년에 존 스튜어트 벨이 CERN의 물리학자들과 나눈 토론을 통해 유명해졌다. 벨은 로렌츠 수축을 근거로 실이 끊어진다고 주장했으나 CERN의 물리학자들 대다수는 실에 변화가 없다고 반박했으며, 한 저명한 물리학자는 벨이 상대론을 오도하고 있다고까지 말했다. 그렇다면 정답은 과연 무엇일까?

정답은 1. 끊어진다 이다.

이 답은 일면 비직관적이다. 로렌츠 수축은 관성계에 의존적인 현상이기 때문이다. 일례로 철수에 대해 영희가 광속에 가깝게 움직인다면 영희는 수축한다. 하지만 동 상황에서 영희의 관성계를 기준으로는 철수가 광속에 가깝게 움직이므로 철수가 수축한다. 이같은 대칭성은 로렌츠 수축이 실재하는 물리적 현상이 아닌 관성계의 선택에 따른 수학적 현상임을 시사한다. 이같은 로렌츠 수축의 해석은 Rindler 1977의 글에서 볼 수 있듯이 물리학계에서 널리 퍼져있다.

로렌츠에 따르면 수축의 원인은 원자 구조를 밀집시키는 전기적 응집력이 [물체가 에테르를 통과함에 따라] 증가하는 데 있다… [하지만] 상대론에서 로렌츠 수축은 본질적으로 기하학적 투영 효과로서, 정지해 있는 막대기를 비스듬한 시선으로 보는 것과 유사하다.¹

그러나 Rindler의 설명은 반만 맞고 반은 틀렸다. 그 이유는 로렌츠 수축에 두 가지 유형이 있기 때문이다. 수동적 로렌츠 변환_{passive Lorentz transformation}의 경우에는 Rindler의 주장대로 로렌츠 수축이 관성계의 선택에 따른 부수 현상에 불과하지만, 능동적 로렌츠 변환_{active Lorentz transformation}의 경우에는 로렌츠 수축이 전기력의 증가와 같은 실질적 물리 현상을 야기한다. 본 글에서는 두 변환의 차이가 무엇인지, 그리고 어떻게 능동적 로렌츠 변환은 전기력과 연관되는지 살펴볼 것이다.

1. 수동적 변환

점입자 A가 빈 공간에서 관성 운동한다. A에 대해 정지해 있는 관성좌표계 $(x, t)$를 기준으로 민코프스키 다이어그램을 그리면 해당 상황은 (a)와 같이 표현할 수 있다. 반면 $(x, t)$에 대해 $0.6c$의 속도를 가지는 관성좌표계 $(x’, t’)$을 기준으로 하는 민코프스키 다이어그램은 (b) 및 (b’)와 같다.²

A의 운동에 좌표를 부여하는 방식은 다르지만 (a)와 (b)는 동일한 물리적 상황을 표현한다. 이와 같이 계의 물리적 속성을 보존하는 관성좌표계의 변환을 수동적 변환이라고 한다. 뉴턴 역학에서 시공간의 수동적 변환은 전단 변환_{shear transformation}으로 주어지지만 잘 알려져 있듯이 상대론에서는 로렌츠 변환으로 주어진다.

2. 능동적 변환

이제 A의 속도에 순간적으로 $-0.6c$가 더해진 상황을 생각해 보자. $(x, t)$에 대해 속도가 더해진 후의 다이어그램은 (c)와 같다.

주목할 점은, (a)-(b)와는 달리 (a)-(c)는 같은 관성좌표계를 사용한다는 것이다. (a)-(c)의 변환은 관성좌표계의 변환이 아닌, A의 속도에 $-0.6c$가 더해졌다는 물리적 변화로 일어났다. 이처럼 물리적 변화로 인한 다이어그램의 변환을 능동적 변환이라고 한다.

일면 능동적 변환 (b)와 수동적 변환 (c)의 차이는 관점의 차이에 지나지 않는 것으로 보인다. 실제로 고전역학에서 능동적 변환과 수동적 변환은 동일시될 수 있으며, 이것은 고전역학에서 뇌터 정리를 적용할 수 있는 조건에 다름 아니다. 하지만 상대론에서 둘의 동일시는 매우 신중한 주의를 요구한다. 왜냐하면 상대론에서는 동시성의 상대성을 고려해야 하기 때문이다.

3. 동시성의 상대성

동시성의 상대성이 왜 중요한지 알아보기 위해 상황을 바꿔보자. 두 점입자 A, B가 빈 공간에서 서로 $c$의 거리를 유지하고 있다. 이 상황을 A에 대해 정지해 있는 관성좌표계 $(x, t)$와, A에 대해 $0.6c$로 움직이는 관성계 $(x’, t’)$으로 표현한 민코프스키 다이어그램은 각각 다음과 같다.

$(x, t)$에서 $P$와 $Q$가 동시적이므로 A, B의 거리는 $d$이다. 반면 $(x’, t’)$에서는 $P$와 $Q’$가 동시적이므로 A, B 거리는 $d’$이다. 민코프스키 기하학을 이용하여 계산하면 $d’ = 0.8c$ 이며 $d’ < d$이다.³

같은 현상을 능동적 변환으로 해석해 보자. A, B가 $c$의 거리를 유지하다가 $(x, t)$에 대해 동시에 $-0.6c$의 속도가 더해졌다고 하자. 민코프스키 다이어그램은 다음과 같다. $(x'', t'')$은 속도가 더해진 이후의 A를 기준으로 하는 관성좌표계이다.

$(x, t)$에서 $(P, Q)$가 동시적이므로 A, B의 거리는 $d$이다. 반면 $(x'', t'')$에서는 $(P, Q'')$가 동시적이므로 A, B의 거리는 $d''$이다. 마찬가지로 민코프스키 기하학을 이용하여 $d''$을 계산하면 $d'' = 1.25c$ 이며 $d'' > d$이다.

따라서 상대론에서는 수동적 변환과 능동적 변환 사이에 실질적인 차이가 있다. 수동적 변환은 A 관점의 거리를 유지시키고 새 관성좌표계 관점의 거리를 수축시키는 한편, 능동적 변환은 기존 관성좌표계 관점의 거리를 유지시키고 A 관점의 거리를 팽창시킨다.

A와 B의 거리	A 관점	A에 대해 움직이는 관성계 관점
수동적 변환	유지	수축
능동적 변환 (A와 B가 분리되어 있을 때)	팽창	유지

4. 강체의 능동적 변환

앞서 본 경우에는 A와 B가 분리되어 있었다. 이제 A와 B가 강체를 이루는 경우를 생각해 보자. 구체적으로 A, B가 길이가 $c$인 강철 막대기 M의 양끝점이라고 하자.

강체의 특징은 수용 가능한 변화에 대해 원 상태를 유지하는 성질을 가지고 있다는 것이다. 예를 들어 고무공은 강체가 아니기 때문에 힘을 가하면 부피가 줄어들거나 늘어나지만, 강철공은 부피가 변하지 않는다.

그렇다면 M이 능동적 변환에 가해졌을 때 무슨 일이 일어날 것인가? 예컨대 M이 관성좌표계 $(x, t)$에서 관성 운동하던 도중, M의 모든 부분이 “$(x, t)$에 대해 동시에” 가속하여 $0.6c$의 속도에 다다르면 M에는 무슨 일이 일어날 것인가?

M이 강체가 아니었다면 M의 길이는 A의 관점에서 $1.25c$로 팽창했을 것이다. 그러나 M은 강체이므로 자신의 원래 길이를 유지하려고 한다. 이에 따라 M이 가속하는 동안 M의 내부에서는 두 가지 효과가 대립하며 매우 복잡한 양상이 펼쳐진다.

• 효과 1: 동시성의 상대성으로 인해 B가 A보다 먼저 가속하여 M의 양끝이 잡아당겨진다.
• 효과 2: M의 강체적 특성으로 인해 M의 원자 구조가 효과 1에 저항하는 장력을 발생시킨다.

효과 2로 발생하는 내부 장력을 상대론적 장력_{relativistic stress}이라고 부른다. 만약 M이 충분히 강한 강체라면 상대론적 장력을 버텨내어 M의 길이는 (A, B의 관점에서) $c$로 유지된다. 그러나 가속이 너무나 급격하여 상대론적 장력이 M의 수용 범위를 벗어나면 강체는 변형되거나 파괴된다. 일례로 쿠크다스를 광속에 가깝게 가속시키면 쿠크다스는 파괴된다.

5. 결론

A와 B의 거리	A 관점	A에 대해 움직이는 관성계 관점
수동적 변환	유지	수축
능동적 변환 (A와 B가 분리되어 있을 때)	팽창	유지
능동적 변환 (A와 B가 강체를 이룰 때)	유지	감소

이제 벨의 사고실험으로 돌아가자. 두 우주선 A, B가 가속할 때 “우주선-실-우주선” 계는 능동적 변환을 겪는다. A의 관점에서 두 효과가 관측된다.

• 효과 1: A와 B는 분리되어 있으므로 A와 B의 거리는 팽창한다.
• 효과 2: 팽팽히 당겨진 실의 강체적 특성에 의해 실의 길이는 유지된다.

이에 따라 가속이 일정 시간 이상 지속되면 효과 1이 효과 2를 압도하여 실은 끊어진다. 만약 A와 B가 실이 아니라 강철 케이블로 연결되어 있었다면 효과 2가 효과 1을 압도하여 A와 B는 (A 및 B의 관점에서) 일정한 거리를 유지하게 된다.

---

Bell's Spaceship Paradox: Passive and Active Lorentz Contraction

17 Nov 2024

Spaceships A and B are connected by a thin thread and are initially at rest (with respect to a common inertial frame). They begin to accelerate simultaneously at the same rate to approach the speed of light. What happens to the thread?

1. It breaks.
2. It loosens.
3. It remains unchanged.

This thought experiment was originally devised by Dewan and Beran in 1959 but gained widespread attention after John Stewart Bell discussed it with CERN physicists in 1976. Bell argued that the thread breaks due to Lorentz contraction. Most CERN physicists disagreed, claiming the thread remains unchanged. One prominent physicist even accused Bell of misrepresenting relativity. So, who is correct?

The answer is 1. It breaks.

This may seem counterintuitive. After all, Lorentz contraction is frame-dependent. If Alice moves at near-light speed relative to Bob, Bob would observe Alice to have contracted. But in Alice’s frame, it is Bob who is moving and therefore contracts. This symmetry suggests that Lorentz contraction is a mathematical artifact arising from frame choice, hence not a physically real phenomenon. Such an interpretation is widespread in physics, e.g. Rindler’s 1977 writes:

According to Lorentz, the cause of contraction lies in the increased electromagnetic cohesion of atomic structures [as an object passes through the ether]… [But] in relativity, Lorentz contraction is essentially a geometric projection effect, akin to viewing a stationary rod from an angle.¹

However, Rindler’s explanation is quite misleading. Rather, it is important to recognise that there are two types of Lorentz contraction. In the case of a passive Lorentz transformation, Lorentz contraction is merely an artifact of changing coordinates. But in the case of an active Lorentz transformation, the contraction corresponds to a real physical effect, such as increased electromagnetic force. This post will explore the difference between the two and show how active transformation relates to physical stress.

1. Passive Transformation

Consider a point particle A moving inertially in vacuum. The Minkowski diagram, with respect to an inertial coordinates $(x, t)$ to which A is at rest, is shown in (a). In another inertial coordinates $(x’, t’)$ moving at $0.6c$ relative to $(x, t)$, the Minkowski diagram is as shown in (b) and (b’).²

The diagrams (a) and (b) represent the same physical scenario using different coordinates. Such transformation between coordinates is called a passive transformation. In Newtonian mechanics, this is represented as shear transformation of Galilean diagram; in relativity, as Lorentz transformation of Minkowski diagram.

2. Active Transformation

Now consider a scenario where A’s velocity changes by $-0.6c$. The Minkowski diagram in $(x, t)$ after this change is shown in (c).

Unlike (a) and (b’), diagrams (a) and (c) use the same coordinates. The change here reflects a physical change in A’s motion, not a change in coordinates. Such a transformation is called an active transformation.

At first glance, the difference between active and passive transformations might seem purely semantic. In classical mechanics, the two are indeed physically equivalent, and this is partly what grounds Noether’s theorem. But in relativity, the distinction becomes crucial due to the relativity of simultaneity.

3. Relativity of Simultaneity

To understand why simultaneity matters, let’s consider two particles A and B maintaining a distance $d$ apart. The Minkowski diagrams based on A’s rest coordinates $(x, t)$ and another diagram based on coordinates $(x’, t’)$ moving at $0.6c$ are shown below:

In $(x, t)$, events $P$ and $Q$ are simultaneous, so the distance between A and B is $d$. But in $(x’, t’)$, $P$ and $Q’$ are simultaneous, and the distance is $d’$. To calculate $d’$ we use the Lorentz transformation formulas:

\[\begin{align} &t' = \gamma \left( t - \frac{vx}{c^2} \right)\\ &x' = \gamma (x - vt)\\ &y' = y\\ &z' = z\\ \end{align}\]

Calculation gives $d’ = 0.8d$, i.e. $d’ < d$.³

Now let’s consider the active transformation case. Suppose A and B, initially at distance $d$, are both accelerated simultaneously, with respect to $(x, t)$, to $-0.6c$. The resulting Minkowski diagram is:

In $(x, t)$, $P$ and $Q$ are simultaneous, and their distance remains $d$. But in $(x'', t'')$, the coordinates to which A is at rest after the acceleration, $P$ and $Q''$ are simultaneous, and the distance is $d'' = 1.25d$. Hence $d'' > d$.

Thus, in relativity, passive and active transformations lead to physically different consequences. Passive transformations preserve distances in A’s frame but contract them in the moving frame, whereas active transformations preserve distances in the original frame but stretch them in A’s new frame.

Distance between A and B	Rest Frame of A	Moving Frame of A
Passive Transformation	Unchanged	Contracted
Active Transformation (isolated)	Expanded	Unchanged

4. Active Transformation of a Rigid Body

Up to now, A and B were isolated particles. Now suppose A and B are endpoints of a rigid rod M of length $l$.

Suppose that every part of M accelerates simultaneously with respect to an inertial frame $(x, t)$ to reach $0.6c$. If M were not rigid, A would observe M’s length as expanding to $1.25c$. But rigidity resists this expansion, leading to an internal stress. Thus from A’s frame of reference, the rod undergoes two two effects.

• Effect 1: Due to relativity of simultaneity, B accelerates before A, which would cause the rod to stretch.
• Effect 2: The rod’s rigidity resists this stretching, generating internal stress.

The internal stress thus arisen is called relativistic stress. If M is strong enough, it endures the stress and maintains its original length. Otherwise, it deforms or breaks. For example, a biscuit rapidly accelerated to near-light speed would shatter, while a rugby ball accelerated to near-light speed would visibly extend.

5. Conclusion

Distance between A and B	Rest Frame of A	Moving Frame of A
Passive Transformation	Unchanged	Contracted
Active Transformation (isolated)	Expanded	Unchanged
Active Transformation (rigid body)	Unchanged	Contracted

Returning to Bell’s paradox, when spaceships A and B accelerate, the “spaceship-thread-spaceship” system undergoes an active transformation. Thus in A’s frame, two effects co-occur:

• Effect 1: Distance between A and B increases (since they are not rigidly connected).
• Effect 2: The thread tries to maintain its original length.

Eventually, if acceleration continues, Effect 1 wins over Effect 2, and the thread breaks. If A and B were connected by a steel cable instead, Effect 2 would dominate, and the distance would remain constant.

---