I collected data from some math books published since 2000 that contain a definition of function; they are listed below.  In this list, "typed" means  function was defined as going from a set A to a set B, A was called the domain, and B was not given a name. If "typed" is followed by a word (codomain, range or target) that was the name given the codomain. One book defined a function essentially as a partial function. Some that did not name the codomain defined "range" in the sense of image. Some of them emphasized that the range/image need not be the same as the codomain.

As far as I know, none of these books said that if two functions had the same domain and the same graph but different codomains they had to be different functions.  But I didn't read any of them extensively. 

My impression is that modern mathematical writing at least at college level does distinguish the domain, codomain, and image/range of a function, not always providing a word to refer to the codomain.

If the page number as a question mark after it that means I got the biblio data for the book from Amazon and the page number from Google books, which doesn't give the edition number, so it might be different.

I did not look for books by logicians or computing scientists.  My experience is that logicians tend to use partial functions and modern computing scientists generally require the codomain to be specified.

Opinion:  If you don't distinguish functions as different if they have different codomains, you lose some basic intuition (a function is a map) and you mess up common terminology.  For example the only function from {1} to {1} is the identity function, and is surjective.  The function from {1} to the set of real numbers (which is a point on the real line) is not the identity function and is not surjective.

THE LIST

Mathematics for Secondary School Teachers
 By Elizabeth G. Bremigan, Ralph J. Bremigan, John D. Lorch, MAA 2011
p. 6 (typed)

Oxford Concise Dictionary of Mathematics, ed. Christopher Clapham and James Nicholson,  Oxford University Press, 4th ed., 2009.
p. 184, (typed, codomain)

Math and Math-in-school: Changes in the Treatment of the Function Concept in …
 By Kyle M. Cochran, Proquest, 2011
p74  (partial function)

 Discrete Mathematics: An Introduction to Mathematical Reasoning
 By Susanna S. Epp, 4th edition, Cengage Learning, 2010 
 p. 294? (typed, co-domain)

 Teaching Mathematics in Grades 6 – 12: Developing Research-Based …
 By Randall E. Groth, SAGE, 2011
 p236 (typed, codomain)

Essentials of Mathematics, by Margie Hale, MAA, 2003.
p. 38 (typed, target).

Elements of Advanced Mathematics
 By Steven G. Krantz, 3rd ed., Chapman and Hall, 2012
p79? (typed, range)

Bridge to Abstract Mathematics
 By Ralph W. Oberste-Vorth, Aristides Mouzakitis, Bonita A. Lawrence, MAA 2012
 p76 (typed, codomain)

The Road to Reality by Roger Penrose, Knopf, 2005.
p. 104 (typed, target)

Precalculus: Mathematics for Calculus
 By James Stewart, Lothar Redlin, Saleem Watson, Cengage, 2011
p. 143.  (typed)

The Mathematics that Every Secondary School Math Teacher Needs to Know
 By Alan Sultan, Alice F. Artzt , Routledge, 2010.
 p.400 (typed)
 
 

• It is the result of my first adventure in revising abstractmath.org in accordance with the ideas in my recent Gyre&Gimble post Writing math for the web.
• One part of the new article incorporates some of the ideas of my post
  The power of being naive
• I did not use the manipulable diagrams in the Naive post in the abstractmath post. It’s not clear to me how many one time drop-ins (which is what I mostly get in abstractmath) will be willing to install Wolfram CDF Player to fiddle with one or two diagrams.
• I have been pleased at the way many of the topics covered in abstractmath come up high when you search for them in Google (including Conceptual Computational, but also things like Mathematical Object and Language of Math (where I even beat Wikipedia)). However, it may be that the high rank occurs because Google knows who I am. I will investigate next time I am in a library!
• I expect to post pieces of Abstracting Algebra on abstractmath when they become decently finished enough.

Learning about the derivative as a concept

The derivative $f'(x)$ of $f(x)$ is the function whose value at $a$ is the slope of the line tangent to the graph $y=f(x)$ at the point $(a,f(a))$.

To gain understanding of the concept of derivative the student need to see and play with the pictures that illustrate the definition. This can be done in stages:

• Give an intuitive, pictorial explanation of the tangent line.
• Show in pictures what the slope of a line is.
• Show in pictures how you can approximate the tangent line with secant lines.

Of course, many teachers and textbooks do this. I propose that:

