Tag Archives: monad

The only axiom of algebra

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

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

Creative Commons License

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


Send to Kindle

Presenting binops as trees

Binary operations as trees

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. In some parts, I present various options that I have not decided between.

This post concerns the presen­ta­tion of binary operations as trees. The Mathematica code for the diagrams is in Substitution in algebra.nb

Binary operations as functions

A binary operation or binop $\Delta$ is a function of two variables whose value at $(a,b)$ is traditionally denoted by $a\Delta b$. Most commonly, the function is restricted to having inputs and outputs in the same set. In other words, a binary operation is a function $\Delta:S\times S\to S$ defined on some set $S$. $S$ is the underlying set of the operation. For now, this will be the definition, although binops may be generalized to multiple sets later in the book.

In AbAl:

  • Binops will be defined as functions in the way just described.
  • Algebraic expressions will be represented
    as trees, which exhibit more clearly the structure of the expressions that is encoded in algebraic notation.
  • They will also be represented using the usual infix expressions such as “$3\times 5$” and “$3-5$”,

Fine points

The definition of a binop as a function has termi­no­logical consequences. The correct point of view concerning a function is that it determines its domain and its codomain. In particular:

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 homo­topy type theory, is a brand new baby Wave. Both Waves have changed and will change our under­standing 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 scat­tered 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 represen­ta­tions 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 repre­sentations. For example “$3+5$” and the left tree in 3trees are two different represen­ta­tions 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

Creative Commons License

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


Send to Kindle

Monads for High School III: Algebras

The interactive examples in this post require installing Wolfram CDF player, which is free and works on most desktop computers using Firefox, Safari and Internet Explorer, but not Chrome. The source code is the Mathematica Notebook MonadAlg.nb, which is available for free use under a Creative Commons Attribution-ShareAlike 2.5 License. The notebook can be read by CDF Player if you cannot make the embedded versions in this post work.

This is a continuation of Monads for high school I and Monads for High School II: Lists. This post covers the concept of algebras for the monad for lists.

Lists

$\textrm{Lists}(S)$ is the set of all lists of finite length whose entries are elements of $S$.

  • $\boxed{2\; 2\; 4}$ is the way I denote the list of length $3$ whose first and second entries are each $2$ and whose third entry is $4$.
  • A list with only one entry, such as $\boxed{2}$, is called a singleton list.
  • The empty list $\boxed{\phantom{2}}$ has no entries.
  • $\textrm{Lists}^*(S)$ is the set of all nonempty lists of finite length whose entries are elements of $S$.
  • $\textrm{Lists}(\textrm{Lists}(S))$ is the list whose entries are lists with entries from $S$.
  • For example, $\boxed{\boxed{5\; 7}\; \boxed{2\; 12\; 7}}$ and $\boxed{\boxed{5\; 7\; 2\; 12\; 7}}$ are both entries in $\textrm{Lists}^*(\textrm{Lists}^*(\mathbb{Z}))$. The second one is a singleton list!
  • $\boxed{\boxed{\phantom{3}}\; \boxed{2}}
    $ and $\boxed{\boxed{\phantom{3}}}$ are entries in $\textrm{Lists}^*(\textrm{Lists}(\mathbb{Z}))$.
  • The empty list $\boxed{\phantom{2}}$ is an entry in $\textrm{Lists}(\mathbb{Z})$, in $\textrm{Lists}(\textrm{Lists}^*(\mathbb{Z}))$ and in $\textrm{Lists}(\textrm{Lists}(\mathbb{Z}))$. If you have stared at this for more than ten minutes, do something else and come back to it later.

The star notation is used widely in math and computing science to imply that you are including everything except some insignificant shrimp of a thing such as the empty list, the empty set, or $0$. For example, $\mathbb{R}^*$ denotes the set of all nonzero real numbers.

More details about lists are in Monads for High School II: Lists.

Join

