\\short-ml
escaper=\
escapee=.
indent=
\\end of header
\HH
\T Binary Operations t\
\^style
\^greek
h\\B <pre>
\bBinary Operations. \
\anbinary_operation" \
\bDefinition. Binary operation b\ is a function : A x B --> C, where
A,B,C are given sets, and A x B is Cartesian product.
For operation * : (a,b) |--> c, a,b are called operands, c is called result, and
instead of notation c = *(a,b), notation c = a*b is usually used.
\bNotation. Binary operation on set M b\ is a binary operation : A x B --> C where A=B=C=M.
Property of operation C=M is called "closure".
\bExample.b\ Addition: 4 = 2 + 2; A=B=C=set of natural numbers.
\bDefinition. Semigroup is a set with associative \a#binary_operation" binary_operation \ b\
Precisely, S is semigroup is for all elements a,b,c in S:
(a*b)*c = a*(c*b)
Associativity implies the following simplification of using parenthesises:
\bTheorem. Regrouping of operands does not change result in semigroup. b\
Precisely: If a\[1 \ , a\[2 \ , ... , a\[n \ are elements of semigroup, and
if L and R are strings with arbitrary distribution of parenthesises between a\[i \
which is meaningful (producing a result),
then (result L)=(result R).
\bProof is not finished here.b\ Using induction. For case n=3, the strings can be only:
(a\[1 \ a\[2 \ )a\[3 \ = a\[1 \ (a\[2 \ a\[3 \ ).
Let's assume that theorem has been proven for n > 2.
...........
\bDefinition. Monoidb\ is a semigroup with neutral element.
Precisely, M is monoid if for elements in M:
1. \^.faa,b,c (a*b)*c = a*(c*b)
2. \^.exe' \^.faa a = e' * a
2'. \^.exe'' \^.faa a = a * e''
If to take a=e'' in 2., then it follows that e'' = e',
so neutral element is uniquie and will be denoted as e.
\bInformal.b\ Natural, rational numbers are monoids in respect to addition.
\bExample.b\ Let M is a set of all functions from A to A, and I is identity function I(a) = a.
Then, M is a monoid with e = I.
</pre>
h\