The student will benefit in the long run by spending a whole class session on the intuitive ideas I just described and doing a set homework based only on intuition. Then you can start doing the algebraic stuff.

This post provides some ideas about manipulable diagrams that students can play with to gain intuition about derivatives. Others are possible. There are many on the Mathematica Demonstrations website. There are others written in Java and other languages, but I don't know of a site that tries to collect them in one place.

My claim that the student will benefit in the long run is not something I can verify, since I no longer teach.

Present the tangent line conceptually

The tangent line to a curve

• is a straight line that touches the curve at a point on the curve,
• and it goes in the same direction that the curve is going, like the red line in the picture below. (See How to manipulate the diagrams.)

My recommendation is that you let the students bring up some of the fine points.

• The graph of $y=x^3-x$ has places where the tangent line cuts the curve at another point without being parallel to the curve there. Move the slider to find these places.
• The graph of $y=\cos(\pi x)$ has places where the same line is tangent at more than one point on the curve. (This may requre stepping the slider using the incrementers.)
• Instigate a conversation about the tangent line to a given straight line.
• My post Tangents has other demos intended to bother the students.
• Show the unit circle with some tangent lines and make them stare at it until they notice something peculiar.
• "This graph shows the tangent line but how do you calculate it?" You can point out that if you draw the curve carefully and then slide a ruler around it so that it is tangent at the point you are interested in, then you can draw the tangent carefully and measure the rise and run with the ruler. This is a perfectly legitimate way to estimate the value of the slope there.

Slope of the tangent line conceptually

This diagram shows the slope of the tangent line as height over width.

• Slide the $x$ slider back and forth. The width does not change. The height is measured from the tangent line to the corner, so the height does change; in particular, it changes sign appropriately.
• This shows that the standard formula for the derivative of the curve gives the same value as the calculated slope of the tangent. (If you are careful you can find a place where the last decimal places differ.) You may want to omit the "derivative value" info line, but most students in college calculus already know how to calculate the formulas for the derivative of a polynomial– or you can just tell them what it is in this case and promise to show how to calculate the formula later.
• Changing the width while leaving $x$ fixed does not change the slope of the tangent line (up to roundoff error).
• In fact I could add another parameter that allows you to calculate height over width at other places on the tangent line. But that is probably excessive. (You could do that in a separate demo that shows that basic property that the slope of a straight line does not change depending on where you measure it — that is what a curve being a straight line means.)
• This graph provides a way to estimate the slope, but does not suggest a way to come up with a formula for the slope, in other words, a formula for the derivative.

Conceptual calculation of the slope

This diagram shows how to calculate the value of the slope at a point using secant lines to approximate the tangent line. If you have a formula for the function, you can calculate the limit of the slope of the secant line and get a formula for the derivative.

• The function $f(x)=x^3-x$.
• The secant points are $(x-h,f(x-h))$ and $(x+h, f(x+h))$. $h$ is called "width" in the diagram.
• Moving $x$ with the slider shows how the tangent line and secant line have similar slopes.
• Moving the width to the left, to $0$ (almost), makes the secant line coincide with the tangent line. So intuitively the limit of the slope of the secant line is the slope of the tangent line.
• The distance between the secant points is the Euclidean distance. (It may be that including this information does not help, so maybe it should be left out.)
• The slope of the secant line is $\frac{f(x+h)-f(x-h)}{(x+h)-(x-h)}$ when $h\neq0$. This simplifies to $3x^2+h^2-1$, so the limit when $h\to0$ is $3x^2-1$, which is therefore a formula for the derivative function.

Testing intuitive concepts

Most of the work students do when studying derivatives is to solve some word problems (rate of change, maximization) in which the student is expected to come up with an appropriate function $f(x)$ and then know or find out the formula for $f'(x)$ in the process of solving the problem. In other words there is a heavy emphasis on computation and much less on concept.

The student in the past has had to do very few homework problems that test for understanding the concept. Lately some texts do have problems that test the concept, for example:

This is the graph of a function and its derivative. Which one is the function and which is its derivative?

Note that the problem does not give you the formula for the function, nor does it have to.

Many variations are possible, all involving calculating parameters directly from the graph:

• "These are the first and second derivatives of a function. Where (within the bounds of the graph) is the function concave up?"
• "These are the first and second derivatives of a function. Where (within the bounds of the graph) are its maxima and minima?"
• "This straight line is the derivative of a function. Show that the function is a quadratic function and measure the slope of the line in order to estimate some of the coefficients of the quadratic."

