## CL-AlgebrasSuppose 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 a´ and given any finite collection of elements, a, b, c etc of K, one may form their {abc...} . Suppose the law of combination has the properties of - Permutability: the order in which the elements are written within the curly brackets is immaterial, so, for example,
{abcde} = {dcaeb} ; and, - 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: - wrap/unwrap: For all a, ((a)) = a ; that is, the complement of the complement is the original element
- delete/undelete: For all a, O a = O ; that is, the combination of a with 1' is 1'
- 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
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 ## Examples
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
2 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 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.
The laws of combination and complementation, in this example, will be more easily explained if the numbers
are written in 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 The complement of a number is the result of changing each 0 into a 1 and It is clear that 2 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:
a(b) = a(ab).
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 |