べき集合上にF_2代数の構造を入れたものとハイパーグラフについて

[環であること]
[加法に関してAbel群]
(i)閉じている
明らか
(ii)結合法則
対称差だから成り立つ
(iii)単位元
$\varnothing$
(iv)逆元
$-A=A$
(v)交換法則
対称差だから成り立つ

[乗法に関してモノイド]
(vi)閉じている
明らか
(vii)結合法則
共通部分だから成り立つ
(viii)単位元
$X$

ついでに可換

[分配法則]
(ix)分配法則
[$(A_0+A_1)A_2 \subset A_0A_2+A_1A_2$]
$x \in (A_0+A_1)A_2$をとる。
$x \in A_2$である。
$(x \in A_0 \land x \not\in A_1)\lor(x \in A_1 \land x \not\in A_0)$である。
よって、$(x \in A_0A_2 \land x \not\in A_1A_2)\lor(x \in A_1A_2 \land x \not\in A_0A_2)$
ゆえに$x \in A_0A_2+A_1A_2$

[$(A_0+A_1)A_2 \supset A_0A_2+A_1A_2$]
$x \in A_0A_2+A_1A_2$をとる。
$(x \in A_0A_2 \land x \not\in A_1A_2)\lor(x \in A_1A_2 \land x \not\in A_0A_2)$である。
どちらの場合も$x \in A_2$で$x \in A_0+A_1$
よって$x \in (A_0+A_1)A_2$

[$\mathbb{F}_2$ベクトル空間であること]
(x)スカラー倍で閉じる
$0A=\varnothing \in 2^X$
(xi)スカラー倍の結合法則
$0(0A)=0=(0 \cdot 0)A$
$0(1A)=0A=0=(0\cdot1)A$
$1(0A)=0=(1\cdot0)A$
$1(1A)=A=(1\cdot1)A$
(xii)分配法則
$(0+0)A=0=0A+0A$
$(0+1)A=A=0A+1A$
$(1+0)A=A=1A+0A$
$(1+1)A=0=1A+1A$

$0(A_0+A_1)=0=0A_0+0A_1$
$1(A_0+A_1)=A_0+A_1=1A_0+1A_1$

[スカラー倍と乗法が両立する]
(xiii)両立性
$0(A_0A_1)=0=A_0(0A_1)$
$1(A_0A_1)=A_0A_1=A_0(1A_1)$

[1次独立]
$X=\{x_0,x_1,...,x_{n-1}\}$とおく。
互いに素な集合同士の対称差は和集合に等しい。
よって、$c_0\{x_0\}+c_1\{x_1\}+...+c_{n-1}\{x_{n-1}\}=0$とおくと、
(左辺)=$\{x_{i_0},x_{i_1},...,x_{i_k}\}$($c_i=1$の部分だけ残る)
(右辺)=$\varnothing$
よって、$c_i=0$

[生成]
$A=\{x_0,...,x_{k-1}\}$とすると、$A=\{x_0\}+...+\{x_{k-1}\}$

$e=\{v_0,...,v_{n-1}\}\in E(G)$をとる。

$\id_{V(G)}(e)=\{v_0,...,v_{n-1}\}\in E(G)$

$e \in E(G_0)$をとる。
$\phi$は準同型だから$\phi(e) \in E(G_1)$
$\psi$は準同型だから$\psi(\phi(e)) \in E(G_2)$
よって$(\psi \circ \phi)(e) \in E(G_2)$

同型写像$\phi$をとる。