How to manipulate the diagrams

• You can move the sliders back and forth to to move to different points on the curve.
• In the first diagram, you can click on one of the four buttons to see how it works for various curves.
• The arrow at the upper right makes it run automatically in a not very useful sort of way.
• The little plus sign below the arrow opens up some other controls and a box showing the value of $a$, including step by step operation (plus and minus signs).
• If you are using Mathematica, you can enter values into the box, but if you are using CDF Player, you can only manipulate the number using the slider or the plus and minus incrementers.

I built my website abstractmath.org during the years 2002 through 2006. After that I made sporadic changes, but medical operations and then teaching courses as an adjunct for a couple of years kept me from making much progress until 2010.

This post is an explanation of the tools I used for abstractmath, what went right and what went wrong, and my plans for redoing the website.

Methodology

My previous experience in publishing math was entirely with TeX. When I began work on abstractmath, I wanted to produce html files, primarily because they refloated the text when the window width changed. I was thinking of small screens and people wanting to look at several windows at once.

In those days, there was no method of starting with a LaTeX input file and producing an html file that preserved all the math and all the formatting. I have over the years spent many hours trying out various systems that claimed to do it and not found one that did not require major massaging to get the look I wanted. Most of them can cannot implement all LaTeX commands, or even most of the LaTeX formatting commands. (I have not looked at any of these since 2011.)

In contrast, systems such as PDFTeX turn even very complicated (in formatting and in math) LaTeX files into nearly perfect PDF files. Unfortunately, PDF files are a major impediment to having several windows open at once.

Word and MathType

My solution was to write abstractmath articles using Microsoft Word with MathType, which provides a plugin for Word.

The MathType interface was a very useful expansion of the Equation Editor in Word, and it produced little .gif files that were automatically inserted into the text. MathType also provided a command to create an html file. This file was produced with the usual “_files” folder that contained all the illustrations I had included as well as all the .gif files that MathType created. The html file contained code that put each .gif file in the right place in the typeset text.

That combination worked well. Using Word allowed me tight control over formatting and allowed floating textboxes, which I used freely. They very nicely moved around when you changed the width of the window.

I had used textboxes in my book A Handbook of Mathematical Discourse for apt quotations, additional comments, and (very clever if I say so myself) page indexes. The Handbook is available in several ways:

• Amazon. The citations are not included.
• The Handbook in paper form. A pdf file showing the book as it appears on paper (all the illos, textboxes and page indexes, no hyperlinks), plus all the citations. (This paragraph was modified on 2013-05-02).
• A version with hyperlinks, This includes the citations but omits the boxes and the illustrations, and it has hyperlinks to the citations. The page indexes are replaced by internal hyperlinks.
• The citations.

That book was written in TeX with much massaging using AWK commands. Boxes are much easier to do in Word than they are in TeX, and the html files produced by MathType preserved them quite well. The abmath article on definitions shows boxes used both for side comments and for quotations.

There were some problems with using MathType and Word together. In particular, a longish article would have dozens or hundreds of .gif files, which greatly slowed down uploading via ftp. I now have WebDrive (thanks to CWRU) and that may make it quicker.

Rot sets in

Without my doing anything at all, the articles on abstractmath began deteriorating. This had several main causes.

• Html was revised over time. Currently it is HTML5.0.
• Browsers changed way they rendered the html. And they had always differed among themselves in some situations.
• Microsoft Word changed the way it generated html.

Two of the more discouraging instances of rot were:

• Many instances of math formulas are now out of line with the surrounding text. This happened without my doing anything. It varies by browser and by when I last revised the article.
• Some textboxes deteriorated. In particular, textboxes generated by newer versions of Word were sometimes nearly illegible. Part of the reason for this is that Word started saving them as images.

Failed Forays

The main consequence of all this was that I was afraid of trying to revise articles (or complete them) because it would make them harder to read or ugly. So I set out to find new ways to produce abmath articles. This has taken a couple of years, while abmath is a big mess sprawling there on its website. A mostly legible big mess, and most of the links work, but frustrating to its appearance-sensitive author.

Automatically convert to a new system

My first efforts were to find another system with the property that I could convert my present Word files or html files to the new system without much hand massaging.

I tried converting the Word files to LaTeX input. This was made easier (I thought) because MathType now provided a means for turning all the MathType itty bitty .gif files into LaTeX expressions. I wrote Word macros to convert much of the formatting (italics, bold, subheads, purple prose, and so on) into LaTeX formatting — although I did have to go through the Word text, select each specially formatted piece, and apply the correct macro.

