측도 문제와 연속체 가설

15 Jan 2026

정의. 측도 $\mu$가 집합 $X$의 모든 부분집합에 대해 정의될 때, $\mu$를 $X$ 위의 측도라고 한다.

정리. 임의의 $A \subseteq \mathbb{R}$과 $x \in \mathbb{R}$에 대해, $\mu(A + x) = \mu(A)$를 만족하는 실수 위의 측도 $\mu$는 존재하지 않는다. ($A + x = \lbrace a + x : a \in A\rbrace$)

증명. 비탈리 집합의 구성을 참고하라.

즉, 평행이동 불변적인 실수 위의 측도는 존재하지 않는다. 대신 평행이동 불변 조건을 약화하여, 르벡 가측인 집합 $A$에 대해서만 $\mu(A) = m(A)$를 만족하는 실수 위의 측도 $\mu$가 가능하지 않을지 물을 수 있다 ($m$은 르벡 측도). 이것을 측도 문제라고 한다.

측도 문제. 임의의 르벡 가측 집합 $A\subseteq \mathbb{R}$에 대해 $\mu(A) = m(A)$를 만족하는 실수 위의 측도 $\mu$가 존재하는가?

사실 위 문제는 다음의 일반화된 문제와 동치임이 알려져 있다.

일반화된 측도 문제. 비자명한 $2^{\aleph_0}$ 위의 측도가 존재하는가?

만약 그러한 측도가 존재한다면, 해당 측도와 $\mathbb{R}$과 $2^{\aleph_0}$ 사이의 전단사 사상을 사용하여 르벡 측도를 $\mathcal{P}(\mathbb{R})$로 확장할 수 있음이 알려져 있기 때문이다.

Remark. 평행이동 불변 조건이 사라졌기 때문에, 집합 $S$ 위에서 측도의 존재성은 오로지 $S$의 기수에만 의존적이다. 따라서 이후 글에서는 기수 위의 측도에 관해서만 관심을 가진다.

흥미롭게도 측도 문제는 연속체 가설 및 큰 기수 공리와 관련이 있다. 먼저 다음 정리를 보자.

정리. $\nu$ 위의 측도가 존재한다면, 어떤 $\kappa \leq \nu$는 약하게 도달 불가능_{weakly inaccessible}하다.

증명. $\nu$ 위의 측도 $\mu$가 존재한다고 하자. $\mu$에 대한 영집합_{null set}들의 모임 $\mathcal{I}$는 아이디얼_ideal이다. 특히, $\mathcal{I}$가 다음을 만족함을 쉽게 보일 수 있다.

1. 홑원소집합 포함: 임의의 $\xi < \nu$에 대해, $\lbrace \xi \rbrace \in \mathcal{I}$.
2. 가산 닫힘: $\lbrace A_n \rbrace _{n < \omega}$이 $\mathcal{I}$에 속하는 집합들의 모임일 때, $\bigcup_{n < \omega} A_n \in \mathcal{I}$.
3. 쌍대 가산 체인 성질_{co-c.c.c. (countable chain condition)}: $\lbrace B_i \rbrace _{i \in J}$가 $\mathcal{I}$에 속하지 않는 서로소 집합들의 모임일 때, $|J| \leq \aleph_0$.

$\kappa \leq \nu$가 위 1, 2, 3의 조건을 만족하면서 $\kappa$의 부분집합으로 이루어진 아이디얼 $\mathcal{J}$가 존재하는 최소 기수라고 하자. 다음의 보조정리를 증명한다.

정의. $\mathcal{I}$가 아이디얼이라고 하자. 임의의 $\lambda < \kappa$에 대해, $\lbrace A_\xi \rbrace _{\xi < \lambda}$가 $\mathcal{I}$의 원소들의 모임일 때, $\bigcup A_\xi \in \mathcal{I}$라면 $\mathcal{I}$가 $\kappa$-완전_{$\kappa$-complete}하다고 한다.

보조정리. $\mathcal{J}$는 $\kappa$-완전하다.

증명. $\mathcal{J}$가 $\kappa$-완전하지 않다고 하자. 그럼 어떠한 $\lambda < \kappa$와 $\mathcal{J}$의 원소들의 모임 $\lbrace A_\xi \rbrace _{\xi < \lambda}$가 존재하여 $\bigcup A_\xi \notin \mathcal{J}$이다. 필요하다면 다음과 같이 재정의함으로써, 일반성을 잃지 않고 $\lbrace A_\xi\rbrace $가 쌍으로 서로소라고 가정할 수 있다.

