Category of Well-Ordered Sets

이 글에서는 다음 내용들을 다루어요.

  • Category of well-ordered sets
  • Statement that “If \{A_{i}\}_{i \in I} forms a/an [some condition] by inclusion and |A_{i}|<\alpha for some cardinal number \alpha, then \left| \bigcup_{i \in I} A_{i} \right| \le \alpha holds.”

[some condition]의 예시로는 directed set, well-ordered set, 그리고 totally ordered set이 있어요.

1. Category of Well-Ordered Sets

Category of well-ordered sets를 정의하기 전, 몇 가지 용어를 알아볼게요.

Definition (lower set, lower closure, cofinal). Let (A,\le) be a preordered set and B \subseteq A. We call B is a lower set of A if b \in B and a \in A satisfies a \le b, then a \in B. Lower closure of B is the smallest lower set of A containing B. We call B is a cofinal of A if the lower closure of B is A.

Fact. Lower closure of B is {a \in A:\exists b \in B, a \le b}.

그러면, category of well-ordered sets을 다음처럼 정의할 수 있어요.

Definition (category of well-ordered sets). Define category of well-ordered sets {\sf WOS} as

  • Objects of {\sf WOS} are well-ordered sets (A, \le_{A}).
  • Morphisms of {\sf WOS} are {\rm Hom}((A, \le_{A}), (B, \le_{B})):= \begin{cases} \{\iota_{B}^{A}:A \to B\} & \text{if } \begin{cases} \cdot \, A \subseteq B \\ \cdot \, \le_{B} \text{ is an extension of } \le_{A} \\ \cdot \, A \text{ is a lower set of } B \end{cases} \\ \emptyset & \text{otherwise} \end{cases}

where \iota_{B}^{A} is an embedding from A to B.

이 글에 쓰인 directed system 등의 용어는 category {\sf WOS} 위의 개념을 말하는 것이에요. 또, {\sf WOS}은 thin category이니 directed system의 morphism은 따로 적지 않더라도 명확하고, 이 글에서는 이것들이 생략되었어요. 이제, 다음이 성립해요!

Theorem. {\sf WOS} has direct limits.

Proof. direct system \{(A_{i}, \le_{A_{i}})\}_{i \in I}를 하나 생각하고, L=\bigcup_{i \in I} A_{i}\le_{L}=\bigcup_{i \in I} \le_{A_{i}}를 정의해요. 그러면 \le_{L}L의 total order가 된다는 것은 그리 어렵지 않고, well-order가 된다는 것은 \emptyset \neq S \subseteq L이면 S \cap A_{i} \neq \emptyset for some i \in I가 되고, \exists \min(S \cap A_{i})S의 minimum이 되는 것으로부터 증명되어요. morphism들은 \iota_{i}:A_{i} \to L를 embedding으로 주도록 해요. 그러면 다음 diagram

이 commute한다는 것은 당연해요.

이제 다른 object (X, \le_{X})와 morphisms \psi_{i}:(A_{i}, \le_{A_{i}}) \to X가 있어서 위와 유사한 commutative diagram을 만든다고 가정할게요. (사실 {\sf WOS}은 thin category라서 diagram이 commute 할 수 밖에 없어요.) 그러면 X \supseteq A_{i} for all i \in I에서 X supseteq L을 얻고, 비슷하게 \le_{X}\le_{L}의 extension이 되어요. 또, A_{i}들이 X의 lower set이니깐 L 역시 X의 lower set이 되고, 곧 unique morphism \eta:L \to X가 있어서 diagram

이 commute해요. 따라서 direct limit (L, \le_{L})=\varinjlim (A_{i}, \le_{A_{i}})이 존재한다는 것을 알 수 있어요. \square

Fact. If there is a directed system \{(A_{i}, \le_{A_{i}})\}_{i \in I} and a cardinal number \alpha satisfying |A_{i}|<\alpha for all i \in I, then the direct limit L of given directed system satisfies |L| \le \alpha (by the theory of ordinal numbers).

2. Cardinality of Union of Sets Whose Cardinality Are Bounded

이번에는 앞서 언급했던 명제 “\{A_{i}\}_{i \in I}가 set inclusion으로 [some condition]을 이루고, |A_{i}|<\alpha for some cardinal number \alpha이라면, \left| \bigcup_{i \in I} A_{i} \right| \le \alpha이다.”를 살펴볼게요. 물론, 아무런 condition을 주지 않는다면 union은 얼마든지 커질 수 있어요.

