## The Mutual Dominance Lemma
The proofs of equivalence, given in the last chapter, have their easy parts and their more difficult parts. In general, the easy parts are where an expression has to be reduced, to _ or O; the difficult parts are where a creative choice has to be made, for example, which expression to copy, where to copy it to, and even worse, what expression to bring into being in the operation we have called undelete.
Absolutely any expression may be brought forth out of an empty circle - which
sounds marvellous; but really offers Reduction is easier than creation: this is what makes the Mutual Dominance Lemma so attractive. As we shall see, it transforms the task of proving an equivalence. Formerly, this was a matter of discovering a sequence of steps, leading from one expression to the other - from A to B, say. Henceforth, there will be an alternative approach, namely, to reduce a third expression, constructed in a standard way out of A and B, to the empty expression. We start with a definition: Given two expressions A and B we say that 'A dominates B', or A≥B, if and only if AB = A. Thus A is sufficiently powerful in relation to B that it outshines or eclipses B when put next to it; conversely, if it wants to, it can produce B from under its petticoat. The second initial equation (delete) tells us that the empty mark O dominates every expression: O A = O; on the other hand, it is of the very essence of the empty expression that it is dominated by every expression. It is the peerless doormat among expressions: A _ = A. Here are some easy lemmas concerning the relation of dominance:
CD≥C ; in other words, a product dominates its factors.
(A(B)) = (A(AB)) [copy] Conversely, given that (A(B))= _ , then AB = A((B)) = A(A(B)) = A, so A dominates B.
A = AB = B.
If (A(B)) = _ and ((A)B) = _ then A=B. We will refer to Lemma 6 as the 'Mutual Dominance Lemma'. It allows us to break the task of proving equivalence between A and B into two parts, each partial task consisting of reducing an expression to the empty expression.
The converse is obvious; the main statement can be proved directly, as will be shown below, but it also follows from the Mutual Dominance Lemma with the help of the following Void Factor Theorem.
A = AAB [premise] (Or: AB≥A by Lemma 1, then apply Lemma 7.) Similarly, B = _ . Applying this theorem to the case in hand, if the expression given in Lemma 8 is equivalent to _ , then so are both the factors, and thus the premises of Lemma 6 are satisfied.
A = A (A(B))((A)B) [premise]
(A(B))((A)B)
[A|B]. When we are working graphically, as opposed to typographically, we will use the form The topic of the equivalence expression is explored in a separate page Development of the Equivalence Expression. For the moment, we just note the important fact that, thanks to Lemma 8, the task of proving two expressions equivalent can always be changed into the task of proving that a third expression - namely, [A|B] - can be reduced to the void _ .
If A(B) = O and (A)B = O then A = B. The equation to be proved is z ( (a)(b)(c)(d)... ) = ( (za) (zb) (zc) (zd) ... ), so we have to prove, firstly, left dominates right: z ( (a)(b)(c)(d)... ) (( (za) (zb) (zc) (zd) ... )) = O and secondly, right dominates left: (z ( (a)(b)(c)(d)... )) ( (za) (zb) (zc) (zd) ... ) = O The first of these is easiest. The expression to be reduced is (drawn with just three inner factors, but there could be any number). The right-hand factor can be unwrapped, then each occurrence of z uncopied. Then (a), (b), (c)... may be uncopied from the left-hand factor, eventually leaving it empty. The empty circle can then destroy everything outside it, and we are left with O. To verify the second dominance relation, we have to reduce the expression Our first move is to copy the left-hand factor into the circle containing z and a. That inner factor becomes Now uncopy the z, unwrap the inner factors, uncopy a out of (a). The factor has turned into The empty circle destroys everything within its sphere of influence, and the factor vanishes. We still have the other inner factors, i.e. (bz) and (cz)... to deal with; but they can be got rid of in exactly the same way. Thus the second factor of the whole expression has been turned into O, which destroys the first factor, and the whole expression reduces to O. The second relation of dominance is proved, and hence the equivalence of the left and right expressions in the original equation. Now enact the proof in the play area!
Exercise: Prove by Mutual Dominance modified distribute, depth-reduction, flip and each way. back to The CL-calculus (Part II) on to The 'Case Analysis' Lemma See also: |