Algernon - the Algebraist

General Rules

Algernon was Arthur's twin brother. He liked what his brother had done, but he was also intrigued, from an early age, by his uncle's rule for reducing an expression: wherever (O x) occurs as a sub-expression of a greater expression, it may be rubbed out. Here x is a sort of shorthand for 'any expression you like'. The rule is powerful, because it covers so many situations in one concise statement.

Another way of putting it: any sub-expression of the form (Ox) may be rubbed out.

Or, again:

(Ox) →

is an allowed transformation (whatever x is, and wherever the pattern (Ox) occurs). Or indeed:

(Ox) =    ,

since if any particular (Ox) can be reduced to _ , then _ can be built up into into (Ox) by reversing the steps. Thus any expression of the form (Ox) can be constructed out of _ .

We know this is a valid equation, because we justified the rub-out method back in the son's chapter. But let's have another go at it. Given any particular x, x reduces either to _ or to O. In the first case

(Ox) = (O) =     [cancel] ;

in the second case,

(Ox) = (OO) = (O) [repeat] =     [cancel].

There is no other case, therefore, whatever particular expression is substituted for x,

(Ox) = _ .

Here is a second example of a general rule:

x x = x .

This asserts that any expression, written down twice (we must substitute the same expression for x, every time it appears in the equation), is equivalent to the same expression, written down just once. Now, any such expression reduces to _ or O. In the first case, x x reduces to _ , so x x = x. In the second case, x x reduces to O O, which reduces to O, so x x = x. Therefore x x = x in all cases. We may call this rule by the same name we have used already, namely repeat.

Here are some more general statements which may be tested in the same manner:

((x)) = x   unwrap
((x)x) =     complements

and here are some involving two or more unknowns. (Where there are two unknowns, there are four cases to try: (i) x=_, y=_; (ii) x=_, y=O; (iii) x=O, y=_; and (iv) x=O, y=O. Where there are n unknowns, there are 2n cases to try.)

((p)(q)) r = ((pr)(qr))   distribute/collect
((a)(b)) ((a)b) = a   each way
(((a)b)c) = (ac) ((b)c)   reduce-depth
( a (b) (c) ) (a(r)) = ( a (br) (cr) )   modified distribute/collect
( (a(r)) (br) ) = ((a)(r)) ((b)r)   flip

Now, testing all the possibilities is certainly a reliable way to test whether or not a general rule is valid; but as the conscientious reader will have just discovered, it quickly becomes rather tedious as the number of variables increases. Is there a better way?

Well, there is at least an alternative approach. This is a method of deriving new general rules from old ones. The method of derivation is such that if the old rules are valid, then the new ones are guaranteed to be valid without having to be tested. It sounds almost too good to be true, doesn't it?

Let's have a look at an example. From

(Ox)= _

it follows that for any x,

((Ox)) = O.

But from the rule ((y)) = y, for any y (the rule we have called unwrap), we can deduce that

((Ox)) = Ox,

for any x, therefore,

Ox = O   delete/insert

Thus the new rule is an easy consequence of the two rules (already established) that we used in the argument. To verify it, we don't have to resort to the reduction of the expression x to _ or O; instead, we can deduce the rule from other rules.

Here are two more rules that can easily be obtained from those already given:

x (x) = O
((x)x) y = y .

The Algebra of the Mark

It is convenient, at this point, to introduce the notion of an 'algebraic expression'. An algebraic expression is a pattern of circles and letters. As usual, the circles are not allowed to intersect, and each letter - or 'unknown' - has to be either inside or outside any given circle. If you like, an expression is what appears on one side of a general rule. Conversely, a general rule states that two algebraic expressions are equivalent: meaning that they reduce to the same primitive expression whenever particular sub-expressions are substituted for the 'unknowns' a,b,c..x,y,z... (The old sort of expression made of circles but without any unknowns, we now term an 'arithmetic expression'. The set of arithmetic expressions is of course a subset of the set of algebraic expressions.)

Any valid rule may be regarded as a 'transformation' of one algebraic expression into an equivalent one.

What are the 'moves' in the game of deducing new rules from old ones? Algernon suggested that there are essentially three kinds of move:

(i) Embedding

Any valid rule can be 'embedded' in a larger expression. For example, the rule x = ((x)) can be embedded within the expression (abx)e giving us the rule

(abx)e = (ab((x)))e.

For, if ((x)) always reduces to the same primitive expression as x, it is clear that the expression on the right will always reduce to the same primitive expression as the expression on the left, whatever particular expressions are substituted for a,b and e.

(ii) Substitution

From the rule

(p(p)) = _

we may deduce the rule

( a(b) (a(b)) ) = _ .

Here we have substituted for p the algebraic expression a(b) . For the first rule applies to any particular expression p, including the one that results when particular expressions are substituted for a and b in a(b). Another way of saying this: if the first rule is true of all expressions p, then it is true, a fortiori, of expressions of the form a(b). In general, we may substitute any algebraic expression for any unknown in a rule, and obtain a second rule, equally valid, but more specialized.

A rule may be transformed by embedding and substitution simultaneously.

(iii) Concatenation

If a=b is a rule, and b=c is a rule, (where a, b and c all stand for algebraic expressions) then a=c is a rule.

By using the three kinds of move together, some surprising transformations can be achieved. For example, the following is an embedding of the rule x = ((x)) (wrap, the reverse of unwrap):

(ab)b = (((a))b)b ,

as is this:

(((a))b)b = (((a))((b)))b.

The following is obtained by substituting in distribute (with (a) for p, (b) for q, b for r):

(((a))((b)))b = (((a)b) ((b)b) ) ;

which we follow by an embedding of complements:

(((a)b) ((b)b) ) = (((a)b)) ;

and an application of unwrap (with (a)b substituted for x):

(((a)b)) = (a)b.

Finally we join these five rules together in a chain to obtain

(ab)b = (a)b   uncopy

(the reverse move being copy).

Another way of describing what has happened: the expression (ab)b has been transformed successively by wrap, wrap, distribute, complements, unwrap into the expression (a)b, which is, therefore, equivalent to(ab)b. Although we could, if we wanted, check the equivalence of the expressions by substituting all possible value-combinations for a and b, there is really no need for that, since we got from one to the other by applying valid transformations in valid ways.

In a manner of speaking, we could say that we got from E = (ab)b to F = (a)b without ever 'touching the ground'; that is to say, we never had to use directly the fact that any particular arithmetic expression is equivalent to one or other of the two primitive expressions. That is why Algernon liked to call this method of getting from one set of rules to another, the 'high-wire act'.

The copy/uncopy rule turns out to be rather useful. Even though it is derivable (as we have shown) from the rules (un)wrap, complements and distribute the derivation is fairly complicated - it is by no means so obvious as to be trivial. In general, it would seem to be an almost hopeless task to determine whether a new general rule is derivable from those that are already known.

Could there be a set of core rules, that we ought to take with us, as we flee our burning city, in order to ensure that we can regenerate all the general rules when we restart civilization in another place?

Algernon often wondered about it, but didn't seem to be able to get a grip on the question. That would be a task for the next generation.