マトロイド閉包作用素の単一公理

ふと，群を単一の公理で特徴づけるという話があったことを思い出し， ^{脚注¹私が知ったきっかけは， alg-d氏のYouTube動画『1つの等式で群を定義する』 で，そこでの文献は Neumann [Neu81] でした． 詳しく知りたい方は，alg-d氏のPDFを参照ください． 群の単一公理については Kunen [Kun92]， McCune [McC93] など，広く研究されているようです．1} マトロイドも単一の公理で書けないかという疑問を抱きました． といっても，基族の公理は実質単一の公理で書けているので，他の公理に目を向けることにしました．

マトロイドは Whitney [Whi35] によって， 線形従属性の抽象的性質を捉える対象として導入されました． 標準的な文献としては Welsh [Wel76]， White [Whi86]，Oxley [Oxl11] などを参照してください．

マトロイドには同値な定義が数多く存在することが知られていますが， その中に「閉包作用素」の公理があります． 他分野の方が「閉包作用素」と聞くと，真っ先に位相空間論における閉包作用素が思い浮かぶかもしれません． 位相的閉包とマトロイドの閉包は，いずれも 「与えられた集合に対して，そこから必然的に付随する点をすべて加える」 という意味で閉包作用素の例です． ただし，位相空間では「近さ」や「極限」によって付随する点が決まり， マトロイド，特に線形マトロイドでは「線形生成」によって付随する点が決まります． したがって，両者は同じ抽象的な語彙で記述できる一方で， 追加で要求される公理は異なります． 位相空間は閉包作用素で特徴づけることもでき，それがKuratowskiの公理です． 調べてみると，Kuratowski の4公理を1本の条件で表す試みは古くからあり， Monteiro [Mon45] ^{脚注²厳密には Monteiro [Mon45] は (KCL1) を 除いた (KCL2)–(KCL4) を導く単一公理を与えています．2}や Pervin [Per64] が 閉包作用素の単一公理化を扱っています． そこで，マトロイドの閉包作用素の公理も単一の公理で書けないか？と考えてみたメモが本ノートです．

というわけで，本題に入る前にPervin [Per64]による 位相空間の閉包作用素の単一公理の話を先にします．

私は位相空間論の専門家ではないですが， 位相空間における閉包 $c(A)$ は， 「$A$ に限りなく近づいてくる点をすべて加えた集合」 であると理解しています． 点 $x \in X$ が $c(A)$ に属するとは， $x$ の任意の近傍が $A$ と交わることを意味します． つまり，$x$ 自身が $A$ に入っていなくても， $x$ のまわりをどれだけ小さく見ても $A$ の点が見えてしまうなら， $x$ は $A$ の閉包に入る，という解釈です．

この意味で，閉包 $c(A)$ は 「任意の近傍が $A$ と交わる点，すなわち $A$ に触れている点をすべて集める操作」 と考えることができます． たとえば実数直線 $\mathbb{R}$ では， 開区間 $(0,1)$ の閉包は $[0,1]$ です． 端点である $0$ と $1$ はもとの集合には含まれていませんが， どれだけ小さい近傍を取っても $(0,1)$ と交わるため， 閉包には含まれます．

さて，そんな閉包作用素のKuratowski [Kur22]による公理は次のような形でした：

これら4つの公理は，位相的閉包が満たすべき性質を抽象化したものです． 一応直観的な解釈を記しておきます．

(KCL1)$c(\emptyset) = \emptyset$(KCL1) 空集合保存

空集合には近づきようがないので，空集合の閉包は空集合である． 近傍が空集合と交わる点は存在しない，ということである．

(KCL2)任意の $A \subseteq X$ に対して，$A \subseteq c(A)$ (拡大性, extensibility)(KCL2) 拡大性

$A$ の点は，当然 $A$ の閉包に含まれる． 閉包とは $A$ を削る操作ではなく，$A$ に必要な点を加える操作である．

(KCL3)任意の $A \subseteq X$ に対して，$c(c(A)) = c(A)$ (べき等性, idempotency)(KCL3) べき等性

一度すべての極限点を加えて閉じた集合にしたなら， もう一度閉包を取っても新しい点は現れない． すなわち，閉包を取る操作は「閉じるまで補う」操作であり， 閉じた後にさらに閉じ直しても変化しない．

(KCL4)任意の $A, B \subseteq X$ に対して，$c(A \cup B) = c(A) \cup c(B)$ (合併保存, union-preserving)(KCL4) 合併保存

