This is one of a series of posts I am writing to help me develop my thoughts about how particular topics in my book** Abstracting Algebra** (“**AbAl**“) should be organized. This post concerns the **relation between substitution and evaluation** that essentially constitutes the definition of algebra. The Mathematica code for the diagrams is in Subs Eval.nb.

## Substitution and evaluation

This post depends heavily on your understanding of the ideas in the post Presenting binary operations as trees.

### Notation for evaluation

I have been denoting evaluation of an expression represented as a tree like this:

In standard algebra notation this would be written:\[(6-4)-1=2-1=1\]

#### Comments

This treatment of evaluation is intended to give you an intuition about evaluation that is divorced from the usual one-dimensional (well, nearly) notation of standard algebra. So it is sloppy. It omits fine points that will have to be included in **AbAl**.

- The evaluation goes from bottom up until it reaches a single value.
- If you reach an expression with an empty box, evaluation stops. Thus $(6-3)-a$ evaluates only to $3-a$.
- $(6-a)-1$ doesn’t evaluate further at all, although you can use properties peculiar to “minus” to change it to $5-a$.
- I used the boxed “1” to show that the value is represented as a trivial tree, not a number. That’s so it can be substituted into another tree.

### Notation for substitution

I will use a configuration like this

to indicate the data needed to substitute the lower tree into the upper one at the variable (blank box). The result of the substitution is the tree

In standard algebra one would say, “Substitute $3\times 4$ for $a$ in the expression $a+5$.” Note that in doing this you have to name the variable.

#### Example

“If you substitute $12$ for $a$ in $a+5$ you get $12+5$”:

results in

#### Example

“If you substitute $3\times 4$ for $a$ in $a+b$ you get $3\times4+b$”:

results in

#### Comments

Like evaluation, this treatment of substitution omits details that will have to be included in **AbAl**.

- You can also substitute on the right side.
- Substitution in standard algebraic notation often requires sudden syntactic changes because the standard notation is essentially two-dimensional. Example: “If you substitute $3+ 4$ for $a$ in $a\times b$ you get $(3+4)\times b$”.
- The allowed renaming of free variables except when there is a clash causes students much trouble. This has to be illustrated and contrasted with the “binop is tree” treatment which is context-free. Example: The variable $b$ in the expression $(3\times 4)+b$
*by itself*could be changed to $a$ or $c$, but in the*sentence*“If you substitute $3+ 4$ for $a$ in $a\times b$ you get $(3+4)\times b$”, the $b$ is*bound*. It is going to be difficult to decide how much of this needs explaining.

## The axiom

The Axiom for Algebra says that the operations of substitution and evaluation **commute**: if you apply them in either order, you get the same resulting tree. That says that for the current example, this diagram commutes:

**The Only Axiom for Algebra**

In standard algebra notation, this becomes:

**Substitute, then evaluate:**If $a=3\times 4$, then $a+5=3\times 4+5=12+5$.**Evaluate, then substitute:**If $a=3\times 4$, then $a=12$, so $a+5=12+5$.

Well, how **underwhelming**. In ordinary algebra notation my so-called Only Axiom amounts to a mere *rewording*. But that’s the point:

The Only Axiom of Algebra is what makes algebraic manipulation work. |

### Miscellaneous comments

- In functional notation, the Only Axiom says precisely that $\text{eval}∘\text{subst}=\text{subst}∘(\text{eval},\text{id})$.
- The Only Axiom has a symmetric form: $\text{eval}∘\text{subst}=\text{subst}∘(\text{id},\text{eval})$ for the right branch.
- You may expostulate: “What about associativity and commutativity.
*They*are axioms of algebra.” But they are axioms of*particular parts*of algebra. That’s why I include examples using operations such as subtraction. The Only Axiom is the (ahem)*only*one that applies to*all*algebraic expressions. - You may further expostulate: Using monads requires the
**unitary**or**oneidentity**axiom. Here that means that a binary operation $\Delta$ can be applied to one element $a$, and the result is $a$. My post Monads for high school III. shows how it is used for associative operations. The unitary axiom is necessary for representing arbitrary binary operations as a monad, which is a useful way to give a theoretical treatment of algebra. I don’t know if anyone has investigated monads-without-the-unitary-axiom. It sounds icky. - The Only Axiom applies to things such as single valued functions, which are unary operations, and ternary and higher operations. They also apply to algebraic expressions involving many different operations of different arities. In that sense, my presentation of the Only Axiom only gives a special case.
- In the case of unary operations, evaluation is what we usually call evaluation. If you think about sets the way I do (as a special kind of category), evaluation is the same as composition. See “Rethinking Set Theory”, by Tom Leinster, American Mathematical Monthly, May, 2014.
- Calculus functions such as sine and the exponential are unary operations. But not all of calculus is algebra, because substitution in the differential and integral operators is context-sensitive.

## References

### Preceding posts in this series

- Abstracting algebra. An outline of the proposed book.
- Presenting binary operations.
- Presenting binary operations as trees.

##### Remarks concerning these posts

- Each of the posts in this series discusses how I will present a small part of
**AbAl**. - The wording of some parts of the posts may look like a first draft, and such wording may indeed appear in the text.
- In many places I will talk about how I should present the topic, since I am not certain about it.

### Other references

- Abstraction in abstractmath.org.
- Algebra is a difficult foreign language. G&G post.
- Monads for high school III. G&G post.
- Monads in Wikipedia
- “Rethinking Set Theory”, by Tom Leinster. American Mathematical Monthly, May, 2014.
- Symbolic language of math in abstractmath.org.
- Visible Algebra I.G&G post.
- Visible algebra I supplement. G&G post.
- Visible Algebra II. G&G post.

This work is licensed under a Creative Commons Attribution-ShareAlike 2.5 License.