The function join (or concatenation) takes two lists and creates a third list. For example, if you join $\boxed{5\; 7}$ to $\boxed{2\; 12\; 7 }$ in that order you get $\boxed{5\; 7\; 2\; 12\; 7}$.

  • I will use this notation: join$\boxed{\boxed{5\; 7}\; \boxed{2\; 12\; 7}}=\boxed{5\; 7\; 2\; 12\; 7}$.
  • This notation means that I am regarding join as a function that takes a two-element list in $\textrm{Lists}(\textrm{Lists}(S))$ to an element of $\textrm{Lists}(S)$.
  • join removes one level of lists
  • join is not commutative: join$\boxed{\boxed{2\; 12\; 7}\; \boxed{5\; 7}}=\boxed{2\; 12\; 7\; 5\; 7}$
  • Join is associative, and as for any associative binary operation, join is defined on any finite list of lists of elements of $S$. So for example, join$\boxed{\boxed{5\; 7}\; \boxed{2\; 12\; 7}\; \boxed{1}}=\boxed{5\; 7\; 2\; 12\; 7\; 1}$.
  • For any single list $\boxed{a\; b\; c}$, join$\boxed{\boxed{a\; b\; c}}=\boxed{a\; b\; c}$. This is required to make the theory work. It is called the oneidentity property.
  • If the empty list $\boxed{\phantom{2}}$ occurs in a list of lists, it disappears when join is applied: join $\boxed{\boxed{2\; 3}\; \boxed{\phantom{2}}\; \boxed{4\; 5\; 6}}=\boxed{2\; 3\; 4\; 5\; 6}$.

More details about join in Monads for High School II: Lists.

The main monad diagram

When you have a list of lists of lists, join can be applied in two different ways, "inside" and "outside" as illustrated in the diagram below. It gives you several different inputs to try out as a way to understand what is happening.

This is the special case of the main diagram for all monads as it applies to the List monad.

As you can see, after doing either of "inside" and "outside", if you then apply join, you get the same list. That list is simply the list of entries in the beginning list (and the two intermediate ones) in the same order, disregarding groupings.

From what I have just written, you must depend on your pattern recognition abilities to learn what inside and outside mean. But both can also be described in words.

  • The lists outlined in black are lists of elements of $\mathbb{Z}$. In other words, they are elements of $\textrm{Lists}(\mathbb{Z})$.
  • The lists outlined in blue are lists of elements of $\textrm{Lists}(\mathbb{Z})$. In other words, they are list of lists of elements of $\mathbb{Z}$. Those are the kinds of things you can apply join to.
  • The leftmost list in the diagram, outlined in green, is a list in $\textrm{Lists}(\textrm{Lists}(\mathbb{Z}))$. This means you can apply join in two different ways:
  • Each list boxed in blue is a list of lists of integers (two of the are singletons!) so you can apply join to each of them. This is joining inside first.
  • You can apply join directly to the leftmost list, which is a list of lists (of lists, but forget that for the moment), so you can apply join to the blue lists. This is join outside first.

To understand this diagram, staring at the diagram (for most people) uses the visual pattern recognition part of your brain (which uses over a fifth of the energy used by your brain) to understand what inside and outside mean, and then check your understanding by reading the verbal description. Starting by reading the verbal description first does not work as well for most people.

The unit monad diagram

There is a second unitary diagram for all monads:

The two right hand entries are always the same. Again, I am asking you to use your pattern recognition abilities to learn what singleton list and singleton each mean.

The main and unit monad diagrams will be used as axioms to give the general definition of monad. To give those axioms, we also need the concepts of functor and natural transformation, which I will define later after I have finished the monad algebra diagrams for Lists and several other examples.

Algebras for the List monad

If you have any associative binary operation on a set $S$, its definition can be extended to any nonempty list of elements (see Monads for High School I.)

Plus and Times are like that:

  • $(3+2)+4$ and $3+(2+4)$ have the same value $9$, so you can write $3+2+4$ and it means $9$ no matter how you calculate it.
  • I will be using the notation Plus$\boxed{3\; 2\; 4}$ instead of $3+2+4$.
  • Times is also associative, so for example we can write Times$\boxed{3\; 2\; 4}=24$.
  • Like join, we require that these operations satisfy oneidentity, so we know Plus$\boxed{3}=3$ and Times$\boxed{3}=3$.
  • When the associative binary operation has an identity element, you can also define its value on the empty list as the identity element: Plus$\boxed{\phantom{3}}=0$ and Times$\boxed{\phantom{3}}=1$. I recommend that you experiment with examples to see why it works.

