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.
Send to Kindle
can mean either iterated composition or multiplication of the values. For example, 
can mean 
or 
. This is exacerbated by the fact that in undergrad calculus texts, 
refers to the arcsine, and 
refers to 
. This causes innumerable students trouble. It is a Big Deal.
" means open interval once and GCD once in the same sentence!) I think the only part that is a Big Deal, or maybe Medium Deal, is the fact that the value of a function 
at an input 
can be written either "
" or as "
". In fact, we do without the parentheses when the name of the function is a convention, as in 
or 
, and with the parentheses when it is a variable symbol, as in "
.) This causes some beginning calculus students to think "