有限個の集合の合併に近づける点は， それぞれの集合のどちらかに近づける点である． 特に2つの集合については， $A \cup B$ の閉包は $A$ の閉包と $B$ の閉包の合併になる． これは，近傍が $A \cup B$ と交わるという条件が， 近傍が $A$ と交わる，または $B$ と交わる，という条件に分解できることを反映している． より正確には，$x \notin c(A)$ かつ $x \notin c(B)$ とすると， $A$ と交わらない $x$ の近傍 $U$ と， $B$ と交わらない $x$ の近傍 $V$ が取れる． このとき $U \cap V$ は再び $x$ の近傍であり， しかも $A \cup B$ と交わらない． したがって $x \notin c(A \cup B)$ である． これにより $c(A \cup B) \subseteq c(A) \cup c(B)$ が従う． 逆包含は単調性から従う．

注意すべき点として，最後の合併保存は有限合併についての性質です． 無限合併については，一般には

とは限りません． たとえば $\mathbb{R}$ において $A_{n} = \{ 1/n \}$ とすると， 各 $A_{n}$ は閉集合ですが， $\bigcup_{n \geq 1} A_{n}$ の閉包には新たに $0$ が加わります．

Kuratowskiによるこれら4つの条件は，Pervinによって以下のように単一の条件にまとめられました：

証明

(必要性) $c$ がKuratowskiの閉包作用素ならば，(P)$\forall A, B \subseteq X, \, A \cup c(A) \cup c(c(B)) = c(A \cup B) \setminus c(\emptyset)$.(P) が成り立つ．

$A, B \subseteq X$ を任意に取る． 空集合保存則 (KCL1)$c(\emptyset) = \emptyset$(KCL1) より $c(\emptyset) = \emptyset$ であるから，

$$c(A \cup B) \setminus c(\emptyset) = c(A \cup B).$$

また拡大性 (KCL2)任意の $A \subseteq X$ に対して，$A \subseteq c(A)$ (拡大性, extensibility)(KCL2) より $A \subseteq c(A)$ であり， べき等性 (KCL3)任意の $A \subseteq X$ に対して，$c(c(A)) = c(A)$ (べき等性, idempotency)(KCL3) より $c(c(B)) = c(B)$ である． したがって

$$A \cup c(A) \cup c(c(B)) = c(A) \cup c(B).$$

合併保存則 (KCL4)任意の $A, B \subseteq X$ に対して，$c(A \cup B) = c(A) \cup c(B)$ (合併保存, union-preserving)(KCL4) より

$$c(A) \cup c(B) = c(A \cup B)$$

である．以上を合わせて

$$A \cup c(A) \cup c(c(B)) = c(A \cup B) \setminus c(\emptyset)$$

が得られる．ゆえに (P)$\forall A, B \subseteq X, \, A \cup c(A) \cup c(c(B)) = c(A \cup B) \setminus c(\emptyset)$.(P) が成り立つ．

(十分性) $c$ が (P)$\forall A, B \subseteq X, \, A \cup c(A) \cup c(c(B)) = c(A \cup B) \setminus c(\emptyset)$.(P) を満たすならば，$c$ はKuratowskiの閉包作用素である．

(KCL1)$c(\emptyset) = \emptyset$(KCL1)–(KCL4)任意の $A, B \subseteq X$ に対して，$c(A \cup B) = c(A) \cup c(B)$ (合併保存, union-preserving)(KCL4) が成り立つことを示せばよい．

空集合保存 (KCL1)$c(\emptyset) = \emptyset$(KCL1) が成り立つこと

(P)$\forall A, B \subseteq X, \, A \cup c(A) \cup c(c(B)) = c(A \cup B) \setminus c(\emptyset)$.(P) において $A = B = \emptyset$ と置くと，

$$\emptyset \cup c(\emptyset) \cup c(c(\emptyset)) = c(\emptyset) \setminus c(\emptyset) = \emptyset$$

である．左辺は $c(\emptyset) \cup c(c(\emptyset))$ であるから，

$$c(\emptyset) \cup c(c(\emptyset)) = \emptyset.$$

特に $c(\emptyset) \subseteq \emptyset$ である．また $\emptyset \subseteq c(\emptyset)$ は常に成り立つので，

$$c(\emptyset) = \emptyset$$

が得られる．

拡大性 (KCL2)任意の $A \subseteq X$ に対して，$A \subseteq c(A)$ (拡大性, extensibility)(KCL2) が成り立つこと

$A \subseteq X$ を任意に取る． (P)$\forall A, B \subseteq X, \, A \cup c(A) \cup c(c(B)) = c(A \cup B) \setminus c(\emptyset)$.(P) において $B = \emptyset$ と置くと，

$$A \cup c(A) \cup c(c(\emptyset)) = c(A) \setminus c(\emptyset).$$