An algebra for the List monad is a function algop:$\textrm{Lists}(S)\to S$ with certain properties: It must satisfy the Main Monad Algebra Diagram and the Unit Monad Algebra Diagram, discussed below.

The main monad algebra diagram

Example using Plus and Times

The following interactive diagram allows you to see what happens with Plus and Times. Afterwards, I will give the general definition.

Plus insides replaces each inside list with the result of applying Plus to it, and the other operation Join is the same operation I have used before.

Another example

The main monad algebra diagram requires that if you have a list of lists of numbers such as the one below, you can add up each list (Plus insides) and then add up the list of totals (top list in diagram), you must get the same answer that you get when you join all the lists of numbers together into one list (bottom list in the diagram) and then add up that list.

This is illustrated by this special case of the main monad algebra diagram for Plus:

General statement of the main monad algebra diagram

Suppose we have any function $\blacksquare$ $:\textrm{Lists}(S)\to S$ for any set $S$.
If we want to give the main monad algebra diagram for $\blacksquare$ we have a problem. We know for example that Plus$\boxed{1\; 2}=3$. But for some elements $a $ and $b$ of $S$, we don’t know what $\blacksquare\boxed{a\; b}$ is. One way to write it is simply to write $\blacksquare\boxed{a\; b}$ (the usual way we write a function). Or we could use tree notation and write

newalopdouble.

I will use tree notation mostly, but it is a good exercise to redraw the diagrams with functional notation.

Main monad diagram in prose

Below is a presentation of the general main monad algebra diagram using (gasp!) English phrases to describe the nodes.

genalgdiag

The unit monad algebra diagram

Suppose $\blacksquare$ is any function from $\textrm{Lists}(S)$ to $S$ for any set $S$. Then the diagram is

UnitMAdiag

This says that if you apply $\blacksquare$ to a singleton you get the unique entry of the singleton. This is not surprising: I defined above what it means when you apply an operation to a singleton just so this would happen!

A particular example

These are specific examples of the general main monad algebra diagram for an arbitrary operation $\blacksquare$:

stalgdiagleft

staldiagright

These examples show that if $\blacksquare$ is any function from $\textrm{Lists}(S)$ to $S$ for any set $S$, then

newalopleft

equals

newaloptriple

and

newalopright

equals

newaloptriple

Well, according to some ancient Greek guy, that means

newalopleft

equals

newalopright

which says that
newalopdouble
is an associative binary operation!

The mother of all associative operations

We also know that any associative binary $\blacksquare$ on any set $S$ can be extended to a function on all finite nonempty lists of elements of $S$. This is the general associative law and was discussed (without using that name) in Monads fo High School I.

Let’s put what we’ve done together into one statement:

Every associative binary operation $\blacksquare$ on a set $S$ can be extended uniquely to a function $\blacksquare:\textrm{Lists}^*(S)\to S$ that satisfies both the main monad algebra diagram and the unit monad algebra diagram. Furthermore, any function $\blacksquare:\textrm{Lists}^*(S)\to S$ that satisfies both the main monad algebra diagram and the unit monad algebra diagram is an asssociative binary operation when applied to lists of length $2$ of elements of $S$.

That is why I claim that the NonemptyList monad is the mother of all associative binary operations.

I have not proved this, but the work in this and preceding posts provide (I think) a good intuitive understanding of this fundamental relationship between lists and associative binary operations.

Things to do in upcoming posts

  • I have to give a proper definition of monads using the concepts of functor and natural transformation. I expect to do this just for set functors, not mentioning categories.
  • Every type of binary operation that is defined by equations corresponds to a monad which is the mother of all binary operations of that type. I will give examples, but not prove the general case.