\[A_\xi' = A_\xi - \bigcup_{\eta < \xi}A_\eta\]

($A_\xi’ \subseteq A_\xi$이므로 $A_\xi \in \mathcal{J}$로부터 $A_\xi’ \in \mathcal{J}$가 따라 나온다. 또한 $A_\xi’$는 공집합일 수도 있지만, 공집합은 다른 집합과 언제나 서로소이기 때문에 이 사실은 증명에 영향을 미치지 않는다.)

다음과 같이 $\lambda$ 위의 아이디얼 $\mathcal{K}$를 정의한다.

\[S \in \mathcal{K} \iff \bigcup_{\xi \in S} A_\xi \in \mathcal{J}\]

$\mathcal{K}$가 1, 2, 3 조건을 만족함을 보이자.

1. 홑원소집합 포함: $\mathcal{K}$의 정의로부터 자명하다.
2. 가산 닫힘: $\mathcal{J}$가 가산 닫힘이므로 $\mathcal{K}$ 또한 가산 닫힘이다.
3. 쌍대 가산 체인 성질: $\lbrace S_i \rbrace _{i \in J}$가 $\mathcal{K}$에 속하지 않는 서로소 집합들의 모임이라고 하자. 각 $i \in J$에 대해 $B_i = \bigcup_{\xi \in S_i} A_\xi$라고 하자. $B_i \notin \mathcal{J}$이고, $i \neq j$일 때 $B_i \cap B_j = \varnothing$이다 (여기서 $\lbrace A_\xi\rbrace $가 쌍으로 서로소라는 성질이 사용된다). 즉 $\lbrace B_i\rbrace _{i \in J}$는 $\mathcal{J}$의 쌍대 반체인이므로, $J$는 가산이다.

그런데 이는 $\kappa$의 최소성 정의에 모순된다. 따라서 $\mathcal{J}$는 $\kappa$-완전하다. □

위 따름정리로부터 $\kappa$가 약하게 도달 불가능함을, 즉 비가산 정칙 극한 기수임을 보일 수 있다.

$\kappa$는 비가산이다.

홑원소집합 포삼 성질과 가산 닫힘 성질에 의해 $\kappa$가 가산이라면 $\kappa \in \mathcal{J}$가 되어 모순이다.

$\kappa$는 정칙이다.

$\kappa$가 정칙이 아니라면 어떤 $\lambda < \kappa$에 대해 $\kappa$보다 작은 기수들의 증가열 $\lbrace \nu_\xi \rbrace _{\xi < \lambda}$가 존재하여 $\bigcup_{\xi < \lambda} \nu_\xi = \kappa$이다. 홑원소집합 포함 성질과 $\kappa$-완전성에 의해 각 $\nu_\xi$는 $\mathcal{J}$의 원소이다. 따라서 다시 $\kappa$-완전성에 의해 $\bigcup_{\xi < \lambda} \nu_\xi = \kappa$는 $\mathcal{J}$의 원소이다. 그런데 이는 $\mathcal{J}$가 아이디얼이라는 사실에 모순된다.

$\kappa$는 극한 기수이다.

$\kappa$가 극한 기수가 아니라면 어떤 서수 $\alpha$에 대해 $\kappa = \aleph_{\alpha + 1}$이다. 따라서 각 $\gamma < \kappa$에 대해, 전사인 $f_\gamma: \omega_\alpha \to \gamma$가 존재한다. 선택 공리를 사용하여 그러한 함수열 $\lbrace f_\gamma \rbrace _{\gamma < \omega_{\alpha + 1}}$을 얻는다.

이제 각 $\beta < \omega_\alpha, \gamma < \omega_{\alpha + 1}$에 대해 다음과 같이 $A_{\gamma\beta}$를 정의한다.

\[A_{\gamma\beta} = \{ \xi < \omega_{\alpha + 1} : f_\xi(\beta) = \gamma \}\]

다음을 관찰하라.

• $\bigcup_{\beta < \omega_\alpha} A_{\gamma\beta} = \omega_{\alpha + 1} - (\gamma + 1)$
• $\gamma_1 \neq \gamma_2 \implies A_{\gamma_1 \beta} \cap A_{\gamma_2 \beta} = \varnothing$

특히, $\kappa$-완전성에 의해 $\gamma + 1 \in \mathcal{J}$이므로 $\bigcup_{\beta < \omega_\alpha}A_{\gamma \beta} \notin \mathcal{J}$이다. 따라서 다시 $\kappa$-완전성에 의해 어떤 $\beta$에 대하여 $A_{\gamma\beta} \notin \mathcal{J}$이다. 각 $\gamma$에 대해 그러한 $\beta_\gamma$를 선택하여, $\lbrace A_{\gamma\beta_\gamma}\rbrace _{\gamma < \omega_{\alpha + 1}}$을 얻는다. 그런데 가능한 $\beta_\gamma$의 경우의 수는 $\omega_\alpha$이므로, 비둘기집의 원리에 의해 어떤 $\beta < \omega_{\alpha}$가 존재하여 $|\lbrace A_{\gamma\beta_\gamma} : \beta_\gamma = \beta \rbrace | = \aleph_{\alpha + 1}$이다. 그런데 이는 가산 쌍대 체인 성질에 모순된다. ■

따름정리. 측도 문제의 답이 긍정적이라면 연속체 가설의 답은 부정적이다.

증명. 측도 문제가 성립하고 $2^{\aleph_0} = \aleph_1$이라면, 정리에 의해 $\aleph_0$ 또는 $\aleph_1$이 약하게 도달 불가능해야 하는데, $\aleph_0$는 가산이고 $\aleph_1$은 계승_successor 기수이므로 이는 모순이다. ■

The Measure Problem and the Continuum Hypothesis

15 Jan 2026

This post was originally written in Korean, and has been machine translated into English. It may contain minor errors or unnatural expressions. Proofreading will be done in the near future.

Definition. When a measure $\mu$ is defined for all subsets of a set $X$, $\mu$ is called a measure on $X$.

Theorem. For any $A \subseteq \mathbb{R}$ and $x \in \mathbb{R}$, there does not exist a measure $\mu$ on the real numbers satisfying $\mu(A + x) = \mu(A)$. (Here, $A + x = \lbrace a + x : a \in A\rbrace$.)

Proof. Refer to the construction of the Vitali set.

Thus, a translation-invariant measure on the real numbers does not exist. Instead, one may weaken the translation-invariance condition and ask whether there exists a measure $\mu$ on the real numbers such that $\mu(A) = m(A)$ for Lebesgue measurable sets $A$, where $m$ denotes the Lebesgue measure. This is called the measure problem.

Measure Problem. Does there exist a measure $\mu$ on the real numbers such that $\mu(A) = m(A)$ for any Lebesgue measurable set $A \subseteq \mathbb{R}$?

In fact, the above problem is known to be equivalent to the following generalised problem:

Generalised Measure Problem. Does there exist a non-trivial probabilistic measure $\mu$ on $2^{\aleph_0}$? (A measure is probabilistic if the measure of the whole space is 1.)

If such a measure exists, it is known that the Lebesgue measure can be extended to $\mathcal{P}(\mathbb{R})$ using this measure and a bijection between $\mathbb{R}$ and $2^{\aleph_0}$.

Remark 1. Since the translation-invariance condition has been removed, the existence of a measure on a set $S$ depends solely on the cardinality of $S$. Therefore, in the subsequent discussion, we focus only on measures on (uncountable) cardinals.

Remark 2. It is known that if $\mu$ is a probabilistic measure on $S$, $C = \lbrace x \in S : \mu(\lbrace x \rbrace ) > 0 \rbrace $ is at most countable. Hence if $|S| = \kappa$ is uncountable, we have $|S| = |S \setminus C|$, and $\mu$ restricted to $S \setminus C$ is a measure satisfying $\mu(\lbrace x \rbrace ) = 0$ for all $x \in S \setminus C$. It follows that if a measure $\mu$ exists on an uncountable cardinal $\kappa$, we may assume without loss of generality $\mu(\lbrace \alpha \rbrace ) = 0$ for all $\alpha < \kappa$. Indeed, we will assume this fact from now on.

Interestingly, the measure problem is related to the continuum hypothesis and large cardinal axioms. Let us first examine the following theorem:

Theorem. If a probabilistic measure exists on $\nu$, then some $\kappa \leq \nu$ is weakly inaccessible.

Proof. Suppose a probabilistic measure $\mu$ exists on $\nu$. The collection $\mathcal{I}$ of null sets with respect to $\mu$ forms an ideal. In particular, it can be easily shown that $\mathcal{I}$ satisfies the following properties:

1. Contains singletons: For any $\xi < \nu$, $\lbrace \xi \rbrace \in \mathcal{I}$.
2. Countably closed: If $\lbrace A_n \rbrace_{n < \omega}$ is a collection of sets in $\mathcal{I}$, then $\bigcup_{n < \omega} A_n \in \mathcal{I}$.
3. Satisfies the countable chain condition: If $\lbrace B_i \rbrace_{i \in J}$ is a collection of pairwise disjoint sets not in $\mathcal{I}$, then $|J| \leq \aleph_0$.

Let $\kappa \leq \nu$ be the smallest cardinal such that there exists an ideal $\mathcal{J}$ on $\kappa$ satisfying the above three conditions. We now prove the following lemma:

Definition. Let $\mathcal{I}$ be an ideal. If for any $\lambda < \kappa$, $\lbrace A_\xi \rbrace_{\xi < \lambda}$ is a collection of sets in $\mathcal{I}$, and $\bigcup A_\xi \in \mathcal{I}$, then $\mathcal{I}$ is said to be $\kappa$-complete.

Lemma. $\mathcal{J}$ is $\kappa$-complete.

Proof. Suppose $\mathcal{J}$ is not $\kappa$-complete. Then there exist some $\lambda < \kappa$ and a collection $\lbrace A_\xi \rbrace_{\xi < \lambda}$ of sets in $\mathcal{J}$ such that $\bigcup A_\xi \notin \mathcal{J}$. Without loss of generality, we may redefine $\lbrace A_\xi \rbrace$ as follows to assume that the sets are pairwise disjoint:

\[A_\xi' = A_\xi - \bigcup_{\eta < \xi} A_\eta\]

(Since $A_\xi’ \subseteq A_\xi$, it follows that $A_\xi’ \in \mathcal{J}$ from $A_\xi \in \mathcal{J}$. Additionally, $A_\xi’$ may be empty, but this does not affect the proof as empty sets are trivially disjoint.)

Define an ideal $\mathcal{K}$ on $\lambda$ as follows:

\[S \in \mathcal{K} \iff \bigcup_{\xi \in S} A_\xi \in \mathcal{J}\]

We verify that $\mathcal{K}$ satisfies the three conditions:

1. Contains singletons: This is immediate from the definition of $\mathcal{K}$.
2. Countably closed: Since $\mathcal{J}$ is countably closed, so is $\mathcal{K}$.
3. Satisfies the countable chain condition: Suppose $\lbrace S_i \rbrace_{i \in J}$ is a collection of pairwise disjoint sets not in $\mathcal{K}$. For each $i \in J$, let $B_i = \bigcup_{\xi \in S_i} A_\xi$. Then $B_i \notin \mathcal{J}$, and $B_i \cap B_j = \varnothing$ for $i \neq j$ (using the disjointness of $\lbrace A_\xi \rbrace$). Thus, $\lbrace B_i \rbrace_{i \in J}$ forms a pairwise disjoint antichain in $\mathcal{J}$, implying that $J$ is countable.

This contradicts the minimality of $\kappa$. Hence, $\mathcal{J}$ is $\kappa$-complete. □

From the above lemma, it follows that $\kappa$ is weakly inaccessible, i.e., an uncountable regular limit cardinal.

$\kappa$ is uncountable.

The singleton containment and countable closure properties imply that if $\kappa$ were countable, $\kappa \in \mathcal{J}$, leading to a contradiction.

$\kappa$ is regular.

If $\kappa$ were not regular, there would exist some $\lambda < \kappa$ and an increasing sequence $\lbrace \nu_\xi \rbrace_{\xi < \lambda}$ of cardinals less than $\kappa$ such that $\bigcup_{\xi < \lambda} \nu_\xi = \kappa$. By the singleton containment and $\kappa$-completeness properties, each $\nu_\xi$ belongs to $\mathcal{J}$. Hence, by $\kappa$-completeness, $\bigcup_{\xi < \lambda} \nu_\xi = \kappa$ belongs to $\mathcal{J}$, contradicting the fact that $\mathcal{J}$ is an ideal.

$\kappa$ is a limit cardinal.

If $\kappa$ were not a limit cardinal, there would exist some ordinal $\alpha$ such that $\kappa = \aleph_{\alpha + 1}$. For each $\gamma < \kappa$, there exists a surjection $f_\gamma: \omega_\alpha \to \gamma$. Using the axiom of choice, we obtain a sequence of such functions $\lbrace f_\gamma \rbrace_{\gamma < \omega_{\alpha + 1}}$.

For each $\beta < \omega_\alpha$ and $\gamma < \omega_{\alpha + 1}$, define:

\[A_{\gamma\beta} = \{ \xi < \omega_{\alpha + 1} : f_\xi(\beta) = \gamma \}\]

Observe the following:

• $\bigcup_{\beta < \omega_\alpha} A_{\gamma\beta} = \omega_{\alpha + 1} - (\gamma + 1)$
• $\gamma_1 \neq \gamma_2 \implies A_{\gamma_1 \beta} \cap A_{\gamma_2 \beta} = \varnothing$

In particular, by $\kappa$-completeness, $\gamma + 1 \in \mathcal{J}$ implies $\bigcup_{\beta < \omega_\alpha} A_{\gamma \beta} \notin \mathcal{J}$. Hence, for some $\beta$, $A_{\gamma\beta} \notin \mathcal{J}$. Choosing such $\beta_\gamma$ for each $\gamma$, we obtain $\lbrace A_{\gamma\beta_\gamma} \rbrace_{\gamma < \omega_{\alpha + 1}}$. However, the possible values of $\beta_\gamma$ are limited to $\omega_\alpha$, so by the pigeonhole principle, there exists some $\beta < \omega_\alpha$ such that $|\lbrace A_{\gamma\beta_\gamma} : \beta_\gamma = \beta \rbrace| = \aleph_{\alpha + 1}$. This contradicts the countable chain condition. ■

Corollary. If the measure problem has a positive solution, then the continuum hypothesis has a negative solution.

Proof. If the measure problem holds and $2^{\aleph_0} = \aleph_1$, then by the theorem, $\aleph_0$ or $\aleph_1$ must be weakly inaccessible. However, $\aleph_0$ is countable, and $\aleph_1$ is a successor cardinal, leading to a contradiction. ■

교환법칙, 분배법칙, 지수법칙의 범주론적 증명

27 Dec 2025

정리.

1. 분배법칙: $(A + B) \times C = A \times C + B \times C$
2. 지수법칙: $(A \times B)^C = A^C \times B^C$

이전 글에서 범주론적 합과 곱을 살펴 보았다. 합은 쌍극한의 일종이고, 곱은 극한의 일종이다. 이 관찰로부터, 분배법칙과 지수법칙을 다음 정리로 일반화할 수 있다.

정리. 좌 어드조인트는 쌍극한_colimit을, 우 어드조인트는 극한_limit을 보존한다.

이 정리의 정확한 의미는 다음과 같다. $F: \mathcal{A} \to \mathcal{B}, G: \mathcal{B} \to \mathcal{A}$에 대해 $F \dashv G$라고 하자. $G$가 극한을 보존_{preserves limits}한다는 것은, 임의의 작은 범주_{small category} $\mathbf{I}$와 함자 $D : \mathbf{I} \to \mathcal{B}$에 대해 다음이 성립한다는 것이다.

$\big(B \xrightarrow{q_I} D(I)\big)_{I \in \mathbf{I}}$가 $\mathcal{B}$에서 극한 고깔_{limit cone}일 때, $\big(G(B) \xrightarrow{G(q_I)} GD(I)\big)_{I \in \mathbf{I}}$가 $\mathcal{A}$에서 극한 고깔이다.

이로부터, $G$가 극한을 보존할 때 다음이 성립함을 알 수 있다.

\[G\left(\lim_{\leftarrow \mathbf{I}} D\right) \cong \lim_{\leftarrow \mathbf{I}} G \circ D\]

쌍극한의 경우에는 고깔을 쌍고깔로 바꿔 정의한다.

한편, 임의의 $X, Y, Z \in \mathbf{Set}$에 대해 $\hom(X \times Y, Z) \cong \hom(X, Z^Y)$가 성립한다 (이는 함수형 프로그래밍에서 자주 등장하는 커링_Currying 기법이다). 이로부터 다음의 어드조인트 관계가 따라 나온다.

\[(-) \times Y \dashv (-)^Y\]

따라서 함자 $(-) \times Y$는 쌍극한을 보존하고, $(-)^Y$는 극한을 보존한다. 이로부터 일반화된 분배법칙과 지수법칙을 얻을 수 있다.

정리. 집합 $A, B, Y$에 대해, $A, B$가 서로소라면 다음이 성립한다.

1. $(A + B) \times Y \cong (A \times Y) + (B \times Y)$
2. $(A \times B)^Y \cong A^Y \times B^Y$

여기서 $+$는 서로소 집합의 합집합으로, $\sqcup$과 의미가 같으나 분배법칙과의 유사성을 강조하기 위해 사용되었다. 좌변이 $G\left(\lim_{\leftarrow \mathbf{I}} D\right)$에, 우변이 $\lim_{\leftarrow \mathbf{I}} G \circ D$에 대응된다. 위 정리에 집합의 크기 연산을 취하면 자연수에서의 분배법칙과 지수법칙을 얻는다.

참고로 극한에 대한 다음 성질 또한 알려져 있다 ($\bullet, -$ 표기법은 이 글을 참고)

정리. $\mathbf{I}, \mathbf{J}$가 작은 범주이고, $\mathcal{S}$가 $\mathbf{I}, \mathbf{J}$ 모양의 극한들을 가지는 국소적으로 작은 범주라고 하자. $D: \mathbf{I} \times \mathbf{J} \to \mathcal{S}$에 대해, 다음이 성립한다.

\[\lim_{\leftarrow \mathbf{J}}\lim_{\leftarrow \mathbf{I}} D(\bullet, -) \cong \lim_{\leftarrow \mathbf{I} \times \mathbf{J}} D \cong \lim_{\leftarrow \mathbf{I}}\lim_{\leftarrow \mathbf{J}} D(-, \bullet)\]

즉, 극한끼리는 교환법칙을 만족한다. 이것은 덧셈의 교환법칙과 곱셈의 교환법칙을 일반화한 것으로 생각할 수 있다.

Categorical Proofs of the Commutative Law, Distributive Law, and Exponential Law

27 Dec 2025

This post was originally written in Korean, and has been machine translated into English. It may contain minor errors or unnatural expressions. Proofreading will be done in the near future.

Theorem.

1. Distributive law: $(A + B) \times C = A \times C + B \times C$
2. Exponential law: $(A \times B)^C = A^C \times B^C$

In a previous post, we explored categorical sums and products. Sums are a type of colimit, while products are a type of limit. From this observation, the distributive and exponential laws can be generalised into the following theorem.

Theorem. Left adjoints preserve colimits, and right adjoints preserve limits.

The precise meaning of this theorem is as follows. Let $F: \mathcal{A} \to \mathcal{B}$ and $G: \mathcal{B} \to \mathcal{A}$, and suppose $F \dashv G$. The statement that $G$ preserves limits means that for any small category $\mathbf{I}$ and functor $D : \mathbf{I} \to \mathcal{B}$, the following holds:

If $\big(B \xrightarrow{q_I} D(I)\big)_{I \in \mathbf{I}}$ is a limit cone in $\mathcal{B}$, then $\big(G(B) \xrightarrow{G(q_I)} G(D(I))\big)_{I \in \mathbf{I}}$ is a limit cone in $\mathcal{A}$.

From this, we can deduce the following when $G$ preserves limits:

\[G\left(\lim_{\leftarrow \mathbf{I}} D\right) \cong \lim_{\leftarrow \mathbf{I}} G \circ D\]

For colimits, the definition is analogous, replacing cones with cocones.

On the other hand, for any $X, Y, Z \in \mathbf{Set}$, the following holds: $\hom(X \times Y, Z) \cong \hom(X, Z^Y)$ (this is a common technique in functional programming known as currying). From this, the following adjoint relationship arises:

\[(-) \times Y \dashv (-)^Y\]

Thus, the functor $(-) \times Y$ preserves colimits, and the functor $(-)^Y$ preserves limits. From this, we can derive the generalised distributive and exponential laws.

Theorem. For sets $A, B, Y$, if $A$ and $B$ are disjoint, the following holds:

1. $(A + B) \times Y \cong (A \times Y) + (B \times Y)$
2. $(A \times B)^Y \cong A^Y \times B^Y$

Here, $+$ denotes the disjoint union of sets, which is equivalent to $\sqcup$, but the notation $+$ is used to emphasise its similarity to the distributive law. The left-hand side corresponds to $G\left(\lim_{\leftarrow \mathbf{I}} D\right)$, while the right-hand side corresponds to $\lim_{\leftarrow \mathbf{I}} G \circ D$. By applying cardinality operations to the sets in the above theorem, we recover the distributive and exponential laws for natural numbers.

Additionally, the following property of limits is also known (the $\bullet, -$ notation is explained in this post):

Theorem. Let $\mathbf{I}$ and $\mathbf{J}$ be small categories, and let $\mathcal{S}$ be a locally small category that admits limits of shape $\mathbf{I}$ and $\mathbf{J}$. For $D: \mathbf{I} \times \mathbf{J} \to \mathcal{S}$, the following holds:

\[\lim_{\leftarrow \mathbf{J}}\lim_{\leftarrow \mathbf{I}} D(\bullet, -) \cong \lim_{\leftarrow \mathbf{I} \times \mathbf{J}} D \cong \lim_{\leftarrow \mathbf{I}}\lim_{\leftarrow \mathbf{J}} D(-, \bullet)\]

In other words, limits satisfy the commutative law. This can be thought of as a generalisation of the commutative laws for addition and multiplication.

서슬린의 문제와 다이아몬드 원리

26 Dec 2025

이전 글에서 다음 정리를 소개했다.

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

1. 완비 전순서 집합이다.
2. 양끝점이 없다.
3. 분리 가능_separable하다. 즉, 어떤 가산인 $Q \subset R$이 존재하여 $Q$가 $R$에서 조밀_dense하다.

3번 성질로부터 다음이 따라 나온다.

정리. $\mathcal{C}$가 $\mathbb{R}$의 개구간들의 모임이라고 하자. $\mathcal{C}$의 원소들이 쌍으로 서로소_{pairwise disjoint}라면 $\mathcal{C}$는 가산이다.

증명. $\mathcal{C}$의 원소들이 쌍으로 서로소이므로, 각 $(x, y) \in \mathcal{C}$를 $q \in (x, y) \cap \mathbb{Q}$에 대응시키는 단사 사상 $\mathcal{C} \to \mathbb{Q}$가 존재한다. 따라서 $\mathcal{C}$는 가산이다. ■

쌍으로 서로소인 개구간들의 모임이 기껏 가산인 순서 집합은 가산 체인 성질_{countable chain condition}을 가진다고 한다. 이 특이한 이름의 이유는 뒤에서 설명할 것이다.

서슬린의 문제_{Suslin’s problem}는 집합론적 실수의 정의에서 분리 가능성을 가산 체인 성질로 약화시킬 수 있는지를 묻는다.

정의. 양끝점이 없고 가산 체인 성질을 가지는 완비 전순서 집합 중 실수와 순서 동형이 아닌 순서 집합을 서슬린 선_{Suslin line}이라고 한다.

따라서 서슬린 선은 분리 가능하지 않아야 한다.

서슬린의 문제. 서슬린 선이 존재하는가?

1920년에 제기된 이 문제는, 1971년 솔로베이_Solovay와 테넨바움_Tennenbaum에 의해 ZFC와 독립적임이 증명되었다. 이 글에서는 독립성 증명을 살펴보는 대신, 서슬린 선의 조합론적 버전인 서슬린 트리에 대해서 알아보고자 한다. 우선 다음의 유명한 정리를 보자.

쾨니히 보조정리_{König’s lemma}. 트리 $T$에 대해, $T$의 높이가 $\omega$이고, $T$의 각 노드가 유한한 수의 자식을 가진다면, $T$는 길이가 $\omega$인 가지를 가진다.

증명. $\alpha_0$를 루트 노드라고 하고, 다음과 같이 귀납적으로 노드열을 정의한다. $\alpha_n$이 주어졌을 때, $\alpha_n$의 자식 노드의 수는 유한하므로, 어떤 자식 노드에 대해 해당 노드를 루트로 하는 트리는 높이가 무한하다. 그러한 자식 노드 중 하나를 선택하여 (여기서 선택 공리가 필요하다) $\alpha_{n + 1}$로 정의한다. $\lbrace a_n \rbrace $은 길이가 무한한 가지이다. ■

$T$의 노드가 가산 수의 자식을 가질 수 있다면 다음과 같이 $T$의 모든 가지가 유한 길이임에도 $T$의 높이는 $\omega$일 수 있다.

자연스러운 질문은, 쾨니히 보조정리를 비가산 기수에 대해 확장할 수 있는지이다. 그러나 이 질문에 대한 답은 부정적이다.

아론샤인 정리_{Aronszajn theorem}. 높이가 $\omega_1$이고, 각 노드가 가산 수의 자식을 가지지만, 길이가 $\omega_1$인 가지가 없는 트리가 존재한다. (그러한 트리를 높이 $\omega_1$의 아론샤인 트리라고 한다.)

따라서 쾨니히 보조정리를 비가산 기수로 확장하기 위해서는 “각 노드가 가산 수의 자식을 가진다”보다 더 강력한 조건이 필요하다. 이를 위해 다음의 정의를 도입한다.

정의. 트리 $T$의 부분집합 $S$에 대해, $S$의 원소들이 서로 비교 불가능_{mutually incomparable}할 때, $S$를 반체인_antichain이라고 한다. $T$의 모든 반체인이 가산일 때, $T$가 가산 체인 성질을 가진다고 한다.

예를 들어 다음 트리의 색칠된 노드들은 반체인을 이룬다.

“각 노드가 가산 수의 자식을 가진다”가 국소적 성질이라면, 가산 체인 성질은 트리 전체에 관한 전역적 성질이다. 즉, 가산 체인 성질은 직관적으로 트리의 “너비”가 $\omega_1$보다 작다는 의미이다. 참고로 가산 반체인 성질이 아니라 가산 체인 성질이라고 부르는 것은 역사적 이유이기 때문에 크게 신경 쓸 필요는 없다.

앞서 쌍으로 서로소인 실수의 개구간들의 모임이 기껏 가산인 성질 또한 가산 체인 성질이라고 부른다고 했는데, 두 용법은 밀접한 관련이 있다. 반체인의 일반적인 정의는 다음과 같다.

정의. $(P, \leq)$가 부분순서라고 하자. $x, y \in P$가 비교 불가능하다는 것은, $z \leq x, z \leq y$인 $z \in P$가 존재하지 않는다는 것이다. $S \subseteq P$의 원소들이 서로 비교 불가능할 때 $S$를 반체인이라고 한다. $P$의 모든 반체인이 가산일 때, $P$가 가산 체인 성질을 가진다고 한다.

트리 $T$에서, 노드 $x$가 노드 $y$의 후손일 때 $x \leq y$라고 하자. 이때 트리의 노드로서 $x, y$가 비교 불가능한 것은 $(T, \leq)$의 원소로서 $x, y$가 비교 불가능한 것과 동치이다.

정의. 가산 체인 성질을 가지는 아론샤인 트리를 서슬린 트리라고 한다.

서슬린 트리의 존재성은 서슬린 선의 존재성과 동치이기 때문에 ZFC와 독립적이다. 동치가 되는 개략적인 이유는 각 성질이 다음 표와 같이 대응하기 때문이다.

서슬린 선	서슬린 트리
분리 불가능성	트리의 높이가 $\omega_1$
개구간의 가산 체인 성질	트리의 가산 체인 성질

분리 불가능성이 높이 $\omega_1$ 성질에 대응되는 개략적인 이유는, 어떤 집합 $D$가 존재하여 $|D| \leq \aleph_0$이고 임의의 개구간 $(a, b)$가 $D$와 교차한다는 사실이 (분리 가능성), 어떤 서수 $\alpha$가 존재하여 $\alpha < \omega_1$이고 임의의 노드 $x \in T$에 대해 $x$가 $T^{(\alpha)}$의 노드들로 이루어진 노드열의 극한이라는 사실과 (트리의 높이가 가산) 대응되기 때문이다.

서슬린 트리와 관련하여, 집합론의 다음 비표준 공리를 살펴보자.

다이아몬드 원리. 어떤 집합열 $\langle W_\alpha : \alpha < \omega_1 \rangle$가 존재하여 $W_\alpha \subseteq \mathcal{P}(\alpha)$이고, 각 $W_\alpha$가 가산집합이며, 임의의 $X \subseteq \omega_1$에 대해 $\lbrace \alpha : \alpha < \omega_1, X \cap \alpha \in W_\alpha \rbrace $가 정상 집합_{stationary set}이다.

다이아몬드 원리는 $\Diamond$로 자주 표기한다. 또한 다이아몬드 원리의 $\langle W_\alpha \rangle$을 다이아몬드 열이라고 부른다.

$X \cap \alpha$는 $\alpha$라는 “거울”을 통해 “비춰” 보인 $X$의 모습으로 생각될 수 있다. 이 경우, 다이아몬드 원리는 $\omega_1$보다 작은 서수들에서 $X$의 반사된 모습이 $\langle W_\alpha \rangle$에서 충분히 자주 나타난다는 의미로 이해될 수 있다 (이 글에서 정상 집합이 “측도 > 0”의 집합론적 버전임을 설명했다).

따라서 다이아몬드 원리는 반사 원리_{reflection principle}의 일종이며, $V = L$ 공리와 비슷하게 집합론적 우주를 규제하는 역할을 한다 (실제로 $V = L$은 $\Diamond$를 함의한다). 그리고 집합론적 우주를 규제하는 공리들이 그렇듯이, 다이아몬드 원리는 연속체 가설을 함의한다.

정리. $\Diamond \implies \mathsf{CH}$

증명. $X \subseteq \omega \subset \omega_1$이라고 하자. $X$가 $< \omega_1$에서 정상적으로 반사되므로, 어떤 $\alpha > \omega$에 대해 $X \cap \alpha = X \in W_\alpha$이다. 따라서 $\omega$의 부분집합들은 모두 $\bigcup_{\alpha < \omega_1} W_\alpha$에 속하는데, 후자의 기수가 $\aleph_1$이므로 $2^{\aleph_0} = \aleph_1$이다. ■

정리. $\Diamond$라면 서슬린 선이 존재한다.

증명. Hrbacek & Jech (3rd ed), Chapter 12, Section 5를 참고하라. 참고로 원문에는 다음의 오타가 있으니 주의하라.

(원문) Lemma 5.3. $\Diamond$ implies that there exists a sequence $\langle Z_\alpha : \alpha < \omega_1 \rangle$ such that, for each $\alpha < \omega_1$, $Z_\alpha \subseteq \omega^{<\alpha}$, $Z_\alpha$ is at most countable, and for any $X \subseteq \omega^{<\omega_1}$ the set $\lbrace \alpha < \omega_1 : X \cap \omega^{<\alpha} \rbrace $ is stationary.

Proof. We note that […] Clearly, $Z_\alpha \subseteq \omega^{<\alpha}$ and is at most countable.

(수정) Lemma 5.3. $\Diamond$ implies that there exists a sequence $\langle Z_\alpha : \alpha < \omega_1 \rangle$ such that, for each $\alpha < \omega_1$, $Z_\alpha \subseteq \mathcal{P}(\omega^{<\alpha})$, $Z_\alpha$ is at most countable, and for any $X \subseteq \omega^{<\omega_1}$ the set $\lbrace \alpha < \omega_1 : X \cap \omega^{<\alpha} \rbrace $ is stationary.

Proof. We note that […] Clearly, $Z_\alpha \subseteq \mathcal{P}(\omega^{<\alpha})$ and is at most countable.

또한 Claim 5.5 직전에 나오는 문장 “Let $\lbrace C_n : n \in \mathbb{N} \rbrace $ be the at most countable collection of those elements of $Z_\alpha$ which happen to be maximal antichains in $T^{(\alpha)}$.”의 의미는, 각 $n$에 대해 $C_n \in Z_\alpha$이고, $C_n \subseteq \omega^\alpha$이며, $C_n$의 원소들을 $T^{(\alpha)}$의 노드로 간주했을 때 $C_n$이 반체인이라는 것이다. ■

따름정리. $V = L$이라면 서슬린 선이 존재한다.

따라서 서슬린 선의 존재성은 집합론적 우주의 규제와 관련이 있다. 이 사실이 모순적으로 느껴질 수 있지만, 서슬린 선의 조건 중 하나가 가산 조밀 집합의 “비”존재라는 사실을 고려하면 그렇게 이상한 것은 아니다. 서슬린 선은 가산 체인 성질까지만 얻고 가산 조밀 집합은 발생시키지 않는 것이 가능한 “허술한” 집합론적 우주의 특징인 것이다.

Suslin's Problem and the Diamond Principle

26 Dec 2025

This post was originally written in Korean, and has been machine translated into English. It may contain minor errors or unnatural expressions. Proofreading will be done in the near future.

In the previous post, the following theorem was introduced:

Definition of the set-theoretic real numbers. A totally ordered set $(R, <)$ satisfying the following properties is unique up to order isomorphism:

1. It is a complete totally ordered set.
2. It has no endpoints.
3. It is separable, i.e., there exists a countable $Q \subset R$ such that $Q$ is dense in $R$.

From the third property, the following result follows:

Theorem. Let $\mathcal{C}$ be the collection of open intervals of $\mathbb{R}$. If the elements of $\mathcal{C}$ are pairwise disjoint, then $\mathcal{C}$ is countable.

Proof. Since the elements of $\mathcal{C}$ are pairwise disjoint, there exists an injective mapping $\mathcal{C} \to \mathbb{Q}$ that maps each $(x, y) \in \mathcal{C}$ to some $q \in (x, y) \cap \mathbb{Q}$. Hence, $\mathcal{C}$ is countable. ■

A totally ordered set in which any collection of pairwise disjoint open intervals is at most countable is said to have the countable chain condition. The peculiar name of this property will be explained later.

Suslin’s problem asks whether the separability condition in the definition of the set-theoretic real numbers can be weakened to the countable chain condition.

Definition. A complete totally ordered set without endpoints that satisfies the countable chain condition but is not order-isomorphic to the real numbers is called a Suslin line.

Thus, a Suslin line must not be separable.

Suslin’s problem. Does a Suslin line exist?

This problem, posed in 1920, was shown to be independent of ZFC by Solovay and Tennenbaum in 1971. Instead of examining the independence proof, this post will explore the combinatorial counterpart of Suslin lines, known as Suslin trees. Let us first consider the following well-known theorem:

König’s lemma. For a tree $T$, if $T$ has height $\omega$ and each node has finitely many children, then $T$ has a branch of length $\omega$.

Proof. Let $\alpha_0$ be the root node, and define a sequence of nodes inductively as follows. Given $\alpha_n$, since $\alpha_n$ has finitely many children, there exists a child node such that the subtree rooted at that node has infinite height. Choose one such child node (using the axiom of choice) and define it as $\alpha_{n+1}$. The sequence ${a_n}$ forms a branch of infinite length. ■

If the nodes of $T$ are allowed to have countably many children, it is possible for all branches of $T$ to have finite length while $T$ itself has height $\omega$, as illustrated below:

A natural question is whether König’s lemma can be extended to uncountable cardinals. However, the answer to this question is negative.

Aronszajn’s theorem. There exists a tree of height $\omega_1$ in which each node has countably many children, but no branch has length $\omega_1$. (Such a tree is called an Aronszajn tree of height $\omega_1$.)

Thus, to extend König’s lemma to uncountable cardinals, a stronger condition than “each node has countably many children” is required. To this end, the following definition is introduced:

Definition. A subset $S$ of a tree $T$ is called an antichain if the elements of $S$ are mutually incomparable. A tree $T$ is said to have the countable chain condition if all antichains in $T$ are countable.

For example, in the tree below, the coloured nodes form an antichain:

While “each node has countably many children” is a local property, the countable chain condition is a global property of the entire tree. Intuitively, the countable chain condition implies that the “width” of the tree is less than $\omega_1$. Note that the term “countable chain condition” rather than “countable antichain condition” is used for historical reasons and need not be a cause for concern.

Earlier, it was mentioned that a collection of pairwise disjoint open intervals of the real numbers is at most countable, and this property is also referred to as the countable chain condition. The two usages are closely related. The general definition of an antichain is as follows:

Definition. Let $(P, \leq)$ be a partially ordered set. Two elements $x, y \in P$ are said to be incomparable if there does not exist $z \in P$ such that $z \leq x$ and $z \leq y$. A subset $S \subseteq P$ is called an antichain if its elements are mutually incomparable. $P$ is said to have the countable chain condition if all antichains in $P$ are countable.

In a tree $T$, let $x \leq y$ denote that the node $x$ is a descendant of the node $y$. Then, two nodes $x$ and $y$ are incomparable as tree nodes if and only if they are incomparable as elements of the partially ordered set $(T, \leq)$.

Definition. An Aronszajn tree with the countable chain condition is called a Suslin tree.

The existence of Suslin trees is equivalent to the existence of Suslin lines, and hence is independent of ZFC. The equivalence arises because each property corresponds as follows:

Suslin line	Suslin tree
Non-separability	Height $\omega_1$
Countable chain condition for open intervals	Countable chain condition for the tree

The correspondence between non-separability and the height $\omega_1$ property can be understood as follows: the existence of a countable set $D$ such that $|D| \leq \aleph_0$ and every open interval $(a, b)$ intersects $D$ (non-separability) corresponds to the existence of an ordinal $\alpha$ such that $\alpha < \omega_1$ and every node $x \in T$ is the limit of a sequence of nodes in $T^{(\alpha)}$ (tree height being countable).

In connection with Suslin trees, consider the following non-standard axiom in set theory:

Diamond principle. There exists a sequence $\langle W_\alpha : \alpha < \omega_1 \rangle$ such that $W_\alpha \subseteq \mathcal{P}(\alpha)$, each $W_\alpha$ is countable, and for any $X \subseteq \omega_1$, the set ${\alpha : \alpha < \omega_1, X \cap \alpha \in W_\alpha}$ is stationary.

The diamond principle is often denoted by $\Diamond$, and the sequence $\langle W_\alpha \rangle$ is called a diamond sequence.

The set $X \cap \alpha$ can be thought of as the “reflection” of $X$ through the “mirror” $\alpha$. In this sense, the diamond principle implies that the reflection of $X$ at ordinals less than $\omega_1$ appears sufficiently often in $\langle W_\alpha \rangle$. (In this post, it was explained that stationary sets are the set-theoretic analogue of “measure > 0”.)

Thus, the diamond principle is a type of reflection principle and plays a role in regulating the set-theoretic universe, similar to the axiom $V = L$ (in fact, $V = L$ implies $\Diamond$). Like other axioms that regulate the set-theoretic universe, the diamond principle implies the continuum hypothesis.

Theorem. $\Diamond \implies \mathsf{CH}$

Proof. Let $X \subseteq \omega \subset \omega_1$. Since $X$ reflects stationarily at ordinals less than $\omega_1$, there exists some $\alpha > \omega$ such that $X \cap \alpha = X \in W_\alpha$. Hence, all subsets of $\omega$ are contained in $\bigcup_{\alpha < \omega_1} W_\alpha$, whose cardinality is $\aleph_1$. Therefore, $2^{\aleph_0} = \aleph_1$. ■

Theorem. If $\Diamond$ holds, then a Suslin line exists.

Proof. See Hrbacek & Jech (3rd ed), Chapter 12, Section 5. Note the following typographical error in the original text:

(Original) Lemma 5.3. $\Diamond$ implies that there exists a sequence $\langle Z_\alpha : \alpha < \omega_1 \rangle$ such that, for each $\alpha < \omega_1$, $Z_\alpha \subseteq \omega^{<\alpha}$, $Z_\alpha$ is at most countable, and for any $X \subseteq \omega^{<\omega_1}$ the set ${\alpha < \omega_1 : X \cap \omega^{<\alpha}}$ is stationary.

Proof. We note that […] Clearly, $Z_\alpha \subseteq \omega^{<\alpha}$ and is at most countable.

(Corrected) Lemma 5.3. $\Diamond$ implies that there exists a sequence $\langle Z_\alpha : \alpha < \omega_1 \rangle$ such that, for each $\alpha < \omega_1$, $Z_\alpha \subseteq \mathcal{P}(\omega^{<\alpha})$, $Z_\alpha$ is at most countable, and for any $X \subseteq \omega^{<\omega_1}$ the set ${\alpha < \omega_1 : X \cap \omega^{<\alpha}}$ is stationary.

Proof. We note that […] Clearly, $Z_\alpha \subseteq \mathcal{P}(\omega^{<\alpha})$ and is at most countable.

Additionally, the sentence “Let ${C_n : n \in \mathbb{N}}$ be the at most countable collection of those elements of $Z_\alpha$ which happen to be maximal antichains in $T^{(\alpha)}$.” just before Claim 5.5 means that for each $n$, $C_n \in Z_\alpha$, $C_n \subseteq \omega^\alpha$, and $C_n$ is an antichain when its elements are regarded as nodes of $T^{(\alpha)}$. ■

Corollary. If $V = L$, then a Suslin line exists.

Thus, the existence of Suslin lines is related to the regulation of the set-theoretic universe. While this may seem paradoxical, it is not so surprising when one considers that one of the conditions for Suslin lines is the “non-existence” of countable dense sets. Suslin lines are a feature of a “loose” set-theoretic universe that achieves the countable chain condition without generating countable dense sets.

오일러-푸앵카레 정리

23 Nov 2025

독자 분은 어렸을 때 다음의 정리를 배웠을 것이다.

오일러 공식. 볼록다면체의 꼭짓점, 모서리, 면의 개수를 $v, e, f$라고 할 때, $v - e + f= 2$이다.

예를 들어 정육면체의 경우 $v = 8, e = 12, f = 6$이므로 $v - e + f = 2$가 성립한다. 볼록다면체라는 조건은 중요한데, 만약 다면체에 “구멍”이 있으면 공식이 성립하지 않기 때문이다. 예를 들어 아래의 구멍 난 프리즘의 경우 $v = 16, e = 32, f = 16$이므로 $v - e + f = 0$이다.

이로부터 우리는 $v - e + f$의 값이 도형의 위상에 의해 결정된다고 추측할 수 있다. 이것이 오일러-푸앵카레 정리의 내용이다. 정리를 진술하기 앞서, 먼저 다음의 개념을 정의하자.

정의. 위상공간 $X$에 대해, $X$의 호몰로지 군 $H_p(X)$의 자유 부분_{free part}의 랭크를 $X$의 $p$번째 베티 수_{Betti number}라고 하며 $R_p(X)$라고 적는다.

원래 $b_p(X)$라고 적는 것이 관행인데, 이 글에서는 $b_p$를 다른 의미로 사용할 것이기 때문에 다른 표기법을 채택했다. 호몰로지 군은 위상 불변이므로 베티 수 또한 위상 불변이다.

예를 들어 토러스의 호몰로지 군은 다음과 같다.

• $H_0(X) = \mathbb{Z}$
• $H_1(X) = \mathbb{Z} \oplus \mathbb{Z}$
• $H_2(X) = \mathbb{Z}$

따라서 토러스의 0차, 1차, 2차 베티 수는 각각 1, 2, 1이다. 베티 수는 직관적으로 구멍의 의미를 가진다 (이전 글 참조). 특히, 0차 베티 수는 $K$를 이루는 연결 요소들의 수이다. 즉, 두 개의 사면체를 하나의 단체 복합체로 간주한다면 이 복합체의 0차 베티 수는 2이다.

오일러-푸앵카레 정리. $n$-단체 복합체 $K$에 대해, $\alpha_p \; (p \leq n)$를 $K$의 $p$-단체들의 개수라고 하자. 다음이 성립한다.

\[\sum^n_{p = 0} (-1)^p\alpha_p = \sum^n_{p=0}(-1)^p R_p(K)\]

위 정리의 증명에서는 $p$-체인들을 자유군의 원소로 보는 것보다 선형 공간의 원소로 보는 것이 더 자연스럽기 때문에 이 접근을 취한다.

증명. $K$의 $p$-체인, 고리, 경계가 각각 유리수체에 대해 이루는 선형 공간을 $C_p, Z_p, B_p$라고 하자. $\lbrace d^i_p \rbrace $가 고리를 선형 생성하지 않는 $C_p$의 극대 부분집합이라고 하고, $\lbrace d^i_p \rbrace $가 생성하는 선형공간을 $D_p$라고 하자. 다음이 성립한다 ($\oplus$는 벡터 공간의 직합).

\[\begin{gather} C_p = D_p \oplus Z_p\\\\ \alpha_p = \dim C_p = \dim D_p + \dim Z_p \end{gather}\]

$p \leq n - 1$에 대해, $b^i_p = \partial d^i_{p + 1}$라고 하자. $\lbrace b^i_p \rbrace $가 생성하는 선형 공간을 $B_p$라고 하자. $\partial$은 선형 연산자이므로, $\lbrace d^i_{p +1} \rbrace $가 $D_{p + 1}$의 선형 기저라는 사실로부터 $\lbrace b^i_p \rbrace $가 $B_p$의 선형 기저라는 사실이 따라 나온다. 다음의 보조정리를 증명한다.

보조정리. $B_p$는 $K$의 모든 $p$-경계들을 포함한다.

증명. 만약 $b_p$가 $K$의 $p$-경계라면, 어떤 $c_{p + 1} \in C_{p + 1}$에 대해 $\partial c_{p + 1} = b_p$이다. $C_{p + 1} = D_{p + 1} \oplus Z_{p + 1}$ 관계에 의해 어떤 유일한 $d_{p + 1} \in D_{p + 1}, z_{p + 1} \in Z_{p + 1}$이 존재하여 $c_{p + 1 } = d_{p + 1} + z_{p + 1}$이다. 그런데 $\partial z_{p + 1} = 0$이므로 $\partial d_{p + 1} = b_p$이다. 따라서 $b_p \in B_p$이다. □

$\lbrace z^i_p \rbrace $가 $B_p$의 원소를 선형 생성하지 않는 $Z_p$의 극대 부분집합이라고 하고, $\lbrace z^i_p \rbrace $가 생성하는 선형공간을 $G_p$라고 하자. 보조정리에 의해 다음이 성립한다.

\[\dim G_p = R_p\]

따라서 다음이 성립한다.

\[\begin{gather} Z_p = B_p \oplus G_p\\\\ \dim Z_p = \dim B_p + \dim G_p = \dim D_{p + 1} + R_p \end{gather}\]

앞선 결과와 연립하면 다음을 얻는다 ($p \leq n - 1$).

\[\alpha_p = \dim D_{p + 1} + \dim D_p + R_p\]

$p = n$일 때 $\alpha_n = \dim D_n + R_n$이고, $p = 0$일 때 $\alpha_0 = \dim D_1 + R_0$이다. 따라서 다음을 얻는다 (wlog, $n$은 짝수).

\[\begin{alignat}{3} &\alpha_n &&= \;\cancel{\dim D_n} + R_p \\ &-\alpha_{n-1} &&= \;\cancel{-\dim D_{n}} \cancel{- \dim D_{n - 1}} - R_{n - 1} \\ &\alpha_{n-2} &&= \;\cancel{\dim D_{n - 1}} \cancel{ + \dim D_{n - 2}} + R_{n - 2} \\ &&\vdots \\ &-\alpha_{1} &&= \;\cancel{-\dim D_{2}} \cancel{-\dim D_{1}} - R_{1} \\ &\alpha_{0} &&= \;\cancel{\dim D_{1}} + R_{0} \\ \hline &\sum_{p = 0}^n (-1)^p \alpha_p &&= \;\sum_{p=0}^n (-1)^p R_p(K) \quad \blacksquare \end{alignat}\]

정의. 위상공간 X에 대해, 다음 값을 오일러 종수_{Euler characteristic}라고 한다.

\[\xi(X) = \sum (-1)^p R_p(X)\]

베티 수가 위상 불변이므로 오일러 종수 또한 위상 불변이다.

따름정리. 다면체 $P$의 꼭짓점, 모서리, 면의 개수를 $v, e, f$라고 하자. 2차원 위상공간으로서의 $P$의 표면을 $X$라고 하자. 다음이 성립한다.

\[v - e + f = \xi(X)\]

증명. $k$각형의 삼각화는 $k - 3$개의 모서리를 추가함으로써 얻을 수 있는데, 이 과정에서 $k - 3$개의 면이 생긴다. 따라서 $P$는 $P$의 삼각화와 $v - e + f$ 값이 같으며, 이는 오일러 종수와 같다. ■

앞서 우리는 구멍이 하나 있는 다면체의 경우 $v - e + f = 0$임을 보았다. 실제로 토러스의 0차, 1차, 2차 베티 수는 1, 2, 1이며, $1 - 2 + 1 = 0$이다. 한편 구의 호몰로지 군은 다음과 같다.

• $H_0(K) = \mathbb{Z}$
• $H_1(K) = 0$
• $H_2(K) = \mathbb{Z}$

따라서 구의 0차, 1차, 2차 베티 수는 1, 0, 1이며, $1 - 0 + 1 = 2$이다. 따라서 볼록다면체의 경우 $v - e + f = 2$이다.

Euler-Poincaré Theorem

23 Nov 2025

This post was originally written in Korean, and has been machine translated into English. It may contain minor errors or unnatural expressions. Proofreading will be done in the near future.

Readers may recall learning the following theorem in their youth:

Euler’s Formula. For a convex polyhedron, let $v, e, f$ denote the number of vertices, edges, and faces, respectively. Then $v - e + f = 2$.

For instance, in the case of a cube, $v = 8, e = 12, f = 6$, so $v - e + f = 2$ holds. The condition of convexity is crucial; if the polyhedron has “holes,” the formula does not hold. For example, in the case of the punctured prism below, $v = 16, e = 32, f = 16$, so $v - e + f = 0$.

From this, we may conjecture that the value of $v - e + f$ is determined by the topology of the shape. This is the essence of the Euler-Poincaré theorem. Before stating the theorem, let us first define the following concept:

Definition. For a topological space $X$, the rank of the free part of the homology group $H_p(X)$ of $X$ is called the $p$th Betti number of $X$, denoted $R_p(X)$.

While it is customary to denote this as $b_p(X)$, we adopt a different notation here as $b_p$ will be used for another purpose in this article. Since homology groups are topological invariants, Betti numbers are also topological invariants.

For example, the homology groups of a torus are as follows:

• $H_0(X) = \mathbb{Z}$
• $H_1(X) = \mathbb{Z} \oplus \mathbb{Z}$
• $H_2(X) = \mathbb{Z}$

Thus, the 0th, 1st, and 2nd Betti numbers of the torus are 1, 2, and 1, respectively. Intuitively, Betti numbers represent the number of “holes” (see previous post). In particular, the 0th Betti number corresponds to the number of connected components of $K$. For instance, if two tetrahedra are considered as a single simplicial complex, the 0th Betti number of this complex is 2.

Euler-Poincaré Theorem. For an $n$-dimensional simplicial complex $K$, let $\alpha_p \; (p \leq n)$ denote the number of $p$-simplices in $K$. Then the following holds:

\[\sum^n_{p = 0} (-1)^p\alpha_p = \sum^n_{p=0}(-1)^p R_p(K)\]

In proving this theorem, it is more natural to view $p$-chains as elements of a vector space rather than a free group, and we adopt this approach.

Proof. Let $C_p, Z_p, B_p$ denote the vector spaces of $p$-chains, cycles, and boundaries of $K$ over the field of rational numbers, respectively. Let $\lbrace d^i_p \rbrace $ be a maximal subset of $C_p$ that does not linearly generate cycles, and let the vector space spanned by $\lbrace d^i_p \rbrace $ be $D_p$. Then the following holds ($\oplus$ denotes the direct sum of vector spaces):

\[\begin{gather} C_p = D_p \oplus Z_p\\\\ \alpha_p = \dim C_p = \dim D_p + \dim Z_p \end{gather}\]

For $p \leq n - 1$, let $b^i_p = \partial d^i_{p + 1}$. Let the vector space spanned by $\lbrace b^i_p \rbrace $ be $B_p$. Since $\partial$ is a linear operator, it follows from the fact that $\lbrace d^i_{p +1} \rbrace $ forms a basis of $D_{p + 1}$ that $\lbrace b^i_p \rbrace $ forms a basis of $B_p$. We prove the following lemma:

Lemma. $B_p$ contains all $p$-boundaries of $K$.

Proof. If $b_p$ is a $p$-boundary of $K$, then there exists some $c_{p + 1} \in C_{p + 1}$ such that $\partial c_{p + 1} = b_p$. By the relation $C_{p + 1} = D_{p + 1} \oplus Z_{p + 1}$, there exist unique $d_{p + 1} \in D_{p + 1}$ and $z_{p + 1} \in Z_{p + 1}$ such that $c_{p + 1 } = d_{p + 1} + z_{p + 1}$. Since $\partial z_{p + 1} = 0$, it follows that $\partial d_{p + 1} = b_p$. Hence, $b_p \in B_p$. □

Let $\lbrace z^i_p \rbrace $ be a maximal subset of $Z_p$ that does not linearly generate elements of $B_p$, and let the vector space spanned by $\lbrace z^i_p \rbrace $ be $G_p$. By the lemma, the following holds:

\[\dim G_p = R_p\]

Thus, we have:

\[\begin{gather} Z_p = B_p \oplus G_p\\\\ \dim Z_p = \dim B_p + \dim G_p = \dim D_{p + 1} + R_p \end{gather}\]

Combining this with earlier results, we obtain the following for $p \leq n - 1$:

\[\alpha_p = \dim D_{p + 1} + \dim D_p + R_p\]

For $p = n$, $\alpha_n = \dim D_n + R_n$, and for $p = 0$, $\alpha_0 = \dim D_1 + R_0$. Hence, we derive the following (wlog, $n$ is even):

\[\begin{alignat}{3} &\alpha_n &&= \;\cancel{\dim D_n} + R_p \\ &-\alpha_{n-1} &&= \;\cancel{-\dim D_{n}} \cancel{- \dim D_{n - 1}} - R_{n - 1} \\ &\alpha_{n-2} &&= \;\cancel{\dim D_{n - 1}} \cancel{ + \dim D_{n - 2}} + R_{n - 2} \\ &&\vdots \\ &-\alpha_{1} &&= \;\cancel{-\dim D_{2}} \cancel{-\dim D_{1}} - R_{1} \\ &\alpha_{0} &&= \;\cancel{\dim D_{1}} + R_{0} \\ \hline &\sum_{p = 0}^n (-1)^p \alpha_p &&= \;\sum_{p=0}^n (-1)^p R_p(K) \quad \blacksquare \end{alignat}\]

Definition. For a topological space $X$, the following value is called the Euler characteristic:

\[\xi(X) = \sum (-1)^p R_p(X)\]

Since Betti numbers are topological invariants, the Euler characteristic is also a topological invariant.

Corollary. Let $v, e, f$ denote the number of vertices, edges, and faces of a polyhedron $P$, respectively. Let $X$ denote the surface of $P$ as a 2-dimensional topological space. Then the following holds:

\[v - e + f = \xi(X)\]

Proof. The triangulation of a $k$-gon can be obtained by adding $k - 3$ edges, which creates $k - 3$ faces. Thus, $P$ has the same $v - e + f$ value as its triangulation, which equals the Euler characteristic. ■

Earlier, we observed that for a polyhedron with one hole, $v - e + f = 0$. Indeed, the 0th, 1st, and 2nd Betti numbers of a torus are 1, 2, and 1, respectively, and $1 - 2 + 1 = 0$. On the other hand, the homology groups of a sphere are as follows:

• $H_0(K) = \mathbb{Z}$
• $H_1(K) = 0$
• $H_2(K) = \mathbb{Z}$

Thus, the 0th, 1st, and 2nd Betti numbers of a sphere are 1, 0, and 1, respectively, and $1 - 0 + 1 = 2$. Therefore, for convex polyhedra, $v - e + f = 2$.

클럽 집합과 정상 집합

11 Nov 2025

클럽 집합

정의. $C \subseteq \omega_1$이 클럽 집합_{club set}이라는 것은 $C$가 닫히고 무계_{closed and unbounded}라는 것이다. 즉,

• 임의의 서수열 $(\alpha_n)_{n \in \omega} \subseteq C$에 대해 $\alpha_n \to \alpha$라면 $\alpha \in C$이다.
• 임의의 $\gamma < \kappa$에 대해 $\alpha > \gamma$인 $\alpha \in C$가 존재한다.

그야말로 정직한 네이밍이 아닐 수 없다.

정리. $C_1, C_2 \subseteq \omega_1$이 두 클럽 집합일 때, $C = C_1 \cap C_2$ 또한 클럽 집합이다.

증명. $C$가 닫힘이라는 것은 쉽게 보여진다. $C$가 무계임을 보이기 위해 임의의 $\gamma \in \omega_1$를 잡자. $C_1$이 무계이므로 $\gamma < \alpha_0$을 만족하는 가장 작은 $\alpha_0 \in C_1$가 있다. $C_2$가 무계이므로 $\alpha_0 < \beta_0$인 가장 작은 $\beta_0 \in C_2$가 있다. 다시 $C_1$이 무계이므로 $\beta_0 < \alpha_1$인 $\alpha_1 \in C_1$가 있다. 이 과정을 계속 반복하여 서수열 $\lbrace \alpha_n \rbrace $과 $\lbrace \beta_n \rbrace $을 얻는다. 두 서수열은 같은 서수 $\delta$로 수렴하므로 $\delta \in C$이며, $\delta > \gamma$이다. (p.s. “가장 작은”은 불필요한 선택 공리의 사용을 피하기 위해 사용되었다) ■

위 증명을 살짝 변형하면 다음 정리를 얻을 수 있다.

정리. $\lbrace C_n \rbrace _{n < \omega}$가 클럽 집합들의 가산 모임일 때, $C = \bigcap C_n$ 또한 클럽 집합이다.

증명. 연습문제 (힌트: 삼각형을 사용한다) ■

따라서 가산 개의 클럽 집합들이 주어지면 교집합을 취함으로써 새로운 클럽 집합을 얻을 수 있다. 한편, 비가산 개의 클럽 집합들이 주어지면 다음을 사용할 수 있다.

정리. $\lbrace C_\xi \rbrace _{\xi < \omega_1}$이 클럽 집합들의 모임일 때, $\lbrace C_\xi \rbrace $의 대각 교집합_{diagonal intersection}을 다음과 같이 정의한다.

\[\Delta_{\xi < \omega_1} C_\xi = \{ \alpha \in \omega_1 : \forall \xi < \alpha \;\; \alpha \in C_\xi \}\]

$D$는 클럽 집합이다.

증명. $D$가 닫혀 있음을 먼저 보이자. 서수열 $(\alpha_n)_{n \in \omega} \subseteq D$에 대해 $\alpha_n \to \alpha$라고 하자. 임의의 $\xi < \alpha$에 대해 $\xi < \alpha_n$인 $n \in \omega$가 존재하며, 대각 교집합의 정의에 의해 $C_\xi$은 $\lbrace \alpha_m : m \geq n \rbrace $을 포함한다. 따라서 $\sup \lbrace \alpha_m : m \geq n \rbrace = \alpha \in C_\xi$이므로 $\alpha \in D$이다.

이제 $D$가 무계임을 보이자. 임의의 $\gamma < \omega_1$에 대해, $D_0 = \bigcap_{\xi < \gamma} C_\xi$는 클럽 집합이므로 무계이다. 따라서 $\alpha_0 > \gamma$를 만족하는 가장 작은 $\alpha_0 \in D_0$가 존재한다. 마찬가지로 $D_1 = \bigcap_{\xi < \alpha_0} C_\xi$가 클럽 집합이므로 $\alpha_1 > \alpha_0$를 만족하는 가장 작은 $\alpha_1 \in D_1$이 존재한다. 이 과정을 귀납적으로 반복하여 얻은 서수열 $(\alpha_n)$의 극한이 $\alpha$라고 하자. 임의의 $\xi < \alpha$에 대해, 어떤 $n$이 존재하여 $\xi < \alpha_n$이므로 임의의 $m \geq n$에 대하여 $\alpha_m \in C_\xi$이다. 따라서 $\alpha \in C_\xi$이며 $\alpha \in D$이다. ■

$\Delta C_\xi \supseteq \bigcap C_\xi$임을 확인하라.

참고로 지금까지의 정의와 정리들은 다음과 같이 일반화될 수 있다. $\kappa$가 $\operatorname{cf}\kappa > \omega$인 비가산 기수라고 하자.

정의. $C \subseteq \kappa$가 클럽 집합_{club set}이라는 것은 $C$가 닫히고 무계_{closed and unbounded}라는 것이다. 즉,

• 임의의 $\alpha < \kappa$에 대해 $\sup (C \cap \alpha) = \alpha$라면 (즉 $C$가 $\alpha$에서 무계라면) $\alpha \in C$이다.
• 임의의 $\gamma < \kappa$에 대해 $\alpha > \gamma$인 $\alpha \in C$가 존재한다.

정리. $\lambda < \operatorname{cf}\kappa$에 대해 $\lbrace C_\xi \rbrace _{\xi < \lambda}$가 클럽 집합들의 모임일 때, $C = \bigcap C_\xi$ 또한 클럽 집합이다.

정리. $\kappa$가 정칙_regular이라면, $\lbrace C_\xi \rbrace _{\xi < \kappa}$가 클럽 집합들의 모임일 때, $\lbrace C_\xi \rbrace $의 대각 교집합 또한 클럽 집합이다.

증명. $\kappa = \omega_1$인 경우와 거의 같다. ■

정상 집합

유한 교집합 닫힘에 의해 클럽 집합들의 모임은 필터를 생성한다. 해당 필터의 쌍대_dual 아이디얼에 속하지 않는 집합을 정상 집합_{stationary set}이라고 한다. 다른 말로 하자면 다음과 같다.

정의. $S \subseteq \omega_1$이라고 하자. 임의의 클럽 집합 $C \subseteq \omega_1$에 대해 $C \cap S \neq \varnothing$이라면 $S$는 정상 집합이다.

어떤 클럽 집합 $C$에 대해 $C \cap S = \varnothing$이라면 $S^c \subseteq C$이므로 $C$는 쌍대 아이디얼의 원소이다. 따라서 두 정의는 동치이다.

정상 집합은 $\omega_1$의 부분집합 중 “유의미하게 큰” 집합들을 포착한다. 이 사실은 다음의 (엄밀하지는 않은) 유비를 통해 더 잘 이해할 수 있다. $\omega_1$의 측도가 1이라고 할 때, 클럽 집합은 $\mu(C) = 1$인 집합에, 정상 집합은 $\mu(S) > 0$인 집합에 대응된다.

다음의 사실들은 쉽게 증명될 수 있다 (1번과 3번이 측도 유비와 자연스럽게 연결되는 것에 주목하라).

정리. 다음이 성립한다.

1. 모든 클럽 집합은 정상 집합이다.
2. 모든 정상 집합은 무계이다.
3. $\bigcup_{n < \omega} A_n$가 정상 집합이라면 어떤 $m \in \omega$에 대해 $A_m$은 정상 집합이다.

정상 집합의 이름이 stationary인 이유는 다음의 정리 때문이다.

정리. $S \subseteq \omega_1$에 대해, $f: S \to \omega_1$이 퇴행적_regressive이라는 것은 임의의 $\alpha \in S$에 대해 $f(\alpha) < \alpha$라는 것이다. 다음이 동치이다.

1. $S$는 정상 집합이다.
2. 임의의 퇴행적 함수 $f: S \to \omega_1$에 대해, $f$는 어떤 무계 집합 $T \subseteq S$ 위에서 상수_constant이다.
3. 임의의 퇴행적 함수 $f: S \to \omega_1$에 대해, $f$는 어떤 정상 집합 $T \subseteq S$ 위에서 상수이다.

증명. 3 ⇒ 2는 자명하므로, 1 ⇒ 3과 2 ⇒ 1을 증명하면 된다.

1 ⇒ 3

대우를 증명한다. 어떤 퇴행적 함수 $f: S \to \omega_1$에 대해, $S$의 모든 정상 부분집합 위에서 $f$가 상수가 아니라고 하자. 즉, 임의의 $\xi \in \omega_1$에 대하여 $A_\xi = f^{-1}(\lbrace \xi \rbrace )$는 정상 집합이 아니다. 따라서 $A_\xi \cap C_\xi = \varnothing$인 클럽 집합 $C_\xi$가 존재한다.

$D = \Delta_{\xi < \omega_1} C_\xi$라고 하자. $D$는 클럽 집합이므로, 만약 $S$가 정상 집합이라면 $D \cap S \neq \varnothing$이다. $\alpha \in D \cap S$라고 하자. $\alpha \in D$이므로 임의의 $\xi < \alpha$에 대하여 $\alpha \in C_\xi$이다. 즉, $\alpha \notin A_\xi$이므로 $f(\alpha) \neq \xi$이다. 그런데 $\alpha \in S$이므로 $f(\alpha) < \alpha$이다. 이는 모순이므로 $S$는 정상 집합이 아니다. □

2 ⇒ 1

마찬가지로 대우를 증명한다. $S$가 정상 집합이 아니라고 하자. 그러면 어떤 클럽 집합 $C$에 대해 $S \cap C = \varnothing$이다. 다음의 함수를 정의하자.

\[f(\alpha) = \sup (C \cap \alpha)\]

임의의 $\alpha \in S$에 대하여 $f(\alpha) \leq \alpha$이다. 만약 $f(\alpha) = \alpha$라면, $C$는 $\alpha$로 수렴하는 서수열을 가진다. 그런데 $C$는 닫힌 집합이므로, $\alpha \in C$이다. 이는 $S \cap C = \varnothing$에 모순이다. 따라서 $f(\alpha) < \alpha$이며, $f$는 퇴행적이다.

만약 어떤 무계 집합 $T$ 위에서 $f$의 값이 $\gamma < \omega_1$로 일정했다면, 어떤 무계인 서수열 $(\alpha_n)$에 대해 $\sup (C \cap \alpha_n) = \gamma$이다. 그런데 $C$는 무계이므로, 이는 $\sup \alpha_n = \gamma$를 함축한다. 그런데 $(\alpha_n)$이 무계이므로 $\sup \alpha_n = \omega_1$이다. 이는 모순이다. 따라서 $f$는 어떠한 무계 집합 위에서도 상수가 아닌 퇴행적 함수이다. ■

위 정리는 다음의 정리로 일반화될 수 있다.

포더 보조정리_{Fodor’s lemma}. $\kappa$가 비가산 정칙 기수라고 하자. 임의의 $S \subseteq \kappa$에 대해 다음이 동치이다.

1. $S$는 정상 집합이다.
2. 임의의 퇴행적 함수 $f: S \to \omega_1$에 대해, $f$는 어떤 무계 집합 $T \subseteq S$ 위에서 상수이다.
3. 임의의 퇴행적 함수 $f: S \to \omega_1$에 대해, $f$는 어떤 정상 집합 $T \subseteq S$ 위에서 상수이다.

정상 집합의 응용

정상 집합의 한 응용으로서 조합론의 다음 정리를 보자.

Δ-계 보조정리_{Δ-system lemma}. $\lbrace A_\xi\rbrace _{\xi < \omega_1}$가 $\omega_1$의 유한부분집합들의 모임이라고 하자. 어떤 무계인 $I \subseteq \omega_1$와 유한집합 $A$가 존재하여, 임의의 $i, j \in I, i \neq j$에 대해 $A_i \cap A_j = A$이다.

증명. 비둘기집의 원리에 의해 일반성을 잃지 않고, 임의의 $\xi < \omega_1$에 대해 $|A_\xi | = n$이라고 가정할 수 있다. 다음과 같이 정의하자.

\[C = \{ \alpha < \omega_1 : \forall \xi < \alpha \;\; \operatorname{max}C_\xi < \alpha \}\]

$C$는 클럽 집합이다. 또한 $0 \leq k \leq n$에 대해 다음과 같이 정의하자.

\[T_k = \{ \alpha \in C : |A_\alpha \cap \alpha | = k \}\]

$\bigcup_{0 \leq k \leq n} T_k = C$이므로 어떤 $m$에 대해 $T_m$은 정적 집합이다. 이제 $0 \leq l < m$에 대해 다음의 함수를 정의하자.

\[f_l(\alpha) : T_m \to \omega_1; \quad \alpha \mapsto \text{$l$th element of $A_\alpha$}\]

$|A_\alpha \cap \alpha| > l$이므로 $f_l(\alpha) < \alpha$이다. 따라서 각 $l$에 대해 $f_l$는 퇴행적이다. 이제 다음의 단계를 반복한다.

• $f_0$가 상수가 되는 정적 집합 $S_0 \subseteq T_m$이 존재한다.
• $f_1 |_{S_0}$이 상수가 되는 정적 집합 $S_1 \subseteq S_0$가 존재한다.
• $f_2 |_{S_1}$이 상수가 되는 정적 집합 $S_2 \subseteq S_1$이 존재한다.
• …
• $f_{m-1} |_{S_{m-2}}$가 상수가 되는 정적 집합 $S_{m-1} \subseteq S_{m-2}$가 존재한다.

그러면 임의의 $0 \leq l < m$에 대해 $f_l$은 $S_{m-1}$에서 상수이다. 이제 $S_{m-1} = I$가 찾고자 하는 집합임을 쉽게 확인할 수 있다. ■

Club Sets and Stationary Sets

11 Nov 2025

This post was originally written in Korean, and has been machine translated into English. It may contain minor errors or unnatural expressions. Proofreading will be done in the near future.

Club Sets

Definition. $C \subseteq \omega_1$ is a club set if $C$ is closed and unbounded. That is,

• For any sequence of ordinals $(\alpha_n)_{n \in \omega} \subseteq C$, if $\alpha_n \to \alpha$, then $\alpha \in C$.
• For any $\gamma < \kappa$, there exists $\alpha \in C$ such that $\alpha > \gamma$.

The name is indeed quite straightforward.

Theorem. If $C_1, C_2 \subseteq \omega_1$ are two club sets, then $C = C_1 \cap C_2$ is also a club set.

Proof. It is easy to show that $C$ is closed. To prove that $C$ is unbounded, let us take an arbitrary $\gamma \in \omega_1$. Since $C_1$ is unbounded, there exists the smallest $\alpha_0 \in C_1$ such that $\gamma < \alpha_0$. Similarly, since $C_2$ is unbounded, there exists the smallest $\beta_0 \in C_2$ such that $\alpha_0 < \beta_0$. Again, since $C_1$ is unbounded, there exists $\alpha_1 \in C_1$ such that $\beta_0 < \alpha_1$. Repeating this process, we obtain sequences of ordinals $\lbrace \alpha_n \rbrace$ and $\lbrace \beta_n \rbrace$. These sequences converge to the same ordinal $\delta$, so $\delta \in C$ and $\delta > \gamma$. (Note: “the smallest” is used to avoid unnecessary reliance on the axiom of choice.) ■

By slightly modifying the above proof, we can derive the following theorem.

Theorem. If $\lbrace C_n \rbrace _{n < \omega}$ is a countable collection of club sets, then $C = \bigcap C_n$ is also a club set.

Proof. Exercise (Hint: Use a triangle argument). ■

Thus, given a countable collection of club sets, we can obtain a new club set by taking their intersection. On the other hand, if we are given an uncountable collection of club sets, the following result can be used.

Theorem. Let $\lbrace C_\xi \rbrace _{\xi < \omega_1}$ be a collection of club sets. The diagonal intersection of $\lbrace C_\xi \rbrace$ is defined as follows:

\[\Delta_{\xi < \omega_1} C_\xi = \{ \alpha \in \omega_1 : \forall \xi < \alpha \;\; \alpha \in C_\xi \}\]

$D$ is a club set.

Proof. First, let us show that $D$ is closed. Suppose $(\alpha_n)_{n \in \omega} \subseteq D$ and $\alpha_n \to \alpha$. For any $\xi < \alpha$, there exists $n \in \omega$ such that $\xi < \alpha_n$. By the definition of the diagonal intersection, $C_\xi$ contains $\lbrace \alpha_m : m \geq n \rbrace$. Hence, $\sup \lbrace \alpha_m : m \geq n \rbrace = \alpha \in C_\xi$, so $\alpha \in D$.

Next, let us show that $D$ is unbounded. For any $\gamma < \omega_1$, let $D_0 = \bigcap_{\xi < \gamma} C_\xi$. Since $D_0$ is a club set, it is unbounded. Thus, there exists the smallest $\alpha_0 \in D_0$ such that $\alpha_0 > \gamma$. Similarly, let $D_1 = \bigcap_{\xi < \alpha_0} C_\xi$. Since $D_1$ is a club set, there exists the smallest $\alpha_1 \in D_1$ such that $\alpha_1 > \alpha_0$. Repeating this process inductively, we obtain a sequence $(\alpha_n)$ whose limit is $\alpha$. For any $\xi < \alpha$, there exists $n$ such that $\xi < \alpha_n$, and for all $m \geq n$, $\alpha_m \in C_\xi$. Hence, $\alpha \in C_\xi$ and $\alpha \in D$. ■

Verify that $\Delta C_\xi \supseteq \bigcap C_\xi$.

The definitions and theorems discussed so far can be generalised as follows. Let $\kappa$ be an uncountable cardinal with $\operatorname{cf}\kappa > \omega$.

Definition. $C \subseteq \kappa$ is a club set if $C$ is closed and unbounded. That is,

• For any $\alpha < \kappa$, if $\sup (C \cap \alpha) = \alpha$ (i.e., $C$ is unbounded at $\alpha$), then $\alpha \in C$.
• For any $\gamma < \kappa$, there exists $\alpha \in C$ such that $\alpha > \gamma$.

Theorem. If $\lambda < \operatorname{cf}\kappa$ and $\lbrace C_\xi \rbrace _{\xi < \lambda}$ is a collection of club sets, then $C = \bigcap C_\xi$ is also a club set.

Theorem. If $\kappa$ is regular, then the diagonal intersection of a collection $\lbrace C_\xi \rbrace _{\xi < \kappa}$ of club sets is also a club set.

Proof. The proof is almost identical to the case $\kappa = \omega_1$. ■

Stationary Sets

By closure under finite intersections, the collection of club sets generates a filter. A set that does not belong to the dual ideal of this filter is called a stationary set. In other words:

Definition. Let $S \subseteq \omega_1$. If $C \cap S \neq \varnothing$ for every club set $C \subseteq \omega_1$, then $S$ is a stationary set.

If there exists a club set $C$ such that $C \cap S = \varnothing$, then $S^c \subseteq C$, so $C$ belongs to the dual ideal. Thus, the two definitions are equivalent.

Stationary sets capture “significantly large” subsets of $\omega_1$. This can be better understood through the following (informal) analogy: if $\omega_1$ has measure 1, then club sets correspond to sets with $\mu(C) = 1$, and stationary sets correspond to sets with $\mu(S) > 0$.

The following facts are easily proven (note how 1 and 3 naturally align with the measure analogy):

Theorem. The following hold:

1. Every club set is a stationary set.
2. Every stationary set is unbounded.
3. If $\bigcup_{n < \omega} A_n$ is a stationary set, then there exists some $m \in \omega$ such that $A_m$ is a stationary set.

The name “stationary” for stationary sets arises from the following theorem.

Theorem. Let $S \subseteq \omega_1$. A function $f: S \to \omega_1$ is regressive if $f(\alpha) < \alpha$ for all $\alpha \in S$. The following are equivalent:

1. $S$ is a stationary set.
2. For any regressive function $f: S \to \omega_1$, $f$ is constant on some unbounded set $T \subseteq S$.
3. For any regressive function $f: S \to \omega_1$, $f$ is constant on some stationary set $T \subseteq S$.

Proof. 3 ⇒ 2 is trivial, so it suffices to prove 1 ⇒ 3 and 2 ⇒ 1.

1 ⇒ 3

We prove the contrapositive. Suppose there exists a regressive function $f: S \to \omega_1$ such that $f$ is not constant on any stationary subset of $S$. That is, for every $\xi \in \omega_1$, $A_\xi = f^{-1}(\lbrace \xi \rbrace)$ is not stationary. Hence, there exists a club set $C_\xi$ such that $A_\xi \cap C_\xi = \varnothing$.

Let $D = \Delta_{\xi < \omega_1} C_\xi$. Since $D$ is a club set, if $S$ is stationary, then $D \cap S \neq \varnothing$. Let $\alpha \in D \cap S$. Since $\alpha \in D$, for any $\xi < \alpha$, $\alpha \in C_\xi$. Thus, $\alpha \notin A_\xi$, so $f(\alpha) \neq \xi$. However, since $\alpha \in S$, $f(\alpha) < \alpha$. This is a contradiction, so $S$ is not stationary. □

2 ⇒ 1

We again prove the contrapositive. Suppose $S$ is not stationary. Then there exists a club set $C$ such that $S \cap C = \varnothing$. Define the following function:

\[f(\alpha) = \sup (C \cap \alpha)\]

For any $\alpha \in S$, $f(\alpha) \leq \alpha$. If $f(\alpha) = \alpha$, then $C$ contains a sequence of ordinals converging to $\alpha$. Since $C$ is closed, $\alpha \in C$. This contradicts $S \cap C = \varnothing$. Thus, $f(\alpha) < \alpha$, and $f$ is regressive.

If $f$ were constant on some unbounded set $T$, then for some $\gamma < \omega_1$, there would exist an unbounded sequence $(\alpha_n)$ such that $\sup (C \cap \alpha_n) = \gamma$. Since $C$ is unbounded, this implies $\sup \alpha_n = \gamma$. However, since $(\alpha_n)$ is unbounded, $\sup \alpha_n = \omega_1$. This is a contradiction. Thus, $f$ is a regressive function that is not constant on any unbounded set. ■

The above theorem can be generalised as follows:

Fodor’s Lemma. Let $\kappa$ be an uncountable regular cardinal. For any $S \subseteq \kappa$, the following are equivalent:

1. $S$ is a stationary set.
2. For any regressive function $f: S \to \omega_1$, $f$ is constant on some unbounded set $T \subseteq S$.
3. For any regressive function $f: S \to \omega_1$, $f$ is constant on some stationary set $T \subseteq S$.

Applications of Stationary Sets

As an application of stationary sets, consider the following combinatorial theorem:

Δ-System Lemma. Let $\lbrace A_\xi\rbrace _{\xi < \omega_1}$ be a collection of finite subsets of $\omega_1$. There exist an unbounded set $I \subseteq \omega_1$ and a finite set $A$ such that for any $i, j \in I$ with $i \neq j$, $A_i \cap A_j = A$.

Proof. By the pigeonhole principle, we may assume without loss of generality that $|A_\xi | = n$ for all $\xi < \omega_1$. Define:

\[C = \{ \alpha < \omega_1 : \forall \xi < \alpha \;\; \operatorname{max}C_\xi < \alpha \}\]

$C$ is a club set. For $0 \leq k \leq n$, define:

\[T_k = \{ \alpha \in C : |A_\alpha \cap \alpha | = k \}\]

Since $\bigcup_{0 \leq k \leq n} T_k = C$, there exists some $m$ such that $T_m$ is stationary. For $0 \leq l < m$, define:

\[f_l(\alpha) : T_m \to \omega_1; \quad \alpha \mapsto \text{$l$th element of $A_\alpha$}\]

Since $|A_\alpha \cap \alpha| > l$, $f_l(\alpha) < \alpha$. Thus, $f_l$ is regressive. Now, repeat the following steps:

• There exists a stationary set $S_0 \subseteq T_m$ such that $f_0$ is constant on $S_0$.
• There exists a stationary set $S_1 \subseteq S_0$ such that $f_1 |_{S_0}$ is constant on $S_1$.
• There exists a stationary set $S_2 \subseteq S_1$ such that $f_2 |_{S_1}$ is constant on $S_2$.
• …
• There exists a stationary set $S_{m-1} \subseteq S_{m-2}$ such that $f_{m-1} |_{S_{m-2}}$ is constant on $S_{m-1}$.

For each $0 \leq l < m$, $f_l$ is constant on $S_{m-1}$. It is now easy to verify that $S_{m-1} = I$ is the desired set. ■