CL-Algebras

Suppose one has a set K, with a 'law of complementation' and a 'law of combination'. That is to say, to any given element a of K there corresponds an element of K, called the complement of a, and written

a´

and given any finite collection of elements, a, b, c etc of K, one may form their combination, also an element of K, and written

{abc...} .

Suppose the law of combination has the properties of

  1. Permutability: the order in which the elements are written within the curly brackets is immaterial, so, for example,
    {abcde} = {dcaeb} ; and,
  2. Dissociativity: the set of elements within the curly brackets can be split into parts or subsets. If the subsets are first combined, then the results combined in turn, the result is the same as if all the elements were combined at once. For example:
    {abcdefghijk} = { {ceghk}{aj}{bdfi} }
    (and then the parts can be subdivided themselves; and so on for as long as you please... )

Suppose further that the property of dissociativity is even more general, and one or more of the subsets in the splitting is allowed to be empty, for example:

{abcdefghijk} = { {ceg}{ }{hk}{aj}{ }{bdfi} }.

For this to make sense, we need to assume that { } is, or stands for, a special element of K, which we may denote 1, and which has the property that

{1a} = a

for all a. That is, the combination of 1 with a is always just a (so 1 behaves like 1 in ordinary, numerical multiplication). We may refer to this as the 'unit-property'.

Then any non-empty CL-expression (circle-and-letter expression), not containing an empty mark O, may be interpreted as follows:

  • each letter is to be interpreted as an element of K
  • if a letter occurs more than once, it represents the same element each time
  • if several letters or sub-expressions lie in the same space, collectively they represent the element of K that is the result of combining the corresponding elements
  • any sub-expression that consists of a circle surrounding another expression E represents the complement of whatever element is represented by E

The empty expression may be interpreted as representing the unit 1. Within any expression, any piece of empty space may be interpreted, if you will, as a sub-expression representing 1. This will make no difference to the value of the expression, thanks to the unit-property of 1.

For consistency, an empty circle must be interpreted as the complement of 1, that is, 1'; for 1, like any other element, must have a complement.

With these additional interpretations, any CL-expression whatever may be taken to represent an element of K: the one that results when each letter is interpreted as a K-element, and the K-elements are then subjected to a scheme of combinations and complementations - the scheme being determined by the circle-structure of the expression.

Similarly, any well-formed expression made out of letters, curly brackets and ' may be converted into a CL-expression; and this is the notation that we will use from now on.

Now suppose further that the laws of complementation and combination satisfy the following constraints:

  1. wrap/unwrap: For all a, ((a)) = a ; that is, the complement of the complement is the original element
  2. delete/undelete: For all a, O a = O ; that is, the combination of a with 1' is 1'
  3. copy/uncopy: For all a and b, a(b) = a(ab) ; that is, the combination of a with the complement of b is the same as the combination of a with the complement of the combination of a with b

Note:

  • The first constraint involves only the operation of complementation
  • Let the complement of 1 be denoted 0 (zero). Then 0 has the zero-property: combined with any other element it makes zero, like zero in multiplication
  • The third constraint constrains the interplay of complementation and combination

Definition A set K, with two operations, complementation and combination, satisfying all the conditions mentioned so far (including the existence of a unit, and the three additional constraints), we term a CL-Algebra.

As we have already seen, once K-elements are substituted for the letters, any CL-expression may be interpreted as a K-element. Given that K and its operations satisfy the three constraints, it is clear that CL-equivalent expressions have the same K-value (i.e. represent the same K-element). Thus all our discoveries in the CL-calculus translate into discoveries about CL-algebras.

Examples

Example 1: CL-expressions using N letters

Let K be the set of equivalence classes of circle-and-letter expressions involving the N letters a, b, c ... up to k. (In the section Exhaustive Case-Analysis we discovered that the number of such equivalence classes is actually 22N.)

Let α, β, γ ... be elements of K; we define their combination as follows: pick expressions A, B and C ... to represent the equivalence classes α, β, γ ... respectively. Let the expressions A, B, C ... be combined in the usual way - by writing them side by side on the same piece of paper, making an expression P. Then the combination {αβγ...} is defined to be the equivalence class π to which the expression P belongs.

(Exercise for the reader: 1) verify that this is a good definition, i.e. that it makes no difference to the final answer π if different representatives are chosen instead of A, B, C ... ; 2) verify that the law of combination is permutable and dissociative as required.)

Similarly, the complement of α is defined to be the class to which (A) (A encircled) belongs.

1 is the equivalence class to which _ belongs; 0, that to which O belongs. It is clear that the 3 constraints are satisfied by these laws of combination and complementation, implying that K is a CL-algebra.

Example 2: The numbers from 0 to 2N-1

The laws of combination and complementation, in this example, will be more easily explained if the numbers are written in binary notation. So each element of K is represented by a sequence of 0's and 1's, of length N.

Given a set of such numbers or sequences, their combination is defined as follows: Write the numbers in a vertical column. Let's call the leftmost bit of each number the first bit, the next one, the second bit, and so on up to the Nth bit. Now focus on the first bits of all the numbers in the column; let all these bits (each of which is 0 or 1) be multiplied together; the answer is the first bit of the combination. Then the other bits of the combination are found in the same way. To put it in a nutshell, the combination is found by bitwise multiplication. Note that a single zero in a column of bits is enough to make the corresponding bit of the combination equal to zero; a 1 means that all the bits in the column are 1.

The complement of a number is the result of changing each 0 into a 1 and vice versa (or, subtract the number from 2N-1).

It is clear that 2N-1 (in binary: 111...1) has the unit-property and so will play the role of _ in the algebra. It is also clear that double complementation amounts to 'do nothing'; and that 0 has the zero-property. Satisfaction of the 'copy' constraint is more interesting.

In a general algebra, let's say that elements b and c are 'a-equal' if and only if

ab = ac .

In this particular case, what does it mean for two elements to be a-equal? The element a may be thought of as a mask, transparent where there is a 1 in the binary representation of a, and opaque where there is a 0. Then b and c are a-equal if and only if they appear equal as seen through the mask that is a. Thus only the bits corresponding to the 1's in a have to be equal; if a has a zero in a particular place, then that bit will automatically be equal (namely zero) in ab and ac.

Now given this interpretation of a-equality, it is clear that the complements (b) and (c) will be a-equal if and only if b and c are a-equal.

It is also clear that for any element e,

aae = ae ;

applying the mask a second time makes no difference. (Indeed, it is clear anyway that aa=a.) Now consider the following lemma:

Lemma: Suppose, in a particular algebra, it is the case that (b) and (c) are a-equal if and only if b and c are a-equal; and also that ae is always equal to aae. Then, for all a, b and c,

a(b) = a(ab).

Proof: b and ab are a-equal, since

ab = aab ;

therefore (b) and (ab) are a-equal; which is what had to be proved.

(Conversely, if the 'copy' axiom holds, then ab=ac implies a(b)=a(c); proof left as exercise for the reader.)

Therefore, in this case too, our laws of combination and complementation satisfy the three constraints, and K is a CL-algebra.

back to An Application of the CL-Calculus (Set Theory)

on to Boolean Algebras

home | Table of Contents