But I had other problems.

• Converting the Mathype images files to LaTeX caused problems because it messed up the spaces before and after the formulas.
• I worked with great sweat and tears to write a macro to extract the addresses from the links — and failed. If I had presevered I probably would have learned how to do it, and learned a lot of Word macros programming in the process.

The automatic conversion process appeared to require more and more massaging.

I made some attempts at automatically converting the html files that Word generates (instead of the doc files), but they are an enormous mess. They insert a huge amount of code (especialy spans) into the text, making it next to impossible to read the code or find anything.

It was beginning to look like I would have to go to an entirely new system and rewrite all the articles from scratch. This was attractive in one respect: in writing this blog my style has changed and I was seeing lots of things I would say or do differently. I have also changed my mind about the importance of some things, and abmath now has stubs and incomplete articles that ought to be eliminated with references to Wikipedia.

Go for rewriting

Meanwhile, I was having trouble with Gyre&Gimble. The WordPress editor works pretty well, but two new products came along:

• MathJax was introduced, providing a much better way to use TeX to insert formulas. (Note: MathType recently implemented the use of MathJax into its html output.)

• Mathematica CDF files, which are interactive diagrams that can be inserted directly into html. (My post Improved Clouds has examples.)

Both MathJax and CDF Player require entering links directly in the html code the WordPress editor produces. The WordPress editor trashed the html code I had entered every time I switched back and forth between “visual” (wysiwyg) and html.

I switched to CKEdit, which preserved the html but has a lot of random behavior. I learned to understand some of the behavior but finally gave up. I started writing my blogs in html using the Coffee Cup HTML Editor — that is how I am writing this. Then I paste it into the WordPress editor.

My current plan is to start revising each abmath article in this way:

• Write html code for the special formatting I want, mostly the code that produces the header, but also purple prose and other things. Once done I can use this code for all the abmath articles with little massaging.
• Start with the Word doc file for an article and use MathType to toggle all the MathType-generated gif files into TeX.
• Generate the html file in a way that preserves the TeX code with dollar signs. (There are two ways to do this and I have not made up my mind which to use.)
• Start revising!

I have already begun doing this. My intention is to revise each abstractmath article, post it, and announce the posting on Gyre&Gimble or on Google+. If an article is heavily revised I expect to post it (or parts of it) on Gyre&Gimble. Some of these things will be ready soon.

Last minute notes

• I used WinEdt, a text editor, to write the Handbook of Mathematical Discourse. It is a powerful html editor, with an extensive macro language that in particular allows rearranging the menus and adding new code to call other applications. It is especially designed for TeX, so is not as convenient as it stands for html. However, its macro language would allow me to convert it to a system that will do most of what Coffee Cup can do. I might do this because Coffee Cup has no macro language and (as far as I can tell) has no way to revise or add to menus.

• It is early days yet, but I am thinking of including pieces of Abstracting Algebra into abstractmath.org.

To manipulate the demos in this post, you must have Wolfram CDF Player installed on your computer. It is available free from the Wolfram website. The code for the demos is in the Mathematica notebook MonadAlg.nb

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

.

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.

The unit monad algebra diagram

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

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$:

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

equals

and

equals

Well, according to some ancient Greek guy, that means

equals

which says that

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!

This post explains some basic distinctions that need to be made about the process of writing and explaining math.  Everyone who teaches math knows subconsciously what is happening here; I am trying to raise your consciousness.  For simplicity, I have chosen a technique used in elementary algebra, but much of what I suggest also applies to more abstract college level math.

An algebra problem

Solve the equation "$ax=b$" ($a\neq0$).

Understanding the statement of this problem requires a lot of Secret Knowledge (the language of ninth grade algebra) that most people don't have.

• The expression "$ax$" means that $a$ and $x$ are numbers and $ax$ is their product. It is not the word "ax". You have to know that writing two symbols next to each other means multiply them, except when it doesn't mean multiply them as in "$\sin\,x$".

• The whole expression "$ax=b$" ostensibly says that the number $ax$ is the same number as $b$.  In fact, it means more than that. The phrase "solve the equation" tells you that in fact you are supposed to find the value of $x$ that makes $ax$ the same number as $b$.

