選択公理⇔連結グラフは全域木をもつ

選択公理

387

選択公理が「すべての連結グラフは全域木をもつ」ことと同値であることを示します．グラフについては自分は詳しくないので，間違いがあればご指摘ください．

$V$ を頂点の集合， $E$ を辺の集合とし，写像 $ϕ : E \to P (V)$ が任意の $e \in E$ に対し $ϕ (e)$ の濃度が $1$ または $2$ であるとする．このとき三つ組 $G = (V, E, ϕ)$ をグラフという．また $V = vert (G), E = edge (G)$ と表す．
グラフ $G^{'} = (V^{'}, E^{'}, ϕ^{'})$ が $V^{'} \subset V, E^{'} \subset E, ϕ^{'} = ϕ |_{E^{'}}$ を満たすとき， $G^{'}$ を $G$ の部分グラフという．
$v, v^{'} \in V$ に対し，頂点の列 $v = v_{0}, v_{1}, \dots, v_{n} = v^{'}$ と辺の列 $e_{0}, \dots, e_{n - 1}$ が存在して $ϕ (e_{i}) = {v_{i}, v_{i + 1}} (0 \leq i \leq n - 1)$ を満たすとき， $v$ を始点とし $v^{'}$ を終点とする道が存在するという．
任意の $v, v^{'} \in V$ に対し， $v$ を始点とし $v^{'}$ を終点とする道が存在する道が存在するとき， $G$ は連結であるとする．
始点と終点が一致する道をサイクルという．
$G$ がサイクルをもたない連結グラフであるとき， $G$ は木であるという．
部分集合 $E^{'} \subset E$ が存在して， $T = (V, E^{'}, ϕ |_{E^{'}})$ が木となるとき， $T$ を全域木という．

次は同値である．

選択公理
すべての連結グラフは全域木をもつ．

⟹

$G = (V, E, ϕ)$ を連結グラフとする． $T = {(V^{'}, E^{'}, ϕ^{'}) ∣ (V^{'}, E^{'}, ϕ^{'})$ は $G$ の部分グラフであり，木である $}$ と定める．また， $T$ 上の二項関係 $⪯$ を部分グラフであることにより定めると， $(T, ⪯)$ は半順序集合になる．これが帰納的であることを示す． $C$ を任意の $T$ の鎖とする． $T_{0} = (⋃_{T \in C} vert (T), ⋃_{T \in C} edge (T), ϕ |_{⋃_{T \in C} edge (T)})$ とおく．任意に $v, v^{'} \in T_{0}$ をとるとき， $C$ が鎖であることからある $(V_{1}, E_{1}, ϕ_{1}) \in C$ が存在して $v, v^{'} \in V_{1}$ となる．ゆえに $v$ を始点とし $v^{'}$ を終点とする道が存在する．また，もし $v$ を通るサイクルが存在するとき，そのサイクルを含むような $(V_{2}, E_{2}, ϕ_{2}) \in C$ が存在することになり矛盾が生じる．よって $T_{0}$ は連結かつサイクルをもたないことから，木である．よって， $T_{0}$ は $C$ の上界である．したがって，Zornの補題より $T$ は極大元 $T$ をもつ．もし， $T$ が $G$ の全域木でないとすると，ある $w, w^{'} \in V$ が存在して， $w$ を始点とし $w^{'}$ を終点とする道は $T$ に存在しない．他方 $G$ は連結であるので， $w$ を始点とし $w^{'}$ を終点とする道は $G$ には存在するので，この道を含むように $T$ を拡大したものを $T^{'}$ とすれば，これは $T ≺ T^{'}$ を満たすので， $T$ の極大性に反する．よって， $G$ の全域木 $T$ の存在が示された．

⟹

$(X_{λ})_{λ \in Λ}$ を空でない集合からなる族とする．グラフ $G = (V, E, ϕ)$ を，
$\begin{aligned} V & = {∙} \cup {◯_{λ} ∣ λ \in Λ} \cup {◻_{λ} ∣ λ \in Λ} \cup (⋃_{λ \in Λ} ({λ} \times X_{λ})) \\ E & = ⋃_{λ \in Λ} ({a_{λ}} \cup {b_{λ, x} ∣ x \in X_{λ}} \cup {c_{λ, x} ∣ x \in X_{λ}}) \end{aligned}$
とし(未定義の文字はすべて異なる)，
$ϕ (a_{λ}) = {∙, ◯_{λ}}, ϕ (b_{λ, x}) = {◯_{λ}, (λ, x)}, ϕ (c_{λ, x}) = {(λ, x), ◻_{λ}}$
で定める．
Gのイメージ
$G$ は連結グラフである．よって全域木 $T = (V, E^{'}, ϕ |_{E^{'}})$ が存在する． $T$ の連結性より，任意の $λ \in Λ$ に対し $◯_{λ}$ を始点とし $◻_{λ}$ が終点となる道が存在し， $T$ がサイクルを持たないことからこれは一意に定まる．すなわち， $b_{λ, x_{λ}}, c_{λ, x_{λ}} \in E^{'}$ を満たす $x_{λ} \in X_{λ}$ が一意に定まる．
Tのイメージ
このとき， $(x_{λ})_{λ \in Λ} \in \prod_{λ \in Λ} X_{λ}$ であるから， $\prod_{λ \in Λ} X_{λ}$ は空でない．