Swiftで代数学入門 〜 2. 群・環・体の定義

どうも、佐野です。前回の記事 で整数は「環」、有理数・実数・複素数は「体」であるという話をしました。今回は「群・環・体」といった代数的構造を protocol として定義し、実体としての整数・有理数・実数を struct として実装していきます。

目次：

1. 数とは何か？
2. 群・環・体の定義 ← イマココ
3. 有理数を作ってみよう
4. 時計の世界の「環」
5. 小さな「体」を作ろう
6. 多項式は整数によく似てる
7. 代数拡大で数を作ろう！

「群」の定義

「群」の数学的な定義はこうです：

集合 $G$ に演算 $\cdot$ があり、以下を満たすとき $G$ を 群 (Group)という：

• [結合性] 任意の $a, b, c \in G$ に対し $(a \cdot b)\cdot c = a \cdot (b \cdot c)$ が成り立つ
• [単位元] ある $e \in G$ があり、任意の $a \in G$ に対して $a \cdot e = e \cdot a = a$
• [逆元] 任意の $a \in G$ に対して、その逆元 $a^{-1} \in G$ があり、$a \cdot a^{-1} = a^{-1} \cdot a = e$

ここで $G$ の演算 $\cdot$ は「積」と言いますが、それは普通の数における「掛け算」のこととは限りません。前回の例で言えば、整数 $\mathbb{Z}$ は演算 $+$ に関して群です。上の定義に当てはめてみれば：

集合 $\mathbb{Z}$ は $+$ に関して群をなす：

• [結合性] 任意の $a, b, c \in \mathbb{Z}$ に対し $(a + b) + c = a + (b + c)$ が成り立つ
• [単位元] $0 \in \mathbb{Z}$ で、任意の $a \in \mathbb{Z}$ に対して $a + 0 = 0 + a = a$
• [逆元] 任意の $a \in \mathbb{Z}$ に対して、$-a \in \mathbb{Z}$ で、$a + (-a) = (-a) + a = 0$

また、有理数 $\mathbb{Q}$ は「0 以外の数全体」について $\times, \div$ で閉じてるという話をしました。これは $\mathbb{Q}$ から $0$ を除いた $\mathbb{Q}^* = \mathbb{Q} - \lbrace 0 \rbrace$ が演算 $\times$ に関して群をなすということです（中学校から掛け算 $\times$ は $\cdot$ と書くようになるので、以後そうします）：

集合 $\mathbb{Q}^* = \mathbb{Q} - \lbrace 0 \rbrace$ は $\cdot$ に関して群をなす：

• [結合性] 任意の $a, b, c \in \mathbb{Q}$ に対し $(a \cdot b) \cdot c = a \cdot (b \cdot c)$ が成り立つ
• [単位元] $1 \in \mathbb{Q}$ で、任意の $a \in \mathbb{Q}$ に対して $a \cdot 1 = 1 \cdot a = a$
• [逆元] 任意の $a \in \mathbb{Q}$ に対して、$\frac{1}{a} \in \mathbb{Q}$ で、$a \cdot \frac{1}{a} = \frac{1}{a} \cdot a = 1$

上の二つの例を見比べると、記号が $(+, 0, -a)$ か $(\cdot, 1, \frac{1}{a})$ かという違いはありますが、どちらも群構造を定めていることが分かると思います。

代数学を学び始めると「こんな当たり前の性質を抽象化して何になる？」と感じると思いますが、「数を作っていく」という立場からすれば「何を持って数は数と言えるか」を規定していこうとしてるとしているといえます。そして「群」のこれだけの単純な性質から驚くほど多くのことがいえますし、これらを満たす「具体的な型」は全てその恩恵を受けることができるのです。

この構造（あるいは仕様）を protocol として定義し、具体的な数を struct として実装していきます。そうすると protocol の性質だけを使って実装されたものは、自ずとそれに適合する全ての struct に入るのです。

その前に「可換性」について書いておきます：

群 $G$ の演算 $\cdot$ が以下を満たすとき $G$ を 可換群（アーベル群） という：

• [可換性] 任意の $a, b \in G$ に対し、 $a \cdot b = b \cdot a$

$\mathbb{Z}, \mathbb{Q}^*$ の例ではどちらも演算は可換なので、これらは可換群ですが、4回目でやる行列の積は可換ではありません（最近は小学校で掛け算の順序を間違えるとバツになるという話がありますが、それとは全く別の話です）。可換性を仮定すれば数としては扱いやすくなりますが、そうでない数の集まりもあるのです。

このようにある公理に要請を追加していくというのはよくやることです。逆に群の公理から「逆元の存在」を取り除いたものが、関数型言語でよく出てくる モノイド です。

条件を強くすればするほど扱いやすくなるけど、より広く扱うには条件を緩める必要がある。扱いたい対象に応じて抽象度をコントロールするのが難しいところであり、また面白いところでもあります。

