彌永昌吉・彌永健一著『岩波基礎講座 基礎数学 9 集合と位相 I』より。

  • §5.1 順序関係、全順序集合
    • テーマ：順序の公理、関連用語の導入

    • 順序関係とは、集合 $a$ とその関係 $f$ に対して、次の条件（順序の公理）をみたすことをいう：

      \[\begin{aligned} \text{(i)}\quad & f \supset \varDelta_a,\\ \text{(ii)}\quad & f \cap f^{-1} = \varDelta_a,\\ \text{(iii)}\quad & f \circ f \subset f. \end{aligned}\]

    • 順序集合とは、順序関係 $f$ の入る集合 $a$ のことであり、 順序集合であることを強調するときには記号 $(a, f)$ で表す。

      • e.g. $(\N, \le)$, $(\N, \vert)$ は順序集合である。縦棒は「割り切る」を表す記号とする。

      • e.g. 集合 $A$ での包含関係は、$2^A$ の元と見て順序関係である：

        \[\subset \coloneqq \{(x, y) \in 2^A \times 2^A \,|\, x \subset y\}.\]

      • コメント：「関係」の定義の復習。これは「型が同じ対応」を意味する。 もっと言うと直積 $a \times a$ の部分集合に過ぎない。 それを踏まえて上の公理がそれぞれ反射律、対称律（？）、推移律を意味することを確認するといい。

      • コメント：SQL の JOIN は対応の合成なのかと思った。
    • 台集合とは、順序集合 $(a, f)$ における集合 $a$ のことである。
    • $x, y \in (a, f)$ に対して $(x, y) \in f$ であることを記号 $x \prec y$ または $y \succ x$ で表す。

    • 全順序集合とは、順序集合 $(a, f)$ であって、次の性質が成り立つものを言う：

      \[\forall (x, y) \in a \times a (x \prec y \lor y \prec x).\]
      • コメント：一般には、順序集合において順序関係が任意の元の対に対して成立するわけではない。
      • e.g. $(\omega, \le)$ は toset であるが $(\omega, \vert)$ は否。

    • 辞書式順序関係とは、二つの順序集合から次のように定義される新たな順序集合 $(a \times b, \prec)$ における順序関係のことである： $(a, \prec)$ と $(b, \prec)$ に対して：

      \[(x_1, y_1) \prec (x_2, y_2) \iff x_1 \prec x_1 \lor (x_1 = x_2 \land y_1 \prec y_2).\]
      • コメント：入力が面倒なので省略したが、上記 $\prec$ は集合ごとに異なるのが一般的だ。
      • コメント：二つどころかそれ以上でも構成可能。

    • （下）切片とは、順序集合 $(a, \prec)$ のある元 $x \in a$ から定まる次のような部分集合 $s(x)$ をいう：

      \[s(x) \coloneqq \{y \in a \,|\, y \prec x\}.\]
      • コメント：下界の定義に似ている。
      • 同様に上切片を用語として定義する。
    • 極小とは、順序集合の元の性質であり、次を意味する：$x \in (a, \prec)$ について $s(x) = \varnothing.$
      • 同様にして極大を、上切片を用いて定義する。

    • 上界集合・下界集合とは、順序集合 $(S, \prec)$ に対する次のそれぞれの集合を意味する：

      \[\begin{aligned} \operatorname{u.b.}(S) &\coloneqq \{x \in a \,|\,\forall s \in S (s \prec x)\},\\ \operatorname{l.b.}(S) &\coloneqq \{x \in a \,|\,\forall s \in S (x \prec s)\}. \end{aligned}\]
      • コメント：全順序集合でない順序集合をイメージしながら各概念を解釈したい。

    • 最小元・最大元とは、順序集合 $(S, \prec)$ に対する次のそれぞれの元を意味する：

      \[\begin{aligned} \max{S} &\coloneqq \{s \in S \,|\, \forall t \in S (t \prec s)\},\\ \min{S} &\coloneqq \{s \in S \,|\, \forall t \in S (s \prec t)\}.\\ \end{aligned}\]
      • ノートの便宜上、集合の形で表記した。存在するときはそれらは反射律から一意的に定まる。

    • 下限・上限とは、順序集合 $(S, \prec)$ に対する次のそれぞれの元を意味する：

      \[\begin{aligned} \inf S &\coloneqq \max \operatorname{l.b.}(S),\\ \sup S &\coloneqq \min \operatorname{u.b.}(S). \end{aligned}\]
      • コメント：定義上、これらは $S$ の元であるとは限らない。
    • 鎖とは、順序集合の部分集合であり、toset になっているものをいう。
  • §5.2 Zorn の補題
    • 集合論の一つの山。
    • 帰納的順序集合 (inductively ordered set) とは、順序集合であって、その任意の鎖が上界をもつものを言う。
      • コメント：上界限定？
      • 例：単位的環の、自分自身を除いたイデアル全部の集合を考える。集合の包含関係を順序関係とする ios が構成できる。 この順序集合の極大元こそがこの環の極大イデアルなのだ。
      • コメント：こういう極大元が一般的に存在するのかという問題が発生する。その問いに対する答えが Zorn の補題だといえる。
    • (Th 5.1) Zorn の補題：ios は極大元を持つ： 順序集合 $(a, \prec)$ について $\alpha \in a$ ならば $a$ の極大元 $\beta$ で $\alpha \prec \beta$ なるものが存在する。
      • 証明がけっこう長い。choice function を用いる議論になる。
      • TODO: キツイので後回し。
    • (Th 5.2) $(S8) \iff$ (Th 5.1)
      • 証明：$\impliedby$ が残っている。
  • §5.3 整列集合
    • テーマ：超限帰納法と整列可能定理。

      • 整列集合 (well ordered set) とは、順序集合 $(a, \prec)$ であり、次を満たすものを言う：

        \[\forall s(s \subset a \land s \ne \varnothing \implies \exists \min s).\]
        • e.g. $(\omega, \le)$ は wos だが $(\omega, \vert)$ は否。
      • コメント：wos は ios である。なぜなら $\forall x \in a \forall y \in a (\min\lbrace x, y\rbrace = x).$ と取り決めることで $x \prec y.$
      • (Th 5.3) 超限帰納法
        • コメント：数学的帰納法の wos 版と考えられる。
        • 仮定
          • $(a, \prec)$ を wos とする。
          • $P(x)$ を $x \in a$ に関する命題とする。

        • 結論

          \[\forall x \in a \forall \in y\\ (y \in s(x) \implies P(y)) \implies P(x)) \\ \implies\\ \forall x \in a (P(x)).\]
        • 証明
          • 方針は $s = \lbrace x \in a\,\mid\,\lnot P(x)\rbrace$ とおいて、$s = \varnothing$ を背理法で示す。
          • 仮に $s \ne \varnothing$ だとする。wos であることから $\exists y (y = \min s).$
            • 仮に $\exists z \in a (z \precneqq y) \implies z \notin s. \quad \therefore P(z).$ ゆえに $\forall z \in s(y) (P(z)).$
            • 本題の仮定から $y P(y)$ であるべきだが、そうなれば $y \in s$ に矛盾する。
      • (Th 5.4) 整列可能定理

        • コメント：任意の集合に対して、適当に順序を定義して wos にすることができる。 その背景は $(\Z, \le)$ は wos ではないのだが（下に有界でない部分集合を取ればいい）、元の順序を付け替えれば wos だと言い張れる。 例えば $\N \cup \lbrace -1 \rbrace$ においては次のようにすればいい：

          \[x \prec y \iff \begin{cases} x \le y, & \forall (x, y) \ne (-1, -1) \in \N \times \N,\\ y = -1, & \forall x \in \N. \end{cases}\]

          以下、$\N \cup \lbrace -1, -2\rbrace, \dotsc$ について順次同様に付け替えが存在する。

        • 証明

          1. $A = \lbrace (s, f) \in 2^a \times 2^{a\times a}\,\mid\,f \subset s \times s \land (s, f) \text{ is wos}\rbrace$ とおく。
          2. $A$ が ios であることを示す。Zorn の補題により極大元が存在するのでそれを $(\tilde s, \tilde f) \in A$ とおく。
          3. $\tilde s = a$ と示して q.e.d.

          1.: $A \ne \varnothing.$

          2.: $A$ に順序関係 $\le$ を導入する：

          \[(s, f) \le (t, g) \iff \exists x \in t (s = \{y \in t\,|\, y \prec x\} \land f \subset g \cap (s \times s)).\]

          そして $(A, \le)$ の任意の鎖 $C$ が上界をもつことを示す：

          \[\sup C = \left(\bigcup_{(s, f) \in C}s,\bigcup_{(s, f) \in C}f\right) \in A.\]

          3: $\exists x \in a\setminus\tilde s$ として矛盾を導く。

          \[\begin{aligned} \tilde t &= \tilde s \cup \{x\},\\ \tilde g &= \tilde f \cup \{\tilde t \times \{x\}\} \end{aligned}\]

          とおくと、$\displaystyle x = \max_{\tilde g} \tilde t, (\tilde t, \tilde g) \in A, (\tilde s, \tilde f) \le (\tilde t, \tilde g), (\tilde s, \tilde f) \ne (\tilde t, \tilde g).$ よって矛盾である。

      • 別項参照

      • (Th 5.5) (Th 5.4) $\iff S8)$
        • (Th 5.1 Zorn) $\implies$ (Th 5.4) を示した。
        • (Th 5.1 Zorn) $\iff (S8)$ は証明済みであるので、残るは (Th 5.4) $\implies (S8)$ だ。
        1. 集合 $a$ に対して $\bigcup a$ の元同士の順序 $\prec$ を $(\bigcup a, \prec)$ が wos となるように定める。
        2. $x \in a$ は次のようにすれば wos になる：「$\prec$ を $x \times x$ に制限する：$\prec \cap (x \times x)$」
        3. $x \ne \varnothing$ ならば $\min x$ が存在する。

        4. 次の $f$ は $a$ の choice function となる条件を満たす：

          \[f = \{(x, y) \in a \times \bigcup a\,|\, x \ne \varnothing \land y = \min x\}.\]

        別項参照

    • 最後、ここでも問題を飛ばして読み終える。