エレファント・コンピューティング調査報告

極限に関する順序を論理プログラミングの手法を使って指定することを目指すブロクです。

半環上のフラクタル代数(2)

背景

論理プログラミングの考え方ではプログラムを論理式と考えることができます。論理プログラミングで無限の時間実行するプログラムについて考えてみます。論理式の作るブール代数を半環と見ることで、環の極限と同様に極限を定義することができます。実際にプログラムとして記述するためには、プログラムの実行順序を指定する必要があると考えられます。半環に順序関係を入れて、それによって作られる数式の標準形として実行順序を決めることにします。一意的な標準形があるかどうかはわかりませんが、ない場合は実行順序を決めることができるような標準形を考えます。この議論を環または体の既存の理論に対応させることができるかどうかをを考えます。その対応があるかどうかはわかりませんが、それによって、数式の変形で実行順序を表すことがこのブログの1つの目標となっています。

環上の加群や環上の代数に対応する半環の用語があるのかどうかわかりませんので、ここで使うための用語を定義しておきます。環上の代数は環となるのですが、半環上の代数は半環とするのか環とするのかどちらもあると思いますので、半環となるものを半環上のフラクタル代数とここでは呼ぶことにします。環上の加群に相当するものをここでは半環上のフラクタル加群と呼ぶことにします。

これを定義して環や体との関連を調べるため、まず群の準同型と環について見ていきます。「群論の計算」の記事でも書きましたがここでも書いておきます。

群の定義

集合 G と G 上の二項演算 \cdot (乗法と呼びます)が以下の条件を満たすとき (G, \cdot) を(または単に G を)群と呼びます。 x \cdot y を xy と書くことがあります。 xy を x と y の積と呼びます。演算の順序を示すためにかっこを使います。

  • 乗法は結合法則を満たす。
    • (xy)z = x(yz) \ \ (\forall x, y, z \in G)
  • 単位元の存在：以下の条件を満たす e \in G がただ一つ存在する。この元を単位元と呼ぶ。
    • ex = xe = x \ \ (\forall x \in G)
  • 逆元の存在：任意の x \in G に対して以下の条件を満たす x^{-1} \in G がただ一つ存在する。この元を x の逆元と呼ぶ。
    • x^{-1}x = xx^{-1} = e

群の定義から「逆元の存在」を除いたものをモノイドと呼びます。群の定義から「単位元の存在」と「逆元の存在」を除いたものを半群と呼びます。半群の元 x, y が単位元であるとすると x = xy = y となるので、半群の単位元が存在すれば一意的となります。モノイドの元 x, y が元 z の逆元であるとすると、 x = xe = xzy = ey = y となるので、モノイドのある元の逆元が存在すれば一意的となります。

乗法が可換であるとき(すなわち任意の x, y \in G に対して xy = yx が成り立つとき)アーベル群と呼びます。アーベル群のとき x \cdot y を x+y と書くことがあります。 x+y を x と y の和と呼びます。

群 G の部分集合 H が G の演算に関して群になるとき、 H は G の部分群と呼びます。

x \in G が x^2=x を満たすとき x = ex = (x^{-1}x)x = x^{-1} x^2 = x^{-1}x = e となって x は G の単位元となります。 G の部分群 H の単位元 x は x^2=x を満たすので G の単位元と一致します。よって e \in H となります。

G の部分群 H の元 x に対して x の H での逆元と G での逆元は一致することがわかります。

よって G の部分群 H は

  • xy \in H \ (\forall x, y \in H)
  • x^{-1} \in H \ (\forall x \in H)

を満たします。

逆に G の空ではない部分集合 H が

  • xy \in H \ (\forall x, y \in H)
  • x^{-1} \in H \ (\forall x \in H)

を満たすとき、 H は G の積に関して群の条件を満たすので群となります。

群の準同型

群 G から群 H への写像 f: G \to H が積を保存するとき、すなわち

  • 任意の x, y \in G に対して f(xy) = f(y)f(y)

が成り立つとき f を群の準同型と呼びます。 f が全単射のとき同型と呼び、同型が存在するとき G と H は同型であると言います。

  • 任意の G の部分集合 S と Tに対して f(ST) = f(S)f(T)

が成り立ちます。

G の単位元を e_G と書くことにします。 f(e_G)^2 = f(e_G) が成り立つので f(e_G) は H の単位元となります。 x \in G に対して f(x^{-1})f(x) = f(x^{-1}x) = f(e_G)、 f(x)f(x^{-1}) = f(xx^{-1}) = f(e_G) となるので f(x^{-1}) は f(x) の逆元となります。よって

  • 任意の G の部分集合 S に対して f(S^{-1}) = f(S)^{-1}

