An operation can be regarded as an operator on a set of ordered pairs. Instead of O(x,y) the shortened notation xOy is often used and, when the operation O is understood, the even shorter xy may suffice.
The statement ‘xOy exists’ is a relation, represented by the set of ordered
pairs on which O operates, that expresses the condition of applicability of the
operation O.
[Example (1) Subtraction: if x and y are cardinal numbers and x−y is
defined to be a cardinal number k such that y+k = x then ‘x−y exists’
means the same as ‘x≥y’.]
[Example (2) Join: if x and y are points in a linear space and xy denotes the line
joining the two points, then ‘xy exists’ if and only if ‘x≠y’.]
If xOy is defined for all ordered pairs of elements x in X and y in Y then O is said to be defined unconditionally on X×Y. It is often helpful to set out the values xOy for selected values of x and y in the form of an operation table. The usual convention is that values of x are shown down the left column and values of y across the top row. The value of xOy is then shown at the cell in the table that is the intersection of row x with column y. In the case of a conditional operation there will be gaps in the table.
A genuine operation is one for which the value of xOy depends on the values of both x and y, that is we do not have xOy = k for all values of x and y (the case of a constant operation) or xOy = F(x) or F(y), i.e. the value depends only on one of the two variables, the case of a semi-constant operation. The table of a constant operation has the same entry everywhere (it is a dull array). The table of a semiconstant operation has dull ranks or files. A genuine operation has at least one non-dull rank and file.
An operation is closed in a set S if for each ordered pair (a, b) of elements of S it determines a unique element aOb also in S. The set S is called a groupoid with respect to O.
Theorem: If A and B are closed with respect toOthen so is A ∩ B. In other words the intersection of groupoids is a groupoid. The groupoids form an intersective system. Proof: If a and b are in A ∩ B they are in A and in B by definition of intersection, so aOb is in A and in B by definition of groupoid, so aOb is in A ∩ B by definition of intersection, so the intersection is a groupoid.
In a groupoid S any expression of the form aObOcO...Ok, suitably bracketed, represents an element of S. If A is a subset of S, then the intersection of all the groupoids H such that A is contained in H and H in S is the groupoid S/A generated by A, and it consists of the set A together with all elements of the groupoid that are expressible as O-combinations of elements of A.
An expression of the form aOaOaO...Oa, suitably bracketed, may be called a repeat of a. The set of all repeats of a, together with a itself, constitute the groupoid generated by the unit set {a}. Using numbers, we can introduce the index notation a°m = aO(aO(aO... (aOa) ... )) where there are m occurrences of a; or defining iteratively: a°(m+1) = aO(a°m). There is only one second repeat, aOa but there may be two third repeats aO(aOa) and (aOa)Oa.
The use of bracketing in algebra serves to avoid ambiguity where the order in which operations are performed can affect the result. It may sometimes be necessary to have several sets of brackets, some nested within others, to prescribe the correct order of operations. Operations within brackets are evaluated first, and those within inner brackets before outer ones. Three distinct styles of bracket are commonly used, namely round (...), square [...] and curly {...} brackets, usually nested in that sequence {[(...)]}. A type of bracketing that is useful but often passes unnoticed, because of the absence of any actual black-on-white printed sign, is spacing. For example, a/b × c/d means the same as (a/b)×(c/d), saving four brackets. The closed-up expressions like a/b and c/d are evaluated first. In some subjects further economy can be achieved by followng a convention that certain operations take precedence over others, for instance in arithmetic that ‘higher’ operations come before ‘lower’, i.e. powers before multiplication and multiplication before addition.
Excluding unnecessary brackets there is one way of bracketing an expression of one or two elements: a and ab; two ways with three elements: a(bc) and (ab)c; five ways with four elements: a(b(cd)), a((bc)d, (ab)(cd), (a(bc))d, ((ab)c)d; fourteen with five elements, and so on.
If there is an element a in a groupoid X such that aOx = x for all x in X then a is a left-identifier in the groupoid. Similarly a right-identifier b has xOb = x for all x. A left and right identifier is called an identity. Analogously a left-nullifier n is such that nOx = n for all x in X, and a right-nullifier m has xOm = m for all x. A left and right nullifier is a nullity.
Theorem. If a groupoid contains a left identifier and a right identifier then they are the same. A groupoid must thus either contain (a) no identifiers or (b) a single identity or (c) one or more one-sided identifiers, all of the same handedness. Proof: If a is left and b right identifier then a = aOb (by property of b) = b (by property of a).
Theorem. If a groupoid contains a left nullifier and a right nullifier then they are the same. A groupoid must thus contain either (a) no nullifiers or (b) a single nullity or (c) one or more one-sided nullifiers, all of the same handedness. Proof: If n is left and m right nullifier then n = nOm (by property of n) = m (by property of m).
An element i such that iOi = i is said to be idempotent. It identifies and nullifies itself on both sides. The groupoid generated by an idempotent is of order one; in this trivial groupoid the single element is both identity and nullity, but in a groupoid of two or more elements the identity and nullity, if both exist, must be different. If aOa = a for all a the operationOis said to be idempotent.
A pair of elements in a groupoid commute if aOb = bOa. An element is commutative if it commutes with every other element, and the operation and the groupoid are commutative if all the elements are. Commutativity of an operation is shown by symmetry of its table about the main diagonal (from top left to bottom right). From any operationOwe can derive a commute O defined by xOy = y O x for all x, y. ThenOis commutative meansO= O. For any operation the commute of the commute is the original operation.
Theorem. In a commutative groupoid there is a unique third repeat of any element, but there may be two different fourth repeats. Proof: aO(aOa) = (aOa)Oa by commutation. Similarly we find: ((aOa)Oa)Oa = (aO(aOa))Oa = aO(aO(aOa)) = aO((aOa)Oa) but the fifth case (aOa)O(aOa) may give a different result, e.g. if aOa = aOb = bOa = b and bOb = a then ((aOa)Oa)Oa = b but (aOa)O(aOa) = a. In the index notation the two fourth repeats are a°4 and (a°2)°2. The 14 fifth repeats reduce to not more than 3, viz a°5, (a°2)O(a°3) and aO((a°2)°2).
A groupoid is inner commutative if (aOb)O(cOd) = (aOc)O(bOd) for any a, b, c, d.
If an expression aObOcOdO... gives the same result no matter in what order the operations are carried out the operationOis called associative, and we can then permit the bracketless expression without ambiguity. We can also use the notation O(a,b,c,...). We call an element a of X social if, for all x and y in X we have (xOa)Oy = xO(aOy).
Theorem. A groupoid is associative if and only if (xOy)Oz = xO(yOz) for all x, y and z in the groupoid. In other words associativity of expressions of three elements implies associativity of expressions of any length. In other wordsOis associative in X if and only if every element is social. Proof: By induction. Suppose that all expressions of up to n elements are associative, then if n + 1 elements a, ..., k are combined in the form (aO...OdOe)O(fO...Ok) then this is equal to (aO...Od)O(eOfO...Ok) by the associative law for three elements. By repeated application of this process the leadingOcan be brought to the fore so that all bracketings of aO...Ok are equivalent to the form aO(bO...Ok). Thus all expressions of n + 1 elements are also associative.
Theorem. If a and b are social then aOb is social. In other words the set of social elements in a groupoid forms a subgroupoid. Proof: (xO(aOb))Oy = ((xOa)Ob)Oy by sociality of a, = (xOa)O(bOy) by sociality of b, = xO(aO(bOy)) by sociality of a, = xO((aOb)Oy) by sociality of b. It is interesting that all five ways of bracketing four elements occur in this proof.
Theorem. If a and b are commutative, and b is social, then aOb is commutative. Proof: (aOb)Ox = aO(bOx) by sociality of b, = (bOx)Oa by commutativity of a, = (xOb)Oa by commutativity of b, = xO(bOa) by sociality of b, = xO(aOb) by commutativity of a or b.
Theorem. In an associative groupoid, if a and b commute then their repeats commute. Proof: By alternate applications of the associative law and the commutative property we have: (aOa)Ob = aO(aOb) = aO(bOa) = (aOb)Oa = (bOa)Oa = bO(aOa), so b commutes with aOa. By repetition of this procedure we prove the general result for longer repeats.
Theorem. In an associative groupoid the relation ‘x is a left factor of y’ is
transitive. Proof: Write the relation x F y, meaning y = xOk for some k, then if
also y F z this means z = yOh for some h. So z = (xOk)Oh = xO(kOh) by association, so x F z.
This remains true if we postulate only reducibilty (?) instead of associativity.
Corollary: If in an associative groupoid x and y is each a left factor of the other,
then by transitivity, each is a factor of itself, i.e. each possesses at least one right
identifier of itself.
Theorem. In an associative groupoid with primitive (?) identity and no partial identifiers the relation ‘x is a left factor of y’ is an order relation. Proof: Transitivity follows from associativity as shown above. Antisymmetry follows since if x F y and y F x then y = xOh and x = yOk for some h and k; hence x = (xOh)Ok = xO(hOk) so hOk = e (since e is the only identifier); but e is primitive, so either h = e or k = e or both. In any case x = y. Reflexivity follows from the existence of the identity: x = xOe for all x.
Theorem. In an associative groupoid, if every element x has a unique right identifier x* then x* is idempotent and is the right identifier also of all elements of the forms bOx or bOx*. Proof: (1) x = xOx* = xO(x*Ox**) = (xOx*)Ox** = xOx** hence x** = x* and x*Ox* = x*. (2) bOx = bO(xOx*) = (bOx)Ox*. (3) bOx* = bO(x*Ox*) = (bOx*)Ox*.
If all elements are associative and commutative then the O-combination of any set of elements A is uniquely defined, and we can introduce notations such as OA = O{a,b,c,...} for this value.
Theorem. An inner commutative groupoid with identity is associative and commutative. Proof: (a) In the inner commutative law replace the two outer elements by the identity, this gives the commutative law. (b) In the inner commutative law replace one of the central elements by the identity, this gives the associative law.
An operator P is said to be linear with respect to an operationOif P(aOb) = (Pa)O(Pb) for all a and b.
An operation X is said to be distributive with respect to an operationO if p X (aOb) = (p X a)O(p X b), in other words the operator pX is linear for each p.
If distributivity applies on left and right we get (aOb) X (cOd) = [(aOb) X c]O[(aOb) X d] = [(a X c)O(b X c)]O[(a X d)O(b X d)] and (aOb) X (cOd) = [a X (cOd)]O[b X (cOd)] = [(a X c)O(a X d)]O[(b X c)O(b X d)]. hence [(a X c)O(b X c)]O[(a X d)O(b X d)] = [(a X c)O(a X d)]O[(b X c)O(b X d)].