すでに $c(\emptyset) = \emptyset$ が示されているので， $c(c(\emptyset)) = c(\emptyset) = \emptyset$ であり，

$$A \cup c(A) = c(A)$$

を得る．したがって $A \subseteq c(A)$ である．

べき等性 (KCL3)任意の $A \subseteq X$ に対して，$c(c(A)) = c(A)$ (べき等性, idempotency)(KCL3) が成り立つこと

$B \subseteq X$ を任意に取る． (P)$\forall A, B \subseteq X, \, A \cup c(A) \cup c(c(B)) = c(A \cup B) \setminus c(\emptyset)$.(P) において $A = \emptyset$ と置くと，

$$\emptyset \cup c(\emptyset) \cup c(c(B)) = c(B) \setminus c(\emptyset).$$

すでに $c(\emptyset) = \emptyset$ が示されているので，

$$c(c(B)) = c(B)$$

を得る．したがって任意の $B \subseteq X$ に対して $c(c(B)) = c(B)$ である．

合併保存 (KCL4)任意の $A, B \subseteq X$ に対して，$c(A \cup B) = c(A) \cup c(B)$ (合併保存, union-preserving)(KCL4) が成り立つこと

$A, B \subseteq X$ を任意に取る． (P)$\forall A, B \subseteq X, \, A \cup c(A) \cup c(c(B)) = c(A \cup B) \setminus c(\emptyset)$.(P) より

$$A \cup c(A) \cup c(c(B)) = c(A \cup B) \setminus c(\emptyset)$$

である．すでに $c(\emptyset) = \emptyset$，$A \subseteq c(A)$， $c(c(B)) = c(B)$ が示されているので，左辺は $c(A) \cup c(B)$ に等しく， 右辺は $c(A \cup B)$ に等しい．ゆえに

$$c(A) \cup c(B) = c(A \cup B)$$

であり，合併保存 (KCL4)任意の $A, B \subseteq X$ に対して，$c(A \cup B) = c(A) \cup c(B)$ (合併保存, union-preserving)(KCL4) が成り立つ．

以上により，$c$ はKuratowskiの閉包作用素である．

証明終わり□

Pervin の単一公理は，一見するとかなり人工的な式に見えますが， この式は Kuratowski の4公理を1本の等式の中に埋め込んだものと見ることができます． このように，Pervin の単一公理は， 「空集合が余計な点を生成しないこと」， 「集合は自分自身を含むこと」， 「閉包を二度取っても変わらないこと」， 「有限合併と閉包が両立すること」 を，一つの等式で同時に要求していると解釈できます．

マトロイドの閉包作用素を理解するうえでは， 線形マトロイドを念頭に置くと分かりやすいので， （マトロイドという用語をまだ導入していませんが）軽く説明しておきます． 有限集合 $E$ で添字付けられたベクトル族 $(v_e)_{e \in E}$ を考える． $A \subseteq E$ に対して

と定めます． つまり，$\cl(A)$ は 「$A$ のベクトルたちから線形結合で生成できる $E$ の元全体」 です． このようにして得られるマトロイドを線形マトロイド (linear matroid) といいます． 線形従属性を抽象化するというこの視点は， マトロイドの出発点である Whitney [Whi35] に遡ります． 線形マトロイドを含む基本例については Oxley [Oxl11, Chap. 1] をご参照ください．

線形マトロイドの場合，$a \in \cl(A)$ とは， $a$ に対応するベクトル $v_{a}$ が $\{ v_{x} : x \in A \}$ の張る部分空間の中に入っていることを意味します． したがって，マトロイドにおける閉包は， 位相的な意味での「極限点を加える操作」ではなく， 線形代数的な意味での 「すでに $A$ から生成できる元をすべて加える操作」 と考えられます．

さて，マトロイドを閉包作用素の公理で定義する方法は次のような形でした：

位相的閉包と異なり，マトロイド閉包では一般に $\cl(\emptyset) = \emptyset$ は要求されません． たとえば線形マトロイドでは，零ベクトルに対応する元は 空集合からすでに生成できるため，$\cl(\emptyset)$ に属します． マトロイドではこのような元をループ (loop) といいます．

線形マトロイドの例を念頭に置くと，マトロイド閉包作用素の公理は次のように理解できます．

(MCL1)任意の $A \subseteq E$ に対して，$A \subseteq \cl(A)$ (拡大性, extensibility)(MCL1) 拡大性

$A$ の各元は，当然 $A$ 自身によって生成できる． したがって

$$A \subseteq E \cap \span \{ v_{a} : a \in A \} = \cl(A)$$

である． 閉包は，もとの集合 $A$ から生成できる元を加える操作なので， $A$ の元を失うことはない．