protocol Group の定義

まず Group には演算 * と、単位元 identity があります。これは Group そのものに付随する性質なので static なものとして要請します。また全ての Group インスタンス（群の元のこと）には逆元があるので、それを返す（インスタンスの）プロパティを要請します。

protocol Group {
    static func *(a: Self, b: Self) -> Self
    static var identity: Self {get}
    var inverse: Self {get}
}

これで protocol Group が定義できたことになりますが、上の「群の定義」と見比べると「結合性」に関する要請がないですし、identity や inverse も定義通りのものが返ってくる保証がありません。これらは Group インスタンスを使うときには「当然成り立っている」と仮定するもので、直接使うものではないからです。

しかし「型がちゃんと仕様として成り立っていることは保証したい」と考えるのは健全なことです。そのためにテストというものがあるのです。そこで Group の extension として、テスト用の static メソッドを追加しましょう：

extension Group {
    static func testAssociativity(a: Self, _ b: Self, _ c: Self) -> Bool {
        return (a * b) * c == a * (b * c)
    }
    
    static func testIdentity(a: Self) -> Bool {
        return (a * Self.identity == a) && (Self.identity * a == a)
    }
    
    static func testInverse(a: Self) -> Bool {
        return (a * a.inverse == Self.identity) && (a.inverse * a == Self.identity)
    }
}

これでよし…と思いきや、こんなエラーが出てます：

Binary operator '==' cannot be applied to two 'Self' operands

これは「Group には == なんて演算入ってないよ」ということです。「でも群の公理にもそんなの入ってないよ」という気になりますが、「集合 $G$ に…」と言ってる時点で、集合の元はイコールで比較できなければならないのです。つまり Group は Equatable でなければなりません。追加しましょう：

protocol Group: Equatable {
    ...
}

これでエラーも消えて完璧です！

protocol AdditiveGroup の定義

「$\mathbb{Z}, \mathbb{Q}^* $ は演算記号の違いだけで、どちらも群だ」という話をしました。しかしコードにおいては記号の違いは大事です。特に $\mathbb{Q}, \mathbb{R}$ などの「体」には $+, \cdot$ という二つの演算で二つの群構造が入ることになるので、これらは protocol レベルで区別しておいた方が良いでしょう。

代数学では演算 $+$ を持つ群のことを特別に「加法群 (Additive Group)」と言います。加法群というときは演算の可換性を仮定する場合が多いようです。Group のときと同じく protocol AdditiveGroup を定義しましょう：

protocol AdditiveGroup: Equatable {
    static func +(a: Self, b: Self) -> Self
    prefix static func -(a: Self) -> Self
    static var zero: Self { get }
}

static func + が加法群の演算、単項演算 prefix - が逆元、そして zero が単位元です。
「引き算」 $a - b$ は $a + (-b)$ のことなので、以下のように二項演算 - も定義しておくと便利です：

func -<G: AdditiveGroup>(a: G, b: G) -> G {
    return (a + (-b))
}

テストメソッドについては同様なので省略します。

さて、ここまで来れば加法群としての $\mathbb{Z}$ は作れるのですが、ちょっとトリッキーなことをしてみます：

typealias Z = Int

extension Z: AdditiveGroup {
    static var zero: Z { return 0 }
}

加法群 $\mathbb{Z}$ できました！

Int には最初から演算 +, - が入っているので、あとは AdditiveGroup が要請する zero を追加し、Z という別名をつければいいだけです。既存の型に勝手に仕様を付け加えることができるというのが Swift の protocol の面白いところです。

ちゃんと自然数から構成したい場合は @yashigani さんの「Swiftで自然数を作るっ」のやり方で自然数 $\mathbb{N}$ を構成し、ℕ×ℕ を同値関係で割る という方法で $\mathbb{Z}$ を作ることもできます。が、計算コストの問題もあるので、今回は「ありものを乗っ取る」というやり方で行きます。

ちなみに Swift では Unicode 文字を識別子に使えるので、こんな風にすることもできます：

extension ℤ: AdditiveGroup {
    ....
}

個人的にはグッとくるのですが、入力が面倒なのでコードでは普通の Z にしておきます。では続けて $\mathbb{Z}$ に掛け算も入れて「整数環」を完成させましょう。

「環」の定義

「環」の定義です：

集合 $R$ に二つの演算 $+, \cdot$ があり、以下を満たすとき $R$ を 環 (Ring) という：

• $R$ は $+$ に関して可換群である.
  • $+$ に関する単位元を $0$,
  • $+$ に関する $a$ の逆元を $-a$ と書く.
• $R$ は $\cdot$ に関してモノイドである.
  • $\cdot$ に関する単位元を $1$ と書く.
• [分配性] 任意の $a, b, c \in R$ に対して以下が成り立つ：
  • $(a + b) \cdot c = a \cdot c + b \cdot c$
  • $a \cdot (b + c) = a \cdot b + a \cdot c$

