概要

まずは、算法を1つ持つ代数系の分類について説明します。 このような代数系の分類として、群・半群などがあります。

群とは

ある代数系(G,・)に対して、以下の条件を考えます。

  1. 「結合法則」が成り立つ。

  2. 「単位元」が存在する。

  3. 「逆元」が存在する。

代数系Gが

  1. を満たすとき、半群(semi-group)とよび、
    1. を満たすとき、モノイド(monoid)と呼びます。 また、1.～3. の全てを満たすとき、Gを群(group)と呼びます。

さらに、群(半群、モノイド)の中で、 「交換法則」を満たすものを可換群(可換半群、可換モノイド)と呼びます。

可換群はアーベル群(abelian group)もしくは加法群(additive group)とも呼ばれ、 その算法は、しばしば ＋ を用いて表します。 （逆に言うと、＋ を用いて表される算法は暗黙的に可換算法であると考えることが多い。）

余談

群という概念は、ニールス・ヘンリック・アーベル（Niels Henrik Abel、ノルウェーの数学者）が 5次方程式の一般解法の存在の有無を調べるために考えたものです。 この当時、アーベルは可換群しか想定していませんでした。 後に、ガロアが群論を構築する際、非可換なものも群として考え、 アーベルの考えた群は可換群として区別するようになりました。 可換群をアーベル群と呼ぶのはこの名残です。

群の例

半群・群の例をいくつか紹介します。

自然数

自然数 ω は加法 ＋ に関して可換モノイドになります。 m ∈ ω, m ≠ 0 に対して、 －m はもはや自然数ではないので、 逆元の存在しない元があり、 群にはなっていません。 ただし、m ＋ 0 ＝ m であり、 単位元 0 が存在するのでモノイドになります。 また、自然数は乗法 × に関して可換モノイドになります。 （単位元は 1 です。）

偶数全体

偶数全体の集合 E ＝ {x | x ∈ Z ∧ x ≡ 0 (mod 2)} は乗法 × に関して可換半群になります。 （偶数同士の掛け算結果はやはり偶数になるので、代数系になる。） 自然数の場合と異なり、 この集合はモノイドではありません。 （1 がないので単位元がない。）

整数

整数は Z は加法 ＋ に関して可換群になります。 単位元は 0、 p ∈ Z の逆元は －p です。 また、乗法に関しては、可換モノイドになります。 （整数同士の割り算は整数になるとは限らない。単位元は 1。）

有限群

自然数や整数などは無限集合ですが、 有限集合になるような群も存在します。

1 の n 乗根

1 の n 乗根になるような複素数 Ωn ＝ {ω | ω ∈ C ∧ n ∈ N ∧ ωn ＝ 1} は n 個の元からなる集合になります。 この集合は、複素数の乗算に関して可換群になります。 例えば、a, b ∈ Ωn に対して、 c ＝ a b ＝ b a と置くと、 cn ＝ (a b)n ＝ an bn ＝ 1 × 1 ＝ 1 なので、c ∈ Ωn になります。 また、 a × an － 1 ＝ an ＝ 1 なので、 a には必ず逆元 an － 1 が存在します。 さらに、1 ∈ Ωn で ∀ω ∈ Ωn, ω × 1 ＝ ω なので、単位元も存在します。

置換群

