群の公理と同値関係 - kazukiotaのブログ

はじめに

こんにちは。KazukiOtaです。

TSG Advent Calendar 2019 - Adventarの17日目の枠埋めとして書きました。

ちこくしたのはゆるして...（12/17よりも後にAdventarに登録したためです。）

概要

群 $G$ の部分群 $H$ を用いて、 $a \sim b \stackrel{{\rm def}}{\iff} ab^{-1} \in H$ として定められる関係を考えます。

この $\sim$ が同値関係であることは、それぞれ次のように対応する群の公理から導かれます。
${\displaystyle \begin{eqnarray} &群の公理&Ⅰ&：&単位元の存在 &\implies& &同値関係の公理&Ⅰ&：&反射律\\ &群の公理&Ⅱ&：&逆元の存在 &\implies& &同値関係の公理&Ⅱ&：&対称律\\ &群の公理&Ⅲ&：&結合法則 &\implies& &同値関係の公理&Ⅲ&：&推移律\\ \end{eqnarray} }$

準備

まず、準備として必要な直積という概念を説明します。

次に、群の公理と同値関係の公理について説明します。
既知の人は飛ばして大丈夫です。

集合の直積

定義 (直積)

$A, B$ を集合とします。このとき、 $A$ と $B$ の直積集合 $A \times B$ を次のように定めます。

$A \times B \stackrel{{\rm def}}{=} \{(a, b) | a \in A, b \in B\}$

群

定義 (群)

集合 $G$ と演算 $*:G\times G \to G$ について、 $(G, *)$ が次の3つの性質を満たすとき、 $(G, *)$ を群と言います。

1. $\exists e \in G, \forall x \in G, e*x=x*e = x$
2. $\forall x \in G, \exists y \in G, x*y = e$
3. $\forall x, y, z \in G, x*(y*z) = (x*y)*z$

注意

1.で与えられる元 $e$ を単位元といい、以降 $e$ として表します。この記事では、1. の性質を「群の公理Ⅰ」と呼びます。

2.で与えられる元 $y$ を $x$ の逆元といい、以降 $x^{-1}$ として表します。この記事では、2. の性質を「群の公理Ⅱ」と呼びます。

3.の性質を結合法則といいます。この記事では、3. の性質を「群の公理Ⅲ」と呼びます。

以降 $x*y$ を単に $xy$ と表します。

定義 (部分群)

$(G,*)$ を群とし、集合 $H$ を $G$ の部分集合とします。このとき、 $(H,*)$ が群であるならば、 $(H, *)$ を $(G, *)$ の部分群と言います。

注意

$(H, *)$ が $(G, *)$ の部分群であるとき、単に $H$ は $G$ の部分群であると言います。

$H$ が $G$ の部分群であるとき、 $H$ が演算で $*$ 閉じていることも必要です。これは、 $(H, *)$ が群であるとき、 $*:H\times H \to H$ になる、という条件に反映されています。

同値関係

定義 (二項関係)

$S$ を集合とします。

$\sim$ は $S$ 上の二項関係であるとは、 $\sim$ が $S\times S$ の部分集合となることを言います。

また、 $(a, b) \in S \times S$ に対して、 $(a, b) \in \;\sim$ を $a \sim b$ と表記します。

定義 (同値関係)

$S$ を集合とし、 $\sim$ は $S$ 上の同値関係とします。 $\sim$ が次の3つの性質を満たすとき、 $\sim$ は同値関係であると言います。

1. $\forall x \in S, x \sim x$
2. $\forall x, y \in S, x \sim y \implies y \sim x$
3. $\forall x, y, z \in x \sim y \wedge y \sim z \implies x \sim z$

注意

1.の性質を反射律といい、この記事では同値関係の公理Ⅰとも言います。

2.の性質を対称律といい、この記事では同値関係の公理Ⅱとも言います。

3.の性質を推移律といい、この記事では同値関係の公理Ⅲとも言います。

本編

関係の定義

$G$ を群とし、 $H$ を $G$ の部分群とします。
$G$ 上の関係 $\sim$ を $H$ を用いて次のように定めます。
$a \sim b \stackrel{{\rm def}}{\iff} ab^{-1} \in H$

これが、同値関係の3つの公理を満たすことは、それぞれ次のようにして示されます。

反射律

${\displaystyle \begin{eqnarray} && e \in H \tag{Hの群の公理Ⅰ：単位元の存在}\\ &\iff& \forall x \in G, xx^{-1} \in H \\ &\iff& \forall x \in G, x \sim x \end{eqnarray} }$

対称律

${\displaystyle \begin{eqnarray} && x \sim y \\ &\iff& xy^{-1} \in H \\ &\iff& yx^{-1} \in H \tag{Hの群の公理Ⅱ：逆元の存在} \\ &\iff& y \sim x \end{eqnarray} }$

推移律

${\displaystyle \begin{eqnarray} &&x \sim y \;\wedge \;y \sim z \\ &\iff& xy^{-1} \in H \;\wedge\; yz^{-1} \in H \\ &\implies& (xy^{-1})(yz^{-1}) \in H \\ &\iff& x(y^{-1}y)z^{-1} \in H \tag{Hの群の公理Ⅲ：結合法則}\\ &\iff& xz^{-1} \in H \\ &\iff& x \sim z \end{eqnarray} }$

本編まとめ

以上から、 $\sim$ は同値関係であることがわかり、同値関係の公理がそれぞれ群の公理から導かれることがわかりました。

まとめ

群 $G$ の部分群 $H$ を用いて、 $a \sim b \stackrel{{\rm def}}{\iff} ab^{-1} \in H$ として定められる関係を考えると、 $\sim$ が同値関係であることは、それぞれ次のように対応する群の公理から導かれました。
${\displaystyle \begin{eqnarray}&群の公理&Ⅰ&：&単位元の存在 &\implies& &同値関係の公理&Ⅰ&：&反射律\\&群の公理&Ⅱ&：&逆元の存在 &\implies& &同値関係の公理&Ⅱ&：&対称律\\&群の公理&Ⅲ&：&結合法則 &\implies& &同値関係の公理&Ⅲ&：&推移律\\\end{eqnarray} }$

おわりに

いかがでしたでしょうか。それぞれの公理で、一対一に対応が取れるのが面白いですね。

明日の記事は、Szkieletorさんの、Brainf*ckで九九表に載っているか判定するプログラム - モモをたずねてです。ぜひお読みください。