Other examples of monads

  • Associative binary operations on $S$ with identity element (monoids) corresponds to all lists, including the empty list, with entries from $S$.
  • Commutative, associative and idempotent binary operations, like and and or in Boolean algebra, correspond to the set monad: $\text{Sets}(S)$ is the set of all finite and countably infinite sets of elements of $S$. (You can change the cardinality restrictions, but you have to have some cardinality restrictions.) Join is simply union.
  • Commutative and associative binary operations corresponds to the multiset monad (with a proper definition of join) and appropriate cardinality restrictions. You have to fuss about identity elements here, too.
  • Various kinds of nonassociative operations get much more complicated, involving tree structures with equivalence relations on them. I expect to work out a few of them.
  • There are lots of monads in computing science that you never heard of (unless you are a computing scientist). I will mention a few of them.

  • Every type of binary operation defined by equations corresponds to a monad. But some of them are unsolvable, meaning you cannot describe the monad precisely.

There will probably be long delay before I get back to this project. There are too many other things I want to do!

Send to Kindle

Monads for high school II: Lists

The interactive examples in this post require installing Wolfram CDF player, which is free and works on most desktop computers using Firefox, Safari and Internet Explorer, but not Chrome. The source code is the Mathematica Notebook Monad.nb, which is available for free use under a Creative Commons Attribution-ShareAlike 2.5 License. The notebook can be read by CDF Player if you cannot make the embedded versions in this post work.

Introduction

This is the second part of a series of posts describing how I will lead up to introducing monads in my proposed e-book Abstracting Algebra (AbAl). It follows Monads for high school I. Comments in red are meta and mostly will not be included in the book.  

Lists 

A list is a specific kind of mathematical object. This is a reasonable specification for lists:

A list of length $n$ determines and is determined by what its first, second, $\ldots$, $n$th entries are. 

In this post, lists will always be finite in length.

For doing rigorous proofs you need a precise definition of a list, such as a function from $\{1,2,…,n\}$ to a set, or a recursive definition.  This book is not about proofs.

Terminology and representation

The most common way in the symbolic language of math to represent a finite list is to use a comma-delimited expression in parentheses.  For example, \[(4,4,2,8)\] is the list of length 4 whose first and second entries are both $4$, third entry $2$ and fourth entry $8$.

  • The order matters and repetitions are allowed. For example, $(4,4,2,8)$, $(4,2,8)$ and $(4,2,4,8)$ are all different lists.
  • Other words for lists are (finite) sequenceword, tuple and string.
  • Many mathematicians would call $(4,4,2,8)$ an $4$tuple.
  • My Discrete math classnotes discusses the specification and the definition of lists called tuples there) at length on pages 50ff. This section of AbAl will incorporate some of the information there.
  • Some computer languages represent our list without the commas: $(4\,\,4\,\,2\,\,8)$.
  • Mathematica represents it this way: $\{4,4,2,8\}$.  This conflicts with the usual set notation, where the order does not matter and where repetitions are ignored  — the set $\{4,4,2,8\}$ has three elements.  But if you type Length[$\{4,4,2,8\}$] in Mathematica, you get the answer 4.
  • A list of characters (alphabetical, numerical, or other symbols) can be represented  by writing the characters down in order without spaces between them.  For example $(a,a,c,d)$ would be written "aacd".  This representation is referred to as a string or as a word in computing science.  The string "4428" is the base-10 representation of the integer $4,428$.  Of course, it is also the hexadecimal representation of the integer $17,448$. 
  • In the text, I will mostly use a cartouche representation: for example, $\boxed{1\ 2\ 3\ 4}$ is the list consisting of the first four positive integers in order.
  • The cartouche is more in-your-face than the other representations I've listed and as far as I know is not used to mean anything else.  I'm not sure I can give any better explanation for why I prefer it than that.  Math is supposed to be explicit and precisely defined and justified by clear reasoning, but after all deciding which representation to use is not math, it is art.

Lists with entries from a given set

If $S$ is any set, finite or infinite, $\textrm{Lists}(S)$ denotes the set of all lists of finite length whose entries come from $S$.  Thus the set $\textrm{Lists}(\{1,\  2,\  3\})$ contains:

  • $\boxed{2\ 2\ 3\ 2\ 2\ 1}$,
  • $\boxed{3\  3\  3\  3}$,
  • the list of length $42$ whose first entry is $3$ and every other entry is $1$,
  • the empty list $\boxed{\vphantom{n}}$,
  • the singleton lists $\boxed{1}$,  $\boxed{2}$ and  $\boxed{3}$, and
  • an infinite number of other lists, 
  • but the list $\boxed{4\  2\  3}$ is not an element of $\textrm{Lists}(\{1,\  2,\  3\})$.

