Concepts from Algebra

spec
     Semigroup =
     sort
          Elem
     op
           __ + __: Elem * Elem -> Elem,
                    assoc
end

spec
     Monoid =
     SemiGroup with sort Elem, op __ + __
then
     op
           0:Elem;
           __ + __: Elem * Elem -> Elem,
                    unit 0
end

spec
     CommutativeMonoid =
     Monoid with sort Elem, op 0, __ + __
then
     op
           __ + __: Elem * Elem -> Elem,
                    comm
end

spec
     DefineGroup =
     Monoid with sort Elem, op 0, __ + __
then
     var
          x:Elem
     .          exists x': Elem . x + x' = 0 /\ x' + x = 0
end

spec
     Group [DefineGroup with sort Elem, op 0, __ + __ ] =
%%def
     ops
           inv: Elem -> Elem;
           __ - __: Elem * Elem -> Elem;
     vars
          x,y: Elem
     %%          inv(x)
     .          x + inv(x) = 0
     .          inv(x) + x = 0
     %%          x - y
     .          x - y = x + inv(y)
end

spec
     DefineCommutativeGroup =
     DefineGroup with sort Elem, op 0, __ + __
then
     op
           __ + __: Elem * Elem -> Elem,
                    comm
end

spec
     CommutativeGroup
     [DefineCommutativeGroup with sort Elem, op 0, __ + __ ] =
%%def
     Group [DefineGroup] with ops inv, __ - __
end

spec
     DefineRing =
     DefineCommutativeGroup with sort Elem, ops 0, __ + __
then
     Monoid
     with
          ops  0 |-> 1,
           __+__ |-> __*__
     then
     %%prec          __ + __ < __ * __
     vars
          x,y,z:Elem
     %%          distributive laws:
     .          (x+y)*z = (x * z) + (y * z)
     .          z * ( x + y ) = (z * x) + (z * y)
end

spec
     Ring [DefineRing with sort Elem, ops 0, 1, __+__, __ * __ ] =
%%def
     CommutativeGroup [DefineCommutativeGroup]
     with ops inv, __ - __
%%prec
     __ - __ < __ * __
then
     %%def
     sort
          RUnit = { x: Elem . exists x': Elem . x * x' = 1 /\ x' * x = 1 }
end

spec
     DefineIntegralDomain =
     DefineRing with sort Elem, ops 0, 1, __+__, __ * __
then
     axiom
          not (1 = 0)
     op
           __ * __: Elem * Elem -> Elem,
                    comm
     vars
          x, y :Elem
     %%          without zero divisors:
     .          x=0 \/ y=0 if x * y = 0
end

spec
     IntegralDomain
     [DefineIntegralDomain with sort Elem, ops 0, 1, __+__, __ * __ ] =
%%def
     Ring [DefineRing] with sort RUnit, ops inv, __ - __
then
     %%def
     sort
           Irred= { x: Elem .                  not (x in RUnit) /\
                  ( forall y, z: Elem . x = y * z => (y in RUnit \/ z in
                  RUnit ) ) }
end

%% the definition of a factorial ring depends on the sorts
%% Unit and Irred, which both have to be interpreted
%% in a structure that shall be seen as a factorial ring
%% therefore we do not split the specification into two parts
%% as we did for the above algebraic structures

spec
     FactorialRing
     [DefineIntegralDomain with sort Elem, ops 0, 1, __+__, __ * __ ] =
     IntegralDomain [DefineIntegralDomain]
     with sorts RUnit, Irred, ops inv, __ - __
     and
     FiniteSet [sort Irred]
      with preds __  elemOf __,__ isSubsetOf __,
           ops __ union __, __ intersection __, add, __ without __, __ -
           __, __ symmDiff __
then
     preds
           equiv: Irred * Irred;
           equiv: FinSet[Irred] * FinSet[Irred]
     op
          prod: FinSet[Irred] -> Elem
     vars
          x: Elem; u,v: RUnit; i,j: Irred; S,T :FinSet[Irred]
     %%          product of a finite set of irreducible elements:
     .          prod({}) = 1
     .          prod(set(i)) = i
     .          prod(S union T) = prod(S) * prod(T)
     %%          equivalence of irreducible elements:
     .          equiv(i,j) <=> exists u: RUnit . i= u * j
     %%          equivalence of finite sets of irreducible elements:
     .           equiv(S,T) <=> ( S={} /\ T={} ) \/
                          (exists s,t: Irred . s  elemOf S /\ t  elemOf T
                          /\
                          equiv(s,t) /\ equiv(S without s, T without t) )
     %%          any element of the ring is the product of irreducible elements:
     .          exists S:FinSet[Irred] . exists u:RUnit . x = u * prod(S)
     %%          the product is "unique":
     .           equiv(S,T) if x=u * prod(S) /\ x=v * prod(T)
end

spec
     ConstructField =
     DefineRing with sort Elem, ops 0, 1, __+__, __ * __
then
     axiom
          0 =/= 1
     sort
          NonZeroElements = { x: Elem . x =/= 0 }
then
     DefineGroup
     with
          sorts Elem |-> NonZeroElements,
           ops 0 |-> 1,
           __+__ |-> __*__
end

%% an obvious view which helps to write the specification Field:

view
     MultiplicativeGroup_in_Field:
     DefineGroup to ConstructField =
     sort
          Elem |-> NonZeroElements,
     ops
           0 |-> 1,
           __+__ |-> __*__
end

spec
     DefineField=
     ConstructField
      hide sort NonZeroElements
      with sort Elem, ops 0, 1, __+__, __ * __
end

spec
     Field [DefineField with sort Elem, ops 0, 1, __+__, __ * __ ] =
%%def
     Ring [DefineRing] with sort RUnit, ops inv, __ - __
then
     %%def
     Group [view MultiplicativeGroup_in_Field]
     with
     ops
           __ - __ |-> __ / __,
           inv |-> multInv
     %%prec
          __+ __, __ - __ < __ / __
then
     op
          __ / __: Elem × Elem ->? Elem
     vars
          x,y: Elem
     .          def x/y <=> not y = 0  %%changed
     .          0/x = 0 if def 0/x
end

spec
     DefineCommutativeField=
     DefineField with sort Elem, ops 0, 1, __+__, __ * __
then
     op
           __ * __ : Elem × Elem -> Elem,
                     comm
end

spec
     CommutativeField
     [DefineCommutativeField with
      sort Elem,
      ops 0, 1, __+__, __ * __
     ] =
%%def
     Field [DefineField]
end



Back to the Basic Datatypes in CASL
Markus Roggenbach last update March 5, 1999.