鎖(順序集合)

1：$C$ が鎖で $D\subset C$ なら、$D$ の 2 元は $C$ の 2 元でもあるので比較可能である。
2：$f(C)$ の 2 元は $f(a),f(b)$（$a,b\in C$）と書ける。$C$ は鎖なので $a\le b$ または $b\le a$ であり、$f$ が単調なので、それぞれ $f(a)\le f(b)$ または $f(b)\le f(a)$ となる。
3：$a,b\in\bigcup\mathcal{K}$ とし、$a\in C$、$b\in C'$ となる $C,C'\in\mathcal{K}$ をとる。$\mathcal{K}$ は包含について鎖なので、$C\subset C'$ または $C'\subset C$ である。前者なら $a,b$ はともに鎖 $C'$ に属し、後者ならともに鎖 $C$ に属するので、どちらの場合も比較可能である。
4：比較可能であることの条件「$a\le b$ または $b\le a$」は、$\le$ と $\ge$ を入れ替えても同じ条件である。$\square$

必要性。 $C$ が極大鎖であるとし、1〜3 のどれかが成り立たないとして矛盾を導く。いずれの場合も、$C$ に属さない元 $d$ で $C\cup\{d\}$ が鎖になるものを作る。$C\subsetneq C\cup\{d\}$ なので、これは極大性に反する。

• 1 が成り立たないとき：$d< c_0$ となる $d\in P$ がある。$d\in C$ なら $c_0$ が $C$ の最小元であることから $c_0\le d$ となり、$d< c_0$ と反対称律から矛盾する。よって $d\notin C$ である。どの $j$ についても $d< c_0\le c_j$ なので、$d$ は $C$ のすべての元と比較可能であり、$C\cup\{d\}$ は鎖である。
• 2 が成り立たないとき：双対順序で 1 の場合を考えればよい（prop-chain-basic の 4）。
• 3 が成り立たないとき：ある $i$ について $c_{i-1}< d< c_i$ となる $d\in P$ がある。$j\le i-1$ なら $c_j\le c_{i-1}< d$、$j\ge i$ なら $d< c_i\le c_j$ なので、$d$ はどの $c_j$ とも異なり（$d\notin C$）、どの $c_j$ とも比較可能である。よって $C\cup\{d\}$ は鎖である。

十分性。 1〜3 が成り立つとし、$C\subsetneq C'$ となる鎖 $C'$ があったとする。$d\in C'\setminus C$ をとる。$d$ は各 $c_j$ と比較可能で、$d\ne c_j$ なので、各 $j$ について $d< c_j$ または $c_j< d$ のちょうど一方が成り立つ。

• $d< c_0$ なら 1 に反する。よって $c_0< d$ である。
• $c_k< d$ なら 2 に反する。よって $d< c_k$ である。
• $d< c_j$ となる $j$ のうち最小のものを $i$ とする（$j=k$ がこの条件を満たすので $i$ は存在し、$c_0< d$ より $i\ge1$ である）。$i$ の最小性から $d< c_{i-1}$ ではないので $c_{i-1}< d$ である。すると $c_{i-1}< d< c_i$ となり、3 に反する。
  したがってそのような $C'$ はなく、$C$ は極大鎖である。

極大鎖の存在。 $D$ を $P$ の鎖とする。$P$ は有限なので、$D$ を含む $P$ の鎖は有限個しかなく、$D$ 自身がその 1 つである。その中で元の個数が最大のもの $C$ をとる。$C\subsetneq C'$ となる鎖 $C'$ があれば、$C'$ も $D$ を含み、元の個数が $C$ より多いので、$C$ の選び方に反する。よって $C$ は $D$ を含む極大鎖である。$P\ne\emptyset$ なら、$a\in P$ について $\emptyset\subsetneq\{a\}$ であり $\{a\}$ は鎖なので、$\emptyset$ は極大鎖でない。$\square$

1：$A\subsetneq B$ で $B\setminus A$ が 2 個以上の元をもつとき、$b\in B\setminus A$ を 1 つとると $A\subsetneq A\cup\{b\}\subsetneq B$ なので、$B$ は $A$ を被覆しない。$B\setminus A=\{b\}$ のとき、$A\subsetneq D\subset B$ となる $D$ をとると、$D\setminus A$ は $B\setminus A=\{b\}$ の空でない部分集合なので $\{b\}$ であり、$D=A\cup\{b\}=B$ となる。よって $A< D< B$ となる $D$ はなく、$A\lessdot B$ である。
2：$\mathcal{P}(X)$ の極小元は最小元 $\emptyset$ だけであり、極大元は最大元 $X$ だけである。$X\ne\emptyset$ のとき、thm-chain-maximal-finite により、極大鎖は $\emptyset$ から始まり $X$ で終わり、隣り合う 2 つが被覆の関係にある鎖である。1 により、1 段上がるごとに元がちょうど 1 個増えるので、$\lvert S_i\rvert=i$ であり、段数は $\lvert X\rvert-\lvert\emptyset\rvert=n$ である。$X=\emptyset$ のときは $\mathcal{P}(X)=\{\emptyset\}$ で、極大鎖は $\{\emptyset\}$ だけであり、主張は $n=0$ の場合として成り立つ。
3：並べ方 $(a_1,\dots,a_n)$ から作った $S_0\subsetneq\cdots\subsetneq S_n$ は、$S_0=\emptyset$、$S_n=X$ で、$S_i\setminus S_{i-1}=\{a_i\}$ なので、1 と thm-chain-maximal-finite により極大鎖である。逆に、2 の形の極大鎖に対し、$S_i\setminus S_{i-1}$ のただ 1 つの元を $a_i$ とおく。$i< j$ なら $a_i\in S_i\subset S_{j-1}$、$a_j\notin S_{j-1}$ なので $a_i\ne a_j$ であり、$\{a_1,\dots,a_n\}=S_n=X$ なので、$(a_1,\dots,a_n)$ は $X$ の並べ方である。帰納法で $S_i=\{a_1,\dots,a_i\}$ が分かるので、2 つの対応は互いに逆である。$n$ 個の元の並べ方は $n!$ 通りある（階乗）ので、極大鎖は $n!$ 本である。$\square$

