[Skip Navigation] [CSUSB] / [CNS] / [Comp Sci & Eng Dept] / [R J Botting] / [ MATHS ] / math_41_Two_Operators
[Contents] [Source Text] || [Notation] || [Copyright] || [Contact] [Search ]
Fri May 23 07:04:04 PDT 2008

Contents

    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.

    1. STANDARD::= See http://cse.csusb.edu/dick/maths/math.11.STANDARD.html
    2. |-STANDARD.

      Distributive laws
    3. 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))}.
    4. 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))}.
    5. 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 *.

    6. For S:Set, absorbitive(S)::={(o,*)||for all a,b(a o (a * b)=a)}.

      High School Identities for sum and product

      Burris & Lee 93, Stanley Burris and Simon Lee, "Tarski's High School Identities", American Math Monthly V100n3(Mar 93) pp231-236.
    7. HSI_bar::={ abstracted from the high school algebra of integers. (A,+) ::Abelian & Semigroup. (A,*,1) ::Abelian & Monoid.
    8. |- (HSd): (*) distributive(A) (+).
    9. For x,y,z:A.
    10. (def)|- (HS1): x+y = y+x,
    11. (def)|- (HS2): x+(y+z) = (x+y)+z,
    12. (def)|- (HS3): x*1 = x,
    13. (def)|- (HS4): x*y = y*x,
    14. (def)|- (HS5): x*(y*z) =(x*y)*z,
    15. (def)|- (HS6): x*(y+z) =(x*y)+(x*z). [click here [socket symbol] if you can fill this hole]

    }=::HSI_bar.
  1. (Burris & Lee 93)|-(Nat, +, *,1) in $ HSI_bar.
  2. (Burris & Lee 93)|-For many H: $ HSI_bar (H<>(Nat, +, *,1)).
  3. (Burris & Lee 93)|-theorems(Nat)=theorems(HSI_bar).
  4. (Burris & Lee 93)|-HSI_bar in decidable_algebras.
  5. Consider{ polynomials nice normal forms for HSI_bar.
  6. normal::expression(HSI_bar)->polynomial.
  7. (above)|-s=t iff normal(s)=normal(t).
  8. }
    }.

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. Hoare 69, C A R Hoare, An Axiomatic Basis for Computer Programming, Comm ACM V12n10(Oct 69)pp576..580+583