$\textrm{Lists}$ is a function from sets to sets.  Its input is any set and its output is the set of all finitely-long lists whose entries are from the input set. We will also use the similar function $\textrm{Lists}^+$ which takes a set to the set of nonempty lists with entries from the set.

Associativity

(Review from Monads for high school I.)  If a binary operation is associative, then the operation is defined on any (finite) list of inputs in its underlying set.  For example, the sum of the list $\boxed{4\ 4\ 2\ 8}$  is 18.  It follows from associativity that you can add it up as $(4+4)+(2+8)$, $4+(4+(2+8))$, $4+((4+2)+8)$, $(4+(4+2))+8$ or as $((4+4)+2)+8$.  They all give the same answer. In other words, Plus is in fact an operation on lists of numbers.  It is customary to extend associative binary operations to lists of length $0$ and $1$ by setting the value at the empty list to be the identity element of the operation, and the value at a one element list to be its only entry.  Thus Plus($\boxed{4\ 4\ 2\ 8}$)$=18$, Plus($\boxed{\ \vphantom{0} }$)$=0$, Times($\boxed{\ \vphantom{0} }$)$=1$ and Plus($\boxed{3 }$)$=3$.

Operations defined on finite lists

 You can join two lists together in order to make one list.  

The order matters.  If you join $\boxed{5\ 7}$ to $\boxed{2\ 12\ 7 }$ in that order you get $\boxed{5\ 7\ 2\ 12\ 7}$.  

Join is in fact an associative binary operation on lists.  Example: 

This means we can define an operation on lists of lists that joins all the lists inside together to make one list. 

 Notice the blue rectangle disappears when you do the operation. What I have defined here is a function that has a list of lists as input and a list of numbers as output.

The operation of joining lists to get a single list has a property shown by the drawing below (which will be interactive when I work on it some more).  Start on the left with a list of lists of lists.  The border colors distinguish the innermost lists, bordered in black, from the second level lists, in blue, and the outside list, bordered in green.

  • There is only one outside list: It is a list of (blue) lists.  That is the kind of list you can apply join to, so when you do you get a single blue list with five lists inside it (on the bottom of the diagram). "Join outside first" means "apply join to the outside list first". 
  • The single blue list on the bottom is again the kind of list you can apply join to, and when you do you get the lower list on the right end of the diagram.
  • However, the green list also contains two lists each of which is a list of lists that you can apply join to.  Apply it to both of them and you get the list at the top of the diagram.  
  • Again, that list is the kind you can apply join to and when you do you get the upper list on the right.

JoinDiagram

The two lists on the right are the same.  That always happens, whatever lists you start with.  (Try it with others, and include some singleton and empty lists while you are at it.) 

You might not have thought of this property, and now that you see it, it may look like some sort of second-rate phenom to take note of.  Or not.  But in fact, it turns out that it means that our modest function  $\textrm{Lists}^+$, that takes a set to the nonempty set of lists of its elements is a monad.  (So is $\textrm{Lists}$.) In order to say this we must define some other concepts: functor and natural transformation, and we have to verify a number of other properties of the $\textrm{List}^+$ function:  It is not just a function, it is a functor on the category of sets, the join function is a natural transformation, and some other technicalities.

Once we do that, we can define what the algebras of the join monad are, and it turns out that they are exactly all the associative binary operations.  

In other words:

The binary operation of join on nonempty lists is the mother of all associative binary operations.

But that will have to wait for the next post.

References

 

Send to Kindle

Monads for high school I

 

Notes for viewing

The interactive examples in this post require installing Wolfram CDF player, which is free and works on most desktop computers using Firefox, Safari and Internet Explorer, but not Chrome. The source code is the Mathematica Notebook associative.nb, which is available for free use under a Creative Commons Attribution-ShareAlike 2.5 License. The notebook can be read by CDF Player if you cannot make the embedded versions in this post work.

