.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::=`possible values`::Sets. 

	(+) ::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 `n`egatives.
. 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><Y)->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