(MCL2)任意の $A \subseteq B \subseteq E$ に対して，$\cl(A) \subseteq \cl(B)$ (単調性, monotonicity)(MCL2) 単調性

$A \subseteq B$ ならば，$A$ で作れるベクトルはすべて $B$ でも作れる． したがって

$$\span \{ v_{a} : a \in A \} \subseteq \span \{ v_{b} : b \in B \}$$

であり，$\cl(A)\subseteq \cl(B)$ が成り立つ． 生成に使える元を増やしても，生成できる元が減ることはない，という性質である．

(MCL3)任意の $A \subseteq E$ に対して，$\cl(\cl(A)) = \cl(A)$ (べき等性, idempotency)(MCL3) べき等性

$\cl(A)$ は，すでに $A$ から生成できる元をすべて集めた集合である． したがって，$\cl(A)$ の元を改めて生成元として加えても， 張られる部分空間は変わらない． すなわち

$$\span \{ v_{a} : a \in \cl(A) \} = \span \{ v_{a} : a \in A \}$$

であり，$\cl(\cl(A))=\cl(A)$ となる． これは「すでに生成できるものを追加しても，生成能力は増えない」 という事実を表している．

(MCL4)任意の $A \subseteq E$, $e \in E$, $a \in \cl(A \cup \{ e \}) \setminus \cl(A)$ に対して，$e \in \cl(A \cup \{ a \})$ (Mac Lane–Steinitz 交換律, Mac Lane–Steinitz exchange property) (MCL4) Mac Lane–Steinitz 交換律

交換律は，線形代数における「従属関係の対称性」を抽象化したものである． いま $a \in \cl(A \cup \{ e \}) \setminus \cl(A)$ とする． 線形マトロイドで考えると，これは $v_{a}$ は $A$ に対応するベクトルたちと $v_{e}$ を使えば生成できるが， $A$ だけでは生成できない，という意味である． したがって，ある $w \in \span\{ v_{x} \mathrel{:} x \in A \}$ とスカラー $\lambda$ によって

$$v_{a} = w + \lambda v_{e}$$

と書ける．ここで $\lambda = 0$ なら $v_{a} \in \span\{ v_{x} \mathrel{:} x \in A \}$ となり， $a \in \cl(A)$ に反する．よって $\lambda \neq 0$ である． したがって

$$v_{e} = \lambda^{-1}(v_{a} - w)$$

であり，$e \in \cl(A \cup \{ a \})$ が従う．

つまり交換律は， 「$e$ を加えることで初めて $a$ が生成できるようになったなら， 逆に $a$ を加えれば $e$ も生成できる」 という性質である．

証明

(必要性) $M = (E, \cl)$ がマトロイドならば，(MCL)$\forall A \subseteq E,\ \forall e \in E, \, \cl(A \cup \{ e \}) = \cl(A) \cup \{ e \} \cup \{ x \in E \mathrel{:} e \in \cl(A \cup \{ x \}) \setminus \cl(A) \}$.(MCL) が成り立つ．

(MCL)$\forall A \subseteq E,\ \forall e \in E, \, \cl(A \cup \{ e \}) = \cl(A) \cup \{ e \} \cup \{ x \in E \mathrel{:} e \in \cl(A \cup \{ x \}) \setminus \cl(A) \}$.(MCL) の両側の包含関係を示す．

($\supseteq$)

$\cl(A) \subseteq \cl(A \cup \{ e \})$ は単調性 (MCL2)任意の $A \subseteq B \subseteq E$ に対して，$\cl(A) \subseteq \cl(B)$ (単調性, monotonicity)(MCL2) から従う． また $e \in \cl(A \cup \{ e \})$ は拡大性 (MCL1)任意の $A \subseteq E$ に対して，$A \subseteq \cl(A)$ (拡大性, extensibility)(MCL1) から従う． さらに， $b \in \{ a \in E \mathrel{:} e \in \cl(A \cup \{ a \}) \setminus \cl(A) \}$ とする．このとき $e \in \cl(A \cup \{ b \}) \setminus \cl(A)$である． Mac Lane–Steinitz交換律 (MCL4)任意の $A \subseteq E$, $e \in E$, $a \in \cl(A \cup \{ e \}) \setminus \cl(A)$ に対して，$e \in \cl(A \cup \{ a \})$ (Mac Lane–Steinitz 交換律, Mac Lane–Steinitz exchange property) (MCL4) を $A$, 元 $b$, 元 $e$ に適用すると， $b \in \cl(A \cup \{ e \})$を得る． したがって右辺の第3項も $\cl(A \cup \{ e \})$ に含まれ， $\cl(A \cup \{ e \}) \supseteq \cl(A) \cup \{ e \} \cup \{ a \in E \mathrel{:} e \in \cl(A \cup \{ a \}) \setminus \cl(A) \}$ が示された．

