郡・環・体の定義

群の定義

集合 $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$

このドットは積と呼ばれるが、いわゆる掛け算である必要はない。また逆元も-1乗でなくその数の集合にいれば何でもいい。だから演算に対して群をなす、という言い方になる。演算が無いと群として成り立てない。

なので $(\cdot, e, a^{- 1})$ に $(+, 0, - a)$ とすれば通る。この二つが通るので整数 $Z$ は演算＋について閉じており演算＋ついて群をなすと言える。

有理数 $Q$ は0以外の数全体で×、÷について閉じている。
このことは $Q^{*} = Q - {0}$ が演算×に関して群をなすと表現する。 $(\cdot, e, a^{- 1})$ には $(\cdot, 1, \frac{1}{a})$ とする。

先ほどの群の定義に、可換性を追加すると、それを満たす群は可換群と呼ばれるようになる。可換群は数として扱いやすい。

可換性は以下。

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

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

整数は可換性があるが、整数から作る行列は可換ではない。

逆に、群の定義から逆元の要請を取り除くと、関数型言語で聞くモノイドというものになる。扱いにくいが広く扱える。

protocol Groupの定義

本題。swiftで上記の条件を記述。
swiftにはクラスや構造体に決まり事としてprotocolというものを準拠させられる。インターフェースを実装するみたいなの。staticにした要素はインスタンスではなく準拠させた型自体から呼ばれる。
swiftでは演算と単位元が既にどんな型にもあるのでstatic。

上から演算、単位元、逆元。まだ概念なのでこのままプロトコルを作るわけじゃないことに注意。

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

まずこうなる。結合性の要請、及び他の要請も定義通りのものが返ってくる保証はない。そのためExtensionでテスト用メソッドを追加しておく。

プロトコルに準拠した型に関数のデフォルト実装や型などを追加できる、エクステンションという機能がある。これはプロトコルを拡張するように書く。

extension Group: Equatable {
    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)
    }
}

ついでに==演算を使うためEquatableに準拠しておく。集合はそもそも集合の元を=比較できるという定義を含んでるものなので。

protocol AdditiveGroup の定義

さっきは＋でも×でも同じく群をなすと言える話をした。
しかし実際は微妙に違う（特に逆元の定義が）ので、コードではそこを分けて実装する必要がある。

演算＋を持つ群を加法群と呼ぶ。加法群と呼ぶときは演算の可換性を仮定することが多い。

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

演算と単位元。逆元は＋－反転なのでーを定義すればいい。ついでにーの方の演算も定義しておくと便利。

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

なお、演算は＋－両方Int型に入っているので、Intに追加するという形でプロトコルを作ることもできる。
真面目に作ると-演算に-使わない方法、同値関係で割る云々やらなきゃいけないので今回はこれ。

typealias Z = Int
 
extension Z: AdditiveGroup {
    static var zero: Z { return 0 }
}

とりあえずここまでで群は完成する。
加法群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$

300 + 12 1 = 42 1

加法群に可換性、積にモノイド、そして分配性を追加。
なおポイントはモノイドの部分。つまり積に関しては逆元の存在を仮定しないこと。

ちなみに、環の定義から「任意の $a \in R$ に対して、 $a \cdot 0 = 0 \cdot a = 0$ 」であることが言える。
証明は＋の単位元から0＋0=0、そしてa・0=0から置き換え使ってa・0を作っていくだけ。

protocol Ring の定義

ではswift。
まずモノイドやって、それをさっき作ったAdditiveGroupと一緒に準拠させればいい。分配則はテストで。

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

AdditiveGroupは＋、－（加法群での逆元）、zero(０)（加法群での単位元）。Monoidは*、Identity(1)（積での単位元）を要請しているのでこれで全部行ける。

protocol Ring: AdditiveGroup, Monoid { }

後でinverseも使うので、protocol Group: MonoidとしてGroupに残しておくといい。

さて、これもまたIntで実装する。Intは＋、ー、×を持っているので実装書かなくていい。zeroとIdentityをデフォルト実装としてExtensionに書いて、あとはIntに準拠させてやる。

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

typealias Z = Int
extension Z: Ring { }

整数環Zの完成。

体の定義

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

43 1 + 0(1) 0 = 4(4) 1

環に×の逆元の定義を追加。ただし0は除く。
新たな定義はないのでprotocol FieldはGroupとRingに準拠するだけでいい。0以外云々はテストで。

protocol Field: Group, Ring { }

ついでに二項演算/を定義しておく。-と同じ理由で便利。これは積での逆元に使う演算になる。

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

ではいよいよ最初の悲願、有理数体と実数体の間を見つけるため有理数体を……作る前に、実数体Rを作成。

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

Doubleは＋、－、×、÷が入っているので、そこに×の逆元を実装しておく。
GroupはMonoid（演算＊、/(積での逆元に使う演算)と1（積での単位元））に、RingはAdditive Group（演算＋、－(加法群での逆元)と0（加法群での単位元かつ積での単位元））とMonoidにそれぞれ準拠しており、Groupに実装してあるのは演算、単位元、逆元のテスト、シグネチャのみ＝宣言だけの関数はinverseだけなので、inverseに×の逆元を実装しても大丈夫。

次からいよいよ有理数体Qを作る。

Sonolart

エクスプローラー