• How do you know that "solve the equation" doesn't mean find the value of $a$ that makes $ax$ the same number as $b$? Answer: The word "solve" triggers a convention that $x$, $y$ and $z$ are numbers you are trying to find and $a$, $b$, $c$ stand for numbers that you are allowed to plug in to the equation.

• The conventions of symbolic math require that you give a solution for any nonzero value of $a$ and any value of $b$.  You specifically are not allowed to pick $a=1$ and $b=33$ and find the value just for those numbers.  (Some college calculus students do this with problems involving literal coefficients.)

• The little thingy "$(a\neq0)$" must be read as a constraint on $a$.  It does not mean that $a\neq0$ is a fact that you ought to know. ( I've seen college math students make this mistake, admittedly in more complex situations). Nor does it mean that you can't solve the problem if $a=0$ (you can if $b$ is also zero!).

So understanding what this problem asks, as given, requires (fairly sophisticated in some cases) pattern recognition both to understand the symbolic language it uses, and also to understand the special conventions of the mathematical English that it uses.

Explicit descriptions

This problem could be reworded so that it gives an explicit description of the problem, not requiring pattern recognition.  (Warning: "Not requiring pattern recognition" is a fuzzy concept.)  Something like this:  

You have two numbers $a$ and $b$.  Find a number $c$ for which if you multiply $a$ by $c$ you get $b$.

This version is not completely explicit.  It still requires understanding the idea of referring to a number by a letter, and it still requires pattern recognition to catch on that the two occurrences of each letter means that their meanings have to match. Also, I know from experience that some American first year college students have trouble with the syntax of the sentence ("for which…", "if…").

The following version is more explicit, but it cheats by creating an ad hoc way to distinguish the numbers.

Alice and Bob each give you a number.  How do you find a number with the property that Alice's number times your number is equal to Bob's number? 

If the problem had a couple more variables it would be so difficult to understand in an explicit form that most people would have to draw a picture of the relationships between them.  That is why algebraic notation was invented.

Visual descriptions

Algebra is a difficult foreign language.  Showing the problem visually makes it easier to understand for most people. Our brain's visual processing unit is the most powerful tool the brain has to understand things.  There are various ways to do this.  

Visualization can help someone understand algebraic notation better.  

You can state the problem by producing examples such as

• $\boxed{3}\times\boxed{\text{??}}=\boxed{6}$ 
• $\boxed{5}\times\boxed{\text{??}}=\boxed{2}$ 
• $\boxed{42}\times\boxed{\text{??}}=\boxed{24}$

where the reader has to know the multiplication symbol and, one hopes, will recognize "$\boxed{\text{??}}$" as "What's the value?". But the reader does not have to understand what it means to use letters for numbers, or that "$x$ means you are suppose to discover what it is".  This way of writing an algebra problem is used in some software aimed at K-12 students.  Some of them use a blank box instead of "$\boxed{\text{??}}$".

Such software often shows the algorithm for solving the problem visually, using algebraic notation like this:

I have put in some buttons to show numbers as well as $a$ and $b$.  If you have access to Mathematica instead of just to CDF player, you can load SolvEq.nb and put in any numbers you want, but CDF's don't allow input data. 

You can also illustrate the algorithm using the tree notation for algebra I used in Monads for high school I  (and other posts). The demo below shows how to depict the value-preserving transformation given by the algorithm.  (In this case the value is the truth since the root operation is equals.)

This demo is not as visually satisfactory as the one illustrating the use of the associative law in Monads for high school I.  For one thing, I had to cheat by reversing the placement of $a$ and $x$.  Note that I put labels for the numerator and denominator legs, a practice I have been using in demos for a while for noncommutative operations.  I await a new inspiration for a better presentation of this and other equation-solving algorithms.

Another advantage of using pictures is that you can often avoid having to code things as letters which then has to be remembered.  In Monads for high school I, I used drawings of the four functions from a two-element set to itself instead of assigning them letters.  Even mnemonic letters such as $s$ for "switch" and $\text{id}$ for the identity element carry a burden that the picture dispenses with.

Commonword names confuse

Many technical words and phrases in math are ordinary English words ("commonwords") that are assigned a different and precisely defined mathematical meaning.  

• Group  This sounds to the "layman" as if it ought to mean the same things as "set".  You get no clue from the name that it involves a binary operation with certain properties.  
• Formula  In some texts on logic, a formula is a precisely defined expression that becomes a true-or-false sentence (in the semantics) when all its variables are instantiated.  So $(\forall x)(x>0)$ is a formula.  The word "formula" in ordinary English makes you think of things like "$\textrm{H}_2\textrm{O}$", which has no semantics that makes it true or false — it is a symbolic expression for a name.
• Simple group This has a technical meaning: a group with no nontrivial normal subgroup.  The Monster Group is "simple".  Yes, the technical meaning is motivated by the usual concept of "simple", but to say the Monster Group is simple causes cognitive dissonance.

Beginning students come with the (generally subconscious) expectation that they will pick up clues about the meanings of words from connotations they are already familiar with, plus things the teacher says using those words.  They think in terms of refining an understanding they already have.  This is more or less what happens in most non-math classes.  They need to be taught what definition means to a mathematician.

Names that don't confuse but may intimidate

Other technical names in math don't cause the problems that commonwords cause.

Named after somebody The phrase "Hausdorff space" leads a math student to understand that it has a technical meaning.  They may not even know it is named after a person, but it screams "geek word" and "you don't know what it means".  That is a signal that you can find out what it means.  You don't assume you know its meaning. 

New made-up words  Words such as "affine", "gerbe"  and "logarithm" are made up of words from other languages and don't have an ordinary English meaning.  Acronyms such as "QED", "RSA" and "FOIL" don't occur often.  I don't know of any math objects other than "RSA algorithm" that have an acronymic name.  (No doubt I will think of one the minute I click the Publish button.)  Whole-cloth words such as "googol" are also rare.  All these sorts of words would be good to name new things since they do not fool the readers into thinking they know what the words mean.

Both types of words avoid fooling the student into thinking they know what the words mean, but some students are intimidated by the use of words they haven't seen before.  They seem to come to class ready to be snowed.  A minority of my students over my 35 years of teaching were like that, but that attitude was a real problem for them.

Audience

You can write for several different audiences.

Math fans (non-mathematicians who are interested in math and read books about it occasionally) In my posts Explaining higher math to beginners and in Renaming technical concepts, I wrote about several books aimed at explaining some fairly deep math to interested people who are not mathematicians.  They renamed some things. For example, Mark Ronan in Symmetry and the Monster used the phrase "atom" for "simple group" presumably to get around the cognitive dissonance.  There are other examples in my posts.  

Math newbies  (math majors and other students who want to understand some aspect of mathematics).  These are the people abstractmath.org is aimed at. For such an audience you generally don't want to rename mathematical objects. In fact, you need to give them a glossary to explain the words and phrases used by people in the subject area.   

Postsecondary math students These people, especially the math majors, have many tasks:

• Gain an intuitive understanding of the subject matter.
• Understand in practice the logical role of definitions.
• Learn how to come up with proofs.
• Understand the ins and outs of mathematical English, particularly the presence of ordinary English words with technical definitions.
• Understand and master the appropriate parts of the symbolic language of math — not just what the symbols mean but how to tell a statement from a symbolic name.

It is appropriate for books for math fans and math newbies to try to give an understanding of concepts without necessary proving theorems.  That is the aim of much of my work, which has more an emphasis on newbies than on fans. But math majors need as well the traditional emphasis on theorem and proof and clear correct explanations.

Lately, books such as Visual Group Theory have addressed beginning math majors, trying for much more effective ways to help the students develop good intuition, as well as getting into proofs and rigor. Visual Group Theory uses standard terminology.  You can contrast it with Symmetry and the Monster and The Mystery of the Prime Numbers (read the excellent reviews on Amazon) which are clearly aimed at math fans and use nonstandard terminology.  

Terminology for algebraic structures

I have been thinking about the section of Abstracting Algebra on binary operations.  Notice this terminology:

The "standard names" are those in Wikipedia.  They give little clue to the meaning, but at least most of them, except "magma" and "group", sound technical, cluing the reader in to the fact that they'd better learn the definition.

I came up with the names in the right column in an attempt to make some sense out of them.  The design is somewhat like the names of some chemical compounds.  This would be appropriate for a text aimed at math fans, but for them you probably wouldn't want to get into such an exhaustive list.

I wrote various pieces meant to be part of Abstracting Algebra using the terminology on the right, but thought better of it. I realized that I have been vacillating between thinking of AbAl as for math fans and thinking of it as for newbies. I guess I am plunking for newbies.

I will call groups groups, but for the other structures I will use the phrases in the middle column.  Since the book is for newbies I will include a table like the one above.  I also expect to use tree notation as I did in Visual Algebra II, and other graphical devices and interactive diagrams.

Magmas

In the sixties magmas were called groupoids or monoids, both of which now mean something else.  I was really irritated when the word "magma" started showing up all over Wikipedia. It was the name given by Bourbaki, but it is a bad name because it means something else that is irrelevant.  A magma is just any binary operation. Why not just call it that?  

Well, I will tell you why, based on my experience in Ancient Times (the sixties and seventies) in math. (I started as an assistant professor at Western Reserve University in 1965). In those days people made a distinction between a binary operation and a "set with a binary operation on it".  Nowadays, the concept of function carries with it an implied domain and codomain.  So a binary operation is a function $m:S\times S\to S$.  Thinking of a binary operation this way was just beginning to appear in the common mathematical culture in the late 60's, and at least one person remarked to me: "I really like this new idea of thinking of 'plus' and 'times' as functions."  I was startled and thought (but did not say), "Well of course it is a function".  But then, in the late sixties I was being indoctrinated/perverted into category theory by the likes of John Isbell and Peter Hilton, both of whom were briefly at Case Western Reserve University.  (Also Paul Dedecker, who gave me a glimpse of Grothendieck's ideas).