色々と書いてありますが、整数が持ってて当然な性質を並べただけです。ポイントは「$R$ は $\cdot$ に関してモノイドである」というところで「群」ではないということです。つまり積に関しては逆元の存在を仮定しないのです。整数 $3$ の逆数 $\frac{1}{3}$ は整数ではありませんよね？

ところでこの「環」の定義から、次のことがいえます：

• 任意の $a \in R$ に対して、 $a \cdot 0 = 0 \cdot a = 0$

証明してみましょう：

任意の $a \in R$ を取る。
0 は $+$ の単位元なので $0 + 0 = 0$。
両辺に $a$ を左からかけて、$a \cdot (0 + 0) = a \cdot 0$。
左辺は分配則より、$a \cdot 0 + a \cdot 0 = a \cdot 0$。
両辺に $a \cdot 0$ の $+$ に関する逆元 $-(a \cdot 0)$ を足して、$a \cdot 0 = 0$。
$0 \cdot a = 0$ についても同様。（証明終）

こんな具合です。$R$ を整数だと思ったら当たり前に成り立つ性質でも、環の性質だけに還元させて証明するというのは結構難しい！こういう縛りプレイを色々とやるのが抽象代数学です（怒られそう）

では protocol を定義しましょう。

protocol Ring の定義

まず Monoid を定義します：

protocol Monoid: Equatable {
    static func *(a: Self, b: Self) -> Self
    static var identity: Self {get}
}

Group から inverse をなくしただけです（改めて protocol Group: Monoid として inverse だけ残しておくと良いでしょう）。すると Ring は：

protocol Ring: AdditiveGroup, Monoid { }

だけでいけます。 +, -, zero は AdditiveGroup で要請され、*, identity は Monoid で要請されているので付け加えるものはありません。分配則についてはテストで実装しておきましょう（省略）。

環 $R$ には $1$ と $+$ があるので、 $1$ を $n$ 回足した $n \cdot 1 = 1 + 1 + \cdots + 1$ という元があります（この $\cdot$ は $R$ の積 $\cdot$ とは別です）。これで Ring の元をインスタンス化してできるようにしておくと便利です。

protocol Ring: ... {
    init(_ intValue: Int)
    ...
}

こうすると AdditiveGroup, Monoid で要請される zero, identity について、次のようなデフォルト実装を与えておくことができます：

extension Ring {
    static var zero: Self {
        return Self.init(0)
    }
    
    static var identity: Self {
        return Self.init(1)
    }
}

ここまで来ると Z は、もう完成してしまっています。

typealias Z = Int
extension Z: Ring { }

+, -, * は Int に初めから入ってます。そして AdditiveGroup, Monoid が要請する zero, identity は Ring の extension で実装済みです。protocol を整備しただけで整数環 Z が作れてしまいました！

「体」の定義

最後に「体」の定義ですが、ここまで来ると簡単です：

集合 $F$ が二つの演算 $+, \cdot$ に関して 環 を成し、 $F - \lbrace 0 \rbrace$ が $\cdot$ に関して 群 を成すとき、$F$ を 体 (Field) という。

「環」の定義が頭に入ってれば、あとは有理数体 $\mathbb{Q}$ や 実数体 $\mathbb{R}$ が「$0$ 以外の数が逆数を持つ」という性質を持つことからこの定義は覚えられるでしょう。

protocol Field はこれだけです：

protocol Field: Group, Ring { } 

Group の積 * は「$0$ 以外の元について…」でなければいけませんが、メソッドのシグネチャにその条件は入れられないので入っていません。テストで保証する方向で行きましょう。

AdditiveGroup で - 演算を定義したように、体においても「割り算」$a \div b$ は $a \cdot b^{-1}$ のことなので、以下のように二項演算 / を定義しておくと便利です：

func /<F: Field>(a: F, b: F) -> F {
    return a * b.inverse
}

さて、$\mathbb{Q}$ を作る前に、さっきのやり方で実数体 $\mathbb{R}$ を定義してしましましょう：

typealias R = Double

extension R: Field {
    var inverse: R {
        return 1 / self
    }
}

これで $\mathbb{R}$ の出来上がりです！

Double に入っている四則演算 +, -, *, / を使って、そのまま Field 型だということにしてしまう訳です。 Double は有限の小数点数なので「実数」ではありえないのですが、このシリーズでは実数はそんなに積極的に使わないのでこれで良いってことにします。

それではいよいよ $\mathbb{Q}$ を実装…と行きたいところですが、既にかなり長くなってしまったので今回はこの辺で。それでは、また次回！

ソースコード

GitHub: SwiftyAlgebra

• Monoid
• Group
• AdditiveGroup
• Ring
• Field

宣伝

• 3/19(土) 「第6回 プログラマのための数学勉強会」
• プログラマのための数学勉強会 Facebook ページ
• 個人ブログ Imaginary & Imaginative