|
A binary operation determines its underlying set.
Thus if we talk about an arbitrary binop $\Delta$, we don’t have to give a name to its underlying set. We can just say “the underlying set of $\Delta$” or “$U(\Delta)$”.
Examples
“$+$” is not one binary operation.
- $+:\mathbb{Z}\times\mathbb{Z}\to\mathbb{Z}$ is a binary operation.
- $+:\mathbb{R}\times\mathbb{R}\to\mathbb{R}$ is another binary operation.
Mathematicians commonly refer to these particular binops as “addition on the integers” and “addition on the reals”.
Remark
You almost never see this attitude in textbooks on algebra. It is required by both category theory and type theory, two Waves flooding into math. Category theory is a middle-aged Wave and type theory, in the version of homotopy type theory, is a brand new baby Wave. Both Waves have changed and will change our understanding of math in deep ways.
Trees
An arbitrary binop $\Delta$ can be represented as a binary tree in this way:
generic binop
This tree represents the expression that in standard algebraic notation is “$a\Delta b$”.
In more detail, the tree is an ordered rooted binary tree. The “ordered” part means that the leaves (nodes with no descendants) are in a specific left to right order. In AbAl, I will define trees in some detail, with lots of pictures.
The root shows the operation and the two leaves show elements of the underlying set. I follow the custom in computing science to put the root at the top.
Metaphors should not dictate your life by being taken literally.
Remark
The Wikipedia treatment of trees is scattered over many articles and they almost always describe things mostly in words, not pictures. Describing math objects in words when you could use pictures is against my religion. Describing is not the same as defining, which usually requires words.
Some concrete examples:
3trees
These are representations of the expressions “$3+5$”, “$3\times5$”, and “$3-5$”.
Just as “$5+3$” is a different expression from “$3+5$”, the left tree in 3trees above is a different expression from this one:
switch
They have the same value, but they are distinct as expressions — otherwise, how could you state the commutative law?
Fine points
I regard an expression as an abstract math object that can have many representations. For example “$3+5$” and the left tree in 3trees are two different representations of the same (abstract) expression. This deviates from the usual idea that “expression” refers to a typographical construction.
In previous posts, when the operation is not commutative, I have sometimes labeled the legs like this:
I have thought about using this notation consistently in AbAl, but I suspect it would be awkward in places.
Evaluation and substitution
|
The two basic operations on algebraic expressions
are evaluation and substitution.
|
They and the Only Axiom of Algebra, which I will discuss in a later post, are all that is needed to express the true nature of algebra.
Evaluation
- If you evaluate $3+5$ you get $8$.
- If you evaluate $3\times 5$ you get $15$.
- If you evaluate $3-5$ you get $-2$.
I will show evaluation on trees like this:
Evaluation with trace
A more elaborate version, valuation with trace, would look like this. This allows you to keep track of where the valuations come from.
You could also keep track of the operation used at each node. An interactive illustration of this is in the post Visible algebra I supplement. That illustration requires CDF Player to be installed on your computer. You can get it free from the Mathematica website.
Variables
In the tree above, the $a$ and $b$ are variables, just as they are in the equivalent expression $a\Delta b$. Algebra beginners have a hard time understanding variables.
- You can’t evaluate an expression until you substitute numbers for the letters, which produces an instance of expression. (“Instance” is the preferable name for this, but I often refer to such a thing as an “example”.)
- If a variable is repeated you have to substitute the same value for each occurrence. So $a\Delta b$ is a different expression from $a\Delta a$: $2+3$ is an instance of $a+b$ but it is not an instance of $a+a$. But $a\Delta a$ and $b\Delta b$ are the same expression: any instance of one is an instance of the other.
- Substitute $a\Delta b$ for $a$ in $a\Delta b$ and you get $(a\Delta b)\Delta b$. You may have committed variable clash. You might have meant $(a\Delta b)\Delta c$. (Somebody please tell me a good link that describes variable clash.)
- Later, you will deal with multiplication tables for algebraic structures. There the elements are denoted by letters of the alphabet. They can’t be substituted for.
Empty boxes
A straightforward way to denote variables would be to use empty boxes:
The idea is that a number (element of the underlying set) can be inserted in each box. If $3$ (left) and $5$ (right) are placed in the boxes, evaluation would place the value of $3\Delta5$ in the root. Each empty box represents a separate variable.
Empty boxes could also be used in the standard algebraic notation: $\Delta$ or $+$ or $-$.
I have seen that notation in texts explaining variables, but I don’t know a reference. I expect to use this notation with trees in AbAl.
To achieve the effect of one variable in two different places, as in
we can cause it to repeat, as below, where “$\text{id}$” denotes the identity function on the underlying set:
To evaluate at a number (member of the underlying set) you insert a number into the only empty box
which evaluates to
which of course evaluates to $3\Delta3$.
This way of treating repeated variables exhibits the nature of repeated variables explicitly and naturally, putting the values automatically in the correct places. This process, like everything in this section, comes from monad theory. It also reminds me of linear logic in that it shows that if you want to use a value more than once you have to copy it.
Substitution
Given two binary trees
you could attach the root of the first one to one of the leaves of the second one, in two different ways, to get these trees:
2trees
which in standard algebra notation would be written $(a-b)-c)$ and $a-(b-c)$ respectively. Note that this tree
would be represented in algebra as $(a-b)-b$.
In general, substituting a tree for an input (variable or empty box) consists of replacing the empty box by the whole tree, identifying the root of the new tree with the empty box. In graph theorem, “substitution” may be called “grafting”, which is a good metaphor.
You can evaluate the left tree in 2trees at particular numbers to evaluate it in two stages:
Of course, evaluating the right one at the same values would give you a different answer, since subtraction is not associative. Here is another example:
Binary trees in general
By repeated substitution, you can create general binary trees built up of individual trees of this form:
In AbAl I will give examples of such things and their counterparts in algebraic notation. This will include binary trees involving more than one binop, as well. I showed an example in the previous post, which example I repeat here:
It represents the precise unsimplified expression
\[A=wh+\frac{1}{2}\left(\pi(\frac{1}{2}w)^2\right)\]
Some of the operations in that tree are associative and commutative, which is why the expression can be simplified. The collection of all (finite) binary trees built out of a single binop with no assumption that it satisfies laws (associative, commutative and so on) is the free algebra on that binary operation. It is the mother of all binary operations, so it plays the same role for an arbitrary binop that the set of lists plays for associative operations, as described in Monads for High School III: Algebras. All this will be covered in later chapters of AbAl.
References
Preceding posts in this series
Other references
|
Send to Kindle