が成り立ちます。

G の f による像 f(G) を \mathrm{Im} \ f と書きます。

  • f(G)^2 = f(G)
  • f(G)^{-1} = f(G)

が成り立ちます。
群 H の空ではない部分集合 K が部分群であることは

  • K^2 \subseteq K かつ
  • K^{-1} \subseteq K

と同値であるため、 f(G) は H の部分群となります。

H の単位元 e_H の f による逆像 f^{-1}(e_H) を f の核と呼び \mathrm{Ker} \ f と書きます。 N = \mathrm{Ker} \ f とおきます。 e_G \in N となります。 E = e_H とおきます。 f(N^2) = f(N)^2 = E^2 = E、 f(N^{-1}) = f(N)^{-1} = E^{-1} = E が成り立つため N は G の部分群となります。任意の x \in G に対して f(x^{-1}Nx) = f(x^{-1})f(N)f(x) = f(x^{-1})Ef(x) = \{ f(x^{-1})e_Hf(x) \} = E となって x^{-1}Nx \subseteq N、 x^{-1}Nx = N、 Nx = xN となります。よって N は G の正規部分群となります。

\bar{G} を G の f による分類とします。 x \in G に対して f(xN) = f(x)f(N) = f(x)E = \{ f(x) \} であるから N の剰余類 xN は \bar{G} の元 f^{-1}(f(x)) に含まれます。逆に y \in f^{-1}(f(x)) は f(y) = f(x) となります。 f(x^{-1}y) = f(x^{-1})f(y) = f(x)^{-1}f(y) = f(x)^{-1}f(x) = e_H より x^{-1}y \in N となって y \in xN となります。よって xN = f^{-1}(f(x)) となります。

よって g: G \to G/N を「分類への自然な写像」とすると f による分類と g による分類は「同値な分類」となります。 G/N は群であり、 G/N の積は G の積を元に定義されたものであるため g は積を保存するので準同型となります。また、 \bar{G} に G/N と同じ積を定義すると群になります。「 f の単射化」 \bar{f}: \bar{G} \to H は単射準同型となり、 \bar{f} の像は \mathrm{Im} \ f となります。

以上のことをまとめると(第一同型定理) f: G \to H が群 G から群 H への準同型であるとき

となります。

環

集合 R と R 上の2つの二項演算、加法 +: R \times R \to R と乗法 \cdot: R \times R \to R の組 (R, + , \cdot) が

  • (R, +) はアーベル群
  • (R, \cdot) は半群
  • 乗法は加法の上に分配的、すなわち
    • x(y + z) = xy + xz \ (\forall x, y, z \in R)
    • (x + y)z = xz + yz \ (\forall x, y, z \in R)

であるとき (R, + , \cdot) を環と呼びます。乗法の単位元が存在するとき単位元を持つ環と呼びます。乗法が可換であるとき可換環と呼びます。 R = \{ 0 \} は環の条件を満たします。これを自明な環と呼びます。

(R, +) がアーベル群ではなく可換なモノイドであるものを半環と呼びます。

  • \cdot を省略して x \cdot y を xy のように書くことがあります。
  • 演算の順序を表すためにかっこを使うことがあります。乗法は加法に優先するとしてかっこを省略することができます。
  • 加法の単位元を 0、乗法の単位元を 1 と書きます。乗法の単位元を単に単位元と呼びます。
  • 加法の x の逆元を -x と書きます。 x + (-y) を x - y と書くことがあります。

ここでは通常は環とは自明ではない単位元を持つ可換環のことを指すものとします。半環の場合も自明ではない単位元を持つ可換な半環のことを指すものとします。

(R \setminus \{0\}, \cdot) が群であるような、自明ではない単位元を持つ可換環を体と呼びます。

環の準同型

環 R から 環 S への写像 f: R \to S が加法、乗法、加法の単位元、乗法の単位元を保存するとき環の準同型と呼びます。すなわち

  • f(x + y) = f(x) + f(y)
  • f(xy) = f(x)f(y)
  • f(0) = 0
  • f(1) = 1

を満たすとき f: R \to S を環の準同型と呼びます。 f(0) = 0 という条件は他の条件から f(0) = f(0) + f(0) - f(0) = f(0 + 0) - f(0) = f(0) - f(0) = 0 と導くことができます。 f(x) + f(-x) = f(x-x) = f(0) = 0 から f(-x) = -f(x) となります。

環の準同型 f: R \to S が全単射であるとき同型と呼びます。このとき逆写像 f^{-1}: S \to R も同型となります。 R と S は同型であると言います。