Now, the idea that a binary operation is a function comes with the fact that it has a domain and a codomain, and specifically that the domain is the Cartesian square of the codomain.  People who didn't think that a binary operation was a function had to introduce the idea of the universe (universal algebraists) or the underlying set (category theorists): you had to specify it separately and introduce terminology such as $(S,\times)$ to denote the structure.   Wikipedia still does it mostly this way, and I am not about to start a revolution to get it to change its ways.

Groups

In the olden days, people thought of groups in this way:

• A group is a set $G$ with a binary operation denoted by juxtaposition that is closed on $G$, meaning that if $a$ and $b$ are any elements of $G$, then $ab$ is in $G$.
• The operation is associative, meaning that if $a,\ b,\ c\in G$, then $(ab)c=a(bc)$.
• The operation has a unity element, meaning an element $e$ for which for any element $a\in G$, $ae=ea=a$.
• For each element $a\in G$, there is an element $b$ for which $ab=ba=e$.

This is a better way to describe a group:

• A group consist of a nullary operation e, a unary operation inv,  and a binary operation denoted by juxtaposition, all with the same codomain $G$. (A nullary operation is a map from a singleton set to a set and a unary operation is a map from a set to itself.)
• The value of e is denoted by $e$ and the value of inv$(a)$ is denoted by $a^{-1}$.
• These operations are subject to the following equations, true for all $a,\ b,\ c\in G$:

   

  • $ae=ea=a$.
  • $aa^{-1}=a^{-1}a=e$.
  • $(ab)c=a(bc)$.

