.Open Algebras with two associative operators This a set of rough notes on what happens when you have a set of elements with two different associative operators. Algebras like these are very common. The background is the standard notations and the rules that relate the two operations together. STANDARD::=http://www/dick/maths/math.11.STANDARD.html |- $STANDARD. . Distributive laws For S:Set, left_distributive(S) ::={(o,*):infix(S)^2 || for all a,b,c:S(a o (b*c)=(a o b)*(a o c))}. For S:Set, right_distributive(S) ::={(o,*):infix(S)^2 ||for all a,b,c:S((b*c) o a=(b o a)*(b o a))}. For S:Set, distributive(S) ::=left_distributive(S) & right_distributive(S). (MATHS_priority_convention): For S,o,*, if ((o) distributive(S) ~ distributive(S) (*) then o has a higher priority than *. For S:Set, absorbitive(S) ::={(o,*)||for all a,b(a o (a * b)=a)}. . High School Identities for sum and product .Source Burris & Lee 93, Stanley Burris and Simon Lee, "Tarski's High School Identities", American Math Monthly V100n3(Mar 93) pp231-236. HSI_bar::={ abstracted from the high school algebra of integers. (A,+) ::Abelian & Semigroup. (A,*,1) ::Abelian & Monoid. |- (HSd): (*) distributive(A) (+). For x,y,z:A. (def)|- (HS1): x+y = y+x, (def)|- (HS2): x+(y+z) = (x+y)+z, (def)|- (HS3): x*1 = x, (def)|- (HS4): x*y = y*x, (def)|- (HS5): x*(y*z) =(x*y)*z, (def)|- (HS6): x*(y+z) =(x*y)+(x*z). .Hole }=::HSI_bar. (Burris & Lee 93)|- (Nat, +, *,1) in$ $HSI_bar. (Burris & Lee 93)|- For many H:$ $HSI_bar (H<>(Nat, +, *,1)). (Burris & Lee 93)|- theorems(Nat)=theorems(HSI_bar). (Burris & Lee 93)|- HSI_bar in decidable_algebras. Consider{ polynomials nice normal forms for HSI_bar. normal::expression(HSI_bar)->polynomial. ()|- s=t iff normal(s)=normal(t). } }. . Hoare's Axiom System One part of Hoare's 1969 paper discusses the assumptions that can be made about computer arithmetic. His systems are interesting variations of the algebras with two operations. .Source Hoare 69, C A R Hoare, An Axiomatic Basis for Computer Programming, Comm ACM V12n10(Oct 69)pp576..580+583 .See http://www/dick/maths/math_42_Numbers.html#HOARE . Lattice A lattice has two operations that are written "+" and "*". However they behave more like "max" and "min" than addition and subtraction. In a lattice x+x = x. y*y = y. Often the operations are called 'lub'/'glb' (least upper bound/greatest lower bound) or 'sup'/'inf' (supremum/infimum). The cleanest formalism is to combine two Semi-Lattices: SEMILATTICE::=http://www.csci.csusb.edu/dick/maths/math_31_One_Associative_Op.html#SEMILATTICE. LATTICE::=Net{ |-$SEMILATTICE(o=>+), |- $SEMILATTICE(o=>*), |-$absorbitive(+,*), |- $absorbitive(*,+), ()|- x+y=y iff x*y=x. A lattice defines an order relationship on its elements. relation::=rel [x,y]( x+y=y ), (<=) ::=$relation, So we have a partially ordered set (poset): ()|- $standard_order. A complete lattice has a unique top and bottom element: complete::@= for 1 top:Set ( top = +Set) and for 1 bot:Set (bot = *Set). if complete then we almost have a$BOOLEAN_ALGEBRA(0=> *Set, 1=> +Set) except there is no $complement operation. .Hole All lattices are isomorphic to a lattice of sets: .See http://www.csci.csusb.edu/dick/maths/logic_31_Families_of_Sets.html#Lattices of Sets .Hole }=::LATTICE. standard_order::=http://www.csci.csusb.edu/dick/maths/math_21_Order.html#standard_order. .Open Boolean Algebra BOOLEAN_ALGEBRA::=Net{ .Source George Boole's "Laws of Thought" .See http://www/dick/maths/math_11_STANDARD.html V::Sets=possible values. (+) ::infix(V). (*) ::infix(V). |- commutative(+). |- commutative(*). (STANDARD)|- for a,b:V(a+b=b+a and a*b=b*a). |- associative(+). |- associative(*). (STANDARD) |- (+) and (*) are serial. |- idempotent(+). |- idempotent(*). (STANDARD)|- for a:V ( a+a = a*a = a). |- distributive(+,*). |- distributive(*,+). |- absorbitive(+,*). |- absorbitive(*,+). 0::unit(+). 1::unit(*). (MONOID)|- (V,+,0) and (V,*,1) in Abelian_monoid. ()|- SEMI_RING(V, +, 0, *, 1) complement::prefix(V)= (-). |- (-) o (-) = Id. |- - 0 = 1. |- (De Morgan): For a,b ( - (a+b) =(-a)*(-b) and - (a*b) =(-a)+(-b) ). .Hole }=::BOOLEAN_ALGEBRA. MONOID::=http://www/dick/maths/math_33_Monoids.html. SEMI_RING::=http://www.csci.csusb.edu/dick/maths/math_41_Two_Operators.html#SEMIRING. . Examples of Boolean Algebra propositions::=BOOLEAN_ALGEBRA( V= @={false, true}. ). subsets::=Net{ For X:Sets, BOOLEAN_ALGEBRA (V=(@^X),...). ...}. bits::=BOOLEAN_ALGEBRA (V= {0, 1}. ...). words::=Net{ w:Nat. BOOLEAN_ALGEBRA (V= bits.V ^ (1..w ),...). ...}. flag_algebra::=Net{ n,q:Nat. Data:Sets^q. FLAG:=indicator_function:Data->bits^(2^n). For all i:1..2^n(FLAG(S)(i) = 1 iff S in Data(i))....} .Source Tavangarian 94. .Close Boolean Algebra . Filters and Ideals .Hole .Open Semiring Some people call semirings .Key rigs because they are like rings with no negatives. . Basis semiring::=$ $SEMIRING. SEMIRING::=Net{ The theory of semirings was published by Eilenberg, in 1974, as an abstract model of "formal power series". These series are useful for answering questions in the theory of languages and automata. |- (SR0): ABELIAN_MONOID(Set, +, 0), |- (SR1): + in idempotent(Set), |- (SR2): MONOID(Set, *, 1), |- (SR3): (*,+) in distributive(Set), |- (SR4): 0 in zeroes(Set, *), (STANDARD)|- For I:finite, x:I->Set, \pi:partition(I), +(x)= + [J:\pi](+(x;J)). .Hole }=::SEMIRING. For +,0,*,1, semiring(+,0,*,1) ::={S || SEMIRING(Set=>S)}. . Example semirings ()|- @ in semiring(or, false, and, true), ()|- Nat in semiring(+,0,*,1), ()|- Real & positive in semiring(+,0,*,1), ()|- Rational & positive in semiring(+,0,*,1). . Example: The Tropical Semiring The tropical semiring consists of the natural numbers extended with infinity and whose operations are minimum and addition. Note that this is the usual semiring to compute shortest paths and that one does not have multiplication readily available in this structure. . Semiring morphisms For S1,S2:Sets, a:arrows, (semiring)S1 a S1::= {f:S1 a S1 || 0.f=0 and 1.f=1 and for x,y:S1( (x+y).f=x.f+y.f and (x*y).f=x.f * y.f) } . Dioids A Dioid is a semiring with idempotent addition: DIOD::= SEMIRING with { for all x(x+x=x).}. Example: Fuzzy sets and regular sets. . Complete Semirings COMPLETE_SEMIRING::=Net{ Allows infinite sums, hence limits. |- monoid(Set, ., 1), |- 0 in zeroes(Set, .), + ::Indexed(Set)->Set, |- For I:Sets, x:I->Set, if I={} then +x=0, |- For i:I, I:={i}, x:I->Set, +x=x(i), |- For I:Sets, x:I->Set, \pi:partition(I), +(x)= + [J:\pi](+(x;J)), |- For I:Sets, x:I->Set, z:Set, z (_+x) = +[i:I](z x(i)), |- For I:Sets, x:I->Set, z:Set, (_+x) z = +[i:I](x(i) z), () |- SEMIRING(+=>map[x,y](+(1+>x | 2+>y))) }=::COMPLETE_SEMIRING. |- COMPLETE_SEMIRING(Set=>Nat |{oo}) and COMPLETE_SEMIRING(Set=>Real|{oo}) where for all x(x+oo=oo+x=oo+oo=oo and x*oo=oo*x=oo*oo=oo and oo*0=0*oo=0) . Positive Semirings These have an oredering of the elements that is consistent with the addition operator. POSITIVE_SEMIRING::=Net{ |- SEMIRING, |- 0<>1, |- if x+y=0 then (x=y=0), |- if x*y=0 then (x=0 or y=0), (<=) ::= rel [ x,y:Set ] (for some z:Set(x=y+z)), ()|- if positive then poset(Set,<=,<,>,>=). }=::POSITIVE_SEMIRING. We can map any positive semiring into a Boolean algebra {false, true}: For S:$ $POSITIVE_SEMIRING, DAGGER(S)::=following, .Net \dagger::(semiring)S->@, |- \dagger(0)=false, |- For x:S~{0} ( \dagger(x)=true ) .Close.Net . Fuzzy Sets, Bags, Spectra, etc. For a set X, and a semiring K, the map X->K abstracts some of the most useful properties of the idea of a collection with multiple or partial membership. For example: a multiset or 'bag' associates a natural number with each element. When the values in K represent a degree of (partial) membership then X->K are called fuzzy-sets. similarly a spectrum associates a power or strength with each possible component or frequency. Perhaps: Probability_Theory::=following, .Net .See http://www/dick/maths/math_81_Probabillity.html .Hole .Close.Net |- For X:Sets, @X=X->@. For X, bags(X) ::=X->Nat0, spectra(X) ::=X->Real, fuzzy_sets(X) ::=$MULTISET(K=>(0..1), (*)=>min, (+)=>max,...). MULTISET::=Net{ X::Sets, K::semiring, subsets::=X->K, For x:X, x::subsets=map[y](if x=y then 1 else 0), For A:subsets, A::X->@=map[x]( A(x)<>0), For A:subsets, x:X, x isin A::@= A(x). (STANDARD)|-For A,B:subsets, A+B=map[x](A(x)+B(x)), acts like union of two sets. (STANDARD)|-For A,B:subsets, A*B=map[x](A(x)*B(x)), acts like intersection. (STANDARD)|-For A:subsets, k:K k*A::=map[x](k*A(x)). For \alpha:Indexed(subsets), +\alpha::=map[x](+[i:index(\alpha)] (\alpha(i)(x) ) ). Power series expansion of a multiset in terms of elements, |- for A:subsets, A= + [x:X](A(x)*x). }=::MULTISET. MULTIRELATION::=Net{ X,Y::Sets, K::semiring, relations::=X->(Y->K), ()|- relations --- (X>K. ...See Eilenberg 1974 Vol 1 p129... }=::MULTIRELATION. regular_algebra::=SEMIRING and Net{ |- unary(Set, #), |- MINMAX, |- for all a:Set, one min {x:Set || x=a.x+1}, |- for all a:Set, #a=the min {x:Set || x=a.x+1}. ()|- #x=x.#x+1, ()|- for all x, #(#x)=#x and x.#x=#x.x. ()|- for all x, #x = +[i:0..](x^i). }. .Close Semirings . Rings RING::=GROUP(Set, +, 0, -) and MONOID(Set, *, 1) and Net{ (.,+) in distributive(Set)} and Net{Commutative:@= (+ in commutative).}. ring::=RING. ()|- ring=\$ Net{ S::Sets, p::infix(S), n::unary(S), m::infix(S), 0,1::S. |- (S=>S, o=>+, i=>n, u=>0) in group and (S=>S, o=>*, u=>1) in monoid and for x,y,z:S(x*(y+z)=(x*y)+(x*z)). }. .Hole . Integral Domains A Ring with commutative addition and multiplication plus a cancellation law: if a b= a c and a<>0 then b=c. Examples - the Integers and the Integers modulo a prime number INTEGRAL_DOMAIN::=RING and Net{ |- Commutative. |- * in commutative. |- (cancel): For a,b,c:S, if a<>0 and a c = a b then c =b. }. .Hole . Fields A Ring where the non-zero elements are a multiplicative group. Examples: Rationals, Real, Complex numbers, Integers modulo a prime, Any finite integral domain FIELD::= RING(Set, +, -, 0, *, 1) and Net{ Group(Set ~ {0}, *, 1, 1/.) Archimedean::@=... }. .Hole .Close Algebras with two associative operators