分配偏代数
partialの訳語に「偏」を使う。「部分」だとsubと区別がつかないので。
集合Aとその上の二項演算 +, * の組(A, +, *)が次を満たすなら分配代数。
- (a + b) + c = a + (b + c)
- a + b = b + a
- (a*b)*c = a*(b*c)
- a*(b + c) = a*b + a*c
- (a + b)*c = a*c + b*c
0(加法単位元)、1(乗法単位元)の存在は要求しない(もちろん、あってもいいが)。掛け算*の可換性も仮定しない。掛け算が可換なら、可換分配代数。
足し算(+), 掛け算(*)は部分的に定義された偏演算(partial operations)でもいいとして、上の法則のイコールをすべてクリーネの等号と解釈すると、分配偏代数(distributive partial algebra)となる。
例:Xが無限集合として、A = Powfin+(X) は、Xの非空有限部分集合の全体とする。a, b∈Aに対して、
- a∩b = 0 のときに限り a + b = a ∪ b
- a∩b ≠ 0 のときに限り a * b = a∩b
0が存在すれば半環、1も存在すれば単位半環(unital semiring)、ただし、1があるケースを半環と呼ぶ流儀もある -- そのときは、1がなければ non-unital semiring。掛け算が可換なら可換半環。それぞれのpartial版は偏半環、単位偏半環など。ベキ等性があれば、加法ベキ等半環、乗法ベキ等半環など。
上の例の分配偏代数は、可換で乗法ベキ等。また、もともとの順序があるから、順序付き可換乗法ベキ等分配偏代数。
(A, +, *) と (B, +, *)が2つの分配偏代数のとき、f:A→B が全域写像で、+と*を保存するとき全域準同型。偏写像であるとき準同型と呼ぶ。分配偏代数は、偏写像(部分写像)の圏における代数の例である。
Catyでは、型表現の全体に、構文的にUnionとIntersection演算が入る。これは意味を考えない演算。tagsという写像は、全域的に定義できて、型表現の世界とPowfin(Tag)の代数構造を結ぶ役割を果たす。