環の準同型 f: R \to S の像 f(R) = \{ f(x) | x \in R \} を \mathrm{Im} \ f と書きます。 \mathrm{Im} \ f は S の部分環となります。 0 の逆像 f^{-1}(0) = \{ x \in R | f(x) = 0 \} を f の核と呼び \mathrm{Ker} \ f と書きます。 \mathrm{Ker} \ f は R のイデアルとなります。 R / \mathrm{Ker} \ f は \mathrm{Im} \ f と同型となります。

アーベル群の自己準同型

群 G に対して準同型 f: G \to G を G の自己準同型と呼びます。

アーベル群 G の自己準同型全体の集合を E = \operatorname{End}_\mathrm{G} G とおきます。 G の演算を * で表すことにします。

以下のように E に演算を定義すると環となります。

加法の定義

f, g \in E に対して f+g : G \to G を (f+g)(x) = f(x)*g(x) と定義すると * は可換なので
(f + g)(x * y) = f(x*y)*g(x*y) = f(x)*f(y) * g(x)*g(y)
= f(x)*g(x) * f(y)*g(y) = (f+g)(x) * (f+g)(y)
となって f + g \in E となります。

加法の結合法則

f, g, h \in E に対して
( (f+g) + h)(x) = (f(x)*g(x))*h(x) = f(x)*(g(x)*h(x)) = ( f+ (g + h))(x)
となるので + は結合法則を満たします。

加法の単位元の存在

0 : G \to G を 0(x) = e と定義すると 0 \in E となります( e は G の単位元)。

f \in E に対して
(0 + f)(x) = 0(x) * f(x) = e * f(x) = f(x)、
(f + 0)(x) = f(x) * 0(x) = f(x) * e = f(x)
となるので 0 は + の単位元となります。

加法の逆元の存在

f \in E に対して -f \in E を -f(x) = f(x)^- と定義すると ( f(x)^- は f(x) の逆元) * は可換なので
-f(x+y) = f(x*y)^- = f(y)^- * f(x)^- = f(x)^- * f(y)^- = -f(x) * -f(y)
となるので -f \in E となります。

f \in E に対して
( (-f) + f ) (x) = -f(x) * f(x) = f(x)^- * f(x) = e、
( f + (-f) ) (x) = f(x) * -f(x) = f(x) * f(x)^- = e
となるので -f は f の逆元となります。

加法の交換法則

f, g \in E に対して * は可換なので
(f+g)(x) = f(x)*g(x) = g(x)*f(x) = (g+f)(x)
となって + は可換となります。

よって (E,+) はアーベル群となります。

乗法の定義と結合法則

f, g \in E に対して f \cdot g を f と g の合成写像 f \circ g と定義すると f \cdot g \in E であり、 \cdot は結合法則を満たします。

分配法則

f, g, h \in E に対して
( f \cdot (g + h ) )(x) = f( (g+h) (x) ) = f(g(x)*h(x)) = f(g(x))*f(h(x))
= (f \cdot g)(x) * (f \cdot h)(x) = ( (f \cdot g) + (f \cdot h) )(x)、
( (f + g) \cdot h )(x) = (f + g)( h (x) ) = f(h(x))*g(h(x))
= (f \cdot h)(x) * (g \cdot h)(x) = ( (f \cdot h) + (g \cdot h) )(x)
となるので、 \cdot は + に対して分配法則を満たします。

乗法の単位元の存在

1 : G \to G を 1(x) = x (恒等写像)と定義すると 1 \in E となります。 G \ne \{e\} ならば 0 \ne 1 となります。

よって E は積 \cdot と和 + に関して環となります。 G \ne \{e\} ならば E は自明ではない単位元を持つ環となります。

環とアーベル群の自己準同型

自明ではない単位元を持つ環 R の元 a に対して f_a: R \to R を f_a(x) = ax と定義することができます。 f_a はアーベル群の準同型となります。アーベル群 R の自己準同型全体の集合を E = \operatorname{End}_\mathrm{G} R とすると、 \varphi: R \to E を \varphi(a) = f_a と定義することができます。
\varphi(a+b)(x) = (a+b)x = ax + bx = \varphi(a)(x) + \varphi(b)(x) = (\varphi(a) + \varphi(b))(x)、
\varphi(ab)(x) = (ab)x = a(bx) = a \varphi(b)(x) = \varphi(a)( \varphi(b)(x) ) = (\varphi(a) \varphi(b))(x)、
\varphi(0)(x) = 0x = 0、
\varphi(1)(x) = 1x = x
となります。よって \varphi: R \to E は環の準同型となります。