($\subseteq$)

$a \in \cl(A \cup \{ e \})$ を任意に取る． もし $a \in \cl(A) \cup \{ e \}$ なら右辺に入る． そうでない場合，つまり $a \notin \cl(A)$ かつ $a \ne e$ ならば， $e \notin \cl(A)$ である． 実際，もし $e \in \cl(A)$ と仮定すると， 拡大性 $A \subseteq \cl(A)$ の両辺に $e$ を加えることで $A \cup \{ e \} \subseteq \cl(A) \cup \{ e \} = \cl(A)$ となる．このとき，単調性とべき等性より

$$\cl(A \cup \{ e \}) \subseteq \cl(\cl(A))=\cl(A)$$

であり，逆包含は単調性から従うので $\cl(A \cup \{ e \}) = \cl(A)$ となる． これは $a \in \cl(A \cup \{ e \}) \setminus \cl(A)$ に反する． したがって確かに $e \notin \cl(A)$ である． さらに，Mac Lane–Steinitz交換律 (MCL4)任意の $A \subseteq E$, $e \in E$, $a \in \cl(A \cup \{ e \}) \setminus \cl(A)$ に対して，$e \in \cl(A \cup \{ a \})$ (Mac Lane–Steinitz 交換律, Mac Lane–Steinitz exchange property) (MCL4) より $e \in \cl(A \cup \{ a \})$ だから，

$$e \in \cl(A\cup\{a\}) \setminus \cl(A)$$

が得られる． したがって $a$ は右辺の集合

$$\{ a \in E \mathrel{:} e \in \cl(A \cup \{ a \}) \setminus \cl(A)\}$$

に入り， $\cl(A \cup \{ e \}) \subseteq \cl(A) \cup \{ e \} \cup \{ a \in E \mathrel{:} e \in \cl(A \cup \{ a \}) \setminus \cl(A) \}$ が示された．

以上により， (MCL)$\forall A \subseteq E,\ \forall e \in E, \, \cl(A \cup \{ e \}) = \cl(A) \cup \{ e \} \cup \{ x \in E \mathrel{:} e \in \cl(A \cup \{ x \}) \setminus \cl(A) \}$.(MCL) が成り立つ．

(十分性) $M = (E, \cl)$ が (MCL)$\forall A \subseteq E,\ \forall e \in E, \, \cl(A \cup \{ e \}) = \cl(A) \cup \{ e \} \cup \{ x \in E \mathrel{:} e \in \cl(A \cup \{ x \}) \setminus \cl(A) \}$.(MCL) を満たすならば， $M$ はマトロイドである．

(MCL1)任意の $A \subseteq E$ に対して，$A \subseteq \cl(A)$ (拡大性, extensibility)(MCL1)–(MCL4)任意の $A \subseteq E$, $e \in E$, $a \in \cl(A \cup \{ e \}) \setminus \cl(A)$ に対して，$e \in \cl(A \cup \{ a \})$ (Mac Lane–Steinitz 交換律, Mac Lane–Steinitz exchange property) (MCL4) が成り立つことを示せばよい．

拡大性 (MCL1)任意の $A \subseteq E$ に対して，$A \subseteq \cl(A)$ (拡大性, extensibility)(MCL1) が成り立つこと

$A \subseteq E$ と $a \in A$ を任意に取る． $A^{\prime} \coloneqq A \setminus \{ a \}$ と置く． 単一公理を $A^{\prime}$ と $a$ に適用すると，

$$\cl(A) = \cl(A^{\prime} \cup \{ a \}) = \cl(A^{\prime}) \cup \{ a \} \cup \{ x \in E \mathrel{:} a\in \cl(A^{\prime} \cup \{ x \}) \setminus \cl(A^{\prime})\}.$$

したがって右辺に $a$ が含まれるので，$a\in\cl(A)$ であり， $A \subseteq \cl(A)$ が示された．

単調性 (MCL2)任意の $A \subseteq B \subseteq E$ に対して，$\cl(A) \subseteq \cl(B)$ (単調性, monotonicity)(MCL2) が成り立つこと

(MCL)$\forall A \subseteq E,\ \forall e \in E, \, \cl(A \cup \{ e \}) = \cl(A) \cup \{ e \} \cup \{ x \in E \mathrel{:} e \in \cl(A \cup \{ x \}) \setminus \cl(A) \}$.(MCL) の右辺には常に $\cl(A)$ が含まれるため， $\cl(A) \subseteq \cl(A \cup \{ e \})$ が常に成り立つ． $E$ は有限であるから，$A \subseteq B$ のとき $B \setminus A$ の元を1つずつ加えていけば， $\cl(A) \subseteq \cl(B)$ が得られる．