$F=\emptyset$ なら、$\mathcal{C}$ の元を 1 つとればよい。$F=\{x_1,\dots,x_m\}$（$m\ge1$）とする。各 $i$ について、$x_i\in\bigcup\mathcal{C}$ なので $x_i\in C_i$ となる $C_i\in\mathcal{C}$ がある（有限個の選び方なので、選択公理は要らない）。$\{C_1,\dots,C_m\}$ は鎖 $\mathcal{C}$ の空でない有限部分集合であり、prop-chain-basic の 1 により包含について鎖、すなわち全順序集合である。全順序 の記事の命題「有限な全順序集合の整列性」により、その中に包含について最大のもの $C_j$ がある。各 $i$ について $x_i\in C_i\subset C_j$ なので、$F\subset C_j$ である。$\square$

1：$U:=\bigcup\mathcal{C}$ とおく。$\mathcal{C}$ は空でないので、その元 $H$ をとると単位元 $e$ は $H$ に属し、$e\in U$ である。$x,y\in U$ とすると、lem-chain-finite-subset を $F=\{x,y\}$ に当てて、$x,y\in H'$ となる $H'\in\mathcal{C}$ がある。$H'$ は部分群なので $xy^{-1}\in H'\subset U$ である。よって $U$ は部分群である。
2：ベクトルの集合 $S$ が線形独立であるとは、$S$ の相異なる有限個の元 $v_1,\dots,v_m$ と $\lambda_1,\dots,\lambda_m\in K$ について $\lambda_1v_1+\cdots+\lambda_mv_m=0$ ならばすべての $\lambda_i$ が $0$ であること、すなわち $S$ のどの有限部分集合も線形独立であることである。$\bigcup\mathcal{C}$ の有限部分集合 $F$ をとると、lem-chain-finite-subset により $F\subset C$ となる $C\in\mathcal{C}$ があり、$C$ は線形独立なのでその部分集合 $F$ も線形独立である。$\square$

1：有理数全体 $\mathbb{Q}$ は可算無限集合なので（有理数 の記事の命題「有理数全体は可算無限集合である」）、全単射 $q\colon\mathbb{N}\to\mathbb{Q}$ がある。実数 $r$ ごとに
$$ S_r:=\{n\in\mathbb{N}\mid q(n)< r\} $$
とおく。$r< s$ とすると、$q(n)< r$ なら $q(n)< s$ なので $S_r\subset S_s$ である。さらに $r< t< s$ となる有理数 $t$ がある（有理数 の記事の定理「実数内での稠密性」）ので、$t=q(n)$ となる $n$ をとると $n\in S_s\setminus S_r$ であり、$S_r\subsetneq S_s$ となる。したがって $r\mapsto S_r$ は単射であり、$\{S_r\mid r\in\mathbb{R}\}$ の 2 元 $S_r,S_s$ は、$r\le s$ か $s\le r$ に応じて $S_r\subset S_s$ か $S_s\subset S_r$ となって比較可能である。よってこれは鎖であり、$\mathbb{R}$ と一対一に対応するので、非可算個の元からなる（可算集合 の記事の定理「実数全体の非可算性」）。
2：$W$ を、包含について整列している $\mathcal{P}(\mathbb{N})$ の鎖とする。$W$ の最大元（包含について最大の元）があればそれを除いた集合を、なければ $W$ 自身を $W'$ とおく。$S\in W'$ をとると、$S$ は $W$ の最大元でないので、$S\subsetneq T$ となる $T\in W$ がある（$W$ は鎖なので、$S$ と比較可能で $S$ に含まれない元 $T$ は $S$ を真に含む）。そこで
$$ S^{+}:=\{T\in W\mid S\subsetneq T\}\ \text{の包含についての最小元} $$
とおく（$W$ が整列しているので存在する）。$S^{+}\setminus S$ は $\mathbb{N}$ の空でない部分集合なので、自然数の大小について最小元をもつ。それを $g(S)$ とおく。
$g\colon W'\to\mathbb{N}$ が単射であることを示す。$S,S'\in W'$、$S\ne S'$ とする。$W$ は鎖なので、必要なら入れ替えて $S\subsetneq S'$ としてよい。すると $S'$ は $\{T\in W\mid S\subsetneq T\}$ の元なので、その最小元 $S^{+}$ について $S^{+}\subset S'$ である。よって $g(S)\in S^{+}\subset S'$ である。一方 $g(S')\in S'^{+}\setminus S'$ なので $g(S')\notin S'$ である。したがって $g(S)\ne g(S')$ である。
$\mathbb{N}$ への単射があるので $W'$ は高々可算であり（可算集合 の記事の命題「単射・全射による特徴づけ」）、$W$ は $W'$ に高々 1 元を加えた集合なので高々可算である。$\square$