Arthur - The Arithmetician
Arthur was a strange child. With his toys he played elaborate games that involved each toy rigidly following a set of rules, specially thought up by Arthur for that particular toy. He felt that the art of evaluating tree-signs needed to be reformed. The way his mother did it was too dependent on human faculties. It seemed to depend on knowing what a mark is and understanding what it does (i.e. marking). What he longed for was a way of doing it that was automatic, similar to the way a machine, or perhaps a small furry animal, would tackle the task. Eventually his longing was satisfied...
Forget about the 'meaning' of the mark, he said, i.e. that it is a mark. I can give you a set of rules (just two in number) for transforming one expression into another. Starting with any expression, I can guarantee that you will be able to reduce it to one of the primitive expressions, O or _ , just by applying my rules over and over.
This game of legal transformations I am going to call 'The Arithmetic of the Mark'. Here are my two rules of transformation:
(When typing, I'll represent the rules as follows:
(O) →
and
OO → O
In the first rule, the encircling circle is represented by a pair of brackets - you just have to imagine the brackets joining up below and above the line of text.)
Ach, the beauty of it! (Arthur used to say). No words anywhere - nothing about 'marks' - how I hate that word! Just symbols, and only one of them (the right-pointing arrow → ), apart from the circles themselves.
Now Arthur was a man of few words, and there was quite a lot he left unsaid about his two 'legal moves'. Here are some things he could have said, if he'd had a mind to. The first move says that a 'double circle' (an empty circle inside another circle) can be replaced by blank space; the second that two empty circles side by side can be replaced by a single empty circle. But what if we are faced with an expression that doesn't consist either of a double circle or two circles side by side? What move can we make then? The answer is that the rules have a certain latitude of interpretation. The double circle can appear anywhere within an expression. It may be deep down in the expression, with many more circles surrounding it. There may be other signs in the same space with it. The context is irrelevant. If you see a double circle anywhere, you may replace it with blank space. The only proviso is that the inner circle of the doublet is strictly empty.
Very similar remarks apply to the second allowed move. The context is immaterial. Wherever there are two empty circles side by side, no matter what else is in the same space with them, you can replace them with just one empty circle.
Let's see how an expression can be reduced, using Arthur's rules. Let's get to work on the same expression we used in the last chapter (Valerie's).
Now, looking at this I can see two empty circles side by side; I can also see a double circle. This gives us two points of attack, at which we can begin our work of demolition. (More will appear as we go on, as we'll see). It so happens that both of these 'points of attack' lie in the same space, but that is immaterial. It also doesn't matter which point we choose to attack first (a fact which will become clearer as we go on). Suppose we take the double circle first, and obliterate it:
Now there is only one move available: replace the two side-by-side circles by one circle:
Now, see, a new opening has appeared: a double circle, that can be obliterated:
- and a new double circle, that can again be rubbed out:
- and finally we are done: there is no further move that we can make. But that is no matter, for we have arrived at one of the two primitive expressions (O and _ ). We have arrived at the value of the original expression: in this case, 'Yes! cut it down!'.
Arthur made the claim that any expression can be reduced, using the two legal moves, to one or other of the primitive expressions. His argument went like this:
Given any expression e, draw the dot-diagram of e (as we did in the last chapter). All we are really interested in are the levels of the various circles, that is, how far down they are from the top of the diagram.
Now, either there are no empty circles within e, in which case e is already the empty expression; or there are some empty circles, each of which has a level in the dot-diagram. Pick a circle C from among the lowest-level circles.
Either C is alone in its space; or C shares its space with some other circles. These other circles must also be empty; for otherwise, C would not after all be at the lowest level.
In the first case, either C is at the top level, in which case the expression has been reduced to O; or C is contained in another circle D, in which case C and D together can be replaced by the empty expression, and we obtain an expression f containing two fewer circles than e.
In the second case, let D be one of the other empty circles in the same space as C. Then C and D together may be replaced by a single circle, and we obtain an expression f with one fewer circle than e.
Summing up, either e is already primitive; or e can be transformed into a smaller expression f.
In the second case, we can treat f in the same manner as we treated e, and reduce it, if necessary, to a smaller expression g; and so on. In this way, we must arrive at a primitive expression in a finite number of steps.
I find that all pretty convincing; don't you?
There remained the question, however, whether the order in which the reduction operations were performed could make any difference to the final result. But Arthur saw that this was really just the same question that had already come up concerning his uncle's original reduction process, and that, like the original question, it was answered by his mother's exhaustive mark-up procedure. That showed that any expression had an unambiguous value: all that remained was to show that neither of the two legal moves made any difference to the mark-up value. To do this, we just mark up the two rules:
Now, Arthur could have left it at that, but he couldn't get rid of the following thought: suppose that two completely different expressions, e and f, can both be reduced (legally) to a single empty circle. Then the expressions have the same value and are in that sense 'equivalent'. Wouldn't it be rather nice if, in such a case, e could actually be transformed into f using legal moves? Clearly this can't be done with the existing moves, since each of them always reduces the number of circles; but why not allow them to be put into reverse? Then we will have two more legal moves:
→ (O)
and
O → O O .
(Again the moves have no effect on value; and again it is to be understood that context is immaterial. The interpretation of the rules is that any bit of blank space anywhere within an expression may be transformed into (O) at will; and any empty circle anywhere within an expression can be 'copied' to make two empty circles where there was one before.)
With the help of the new moves it is no problem to transform e into f. First transform f into O, noting down the moves as you perform them. Then transform e into O, then transform O into f by performing the noted down moves in reverse (and in reverse order). The overall result: e is transformed into f. It would all work just the same if e and f could both be reduced to _ , rather than to O. (Sometimes, of course, there will be a more direct route from e to f; but this fall-back method can be relied on to work in all cases.)
It's time for some play. Start by clicking on the button labelled 'Free Construction'. This will allow you to build up an expression, just as in the previous play-areas. When you are satisfied, click on the 'Arithmetic rules' button, and see if you can reduce the expression to its value. The first allowed move (replace (O) by _ ) is done by shift-clicking within the inner circle. The second allowed move ( OO to O ) is done by dragging one empty circle into the other. A small circular cursor will show you what is happening.
Once you've mastered the reduction game, you can move onto construction. In arithmetic mode (if necessary, click the Arithmetic Rules button in order to get into arithmetic mode) you can create a marked mark by clicking anywhere (without shift-key pressed); and you can copy an empty circle by dragging from the empty circle into the space outside it.
You should be able to create any desired expression - but only if you start from the correct primitive expression!
The equals sign
Let us write (for example)
to assert that the expression on the left may be transformed into the expression on the right, and vice versa (the 'vice versa' is always possible: just reverse the steps). Clearly, if two expressions can both be reduced to the same primitive expression, then an equals sign may be written between them; otherwise, not.
The four legal moves may be regarded as springing from two fundamental equations (the axioms of the arithmetic):
(O) = cancel
O O = O repeat
We have given each equation a handy name to make reference to it easier.
... next: Algernon, the Algebraist
back to Valerie