べき等性 (MCL3)任意の $A \subseteq E$ に対して，$\cl(\cl(A)) = \cl(A)$ (べき等性, idempotency)(MCL3) が成り立つこと

拡大性より $A \subseteq \cl(A)$ である． $E$ は有限なので，

$$\cl(A) \setminus A = \{ e_{1}, \dots, e_{n} \}$$

と書ける． $A_{0} \coloneqq A$，$A_{i} \coloneqq A_{i-1} \cup \{ e_{i} \}$ と置く． 単調性より $\cl(A) \subseteq \cl(A_{i-1})$ であるから， 特に $e_{i} \in \cl(A_{i-1})$ である． ここで (MCL)$\forall A \subseteq E,\ \forall e \in E, \, \cl(A \cup \{ e \}) = \cl(A) \cup \{ e \} \cup \{ x \in E \mathrel{:} e \in \cl(A \cup \{ x \}) \setminus \cl(A) \}$.(MCL) より，

$$\tag{*} \cl(A_{i-1} \cup \{ e_{i} \}) = \cl(A_{i-1}) \cup \{ e_{i} \} \cup \{ a \in E : e_{i} \in \cl(A_{i-1} \cup \{ a \}) \setminus \cl(A_{i-1})\}.$$

であるが，いま $e_{i} \in \cl(A_{i-1})$ であるから， 右辺の第2項 $\{ e_{i} \}$ はすでに $\cl(A_{i-1})$ に含まれる． また任意の $a \in E$ について， $e_{i} \in \cl(A_{i-1})$ であるため

$$e_{i} \notin \cl(A_{i-1} \cup \{ a \}) \setminus \cl(A_{i-1})$$

である．したがって第3項は空集合であり，

$$\cl(A_{i}) = \cl(A_{i-1} \cup \{ e_{i} \}) = \cl(A_{i-1})$$

を得る． 帰納的に

$$\cl(\cl(A)) = \cl(A_{n}) = \cl(A_{0}) = \cl(A)$$

を得る．

Mac Lane–Steinitz 交換律 (MCL4)任意の $A \subseteq E$, $e \in E$, $a \in \cl(A \cup \{ e \}) \setminus \cl(A)$ に対して，$e \in \cl(A \cup \{ a \})$ (Mac Lane–Steinitz 交換律, Mac Lane–Steinitz exchange property) (MCL4) が成り立つこと

$A \subseteq E$, $e \in E$, $a \in \cl(A \cup \{ e \}) \setminus \cl(A)$ を任意に取る．

$a = e$ なら，結論は $e \in \cl(A \cup \{ e \})$ であり，これは仮定 $a \in \cl(A \cup \{ e \}) \setminus \cl(A)$ から従う． したがって以下では $a \neq e$ とする． このとき， (MCL)$\forall A \subseteq E,\ \forall e \in E, \, \cl(A \cup \{ e \}) = \cl(A) \cup \{ e \} \cup \{ x \in E \mathrel{:} e \in \cl(A \cup \{ x \}) \setminus \cl(A) \}$.(MCL) の右辺で $a$ は $\cl(A)$ にも $\{ e \}$ にも属さないため，必ず

$$a \in \{ x \in E \mathrel{:} e \in \cl(A \cup \{ x \}) \setminus \cl(A) \}$$

に属す．ゆえに，$e \in \cl(A \cup \{ a \}) \setminus \cl(A)$ が示された．

証明終わり□

線形マトロイドでの解釈も明快で， $A$ と $e$ が張る部分空間に入る元は，すでに $A$ で張れる元と$e$ 自身に加え， $a$ を加えれば逆に $e$ を張れるような元であるということです． このような単一の要請でマトロイドの閉包作用素を特徴づけられるというのが上の定理の主張です．

なお，交換性質を持つ一般の閉包空間については Faigle [Fai86] も参照してください．

基本的に単に「マトロイド」と言ったときは，有限マトロイドを指し， 私の研究対象も有限マトロイドです． そのため，無限マトロイドについては触れませんでしたが， 今回の単一公理は有限性が必要であることを最後に注意として書いておきます．

脚注