Monads in Abstracting Algebra

I've been working on first drafts (topic posts) of several sections of my proposed book Abstracting algebra (AbAl), concentrating on the ideas leading up to monads.  This is going slowly because I want the book to be full of illustrations and interactive demos.  I am writing the demos in Mathematica simultaneously with writing the text, and designing demos is very s l o w work. It occurred to me that I should write an outline of the path leading up to monads, using some of the demos I have already produced. This is the first of probably two posts about the thread.

  • AbAl is intended to give people with a solid high school math background a mental picture of or way of thinking about the various levels of abstraction of high school algebra.
  • This outline is not a "Topic post" as described in the AbAl page. In particular, it is not aimed at high school students! It is a guided tour of my current thoughts about a particular thread through the book.
  • The AbAl page has a brief outline of the topics to be covered in the whole book.  Perhaps it should also have a list of threads like this post.

Associativity

AbAl will have sections introducing functions and binary operations using pictures and demos (not outlined in this thread).  The section on binary operations will introduce infix, prefix and postfix notation but will use trees (illustrated below) as the main display method.  Then it will introduce associativity, using demos such as this one: 

Using this computingscienceish tree notation makes it much easier to visualize what is happening (see Visible Algebra II), compared to, for example, \[(ab)(cd)=a(b(cd))=a((bc)d)=((ab)c)d=(a(bc))d\]  In this equation, the abstract structure is hidden.  You have to visualize doing the operation starting with the innermost parentheses and moving out.  With the trees you can see the computation going up the tree.

I will give examples of associative functions that are not commutative using $2\times2$ matrices and endofunctions on finite sets such as the one below, which gives all the functions from a two element set to itself. 


  • Note that each function is shown by a diagram, not by an arbitrary name such as "id" or "sw", which would add a burden to the memory for an example that occurs in one place in the book. (See structural notation in the Handbook.) 
  • The section on composition of functions will also look in some depth at permutations of a three-element set, anticipating a section on groups.

 By introducing a mechanism for transforming trees of associative binary operations, you can demonstrate (as in the demo below) that any associative binary operation is defined on any list of two or more elements of its domain.

For example, applying addition to three numbers $a$, $b$ and $c$ is uniquely defined. This sort of demo gives an understanding of why you get that unique definition but it is not a proof, which requires formal induction. AbAl is not concerned with showing the reader how to prove math statements.

In this section I will also introduce the oneidentity concept: the value of an associative binary operation on a an element $a$ is $a$.  Thus applying addition or multiplication to $a$ gives $a$.  (The reason for this is that you want an associative binary operation to be a unique quotient of the free associative binary operation.  That will come up after we talk about some examples of monads.)  

The oneidentity property also implies that for an associative binary operation with identity element, applying the operation to the empty set gives the identity element.  Now we can say:

An associative binary operation with identity element is uniquely defined on any finite list of elements of its domain.

Thus, in prefix notation,$+(2,3)=5$, $+(2,3,5)=10$, $+(2)=2$ and $+()=0$.  Similarly $\times(2)=2$ and $\times()=1$.

This fact suggests that the natural definition of addition, multiplication, and other associative binary operations is as functions from lists of elements of the domain to elements of the domain.   This fits with our early intuition of addition from grade school, not to mention from Excel:  Addition is something you do to lists.  That feeling (for me) is not so strong for multiplication; for many common business applications you generally multiply two things like price and number sold. That's because multiplication is usually for things of different data types, but you usually add things of the same data type (not apples and oranges?).   

That raises the question: Does every function taking lists to elements come from an associative binary operation?  I will give an example that says no.  But the next thing is to introduce joining lists (concatenation), where we discover that joining lists is an associative binary operation.  So it is really an operation on lists of lists.  This will turn out to give us a systematic way to define all associative binary operations by one mechanism, because it is an example of a monad.  That is for the second installment of this outline.

Send to Kindle

Abstracting algebra

This post has been turned into a page on WordPress, accessible in the upper right corner of the screen.  The page will be referred to by all topic posts for Abstracting Algebra.

 