有限集合に対する「[全単写](../set/map.md#bijection)」を置換（permutation）といいます。 置換という言葉は、 (a, b, c) を (a, c, b) に並べ替えるような操作という意味です。 ここでは単純化のため、3つの元に対する置換に付いてのみ説明しますが、 元の数が3以外の場合でも同様のことが成り立ちます。 置換は以下のような書き方で表現します。
[
012
120
]
この例は、0番目の元を1番目の元と、 1番目を2番目と、 2番目を0番目と入れ替えるという意味です。 例として、 (a, b, c) に対してこの置換を適用すると、 (b, c, a) になります。 この記法で表すなら、 3つの元に対する置換は以下の6通りになります。
[
012
012
] , [
012
021
] , [
012
210
] , [
012
102
] , [
012
120
] , [
012
201
]
置換は、写像の合成に関して群を成していて、 この群を置換群（permutation group）と呼びます。

群に関する諸概念

位数

群の元の数を位数（order）といいます。 集合の元の数と同様に、群 G の位数を |G| と表します。 「群の例」で出てきた例に関しては、 整数や偶数全体の集合の位数は無限、 1 の n 乗根の位数は n、 n 元に対する置換群の位数は n! になります。

同型

二つの群 {G, ・G} , {H, ・H} の間に、 「全単写」f : G → H で、 任意の a, b ∈ G に対して、 条件

f(a ・G b) ＝ f(a) ・H f(b)
を満たすものが存在するとき、 この写像 f を群同型写像（group isomorphism）と呼び、 2つの群は互いに群同型である（group isomorphic）と言います。 （群であることが明白である場合、単に同型であると言います。） すなわち、群同型とは、 2つの群が集合として「[同値](../set/map.md#equivalent)」であり、 さらに、算法の結果にも1対1の対応が取れることを言います。 例として、以下のような2つの群
{ {0, 1, 2}, ＋}
0 ＋ 1 ＝ 1 ＋ 0 ＝ 2 ＋ 2 ＝ 1
0 ＋ 2 ＝ 2 ＋ 0 ＝ 1 ＋ 1 ＝ 2
1 ＋ 2 ＝ 2 ＋ 1 ＝ 0 ＋ 0 ＝ 0
と
{ {a, b, c}, ・}
a ・ b ＝ b ・ a ＝ c ・ c ＝ b
a ・ c ＝ c ・ a ＝ b ・ b ＝ c
b ・ c ＝ c ・ b ＝ a ・ a ＝ a
を考えます。 まあ、この例は単純なので、ぱっと見で自明だと思いますが、 f(0) ＝ a, f(1) ＝ b, f(2) ＝ c となるような写像 f を用意すれば、同型になります。 要するに、同型という概念は、 外面だけ見ると、0, 1, 2 と a, b, c と言うように 異なる群のように見えるかもしれないけれども、 実質的には同じ構造をになっているようなもののことを言います。

部分群

群 {G, ・} があるとき、 G の部分集合 H が ・ に関して群を成しているとき、 群 {H, ・} を {G, ・} の部分群（sub group）と呼びます。

例えば、整数は加法に関して有理数の部分群になります。

また、整数 Z に対して、 偶数全体の集合や、 3の倍数の集合は加法に関して整数の部分群になっています。 （偶数同士を足すとやはり偶数になるし、 3の倍数同士もやはり3の倍数。） より一般的にいうと、 ある整数 N の倍数全体の集合は整数の部分群になります。

さらに言うと、 「環」R に対して、R の元のうちからの1つ a を選んだとき、

G ＝ {x | ∃y ∈ R, x ＝ a y}
と表せるような（形式的には a の倍数になっているような）集合 G は R の部分群になります。 （詳しくは「[環・体](field.md)」で述べますが、実際は部分環になります。） このような形の部分群を aR と書き表します。 （この記法を用いると、 偶数全体の集合は 2Z、 3の倍数全体の集合は 3Z となります。） 注： G が非可換群の場合には、 g を左からかけた場合 gG と、右から書けた場合 Gg の2つが考えられます。

剰余群

群 G とその部分群 H があるときに、以下のようにして新しい集合を定義することを考えます。

  • a, b ∈ G

  • a b－ ∈ Hのとき、aとbは「同値」であるものとする。

  • この同値関係を使って「商集合」G/Hを作る。

  • G/Hの元に対して、Gと同じ算法を適用する。

このようにして作った商集合 G/H は、 G と同じ算法に関して群になります。 このような群を剰余群（residual group）もしくは商群（quotient group）と呼びます。

整数の剰余群

簡単な例として、剰余群 Z/3Z を挙げてみます。 上述の手順において、 G ＝ Z、 H ＝ 3Z として、 商集合を作ると、 G/H ＝ {0, 1, 2} になります。 G/H の元に対して、 G の加法をそのまま適用すると、
0 ＋ 0 ＝ 0 ＋ 0 ＝ 0
0 ＋ 1 ＝ 0 ＋ 1 ＝ 1
0 ＋ 2 ＝ 0 ＋ 2 ＝ 2
1 ＋ 1 ＝ 1 ＋ 1 ＝ 2
1 ＋ 2 ＝ 1 ＋ 2 ＝ 3 ＝ 0
2 ＋ 2 ＝ 2 ＋ 2 ＝ 4 ＝ 1
となります。 単位元は 0 で、 1 の逆元は 2 になります。

1 の n 乗根の剰余群

「[有限群](#finite)」で述べたように、 1 の n 乗根で作った集合は複素数の乗法に関して群を成します。 実は、n が素数ではないとき、この群は部分群を持ちます。 ここでは例として、n ＝ 6 の場合を挙げます。 まず、1 の3乗根のうちで、偏角の最も小さいものを ω としましょう。 そうすると、1 の6乗根は、 Ω6 ＝ {1, ω, ω2, －1, －ω, －ω2} の6つになります。 見るからに明らかですが、この6つのうちの {1, ω, ω2} の3つは 1 の3乗根Ω3ですので、群になっています。 すなわち、 Ω3 は Ω6 の部分群になります。 ちなみに、Ω2 ＝ {1, －1} も Ω6 の部分群です。 さて、それでは、これらを使って剰余群を作ってみましょう。 まずは、Ω3 を使った剰余群ですが、
ω/1 ＝ ω ∈Ω3, ω2/1 ＝ ω2 ∈Ω3, ω2/ω ＝ ω ∈Ω3,
－ω/－1 ＝ ω ∈Ω3, －ω2/－1 ＝ ω2 ∈Ω3, －ω2/－ω ＝ ω ∈Ω3,
なので、「[同値類](../set/integer.md#eq_class)」は
1 ＝ {1, ω, ω2}, －1 ＝ {－1, －ω, －ω2}
の2つなので、剰余群は
Ω6 / Ω3 ＝ {1, －1}
になります。 まあ、見るからにそうなんですが、 これは Ω2 と「[群同型](#g_isomorphic)」になります。 同様に、Ω2 を使った剰余群は、
1/－1 ＝ －1 ∈Ω2, ω/－ω ＝ －1 ∈Ω2, ω2/－ω2 ＝ －1 ∈Ω3,
なので、同値類は
1 ＝ {1, －1}, ω ＝ {ω, －ω}, ω2 ＝ {ω2, －ω2}
の3つになり、
Ω6 / Ω2 ＝ {1, ω, ω2}
になります。 これも見るからに、Ω3 と群同型です。 要するに、群同型を記号 ～ で表すと、
Ω6 / Ω2 ～ Ω3
Ω6 / Ω3 ～ Ω2
 となります。 実はこの逆もまた叱りで、 Ω2 と Ω3 の直積集合
Ω2 × Ω3 ＝ {(1, 1), (1, ω), (1, ω2), (－1, 1), (－1, ω), (－1, ω2)}
に対して、 (1, 1) → 1、 (1, ω), → ω、 (1, ω2), → ω2、 (－1, 1), → －1、 (－1, ω), → －ω、 (－1, ω2) → －ω2 というように同一視して考えると、
Ω6 ～ Ω2 × Ω3
 となります。

半群から群を機械的に作る

実は、半群から群を機械的に作ることが出来ます。 最も分かりやすい例は、自然数から整数を定義する手順なんですが、 これに関しては「整数の定義」で説明しています。

商集合が群になることの証明はここでは省略しますが、 この手順を任意の半群 S に対して一般化すると、以下のようになります。

  • 半群Sの対(a, b) ∈ S×Sを用意する。

  • 2つの対m ＝ (a, b), n ＝ (c, d)に対して、「ad ＝ bcのとき互いに同値」という同値関係～を定める。

  • この同値関係を使って商集合S×S / ～を作る。

  • この商集合は群になる。

  • 形式的に、対(a, b)をab－1と書く。

  • mとnとの間の算法はmn ＝ (ac, bd)で定める。

執筆予定

・部分群

・巡回群とかの説明もここ？

ある元 a があって、
全ての元が a の冪で書き表せるとき、その群を巡回群という。
a のことは生成元という。