前の記事：Pythonで群を実装する：群構造をデータとして表し、Hypothesisで公理を検証する
前の記事では、群の要素と群構造を Group[G] として分けて表しました。今回は、群の間の写像を扱います。
群準同型は、群の演算を保つ写像です。後の記事で部分群の包含写像や、剰余群から像への写像を扱うため、ここで共通のデータ構造を定義します。
コード例は Python 3.12 以降を前提にしています。
群準同型の定義
群 $G$ から群 $H$ への写像 $f : G \to H$ が準同型であるとは、任意の $a, b \in G$ に対して
f(ab) = f(a)f(b)
が成り立つことです。この条件から、単位元と逆元も保たれます。
f(e_G) = e_H, \qquad f(a^{-1}) = f(a)^{-1}
群準同型を実装する
homomorphism.py
from __future__ import annotations
from collections.abc import Callable, Iterable
from dataclasses import dataclass
from group import Group
@dataclass(frozen=True, slots=True)
class GroupHomomorphism[G, H]:
f: Callable[[G], H]
source: Group[G]
target: Group[H]
def __call__(self, value: G) -> H:
return self.f(value)
def assert_preserves_operation(self, a: G, b: G) -> None:
assert self(self.source.op(a, b)) == self.target.op(self(a), self(b))
def assert_preserves_identity(self) -> None:
assert self(self.source.identity) == self.target.identity
def assert_preserves_inverse(self, a: G) -> None:
assert self(self.source.inv(a)) == self.target.inv(self(a))
def identity_homomorphism[G](group: Group[G]) -> GroupHomomorphism[G, G]:
return GroupHomomorphism(
f=lambda value: value,
source=group,
target=group,
)
def compose_homomorphisms[K, G, H](
outer: GroupHomomorphism[G, H],
inner: GroupHomomorphism[K, G],
) -> GroupHomomorphism[K, H]:
if outer.source is not inner.target:
raise ValueError("the target of inner must be the source of outer")
return GroupHomomorphism(
f=lambda value: outer(inner(value)),
source=inner.source,
target=outer.target,
)
@dataclass(frozen=True, slots=True)
class InjectiveGroupHomomorphism[G, H](GroupHomomorphism[G, H]):
def assert_injective(self, samples: Iterable[G]) -> None:
samples = tuple(samples)
images = [self(value) for value in samples]
assert len(set(images)) == len(samples)
@dataclass(frozen=True, slots=True)
class SurjectiveGroupHomomorphism[G, H](GroupHomomorphism[G, H]):
def assert_surjective(
self,
source_samples: Iterable[G],
target_samples: Iterable[H],
) -> None:
images = {self(value) for value in source_samples}
assert set(target_samples) <= images
@dataclass(frozen=True, slots=True)
class BijectiveGroupHomomorphism[
G, H
](InjectiveGroupHomomorphism[G, H], SurjectiveGroupHomomorphism[G, H]):
pass
GroupHomomorphism は、写像と入力側・出力側の群を一つの値として保持します。検証メソッドは、与えられた具体例について性質を確認するものです。インスタンスを作っただけで、任意の要素について準同型性が証明されるわけではありません。
単射・全射・全単射も、群準同型のサブクラスとして表せます。assert_injective() と assert_surjective() は、有限モデルの要素や検証対象のサンプルを使って、それぞれの性質を確認します。BijectiveGroupHomomorphism は、単射と全射の両方を継承します。
恒等射と準同型の合成
群 $G$ の恒等射は、各要素をそのまま返す写像です。
\operatorname{id}_G : G \to G,
\qquad \operatorname{id}_G(a) = a
恒等射は演算を保つため、群準同型です。また、群準同型 $f : G \to H$ と $g : H \to K$ の合成
g \circ f : G \to K
も群準同型になります。identity_homomorphism() と compose_homomorphisms() で、この2つの構成を表せます。
符号写像を具体例にする
置換の符号写像は、次の準同型です。
\operatorname{sgn}: S_n \to \{ -1, 1 \}
sign_homomorphism.py
from permutation import Permutation
def sign(permutation: Permutation) -> int:
inversions = sum(
permutation.values[i] > permutation.values[j]
for i in range(len(permutation.values))
for j in range(i + 1, len(permutation.values))
)
return -1 if inversions % 2 else 1
符号の値 -1 と 1 は整数の乗法群の要素として扱えます。
test_sign_homomorphism.py
from hypothesis import given, strategies as st
from group import Group
from homomorphism import (
SurjectiveGroupHomomorphism,
compose_homomorphisms,
identity_homomorphism,
)
from permutation import Permutation, symmetric_group
from sign_homomorphism import sign
source = symmetric_group(3)
target = Group[int](
identity=1,
inv=lambda value: value,
op=lambda left, right: left * right,
)
sign_homomorphism = SurjectiveGroupHomomorphism(sign, source, target)
permutations = st.permutations(range(3)).map(Permutation)
source_samples = tuple(
Permutation(values)
for values in (
(0, 1, 2),
(0, 2, 1),
(1, 0, 2),
(1, 2, 0),
(2, 0, 1),
(2, 1, 0),
)
)
sign_values = {-1, 1}
@given(permutations, permutations)
def test_sign_preserves_multiplication(
left: Permutation, right: Permutation
) -> None:
sign_homomorphism.assert_preserves_operation(left, right)
@given(permutations)
def test_sign_preserves_inverse(permutation: Permutation) -> None:
sign_homomorphism.assert_preserves_inverse(permutation)
def test_sign_preserves_identity() -> None:
sign_homomorphism.assert_preserves_identity()
def test_identity_is_a_homomorphism() -> None:
identity = identity_homomorphism(source)
identity.assert_preserves_identity()
for value in source_samples:
identity.assert_preserves_inverse(value)
for left in source_samples:
for right in source_samples:
identity.assert_preserves_operation(left, right)
def test_composition_is_a_homomorphism() -> None:
identity = identity_homomorphism(source)
composed = compose_homomorphisms(sign_homomorphism, identity)
for value in source_samples:
assert composed(value) == sign_homomorphism(value)
composed.assert_preserves_identity()
for left in source_samples:
for right in source_samples:
composed.assert_preserves_operation(left, right)
def test_sign_is_surjective() -> None:
sign_homomorphism.assert_surjective(source_samples, sign_values)
核と像
準同型 $f : G \to H$ に対して、核と像を次で定義します。
\ker f = \{ g \in G \mid f(g) = e_H \}
\operatorname{im} f = \{ f(g) \mid g \in G \}
符号写像の場合、核は偶置換全体です。$S_3$ には6個の要素があり、偶置換は3個なので、核の要素数は3です。像は $\{ -1, 1 \}$ になります。
kernel_and_image.py
from homomorphism import GroupHomomorphism
from permutation import Permutation, symmetric_group
from sign_homomorphism import sign
from group import Group
S3 = frozenset(
Permutation(values)
for values in (
(0, 1, 2),
(0, 2, 1),
(1, 0, 2),
(1, 2, 0),
(2, 0, 1),
(2, 1, 0),
)
)
source = symmetric_group(3)
target = Group[int](
identity=1,
inv=lambda value: value,
op=lambda left, right: left * right,
)
sign_homomorphism = GroupHomomorphism(sign, source, target)
kernel = {
permutation
for permutation in S3
if sign_homomorphism(permutation) == target.identity
}
image = {sign_homomorphism(permutation) for permutation in S3}
assert len(kernel) == 3
assert image == {-1, 1}
核は後の記事で部分群として扱い、符号写像の核 A_3 による剰余群を構成します。
まとめ
- 群準同型は群の演算を保つ写像である
-
GroupHomomorphism[G, H]に写像と入出力の群をまとめた - 単位元・逆元・演算を保つ性質を検証した
- 符号写像の核と像を具体的に計算した
次の記事では、包含写像を使って部分群・正規部分群・交換子部分群を表します。