$f:E(G)→E(G')$
$e↦\phi(e)$
とおく。

[$f$は全単射]
[$f$は全射]
$\{v_0',v_1',...,v_{n-1}'\} \in E(G')$をとる。
$\phi$は同型写像だから、$\phi^{-1}$も準同型で、$\phi^{-1}(\{v_0',v_1',...,v_{n-1}'\}) \in E(G)$
$\{v_0,v_1,...,v_{n-1}\} = \phi^{-1}(\{v_0',v_1',...,v_{n-1}'\})$とおく。
$f(\{v_0,v_1,...,v_{n-1}\})=\phi(\{v_0,v_1,...,v_{n-1}\})=\{v_0',v_1',...,v_{n-1}'\}$

[$f$は単射]
$e_0,e_1 \in E(G) (e_0\not=e_1)$をとる。
$\phi$は単射より$\phi(e_1)\not=\phi(e_1)$
よって$f(e_0)\not=f(e_1)$

$[v \in V_0+V_1]=1 ⇔ v$が$V_0,V_1$のどちらか一方にのみ入っている$⇔[v \in V_0]+[v \in V_1]=1$
$[v \in V_0+V_1]=0 ⇔ v$が$V_0,V_1$のどちらにも入っていないまたはどちらにも入っている$⇔[v \in V_0]+[v \in V_1]=0$

$[v \in V_0V_1]=1 ⇔ v \in V_0 \cap V_1 ⇔ [v \in V_0]=1 \land [v \in V_1]=1 ⇔ [v \in V_0][v \in V_1]=1$
$[v \in V_0V_1]=0 ⇔ v \not\in V_0 \cap V_1 ⇔ [v \in V_0]=0 \lor [v \in V_1]=0 ⇔ [v \in V_0][v \in V_1]=0$

$[v \in 1V]=[v \in V]=1[v \in V]$
$[v \in 0V]=0=0[v \in V]$

$E_0,E_1 \in \mathcal{E}(G)$をとる。

[和]
\begin{align} v \in B_G(E_0+E_1) &⇔ v \in \sum_{e \in E_0+E_1}e\\ &⇔ v \in e となるeがE_0+E_1に奇数個ある \\ &⇔ v \in e となるeが(E_0に奇数個かつE_1に偶数個)または(E_0に偶数個かつE_1に奇数個) \\ &⇔ v \in \sum_{e \in E_0} e + \sum_{e \in E_1} e \\ &⇔ v \in B_G(E_0)+B_G(E_1) \end{align}

[スカラー倍]
$B_G(0E)=B_G(0)=0=0B_G(E)$
$B_G(1E)=B_G(E)=1B_G(E)$

$V_0,V_1 \in \mathcal{V}(G)$をとる。

[和]
\begin{align} e \in \ ^tB_G(V_0+V_1) &⇔ e \in \sum_{v \in V_0+V_1}E_G(v) \\ &⇔ e \in E_G(v) となる v が V_0+V_1 に奇数個ある \\ &⇔ e \in E_G(v) となる v が (V_0に奇数個かつV_1に偶数個)または(V_0に偶数個かつV_1に奇数個) \\ &⇔ e \in \sum_{v \in V_0}E_G(v)+\sum_{v \in V_1}E_G(v) \\ &⇔ e \in \ ^tB_G(V_0) + \ ^tB_G(V_1) \end{align}

[スカラー倍]
$^tB_G(0V)=\ ^tB_G(0)=0=0\ ^tB_G(V)$
$\ ^tB_G(1V)=\ ^tB_G(V)=1\ ^tB_G(V)$

$v \in e ⇔ v \in \sum_{e' \in \{e\}}e' ⇔ v \in B_G(\{e\}) $

$v \in e ⇔ e \in E_G(v) ⇔ e \in \sum_{v' \in \{v\}} E_G(v') ⇔ e \in \ ^tB_G(\{v\})$

$E \in \mathcal{E}(G)$は
$$E = \sum_{e \in E(G)} [e \in E]\{e\}$$
と表せる。

両辺に$B_G$を作用させると、線形性より、
$$B_G(E)=\sum_{e \in E(G)} [e \in E]B_G(\{e\}) $$

これは$\mathcal{V}(G)$の元。
$v \in V(G)$に対して、$[v \in \cdot\ ]$の線形性より、
$$[v \in B_G(E)]=[v \in \sum_{e \in E(G)}[e \in E]B_G(\{e\})]=\sum_{e \in E(G)} [e \in E][v \in B_G(\{e\})]$$

よって、$[v \in B_G(E)]=\sum_{e \in E(G)}[e \in E][v \in e]$

$V \in \mathcal{V}(G)$は
$$V=\sum_{v \in V(G)}[v \in V]\{v\}$$
と表せる。

両辺に$^tB_G$を作用させると線形性より
$$^tB_G(V)=\sum_{v \in V(G)}[v \in V]^tB_G(\{v\})$$

$e \in E(G)$に対して、
$$[e \in\ ^tB_G(V)]=\sum_{v \in V(G)}[v \in V][e \in ^tB_G(\{v\})]$$

よって、
$$[e \in \ ^tB_G(V)]=\sum_{v \in V(G)}[v \in V][v \in e]$$

[対称]
自明

[非退化]
$V \in \mathcal{V}(G) \setminus \{0\}$をとる。
$V$と1点だけ同じ$V' \in \mathcal{V}(G)$を取れば$(V,V')_{\mathcal{V}(G)}=1$となる。

[$\forall V \in \mathcal{V}(G), \forall E \in \mathcal{E}(G), (V,B_G(E))_{\mathcal{V}(G)}=(^tB_G(V),E)_{\mathcal{E}(G)}$]
$V \in \mathcal{V}(G)$をとる。
$E \in \mathcal{E}(G)$をとる。

\begin{align} (V,B_G(E))_{\mathcal{V}(G)}&=\sum_{v \in V(G)}[v \in V][v \in B_G(E)]\\ &=\sum_{v \in V(G)}[v \in V](\sum_{e \in E(G)}E(e)[v \in e])\\ &=\sum_{v \in V(G)}\sum_{e \in E(G)}[v \in V][e \in E][v \in e]\\ \end{align}

\begin{align} (^tB_G(V),E)_{\mathcal{E}(G)}&=\sum_{e \in E(G)}[e \in \ ^tB_G(V)][e \in E]\\ &=\sum_{e \in E(G)}(\sum_{v \in V(G)}[v \in V][v \in e])[e \in E]\\ &=\sum_{e \in E(G)}\sum_{v \in V(G)}[v \in V][e \in E][v \in e]\\ \end{align}