Send to Kindle

Visible algebra II

The interactive examples in this post require installing Wolfram CDF player, which is free and works on most desktop computers using Firefox, Safari and Internet Explorer, but not Chrome. The source code is the Mathematica Notebook Wolfram website. The code for the demos is in the Mathematica notebook algebra2.nb, which is available for free use under a Creative Commons Attribution-ShareAlike 2.5 License. The notebook can be read by CDF Player if you cannot make the embedded versions in this post work.

More about visible algebra

I have written about visible algebra in previous posts (see References). My ideas about the interface are constantly changing. Some new ideas are described here.

In the first place I want to make it clear that what I am showing in these posts is a simulation of a possible visual algebra system.  I have not constructed any part of the system; these posts only show something about what the interface will look like.  My practice in the last few years is to throw out ideas, not construct completed documents or programs.  (I am not saying how long I will continue to do this.)  All these posts, Mathematica programs and abstractmath.org are available to reuse under a Creative Commons license.

Commutative and associative operations

Times and Plus are commutative and associative operations.  They are usually defined as binary operations.  A binary operation $*$ is said to be commutative if for all $x$ and $y$ in the underlying set of the operation, $x*y=y*x$, and it is associative if for all $x$,$y$ and $z$ in the underlying set of the operation, $(x*y)*z=x*(y*z)$. 

It is far better to define a commutative and associative operation $*$ on some underlying set $S$ as an operation on any multiset of elements of $S$.  A multiset is like a set, in particular elements can be rearranged in any way, but it is not like a set in that elements can be repeated and a different number of repetitions of an element makes a different multiset.  So for any particular multiset, the number of repetitions of each element is fixed.  Thus $\{a,a,b,b,c\} = \{c,b,a,b,a\}$ but $\{a,a,b,b,c\}\neq\{c,b,a,b,c\}$. This means that the function (operation) Plus, for example, is defined on any multiset of numbers, and \[\mathbf{Plus}\{a,a,b,b,c\}=\mathbf{Plus} \{c,b,a,b,a\}\] but $\mathbf{Plus}\{a,a,b,b,c\}$ might not be equal to $\mathbf{Plus} \{c,b,a,b,c\}$.

This way of defining (any) associative and commutative operation comes from the theory of monads.  An operation defined on all the multisets drawn from a particular set is necessarily commutative and associative if it satisfies some basic monad identities, the main one being it commutes with union of multisets (which is defined in the way you would expect, and if this irritates you, read the Wikipedia article on multisets.). You don't have to impose any conditions specifically referring to commutativity or associativity.  I expect to write further about monads in a later post. 

The input process for a visible algebra system should allow the full strength of this fact. You can attach as many inputs as you want to Times or Plus and you can move them around.  For example, you can click on any input and move it to a different place in the following demo.

Other input notations might be suitable for different purposes.  The example below shows how the inputs can be placed randomly in two dimensions (but preserving multiplicity).  I experimented with making it show the variables slowly moving around inside the circle the way the fish do in that screensaver (which mesmerizes small children, by the way — never mind what it does to me), but I haven't yet made it work.

A visible algebra system might well allow directly input tables to be added up (or multiplied), like the one below. Spreadsheets have such an operation In particular, the spreadsheet operation does not insist that you apply it only as a binary operation to columns with two entries.  By far the most natural way to define addition of numbers is as an operation on multisets of numbers.

Other operations

Operations that are associative but not commutative, such as matrix multiplication, can be defined the monad way as operations on finite lists (or tuples or vectors) of numbers.  The operation is automatically associative if you require it to preserve concatenation of lists and some other monad requirements.

Some binary operations are neither commutative nor associative.  Two such operations on numbers are Subtract and Power.  Such operations are truly binary operations; there is no obvious way to apply them to other structures.  They are only binary because the two inputs have different roles.  This suggests that the inputs be given names, as in the examples below.

Later, I will write more about simplifying trees, solving the max area problem for rectangles surmounted by semicircles, and other things concerning this system of doing algebra.

References

Previous posts about visible algebra

Other references

 

Send to Kindle