多項式
自然数
項 T(0, s) は以下の条件を満たす最小の集合とします。
- 0∈T(0, s)
- x∈T(0, s) ⇒ s(x)∈T(0, s)
+, *: T(0, s)×T(0, s)→T(0, s) を以下のように定義します。
- x + 0 = x
- x + s(y) = s(x + y)
- x * 0 = 0
- x * s(y) = x * y + x
T(0, s) では以下のことが成り立ちます。
- (R1) (x + y) + z = x + (y + z)
- (R2) x + y = y + x
- (R3) x + 0 = 0 + x = x が成り立つような 0 が存在する
- (R4) (x * y) * z = x * (y * z)
- (R5) x * y = y * x
- (R6) x * 1 = 1 * x = x が成り立つような 1 が存在する
- (R7) (x + y) * z = x * z + y * z
- (R8) x * (y + z) = x * y + x * z
重複を許す集合
項 T(V, +) は以下の条件を満たす最小の集合とします。
- x∈V ⇒ x∈T(V, +)
- x, y∈T(V, +) ⇒ x + y∈T(V, +)
{R1, R2}* を T(V, +) 上の
(R1), (R2) とその逆関係の反射的推移的閉包
((R1), (R2) とその逆関係で生成される単位元を持つ半群で決まる同値関係)
とします。
T(V, +)/{R1, R2}* に f: V→N
(Nは自然数の集合、f(v)≠0 となる v は有限個)を、
x の同値類に x = v + … + v + … と書くことができる最大の個数を f(v)
となるように対応させることができます。
この対応で、N[V] = {f: V→N | f(v)≠0 となる v は有限個}
に演算 + を定義することができます。
自然数上の多項式
項 T(V, +, *) は以下の条件を満たす最小の集合とします。
- x∈V ⇒ x∈T(V, +, *)
- x, y∈T(V, +, *) ⇒ x + y∈T(V, +, *)
- x, y∈T(V, +, *) ⇒ x * y∈T(V, +, *)
{R1, R2, R4, R7, R8}* を T(V, +, *) 上の
(R1), (R2), (R4), (R7), (R8) とその逆関係の反射的推移的閉包
とします。
項 T(V, *) は以下の条件を満たす最小の集合とします。
- x∈V ⇒ x∈T(V, *)
- x, y∈T(V, *) ⇒ x * y∈T(V, *)
{R4}* を T(V, *) 上の
(R4) とその逆関係の反射的推移的閉包として、
S = T(V, *)/{R4}* とします。
T(V, +, *)/{R1, R2, R4, R7, R8}* に f: S→N
(Nは自然数の集合、f(s)≠0 となる s は有限個)を、
x の同値類に x = s + … + s + … と書くことができる最大の個数を f(s)
となるように対応させることができます。
この対応で、N[S] = {f: S→N | f(s)≠0 となる s は有限個}
に演算 +, * を定義することができます。
環上の多項式
集合 R は
(R1), (R2), (R3), (R4), (R6), (R7), (R8) をみたす
演算 +R, *R が定義されているとします。
項 T(V, R, +, *) は以下の条件を満たす最小の集合とします。
- x∈V ⇒ x∈T(V, R, +, *)
- x∈R ⇒ x∈T(V, R, +, *)
- x, y∈T(V, R, +, *) ⇒ x + y∈T(V, R, +, *)
- x, y∈T(V, R, +, *) ⇒ x * y∈T(V, R, +, *)
〜 を T(V, R, +, *) 上の
(R1), (R2), (R4), (R7), (R8),
- x, y∈R ⇒ x + y = x +R y
- x, y∈R ⇒ x * y = x *R y
とその逆関係の反射的推移的閉包
とします。
項 T(V, *) は以下の条件を満たす最小の集合とします。
- x∈V ⇒ x∈T(V, *)
- x, y∈T(V, *) ⇒ x * y∈T(V, *)
{R4}* を T(V, *) 上の
(R4) とその逆関係の反射的推移的閉包として、
S = T(V, *)/{R4}* とします。
T(V, R, +, *)/〜 に f: S→N
(Nは自然数の集合、f(s)≠0 となる s は有限個)を、
x の同値類に x = s + … + s + … と書くことができる最大の個数を f(s)
となるように対応させることができます。
この対応で、R[S] = {f: S→N | f(s)≠0 となる s は有限個}
に演算 +, * を定義することができます。
R がさらに
- (R9) 任意の元 x に対して x + -x = -x + x = 0 が成り立つような -x が存在する
を満たすとき R を環といいます。
〜にも(R9)を追加して、同じように R[S] を作ることができます。
R[S] は環になります。
(一般的には S が半群のとき) R[S] を群環といいます。
R がさらに(R5)
を満たすとき R を可換環といいます。
S = T(V, *)/{R4, R5}*として、同じように R[S] を作ることができます。
V = {X1, … , Xn} のとき
R[S] = R[X1, … , Xn] は可換環になります。
これを多項式環といいます。
V={X} のとき
S は、{f: V→N | f(v)≠0 となる v は有限個}
に対応させることができます。
したがって S は N と同一視することができます。
R[X] は {f: N→R | f(v)≠0 となる v は有限個} と同一視することができます。
R[X, Y] は R[X][Y] と同一視することができます。
集合 R は
(R1), (R2), (R3), (R4), (R5), (R6), (R7), (R8) をみたす
演算 +R, *R が定義されているとします。
f(X)∈R[X] として、
〜 を R[X] 上の
(R1), (R2), (R3), (R4), (R5), (R6), (R7), (R8),
とその逆関係の反射的推移的閉包
とします。
R[X]/〜 は R に f(X)=0 を満たす X を付け加えたものになります。
自然数に -1 を付け加えると整数になります。
実数に i2=-1 を満たす i を付け加えると複素数になります。
木
集合 R は集合 E のべき集合とします。
R の演算 +R, *R を
- x +R y = (x ∩ yc) ∪ (xc ∩ y)
- x *R y = x ∩ y
と定義すると、R は単位元を持つ可換環になります。
V を有限集合とし、S を V で生成される単位元を持つ自由半群とします。
f∈R[S] が
- f(s)≠φ ⇒ f(s) の元の個数は1個
- f(s)≠φ ⇒ s を1個短くした t があれば f(t)≠φ
- E はオブジェクトの種類を表す集合 O と木の要素を表す集合 A の直和で
- s を1個長くしたすべての t に対して f(t)=φ ⇒ f(s) は O の元からなる
- s を1個長くしたある t が存在して f(t)≠φ ⇒ f(s) は A の元からなる
をみたすとき、f で木を表すことができます。
s を何個か(0個も含む)長くしたものが t のとき、s≦t と書きます。
s≦t のとき、su=t となる u が一意的に決まります。u=t/s と書きます。
f∈R[S], f(s)≠φ に対して、s≦t となる t に対して g(t/s)=f(s)、
そうでない t に対しては g(t)=φ としたものを f/s と書きます。
f が木を表すとき、f/s も木を表します。
f, g が木を表すとき、f+(f/s+g)*s も木を表します。
参考文献
-
小野寛晰: 情報代数, 共立出版, 1994.