먼저, limit을 정의할 때 등장하는 directed set을 생각해볼 수 있어요. 하지만, directed set 조건을 주더라도 union이 충분히 커질 수 있는데, \alpha \ge \aleph_{0}이기만 하면 아무 set A에 대해 collection \{S \in \mathcal{P}(A): |S|<\infty\}은 directed set and |S|< \alpha for all elements S를 만족하지만, 이것의 union은 A가 되기 때문이에요.

그렇다면 조건을 많이 강하게 well-ordered set을 생각해볼게요. 이번엔 앞의 명제가 성립한다는 것을 보일 수 있어요(!)

Theorem. If \{A_{i}\}_{i \in I} forms a well-ordered set by inclusion and |A_{i}|<\alpha for some cardinal number \alpha, then \left| \bigcup_{i \in I} A_{i} \right| \le \alpha holds.

Proof. A_{i} 위에 적절한 well-order \le_{A_{i}}를 주어서 direct system \{(A_{i}, \le_{A_{i}})\}_{i \in I}를 만들 수 있다면 증명이 끝나요. 여기선 transfinite induction으로 이것을 증명할게요. 또, transfinite induction을 사용하기 쉽게 명제의 \{A_{i}\}_{i \in I}를 (I를 ordinal number로 생각해서) \{A_{i}\}_{i \le I}로 바꾼 것을 증명하기로 해요.

I=0: well-ordering principle에 의해 성립해요.

I \rightarrow I+1: 귀납가설에 의해 direct system \{(A_{i}, \le_{A_{i}})\}_{i \le I}를 만들 수 있고, well-ordering principle에 의해 A_{I+1} \setminus A_{I}에 well-order \le를 줄 수 있고, A_{I+1}에 다음과 같은 순서를 줄 수 있어요:

\displaystyle a \le_{A_{I+1}} b \overset{\text{def}}{\Longleftrightarrow} \begin{cases} a \le_{A_{I}} b & \text{if } a,b \in A_{I} \\ a \le b & \text{if } a,b \in A_{I+1} \setminus A_{I} \\ (a,b) \in A_{I} \times (A_{I+1} \setminus A_{I}) & \text{otherwise} \end{cases}

\{(A_{i}, \le_{A_{i}})\}_{i \le I}{\sf WOS}의 directed set을 이룬다는 것은 쉽게 확인할 수 있어요.

I is a limit ordinal: set S=\{\{(A_{i}, \le_{A_{i}})\}_{i \le J}:J \le I, \{(A_{i}, \le_{A_{i}})\}_{i \le J} \text{ is a direct system.}\}으로 정의하면 \emptyset \in S에서 S \neq \emptyset이라는 것을 알 수 있어요. S 위에 순서를 \subseteq로 준다면 S의 모든 chain이 bounded above라는 것은 그리 어렵지 않고, 곧 Zorn’s lemma에 의해 maximal element \{(A_{i}, \le_{A_{i}})\}_{i \le I'}이 존재해요. 그런데, 앞의 “I \rightarrow I+1” 경우에 의해 I'=I일 수 밖에 없고, 곧 증명이 끝나요. \square

사실 위의 정리는 totally ordered set 위에서도 성립하는데, 다음 보조정리를 볼게요:

Lemma. Every totally ordered set has a well-ordered cofinal.

Proof. S=\{B \in \mathcal{P}(A):(B, \le \cap (B \times B)) \text{ is well-ordered.}\}으로 정의하고, 이 위에 순서를 {\sf WOS}에서 morphism 주듯 줄 수 있어요. (poset을 순서로 정의하는 것과 category로 정의하는 것을 생각하면 좋을 것 같아요. 실제로 thin category는 posetal category라고 불리기도 해요.) Hausdorff maximal principle에 의해 S에는 maximal chain C가 존재하고, existence of direct limits in {\sf WOS}을 상기하면 M=\bigcup C는 well-ordered set이 되어요. MS의 maximal element가 된다는 것을 쉽게 알 수 있는데, 만일 MA의 cofinal이 아니라면 M의 upper bound m \in A가 존재하고, M \cup \{m\} \supsetneq M이 well-ordered라는 것은 쉬워요. 하지만 이것은 M의 maximality에 모순이고, 곧 A는 well-ordered cofinal을 가져요. \square

Corollary. If \{A_{i}\}_{i \in I} forms a totally ordered set by inclusion and |A_{i}|<\alpha for some cardinal number \alpha, then \left| \bigcup_{i \in I} A_{i} \right| \le \alpha holds.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s