[ notn_6_Algebra.html ]
- ALGEBRA::=
Net{
An algebra is a set of objects (called Set here) plus other documentation
(named DOC here) defining constants, operations and axioms. In
Mathematics the lagebra is represented by an n-tple which lists
the parameters defining the particular algebra. The Integers
for example with the operations of addition and subtraction with
unit 0 is said to be a group ( Integer, +, 0, -).
Conventionally similar names are given to the set of ntples:
- (GROUP(Set=>Integers, op=>(+), id=>(0), inv=>(-) )
and to the Set itself:
- ( Integers in Group ).
This network of propositions (ALGEBRA), formalizes the relationship between the documentation of an algebra, the name of the set of ntples, and the type of the objects that fit the algebra.
- DOC::name_of_documentation,
- |-Set in variables(DOC).
- Name::=$ DOC,
- name::={ Set:Type(DOC).Set || DOC },
- For X:modification, name(X)::={ $(DOC(X)).Set || $(DOC(X)) in $ DOC(X) }
}=::
ALGEBRA.
- ALGEBRA(SEMIGROUP, Semigroup, semigroup).
- ALGEBRA(MONOID, Monoid, monoid).
- ALGEBRA(GROUP, Group, group).
- ALGEBRA(SEMILATTICE, Semilattice, semilattice).
For more information on the above family of algebras see
[ math_31_One_Associative_Op.html ]
with the formal definitions:
- SEMIGROUP::= See http://cse.csusb.edu/dick/maths/math_31_One_Associative_Op.html#SEMIGROUP.
- MONOID::= See http://cse.csusb.edu/dick/maths/math_31_One_Associative_Op.html#MONOID.
- GROUP::= See http://cse.csusb.edu/dick/maths/math_31_One_Associative_Op.html#GROUP.
- SEMILATTICE::= See http://cse.csusb.edu/dick/maths/math_31_One_Associative_Op.html#SEMILATTICE.
Often expressed in mathematics as Σ Algebras, in MATHS expressed using to "Sigma"
to make this term easy to search. Wikipedia hase σ algebras as a part of measure theory.
Σ algebras develop from the theory of formal specifications in computer science.
The idea is that the Σ describes a collection of data types(sorts) plus a collection of operations
(functions) that operate on them. However these are not the actual functions, but a description
of the abstract functions.
[click here if you can fill this hole]
- SIGNATURE::=following,
Net
Ξ:$ SIGNATURE::=(Sorts=>{X}, Operators=>{a,b}, signature=>(a+>((X,X),X)|b+>((),X))).
- For Sigma:$ SIGNATURE,
- Sigma.ASSIGNMENT::=
Net{
Assigns types to the sorts and operators of Sigma.
- A::Sigma.Sorts->Types.
- F::Sigma.Operators->Types.
}=::
Sigma.ASSIGNMENT.
[click here if you can fill this hole]
- UNIVERSAL_ALGEBRA::=
- For Sigma:$ SIGNATURE, Sigma.algebra::={ a:$ ASSIGNMENT(Sigma) || UNIVERSAL_ALGEBRA(Sigma=>Sigma, A=>a.A, F=>a.F) }.
[ Example signature ]
- (above)|-Ξ=( Sorts=>{X}, Operators=>{a,b}, signature=> (a+>((X,X),X) |b+>((),X))) in $ SIGNATURE.
- (A=>X+>2^Nat, F=>(a+>(*).Nat|b+>1.Nat)) and (A=>X+>Nat0, F=>(a+>(+).Nat0|b+>0.Nat0)) in Ξ.algebra.
- For Sigma:$ SIGNATURE, a:Arrows, A1,A2:Sigma.algebra, ((Sigma.maps)A1 a A2) ::= |[s:Sigma.Sorts](A1.A(s) a A2.A.(s))
((Sigma.algebra)A1 a A2) ::= {h:Sigma.Sorts->Sigma.maps(A1 a A2)
- | for all s:Sigma.sorts(h(s) in A1.A(s) a A2.A(s))
- and for all (d,c):Sigma.signature(h(c)(F(A1)(d,c))=(F(A2)(d,c)) o (h o d))
}.
[ Example Algebra ]
Let
- h:=map[n:Nat0](2^n)
then
- (above)|-h(0)=1 and h(a+b)=h(a)*f(b).
So since
- (above)|-Ξ=(Sorts=>{X}, Operators=>{a,b}, signature=>(a+>((X,X),X)|b+>((),X))).
- (above)|-(X+>h) in (Ξ.algebra)(A=>Nat0, F=>(a+>(+).Nat0|b+>0.Nat0))-->(A=>Nat, F=>(a+>(*).Nat|b+>1.Nat)).
- (above)|-For Sigma, Category(Objects=>Sigma.algebra, Arrows=>map[A,B]( (Sigma.algebra)A->B).
- Sigma.Initial_algebra::=Initial_object(Sigma.algebra).
[ Example morphism ]
- (above)|-Ξ.initial_algebra---(A=>X+>Lists, F=>(a+>cons|b+>null),
- cons::=map[x,y](x,y),
- null::=().
- Lists::={(),((),()),((),((),())),...}.
- Grammar::=${a+>(), a+>(a,a)}.
- GENESYS(basis=>(), generator=>map[X]{(x,y) || x,y:X}).
In general, the GENESYS with generator being the union of all operators of a Sigma.algebra will be an Sigma.initial_algebra iff it is a free GENESYS.
[ math_25_Categories.html ]
. . . . . . . . . ( end of section Algebras) <<Contents | End>>
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
might be described by
Net{radius:Positive Real, center:Point, area:=π*radius^2, ...}.
For a complete listing of pages in this part of my site by topic see
[ home.html ]
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
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.