\\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\