[ HOARE in math_42_Numbers ]

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::= See http://www.csci.csusb.edu/dick/maths/math_31_One_Associative_Op.html#SEMILATTICE.

  • LATTICE::=
    Net{

    1. |-SEMILATTICE(o=>+),
    2. |-SEMILATTICE(o=>*),
    3. |-absorbitive(+,*),
    4. |-absorbitive(*,+),
    5. (above)|-x+y=y iff x*y=x.

      A lattice defines an order relationship on its elements.

    6. relation::=rel [x,y]( x+y=y ), (<=) ::= relation,

      So we have a partially ordered set (poset):

    7. (above)|-standard_order.

      A complete lattice has a unique top and bottom element:

    8. complete::@= for 1 top:Set ( top = +Set) and for 1 bot:Set (bot = *Set).

    9. if complete then we almost have a BOOLEAN_ALGEBRA(0=> *Set, 1=> +Set) except there is no complement operation.

      [click here [socket symbol] if you can fill this hole]

    10. All lattices are isomorphic to a lattice of sets: [ Lattices of Sets in logic_31_Families_of_Sets ]

      [click here [socket symbol] if you can fill this hole]


    }=::LATTICE.

  • standard_order::= See http://www.csci.csusb.edu/dick/maths/math_21_Order.html#standard_order.

    Boolean Algebra

    1. BOOLEAN_ALGEBRA::=
      Net{
        George Boole's "Laws of Thought" [ math_11_STANDARD.html ]
      1. V::=possible values::Sets.

        (+) ::infix(V). (*) ::infix(V).


      2. |-commutative(+).
      3. |-commutative(*).
      4. (STANDARD)|-for a,b:V(a+b=b+a and a*b=b*a).
      5. |-associative(+).
      6. |-associative(*).
      7. (STANDARD)|-(+) and (*) are serial.
      8. |-idempotent(+).
      9. |-idempotent(*).
      10. (STANDARD)|-for a:V ( a+a = a*a = a).
      11. |-distributive(+,*).
      12. |-distributive(*,+).


      13. |-absorbitive(+,*).
      14. |-absorbitive(*,+).

      15. 0::unit(+).
      16. 1::unit(*).
      17. (MONOID)|-(V,+,0) and (V,*,1) in Abelian_monoid.
      18. (above)|-SEMI_RING(V, +, 0, *, 1)

      19. complement::= (-) :: prefix(V).


      20. |-(-) o (-) = Id.
      21. |-- 0 = 1.
      22. |- (De Morgan): For a,b ( - (a+b) =(-a)*(-b) and - (a*b) =(-a)+(-b) ). [click here [socket symbol] if you can fill this hole]

      }=::BOOLEAN_ALGEBRA.

    2. MONOID::= See http://cse.csusb.edu/dick/maths/math_33_Monoids.html.
    3. SEMI_RING::= See http://www.csci.csusb.edu/dick/maths/math_41_Two_Operators.html#SEMIRING.

      Examples of Boolean Algebra
    4. propositions::=BOOLEAN_ALGEBRA( V= @={false, true}. ).
    5. subsets::=Net{ For X:Sets, BOOLEAN_ALGEBRA (V=(@^X),...). ...}.
    6. bits::=BOOLEAN_ALGEBRA (V= {0, 1}. ...).
    7. words::=Net{ w:Nat. BOOLEAN_ALGEBRA (V= bits.V ^ (1..w ),...). ...}.
    8. 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))....} Tavangarian 94.

    . . . . . . . . . ( end of section Boolean Algebra) <<Contents | End>>

    Filters and Ideals

    [click here [socket symbol] if you can fill this hole]

    Semiring

      Some people call semirings rigs because they are like rings with no negatives.

      Basis

    1. semiring::=$ SEMIRING.
    2. 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.
      1. |- (SR0): ABELIAN_MONOID(Set, +, 0),
      2. |- (SR1): + in idempotent(Set),
      3. |- (SR2): MONOID(Set, *, 1),
      4. |- (SR3): (*,+) in distributive(Set),
      5. |- (SR4): 0 in zeroes(Set, *),
      6. (STANDARD)|-For I:finite, x:I->Set, π:partition(I), +(x)= + [J:π](+(x;J)). [click here [socket symbol] if you can fill this hole]

      }=::SEMIRING.

    3. For +,0,*,1, semiring(+,0,*,1)::={S || SEMIRING(Set=>S)}.

      Example semirings


    4. (above)|-@ in semiring(or, false, and, true),
    5. (above)|-Nat in semiring(+,0,*,1),
    6. (above)|-Real & positive in semiring(+,0,*,1),
    7. (above)|-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

    8. For S1,S2:Sets, a:arrows, (semiring)S1 a S1::=
    9. {f:S1 a S1 || 0.f=0 and 1.f=1
    10. and for x,y:S1( (x+y).f=x.f+y.f and (x*y).f=x.f * y.f)
    11. }

      Dioids

      A Dioid is a semiring with idempotent addition:
    12. DIOD::= SEMIRING with { for all x(x+x=x).}.

      Example: Fuzzy sets and regular sets.

      Complete Semirings

    13. COMPLETE_SEMIRING::=
      Net{
        Allows infinite sums, hence limits.
      1. |-monoid(Set, ., 1),
      2. |-0 in zeroes(Set, .),
      3. +::Indexed(Set)->Set,
      4. |-For I:Sets, x:I->Set, if I={} then +x=0,
      5. |-For i:I, I:={i}, x:I->Set, +x=x(i),
      6. |-For I:Sets, x:I->Set, π:partition(I), +(x)= + [J:π](+(x;J)),
      7. |-For I:Sets, x:I->Set, z:Set, z (_+x) = +[i:I](z x(i)),
      8. |-For I:Sets, x:I->Set, z:Set, (_+x) z = +[i:I](x(i) z),
      9. ()|-SEMIRING(+=>map[x,y](+(1+>x | 2+>y)))

      }=::COMPLETE_SEMIRING.


    14. |-COMPLETE_SEMIRING(Set=>Nat |{oo}) and COMPLETE_SEMIRING(Set=>Real|{oo})
    15. 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.
    16. POSITIVE_SEMIRING::=
      Net{

      1. |-SEMIRING,
      2. |-0<>1,
      3. |-if x+y=0 then (x=y=0),
      4. |-if x*y=0 then (x=0 or y=0), (<=) ::= rel [ x,y:Set ] (for some z:Set(x=y+z)),
      5. (above)|-if positive then poset(Set,<=,<,>,>=).

      }=::POSITIVE_SEMIRING.

      We can map any positive semiring into a Boolean algebra {false, true}:

    17. For S:$ POSITIVE_SEMIRING, DAGGER(S)::=following,
      Net
      1. \dagger::(semiring)S->@,
      2. |-\dagger(0)=false,
      3. |-For x:S~{0} ( \dagger(x)=true )

      (End of 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:

    18. Probability_Theory::=following,
      Net
        [ math_81_Probabillity.html ] [click here [socket symbol] if you can fill this hole]

      (End of Net)


    19. |-For X:Sets, @X=X->@. For X,
    20. bags(X)::=X->Nat0,
    21. spectra(X)::=X->Real,
    22. fuzzy_sets(X)::=MULTISET(K=>(0..1), (*)=>min, (+)=>max,...).

    23. MULTISET::=
      Net{
      1. X::Sets,
      2. K::semiring,
      3. subsets::=X->K,
      4. For x:X, x::subsets=map[y](if x=y then 1 else 0),
      5. For A:subsets, A::X->@=map[x]( A(x)<>0),
      6. For A:subsets, x:X, x isin A::@= A(x).
      7. (STANDARD)|-For A,B:subsets, A+B=map[x](A(x)+B(x)), acts like union of two sets.
      8. (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)).
      9. For α:Indexed(subsets), +α::=map[x](+[i:index(α)] (α(i)(x) ) ).


        Power series expansion of a multiset in terms of elements,

      10. |-for A:subsets, A= + [x:X](A(x)*x).

      }=::MULTISET.

    24. MULTIRELATION::=
      Net{
        X,Y::Sets,
      1. K::semiring,
      2. relations::=X->(Y->K),
      3. (above)|-relations --- (X><Y)->K.
      4. ...See Eilenberg 1974 Vol 1 p129...

      }=::MULTIRELATION.

    25. regular_algebra::=$ SEMIRING and
      Net{

      1. |-unary(Set, #),
      2. |-MINMAX,
      3. |-for all a:Set, one min {x:Set || x=a.x+1},
      4. |-for all a:Set, #a=the min {x:Set || x=a.x+1}.
      5. (above)|-#x=x.#x+1,
      6. (above)|-for all x, #(#x)=#x and x.#x=#x.x.
      7. (above)|-for all x, #x = +[i:0..](x^i).
        }.

    . . . . . . . . . ( end of section Semirings) <<Contents | End>>

    Rings

  • RING::=GROUP(Set, +, 0, -) and MONOID(Set, *, 1) and Net{ (.,+) in distributive(Set)} and Net{Commutative:@= (+ in commutative).}.

  • ring::=$ RING. (above) |-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))
    }.

    [click here [socket symbol] if you can fill this 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{

    1. |-Commutative.
    2. |-* in commutative.
    3. |- (cancel): For a,b,c:S, if a<>0 and a c = a b then c =b.
    4. }.

      [click here [socket symbol] if you can fill this 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

    5. FIELD::= RING(Set, +, -, 0, *, 1) and
    6. Net{ Group(Set ~ {0}, *, 1, 1/.)
    7. Archimedean::@=...
      }.

    [click here [socket symbol] if you can fill this hole]

    . . . . . . . . . ( end of section Algebras with two associative operators) <<Contents | End>>

    Notes on MATHS Notation

    Special characters are defined in [ intro_characters.html ] that also outlines the syntax of expressions and a document.

    Proofs follow a natural deduction style that start with assumptions ("Let") and continue to a consequence ("Close Let") and then discard the assumptions and deduce a conclusion. Look here [ Block Structure in logic_25_Proofs ] for more on the structure and rules.

    The notation also allows you to create a new network of variables and constraints. A "Net" has a number of variables (including none) and a number of properties (including none) that connect variables. You can give them a name and then reuse them. The schema, formal system, or an elementary piece of documentation starts with "Net" and finishes "End of Net". For more, see [ notn_13_Docn_Syntax.html ] for these ways of defining and reusing pieces of logic and algebra in your documents. A quick example: a circle = Net{radius:Positive Real, center:Point}.

    For a complete listing of pages in this part of my site by topic see [ home.html ]

    Notes on the Underlying Logic of MATHS

    The notation used here is a formal language with syntax and a semantics described using traditional formal logic [ logic_0_Intro.html ] plus sets, functions, relations, and other mathematical extensions.

    For a more rigorous description of the standard notations see

  • STANDARD::= See http://www.csci.csusb.edu/dick/maths/math_11_STANDARD.html

    Glossary
  • above::reason="I'm too lazy to work out which of the above statements I need here", often the last 3 or 4 statements. The previous and previous but one statments are shown as (-1) and (-2).
  • given::reason="I've been told that...", used to describe a problem.
  • given::variable="I'll be given a value or object like this...", used to describe a problem.
  • goal::theorem="The result I'm trying to prove right now".
  • goal::variable="The value or object I'm trying to find or construct".
  • let::reason="For the sake of argument let...", introduces a temporary hypothesis that survives until the end of the surrounding "Let...Close.Let" block or Case.
  • hyp::reason="I assumed this in my last Let/Case/Po/...".
  • QED::conclusion="Quite Easily Done" or "Quod Erat Demonstrandum", indicates that you have proved what you wanted to prove.
  • QEF::conclusion="Quite Easily Faked", -- indicate that you have proved that the object you constructed fitted the goal you were given.
  • RAA::conclusion="Reducto Ad Absurdum". This allows you to discard the last assumption (let) that you introduced.

    End