1. 私が知ったきっかけは， alg-d氏のYouTube動画『1つの等式で群を定義する』 で，そこでの文献は Neumann [Neu81] でした． 詳しく知りたい方は，alg-d氏のPDFを参照ください． 群の単一公理については Kunen [Kun92]， McCune [McC93] など，広く研究されているようです． ↩
2. 厳密には Monteiro [Mon45] は (KCL1)$c(\emptyset) = \emptyset$(KCL1) を 除いた (KCL2)任意の $A \subseteq X$ に対して，$A \subseteq c(A)$ (拡大性, extensibility)(KCL2)–(KCL4)任意の $A, B \subseteq X$ に対して，$c(A \cup B) = c(A) \cup c(B)$ (合併保存, union-preserving)(KCL4) を導く単一公理を与えています． ↩
3. 名称の歴史的背景については Steinitz [Ste10]， Mac Lane [Mac38] を参照． 本稿で用いるマトロイド閉包公理としては Oxley [Oxl11, Section 1.4] を参照すれば十分である． ↩

参考文献

1. [Neu81] B. H. Neumann. Another single law for groups. Bull. Austral. Math. Soc., vol. 23, no. 1, pp. 81–102, 1981. doi:10.1017/S0004972700006912 引用箇所私が知ったきっかけは， alg-d氏のYouTube動画『1つの等式で群を定義する』 で，そこでの文献は Neumann [Neu81] でした． 詳しく知りたい方は，alg-d氏のPDFを参照ください． 群の単一公理については Kunen [Kun92]， McCune [McC93] など，広く研究されているようです．↩
2. [Kun92] Kenneth Kunen. Single axioms for groups. J. Automat. Reason., vol. 9, no. 3, pp. 291–308, 1992. doi:10.1007/BF00245293 引用箇所私が知ったきっかけは， alg-d氏のYouTube動画『1つの等式で群を定義する』 で，そこでの文献は Neumann [Neu81] でした． 詳しく知りたい方は，alg-d氏のPDFを参照ください． 群の単一公理については Kunen [Kun92]， McCune [McC93] など，広く研究されているようです．↩
3. [McC93] William W. McCune. Single axioms for groups and abelian groups with various operations. J. Automat. Reason., vol. 10, no. 1, pp. 1–13, 1993. doi:10.1007/BF00881862 引用箇所私が知ったきっかけは， alg-d氏のYouTube動画『1つの等式で群を定義する』 で，そこでの文献は Neumann [Neu81] でした． 詳しく知りたい方は，alg-d氏のPDFを参照ください． 群の単一公理については Kunen [Kun92]， McCune [McC93] など，広く研究されているようです．↩
4. [Whi35] Hassler Whitney. On the Abstract Properties of Linear Dependence. Amer. J. Math., vol. 57, no. 3, pp. 509–533, 1935. doi:10.2307/2371182 引用箇所マトロイドは Whitney [Whi35] によって， 線形従属性の抽象的性質を捉える対象として導入されました． 標準的な文献としては Welsh [Wel76]， White [Whi86]，Oxley [Oxl11] などを参照してください．↩1 引用箇所と定めます． つまり，$\cl(A)$ は 「$A$ のベクトルたちから線形結合で生成できる $E$ の元全体」 です． このようにして得られるマトロイドを線形マトロイド (linear matroid) といいます． 線形従属性を抽象化するというこの視点は， マトロイドの出発点である Whitney [Whi35] に遡ります． 線形マトロイドを含む基本例については Oxley [Oxl11, Chap. 1] をご参照ください．↩2
5. [Wel76] D. J. A. Welsh. Matroid theory. Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York, vol. No. 8, pp. xi+433, 1976 引用箇所マトロイドは Whitney [Whi35] によって， 線形従属性の抽象的性質を捉える対象として導入されました． 標準的な文献としては Welsh [Wel76]， White [Whi86]，Oxley [Oxl11] などを参照してください．↩
6. [Whi86] Neil White. Theory of Matroids. Cambridge University Press, vol. 26, 1986. doi:10.1017/CBO9780511629563 引用箇所マトロイドは Whitney [Whi35] によって， 線形従属性の抽象的性質を捉える対象として導入されました． 標準的な文献としては Welsh [Wel76]， White [Whi86]，Oxley [Oxl11] などを参照してください．↩
7. [Oxl11] James G. Oxley. Matroid Theory. Oxford University Press, vol. 21, 2011 引用箇所マトロイドは Whitney [Whi35] によって， 線形従属性の抽象的性質を捉える対象として導入されました． 標準的な文献としては Welsh [Wel76]， White [Whi86]，Oxley [Oxl11] などを参照してください．↩1 引用箇所と定めます． つまり，$\cl(A)$ は 「$A$ のベクトルたちから線形結合で生成できる $E$ の元全体」 です． このようにして得られるマトロイドを線形マトロイド (linear matroid) といいます． 線形従属性を抽象化するというこの視点は， マトロイドの出発点である Whitney [Whi35] に遡ります． 線形マトロイドを含む基本例については Oxley [Oxl11, Chap. 1] をご参照ください．↩2 引用箇所名称の歴史的背景については Steinitz [Ste10]， Mac Lane [Mac38] を参照． 本稿で用いるマトロイド閉包公理としては Oxley [Oxl11, Section 1.4] を参照すれば十分である．↩3
8. [Mon45] António Monteiro. Caractérisation de l'opération de fermeture par un seul axiome. Portugal. Math., vol. 4, pp. 158–160, 1945 引用箇所厳密には Monteiro [Mon45] は item:emptyset-preserving を 除いた item:K-extensibility–item:union-preserving を導く単一公理を与えています．↩1 引用箇所マトロイドには同値な定義が数多く存在することが知られていますが， その中に「閉包作用素」の公理があります． 他分野の方が「閉包作用素」と聞くと，真っ先に位相空間論における閉包作用素が思い浮かぶかもしれません． 位相的閉包とマトロイドの閉包は，いずれも 「与えられた集合に対して，そこから必然的に付随する点をすべて加える」 という意味で閉包作用素の例です． ただし，位相空間では「近さ」や「極限」によって付随する点が決まり， マトロイド，特に線形マトロイドでは「線形生成」によって付随する点が決まります． したがって，両者は同じ抽象的な語彙で記述できる一方で， 追加で要求される公理は異なります． 位相空間は閉包作用素で特徴づけることもでき，それがKuratowskiの公理です． 調べてみると，Kuratowski の4公理を1本の条件で表す試みは古くからあり， Monteiro [Mon45] や Pervin [Per64] が 閉包作用素の単一公理化を扱っています． そこで，マトロイドの閉包作用素の公理も単一の公理で書けないか？と考えてみたメモが本ノートです．↩2
9. [Per64] William J. Pervin. Foundations of General Topology. Academic Press, 1964 引用箇所マトロイドには同値な定義が数多く存在することが知られていますが， その中に「閉包作用素」の公理があります． 他分野の方が「閉包作用素」と聞くと，真っ先に位相空間論における閉包作用素が思い浮かぶかもしれません． 位相的閉包とマトロイドの閉包は，いずれも 「与えられた集合に対して，そこから必然的に付随する点をすべて加える」 という意味で閉包作用素の例です． ただし，位相空間では「近さ」や「極限」によって付随する点が決まり， マトロイド，特に線形マトロイドでは「線形生成」によって付随する点が決まります． したがって，両者は同じ抽象的な語彙で記述できる一方で， 追加で要求される公理は異なります． 位相空間は閉包作用素で特徴づけることもでき，それがKuratowskiの公理です． 調べてみると，Kuratowski の4公理を1本の条件で表す試みは古くからあり， Monteiro [Mon45] や Pervin [Per64] が 閉包作用素の単一公理化を扱っています． そこで，マトロイドの閉包作用素の公理も単一の公理で書けないか？と考えてみたメモが本ノートです．↩1 引用箇所というわけで，本題に入る前にPervin [Per64]による 位相空間の閉包作用素の単一公理の話を先にします．↩2
10. [Kur22] Casimir Kuratowski. Sur l'opération A de l'Analysis Situs. Fundamenta Mathematicae, vol. 3, no. 1, pp. 182–199, 1922. doi:10.4064/fm-3-1-182-199 https://eudml.org/doc/213290 引用箇所さて，そんな閉包作用素のKuratowski [Kur22]による公理は次のような形でした：↩
11. [Ste10] Ernst Steinitz. Algebraische Theorie der Körper. J. Reine Angew. Math., vol. 137, pp. 167–309, 1910. doi:10.1515/crll.1910.137.167 引用箇所名称の歴史的背景については Steinitz [Ste10]， Mac Lane [Mac38] を参照． 本稿で用いるマトロイド閉包公理としては Oxley [Oxl11, Section 1.4] を参照すれば十分である．↩
12. [Mac38] Saunders Mac Lane. A lattice formulation for transcendence degrees and p-bases. Duke Math. J., vol. 4, no. 3, pp. 455–468, 1938. doi:10.1215/S0012-7094-38-00438-7 引用箇所名称の歴史的背景については Steinitz [Ste10]， Mac Lane [Mac38] を参照． 本稿で用いるマトロイド閉包公理としては Oxley [Oxl11, Section 1.4] を参照すれば十分である．↩
13. [Fai86] Ulrich Faigle. Exchange properties of combinatorial closure spaces. Discrete Appl. Math., vol. 15, no. 2-3, pp. 249–260, 1986. doi:10.1016/0166-218X(86)90046-6 引用箇所なお，交換性質を持つ一般の閉包空間については Faigle [Fai86] も参照してください．↩