This definition makes it clear that a group is a structure consisting of a set and three operations whose axioms are all equations.  It was formulated by people in universal algebra but you still see the older form in texts.

The old form is not wrong, it is merely inelegant.  With the old form, you have to prove the unity and inverses are unique before you can introduce notation, and more important, by making it clear that groups satisfy equational logic you get a lot of theorems for free: you construct products on the cartesian power of the underlying set, quotients by congruence relations, and other things. (Of course, in AbAl those theorem will be stated later than when groups are defined because the book is for newbies and you want lots of examples before theorems.)

References

1. Three kinds of mathematical thinkers (G&G post)
2. Technical meanings clash with everyday meanings (G&G post)
3. Commonword names for technical concepts (G&G post)
4. Renaming technical concepts (G&G post)
5. Explaining higher math to beginners (G&G post)
6. Visual Algebra II (G&G post)
7. Monads for high school II: Lists (G&G post)
8. The mystery of the prime numbers: a review (G&G post)
9. Hersh, R. (1997a), "Math lingo vs. plain English: Double entendre". American Mathematical Monthly, volume 104, pages 48–51.
10. Names (in abmath)
11. Cognitive dissonance (in abmath)

To manipulate the demos in this post, you must have Wolfram CDF Player installed on your computer. It is available free from the Wolfram website. The code for the demos is in the Mathematica notebook Monad.nb.  

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) sequence, word, 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\ 4\ 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.

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

• Associative in Wikipedia.
• Binary operation in Wikipedia.
• Discrete math classnotes, by Charles Wells.
• Toposes, triples and theories, by Michael Barr and Charles Wells.