## Reduction to Standard Form## &## Link TheoremNote: this page belongs to an older version of this website. It has been superseded by the following pages: The 'Case Analysis' Lemma and Exhaustive Case Analysis and the Standard Form of an Expression. All the general rules of arithmetic that we know about (so far) have proved to be demonstrable as equivalences in the pure algebra. The burning question, for Algernon, was whether Eventually, Algernon's efforts were crowned by success - he was able to answer his burning question. The solution depended on a method of reducing any expression to a standard form: that is what most of the present chapter will be about. ## The Depth LemmaGiven any algebraic expression, consider its arithmetic skeleton, that is, what is left when all the letters have been taken out of the expression, leaving a pattern of nested circles. Each space (enclosed by a circle C) in the pattern can be assigned a 'depth' by the following (recursive) rules: - the depth of a space is one more than the depth of its parent space (i.e. the space outside C)
- if a space has no parent (i.e. if it is the outermost space) its depth is zero
The
In this example, the content of the outer circle is an expression that is the product of seven prime factors, three of which are empty circles, four of which are non-empty. The non-empty factors contain 1, 1, 3 and 5 empty circles, respectively. In general there could be (say) P empty circles and Q non-empty circles, containing N So much for the bare skeleton; to get back to our expression we need to pepper the skeleton with letters. The general prime expression of depth 3 has the form:
e = ( ((a Here c stands for an expression of depth one or less; it includes all the inner factors whose intrinsic depth is only one. Each term a e = ( ((a with
C Thus all the inner factors apart from the first have been grouped into the expression C e = (a The number of factors is N
C with C Substituting this new form for C When we have performed Q steps of this type, we find that C (N Each of these many, many factors has the form (x where each x { a This whole process of 'horizontalization' of the expression e could be described (if you liked) as 'multiply-extended depth-reduction'. Exercise: In the algebra play-area, start with the expression
and transform it into
Hint: first rehearse the moves for converting (((a)b)c) into (ac)((b)c) until you have got them off pat. (The moves are given here.) So far, so good. If you give me a prime expression of depth 3 I can turn it into a (very composite) expression of depth 2. But what if you give me a general expression of depth n (with n≥3)? If the expression has depth n, that implies that it contains at least one space of depth n. Let all the spaces of depth n be sorted into groups, such that spaces in the same group share the same 'grandparent' (i.e. parent space of the parent space). (Given that n≥3, we can be sure that each deepest space Then the whole process may be repeated, until the intrinsic depth of the whole expression is reduced to no more than two. Q.E.D. ## The Variable LemmaSo much for the Depth Lemma: we are half way to standardizing our expression. To complete the process we need also the following
(OOO...)(OOO...)(OOO...)...OOO.. The expression itself will have the form
((a where each a
In each of a If x occurs in d, all other instances of x may be uncopied, and we are left with an expression of the form xC, where C is an expression not containing x. The expression may then be transformed into an expression of the desired form: xC = x((C)) = x(x(C)) = ((x))(x(C)) = (x(C)) ((x)(O)) . Otherwise, if (for some particular i) x appears in b
If x does not occur in b ((cx)(dx)(ex)...G) where c,d,e,G do not contain x. We can collect up the x's using modified collect, converting the factor into ((c)(d)(e)...G) (G(x)) which is of the form H(G(x)) (with H not involving x). If x occurs nowhere in b Each of the terms (c In sum, the expression e is equivalent to a product of factors of the form (Fx), factors of the form (G(x)), and factors of the form H (not containing x at all). Now, any product of factors of the form (Fx) may be transformed into an expression of the same form. Thus (ax)(bx)(cx)... = (( (ax)(bx)(cx)... )) = (x ((a)(b)(c)...) ) which is of the form (Ax), with A = ((a)(b)(c)...). Similarly, any product of factors of the form (G(x)) may be transformed into an expression of the form (B(x)); and the product of terms of the form H may be denoted C. Thus
e = (Ax) (B(x)) C which is of the form ( (xD) ((x)E) ) with D = (A)C To cover the cases where the expression contains no factors of the form (Fx), just put A=O (so D=C); to cover the cases where the expression contains no factors of the form (G(x)), just put B=O (so E=C). If there are no factors of the form H, then C = _ . Thus in all cases, e may be transformed into an expression of the form ( (xD) ((x)E) ) with D and E not containing x; and this may be converted, using flip once more, into (x(D)) ((x)(E)), which is the required form to prove the lemma.
e = (x(D)) ((x)(E)). Substituting x = _ into both sides of this equation, we obtain as a consequence e where e e = (x(e ## The Standard FormLet's have a look at some particular cases. Suppose our expression e involves only one letter, namely x. Then e may be reduced to the form (x(D)) ((x)(E)), with D and E not involving x, and therefore not involving any letters at all (since at no point in the proof of the lemmas did we introduce any new letters! See also the note just above.). D and E are therefore arithmetic expressions, which may be reduced to primitive values, i.e. to _ or O. This gives us just four possibilities for e:
We now know that any expression involving the letter x (and no other letter) can be reduced to one of these four. Moreover, no two of these expressions can be equivalent to one another, because 1) equivalent expressions remain equivalent when primitive values are substituted for their letters and 2) e=(x(D))((x)(E)) is equivalent to D when _ is substituted for x, and to E when O is substituted for x. Thus e=(x(D))((x)(E)) is equivalent to e'=(x(D'))((x)(E')) if and only if D=D' and E=E'. Next, let us progress to two letters, x and y. Our expression e may be reduced to e = (x(D))((x)(E)) with D and E involving only the letter y. But then D and E may be reduced to the forms D = (y(F)) ((y)(G)) Substituting back into e we obtain e = (x( (y(F)) ((y)(G)) ) ((x)( (y(H)) ((y)(I)) ) e has been reduced to a product of four factors. When primitive values are substituted for x and y, just one of the four factors is non-vanishing and therefore determines the value of e. For example, when x=_ and y=O, then e=G, and so on. When our expression e involves three letters, x, y and z, say, we can reduce e to the form (xyz(J)) (xy(z)(K)) (x(y)z(L)) (x(y)(z)(M)) ((x)yz(N)) ((x)y(z)(P)) ((x)(y)z(Q)) ((x)(y)(z)(R)) - and so on.
Note that when actual primitive values are substituted for the tokens J, K, L, M, N, etc., any factor whose associated primitive value is _ drops out; while if Q, say, is O (Q being the value taken by e when O is substituted for x, O for y and _for z), then (Q) is _ and the factor containing Q becomes simply ((x)(y)z). In general, we have that e (involving x, y and z) may be converted into a product of prime expressions, picked out of the set { (xyz),(xy(z)),(x(y)z),(x(y)(z)),((x)yz),((x)y(z)),((x)(y)z),((x)(y)(z)) }. Thus the various equivalence classes of expressions are in one-to-one correspondence with the subsets of this set. The number of subsets (given that the set has eight members) is 2 Going back to two variables, we are concerned with the subsets (16 in number) of { (xy),(x(y)),((x)y),((x)(y)) }. The subsets may be labelled by the binary numbers running from 0000 to 1111, where a 1 in the nth place indicates that the nth member of the set
(We made liberal use of each way to simplify the expressions.) All expressions involving just two letters x and y reduce to one of these 16 forms. ## Link TheoremWe aim to prove the following:
Sometimes, when comparing different expressions such as e and f, it may be that some letters appear in one expression but not the other. Let A be the set of all the letters that appear in either of the two expressions (or both). Then one may consider the 'extended value-table' of e, which records the values taken by e when values are assigned to all the letters in A, with the understanding that the value assigned to a letter in the set A, but not actually appearing in e, makes no difference at all to the value of e. The same may be done for f. The point is that the value-tables of e and f may then be compared, even though e does not contain exactly the same set of letters as f. (This does not necessarily stand in the way of their equivalence, as the each way move illustrates.) Within this proof, we shall denote equivalence in the sense 'valid as a general rule' by the ordinary equals sign = ; and pure algebraic equivalence by the sign ≡ . If g is an expression, by g We first prove the 'if' part of the theorem. Suppose e ≡ f. Then there is a chain of legal moves by which e may be transformed into f. Suppose g is turned into h by applying one of the set of initial moves (using the latitude given by the canons of interpretation, embedding and substitution). Then, we claim, the value-table of h is the same as the value-table of g. The question is, can (firstly) any application of a → ((a)) to a sub-expression a within g make any difference to the value-table of g? The answer is no, because the value of ((a)) is the same as the value of a under any circumstances. The same applies to O → O a and to a(b) → a(ab). What this boils down to is 1) each of the initial equations of the pure algebra is valid as a general rule of the arithmetic; 2) the canons of interpretation were first established as a valid means of obtaining new general rules out of old ones; then adopted as axiomatic (unproven) for the pure algebra. Since each single move does nothing to the value-table, neither does the chain of moves connecting f with e. Therefore the value-table of f coincides with that of e, which means that e=f is valid as a general rule. We now pass to the 'only if' part of the proof. Suppose e = f. Let e be transformed (in the pure algebra) into its standard form e e ≡ e similarly, f ≡ f Then, since legal moves do not affect value-tables (as shown in the first part of this proof), and since e = f, e But the standard form of an expression is essentially the same as its value-table. If e e ≡ f, and we are done. We note a powerful corollary of the Link Theorem:
ef ≡ _ then e ≡ _ and f ≡ _ .
back to The 'Case Analysis' Lemma |