Category Archives: exposition

category theory, exposition, language of math, math, proof, understanding math

A proof by diagram chasing

1 Comment


In Rigorous proofs, I went through the details of a medium-easy epsilon-delta proof in great detail as a way of showing what is hidden by the wording of the proof. In this post, I will do the same for an easy diagram-chasing proof in category theory. This theorem is stated and proved in Category Theory for Computing Science, page 365, but the proof I give here maximizes the diagram-chasing as a way of illustrating the points I want to make.

Theorem (J. Lambek) Let $F$ be a functor from a category to itself and let $\alpha:Fa\to a$ be an algebra for $F$ which is initial. Then $\alpha$ is an isomorphism.

Proof

  1. $F\alpha:FFa\to Fa$ is also an $F$-algebra.
  2. Initiality means that there is a unique algebra morphism $\eta:a\to Fa$ from $\alpha:Fa\to a$ to $F\alpha:FFa\to Fa$ for which this diagram commutes:




  3. To that diagram we can adjoin another (obviously) commutative square:




  4. Then the outside rectangle in the diagram above also commutes.
  5. This means that $\alpha\circ\eta:a\to a$ is an $F$-algebra morphism from $\alpha:Fa\to a$ to itself.
  6. Another such $F$-algebra morphism is $\text{id}_{A}$.
  7. Initiality of $\alpha$ means that the diagram below commutes:




  8. Because the upper bow and the left square both commute we are justified in inserting a diagonal arrow as below.




  9. Now we can read off the diagram that $F\alpha\circ F(\eta)=\text{id}_{Fa}$ and $\eta\circ\alpha=\text{id}_a$. By definition, then, $\eta$ is a two-sided inverse to $\alpha$, so $\alpha$ is an isomorphism.

Analysis of the proof

This is an analysis of the proof showing what is not mentioned in the proof, similar to the analysis in Rigorous proofs.

  • An $F$-algebra is any arrow of the form $\alpha:Fa\to a$. This definition directly verifies statement (1). You do need to know the definition of “functor” and that the notation $Fa$ means $F(a)$ and $FFa$ means $F(F(a))$.
  • When I am chasing diagrams, I visualize the commutativity of the diagram in (2) by thinking of the red path and the blue path as having the same composites in this graph:





    In other words, $F\alpha\circ F\eta=\eta\circ\alpha$. Notice that the diagram carries all the domain and codomain information for the arrows, whereas the formula “$F\alpha\circ F\eta=\eta\circ\alpha$” requires you to hold the domains and codomains in your head.

  • (Definition of morphism of $F$-algebra) The reader needs to know that a morphism of $F$ algebras is any arrow $\delta:c\to d$ for which




    commutes.
  • (Definition of initial $F$-algebra) $\alpha$ is an initial $F$-algebra means that for any algebra $\beta:Fb\to b$, there is a unique arrow $\delta$ for which the diagram above commutes.
  • (2) is justified by the last two definitions.
  • Pulling a “rabbit out of a hat” in a proof means introducing something that is obviously correct with no motivation, and then checking that it results in a proof. Step (9) in the proof given in Rigorous proofs has an example of adding zero cleverly. It is completely OK to pull a rabbit out of a hat in a proof, as long as the result is correct, but it makes students furious.
  • In statement (3) of the proof we are considering here, the rabbit is the trivially commutative diagram that is adjoined on the right of the diagram from (2).
  • Statement (4) uses a fact known to all diagram chasers: Two joined commutative squares make the outside rectangle commute. You can visualize this by seeing that the three red paths shown below all have the same composite. When I am chasing a complicated diagram I trace the various paths with my finger, or in my head.



    You could also show it by pointing out that $\alpha\circ F\alpha\circ F\eta=\alpha\circ\eta\circ\alpha$, but to check that I think most of us would go back and look at the diagram in (3) to see why it is true. Why not work directly with the diagram?

  • The definition of initiality requires that there be only one $F$-algebra morphism from $\alpha:Fa\to a$ to itself. This means that the upper and lower bows in (7) commute.
  • The diagonal identity arrow in (8) is justified by the fact that the upper bow is exactly the same diagram as the upper triangular diagram in (8). It follows that the upper triangle in (8) commutes. I visualize this as moving the bow down and to the left with the upper left node $Fa$ as a hinge, so that the two triangles coincide. (It needs to be flipped, too.) I should make an interactive diagram that shows this.
  • The lower triangle in (8) also commutes because the square in (2) is given to be commutative.
  • (Definition of isomorphism in a category) An arrow $f:a\to b$ in a category is an isomorphism if there is an arrow $g:b\to a$ for which these diagrams commute:


    xx


    This justifies statement (9).

Remark: I have been profligate in using as many diagrams as I want because this can be seen on a screen instead of on paper. That and the fact that much more data about domains and codomains are visible because I am using diagrams instead of equations involving composition means that the proof requires the readers to carry much less invisible data in their heads.

Send to Kindle
exposition, language of math, math, proof, understanding math

Rigorous proofs

2 Comments

Rich and rigorous

When we try to understand a math statement, we visualize what the statement says using metaphors, images and kinetic feelings to feel how it is true, or to suggest that the statement is not true.

If we are convinced that it is true, we may then want to prove it. Doing that involves pitching out all the lovely pictures and metaphors and gestures and treating the mathematical objects involved in the proof as static and inert. “Static” means the object does not change. “Inert” means that it does not affect anything else. I am saying how we think about math objects for the purpose of rigorous proof. I am not saying anything about “what math objects are”.

In this post I give a detailed example of a proof of the rigorous sort.

Example

Informal statement

First, I’ll describe this example in typical spoken mathematical English. Suppose you suspect that the following statement is true:

Claim: Let $f(x)$ be a differentiable function with $f'(a)=0$.
Going from left to right, suppose the graph of $f(x)$ goes UP before $x$ reaches $a$ and then DOWN for $x$ to the right of $a$
Then $a$ has to be a local maximum of the function.

This claim is written in informal math English. Mathematicians talk like that a lot. In this example they will probably wave their hands around in swoops.

The language used is an attempt to get a feeling for the graph going up to $(a,f(a))$ and then falling away from it. It uses two different metaphors for $x\lt a$ and $x\gt a$. I suspect that most of us would want to clean that up a bit even in informal writing.

A more formal statement

Theorem: Let $f$ be a real valued differentiable function defined on an open interval $R$. Let $a$ be a number in $R$ for which $f'(a)=0$. Suppose that for all $x\in R$, $f$ increases for $x\lt a$ and decreases for $x\gt a$. Then $f(a)$ is a maximum of $f$ in $R$.

Proof

  1. By definition of derivative, \[\lim_{x\to a}\frac{f(x)-f(a)}{x-a}=0.\]
  2. By definition of limit, then for any positive $\epsilon$ there is a positive $\delta$ for which if $0\lt|x-a|\lt\delta$ then \[\left|\frac{f(x)-f(a)}{x-a}\right|\lt\epsilon.\]
  3. By requiring that $\delta\lt 1$, it follows from (2) that for any positive $\epsilon$, there is a positive $\delta$ for which if $0\lt|x-a|\lt\delta$, then $|f(x)-f(a)|\lt\epsilon$.
  4. “$f$ increases for $x\lt a$” means that if $x$ and $y$ are numbers in $R$ and $x\lt y\lt a$, then $f(x)\lt f(y)$.
  5. “$f$ decreases for $x\gt a$” means that if $x$ and $y$ are numbers in $R$ and $a\lt x\lt y$, then $f(x)\gt f(y)$.
  6. “$f(a)$ is a maximum of $f$ in $R$” means that for $x\in R$, if $x\neq a$, then $f(x)\lt f(a)$.
  7. Suppose that $x\in R$ and $x\lt a$. (The case that $x\gt a$ has a symmetric proof.)
  8. Given $\epsilon\gt0$ with $\delta$ as given by (3), choose $y\in R$ such that $x\lt y\lt a$ and $|f(y)-f(a)|\lt\epsilon$.
  9. By (4), $f(x)\lt f(y)$. So by (8), \[\begin{align*}
    f(x)-f(a)&=
    f(x)-f(y)+f(y)-f(a)\\ &\lt f(y)-f(a)\\ &\leq|f(y)-f(a)|\lt\epsilon\end{align*}\]
    so that $f(x)\lt f(a)+\epsilon$. By inserting “$-f(y)+f(y)$” into the second formula, I am “adding zero cleverly”, an example of pulling a rabbit out of a hat. Students hate that. But you have to live with it; as long as the statements following are correct, it makes a valid proof. Rabbit-out-of-a-hat doesn’t make a proof wrong, but it does make you wonder how the author thought of it. Live with it.
  10. Since (9) is true for all positive $\epsilon$, it follows that $f(x)\leq f(a)$.
  11. By the same argument as that leading up to (10), $f(\frac{x-a}{2})\leq f(a)$.
  12. Since $f(x)\lt f(\frac{x-a}{2})$, it follows that $f(x)\lt f(a)$ as required.

About the proof

This proof is intended to be a typical “rigorous” proof. I suspect it tends to be more rigorous than most mathematicians would find necessary,

Extensionality

The point about “rigor”, about insisting that the objects be static and inert, is that this causes symbols and expression to retain the same meaning throughout the text. This is one aspect of extensionality.

Of course, some of the symbols denote variables, or variable objects. This does not mean they are “varying”. I am taking this point of view: A variable refers to a math object but you don’t know what it is. Constraints such as $x\lt a$ rule out some possible values but don’t generally tell you exactly what $x$ is. There is more about this in Variable Objects

The idea in (6), for example, is that $y$ denotes a real number. You don’t know which number it is, but you do know some facts about it: $x\lt y\lt a$, $|f(y)\lt f(a)|\lt\epsilon$ and so on. Similarly you don’t know what function $f$ is, but you do know some facts about it: It is differentiable, for example, and $f'(a)=0$.

My statement that the variables aren’t “varying” means specifically that each unbound occurrence of the variable refers to the same value as any other occurrence, unless some intervening remark changes its meaning. For example, the references to $x$ in (7) through (10) refer to the same value it has in (6), and (10), in particular, constitutes a statement that the claim about $x$ is correct.

Checkability

The elimination of metaphors that lets the proof achieve rigor is part of a plan in the back of the mind of at least some mathematicians who write proofs. The idea is that the proof be totally checkable:

  • Every statement in the proof has a semantics, a meaning, that is invariant (given the remark about variables above).
  • Each statement is justified by some of the previous statements. This justification is given by two systems that the reader is supposed to understand.
  • One system is the rules of symbol manipulation that are applied to the symbolic expressions, ordinary algebra, and higher-level manipulations used in particular branches of math.
  • The other system consists of the rules of logical reasoning that justify the claims that each statement follows logically from preceding ones.
  • These two systems are really branches of one system, the entire system of math computation and reasoning. It can be obscure which system is being used in a particular step.

Suppression of reasons

The logical and symbolic-manipulation reasons justifying the deductions may not be made completely explicit. In fact, for many steps they may not be mentioned at all, and for others, one or two phrases may be used to give a hint. This is standard practice in writing “rigorous” proofs. That is a descriptive statement, made without criticism. Giving all the reasons is essentially impossible without a computer.

I am aware that some work has been done to write proof checkers that can read a theorem like the one we are considering, stated in natural language, and correctly implement the semantics I have described in this list. I don’t know of any references to such work and would appreciate information about it.

Suppression of reasons makes it difficult to mechanically check a proof written in this standard “rigorous” writing style. Basically, you must be at at least the graduate student level to be able to make sense of what is said, and even experienced math research people find it difficult to read a paper in a very different field. Writing the proof so that it can be checked by a proof checker requires understanding of the same sort, and it typically makes the proof much longer.

One hopeful new approach is to write the proofs using homotopy type theory. The pioneers in that field report that the proofs don’t expand nearly as much as is required by first order logic.

Examples of suppression

Here are many examples of suppression in the $\epsilon$-$\delta$ proof above. This is intended to raise your consciousness concerning how nearly opaque writing in math research is to anyone but the cognoscenti.

  • The first sentence of the theorem names $R$ and $f$ and puts constraints on them that can be used to justify statements in the proof. The naming of $R$ and $f$ requires that every occurrence of $R$ in the proof refers to the same mathematical object, and similarly for $f$.

Remark: The savvy reader “knows” the facts stated in (a), possibly entirely subconsciously. For many of us there is no conscious thought of constraints and permanence of naming. My goal is to convince those who teach beginning abstract math course to become conscious of these phenomena. This remark applies to all the following items as well.

  • The second sentence gives $a$ a specific meaning that will be maintained throughout the proof. It also puts constraints on $a$ and an additional constraint on $f$.
  • The third sentence gives a constraint on $R$, $f$ and $a$. It does not give a constraint on $x$, which is a bound variable. Nor does it name $x$ as a specific number with the same meaning in the rest of the proof. (That happens later).
  • The fact that the first three sentences impose constraints on various objects is signaled by the fact that the sentences are introduced by “let” and “suppose”. The savvy reader knows this.
  • The fourth sentence announces that “$f(a)$ is a maximum of $f$ in $R$” is a consequence of the constraints imposed by the preceding three sentences. (In other words, it follows from the context.) This is signaled by the word “then”.
  • The fact that the paragraph is labeled “Theorem” informs us that the fourth sentence is therefore a statement of what is to be proved, and that every constraint imposed by the first three sentences of the Theorem may be used in the proof.
  • In the proof, statements (1), (4), (5) and (6) rewrite the statements in the theorem according to the definitions of the words involved, namely “derivative: “increases”, “decreases” and “maximum”. Rewriting statements according to the definitions of the words involved is a fundamental method for starting a proof.
  • (2) follows from (1) by rewriting using the definition of “limit”. Note that pattern-matching against the definition of limit requires understanding that there is a zero inside the absolute value signs that is not written down. Could a computer proof-checker handle that?
  • (3) follows from (2). The reader or proof-checker must:
    • Know that it is acceptable to put an upper bound on $\delta$ in the definition of limit.
    • Notice that you can move $|x-a|$ out of the denominator because $x\neq a$ by (2).
  • The conclusion in (6) that we much show that $f(x)\lt f(a)$ is now the statement we must prove.

Remark: In the following items, I mention the context of the proof. I am using the word informally here. It is used in some forms of formal logic with a related but more precise meaning. The context consists of the variables you must hold in your head as you read each part of the proof, along with their current constraints. “Current” means the “now” that you are in when considering the step of the proof you are reading right now. I give some references at the end of the post.

  • At the point between (6) and (7), our context consists of $a$, $R$ and $f$ all subject to some constraints. $x$ is not yet in the context of our proof because its previous occurrences in the theorems and in (1) through (6) have been bound, mostly by an unexpressed universal quantifier. Now we are to think of $x$ as a specific number bound by some constraints.
  • The statement in (7) that the case $x\gt a$ as a symmetric proof is a much higher-level claim than the other steps in this proof, even though in fact it is not very high level compared to statements such as “An application of Serre’s spectral sequence shows$\ldots$”. Most mathematicians with even a little experience will read this statement and accept it in the confidence that they will know how to swap “$\lt$” and “$\gt$” in the proof in the correct way (which is a bit picky) to provide a dual proof. Some students might write out the dual proof to make sure they understand it (more likely because writing it out was a class assignment). I await the day that an automated proof checker can handle a statement like this.
  • (8) introduces three new math objects $\epsilon$, $\delta$ and $y$ subject to several constraints. The symbols occur earlier but they are all bound. $\epsilon$ will be fixed in our context from now until (10). The others don’t appear later.
  • (9) consists of several steps of algebraic computation. A cognoscent (I am tired of writing “savvy”) reader first looks at the computation as a whole and notices that it deduces that $|f(x)-f(a)|\lt\epsilon$, which is almost what is to be proved. This helps the reader understand the reason for the calculation. No mention whatever is made in this step of all this stuff that should go through your mind (or the proof-checker’s “mind”).
  • The computations in (9) are are basic algebra not explained step by step, except that the remark that $f(x)\lt f(y)$ explains how you get $f(x)-f(y)+f(y)-f(a) \lt f(y)-f(a)$.
  • (10) banishes $\epsilon$ from the context by universally quantifying over it. That $f(x)\leq f(a)$ follows by the garbage-dump-in-Star-Wars trick that often baffles first year analysis students: Since for all positive $\epsilon$, $f(x)\lt f(a)+\epsilon$, then $f(x)\leq f(a)$. (See also Terry Tao’s article in Tricks Wiki.)
  • (11) “By the same argument as leading up to (10)” puts some demands on the reader, who has to discover that you have to go back to (7) and do the following steps with a new context using a value of $x$ that is halfway closer to $a$ than the “old” $x$ was. This means in particular that the choice of $\frac{x-2}{2}$ is unnecessarily specific. But it works.
  • (12) suppresses the reference to (11).

    • References

    I have written extensively on these topics. Here are some links.

    Rich-rigorous bifurcation in math thinking

The symbolic language

Math English and the language of proofs

Proofs and context

Send to Kindle
abstractmath.org, exposition, math, representations, understanding math

Thinking about a function as a mathematical object

Leave a comment

A mathematician’s mental representation of a function is generally quite rich and may involve many different metaphors and images kept in mind simultaneously. The abmath article on metaphors and images for functions discusses many of these representations, although the article is incomplete. This post is a fairly thorough rewrite of the discussion in that article of the representation of the concept of “function” as a mathematical object. You must think of functions as math objects when you are taking the rigorous view, which happens when you are trying to prove something about functions (or large classes of functions) in general.

What often happens is that you visualize one of your functions in many of the ways described in this article (it is a calculation, it maps one space to another, its graph is bounded, and so on) but those images can mislead you. So when you are completely stuck, you go back to thinking of the function as an axiomatically-defined mathe­matical structure of some sort that just sits there, like a complicated machine where you can see all the parts and how they relate to each other. That enables you to prove things by strict logical deduction. (Mathematicians mostly only go this far when they are desperate. We would much rather quote somebody’s theorem.) This is what I have called the dry bones approach.

The “mathematical structure” is most commonly a definition of function in terms of sets and axioms. The abmath article Specification and definition of “function” discusses the usual definitions of “function” in detail.

Example

This example is intended to raise your consciousness about the possibilities for functions as objects.

Consider the function $f:\mathbb{R}\to\mathbb{R}$ defined by $f(x)=2{{\sin }^{2}}x-1$. Its value can be computed at many different numbers but it is a single, static math object.

You can apply operators to it

  • Just as you can multiply a number by $2$, you can multiply $f$ by $2$.   You can say “Let $g(x)=2f(x)$” or “Let $g=2f$”. Multiplying a numerical function by $2$ is an operator that take the function $f$ to $2f$. Its input is a function and its output is another function. Then the value of $g$ (which is $2f$) at any real $x$ is $g(x)=2f(x)=4{{\sin }^{2}}x-2$. The notation  “$g=2f$” reveals that mathematicians think of $f$ as a single math object just as the $3$ in the expression “$2\times 3$” represents the number $3$ as a single object.
  • But you can’t do arithmetic operations to functions that don’t have numerical output, such as the function $\text{FL}$ that takes an English word to its first letter, so $\text{FL}(`\text{wolf’})=`\text{w’}$. (The quotes mean that I am writing about the word ‘wolf’ and the letter ‘w’.) The expression $2\times \text{FL}(`\text{wolf’})$ doesn’t make sense because ‘w’ is a letter, not a number.
  • You can find the derivative.  The derivative operator is a function from differentiable functions to functions. Such a thing is usually called an operator.  The derivative operator is sometimes written as $D$, so $Df$ is the function defined by: “$(Df)(x)$ is the slope of the tangent line to $f$ at the point $(x,f(x)$.” That is a perfectly good definition. In calculus class you learn formulas that allow you to calculate $(Df)(x)$ (usually called “$f'(x)$”) to be $4 \sin (x) \cos (x)$.

Like all math objects, functions may have properties

  • The function defined by $f(x)=2{{\sin}^{2}}x-1$ is differentiable, as noted above. It is also continuous.
  • But $f$ is not injective. This means that two different inputs can give the same output. For example,$f(\frac{\pi}{3})=f(\frac{4\pi}{3})=\frac{1}{2}$. This is a property of the whole function, not individual values. It makes no sense to say that $f(\frac{\pi}{3})$ is injective.
  • The function $f$ is periodic with period $2\pi$, meaning that for any $x$, $f(x+2\pi)=f(x)$.     It is the function itself that has period $2\pi$, not any particular value of it.  

As a math object, a function can be an element of a set

  • For example,$f$ is an element of the set ${{C}^{\infty }}(\mathbb{R})$ of real-valued functions that have derivatives of all orders.
  • On ${{C}^{\infty }}(\mathbb{R})$, differentiation is an operator that takes a function in that set to another function in the set.   It takes $f(x)$ to the function $4\sin x\cos x$.
  • If you restrict $f$ to the unit interval, it is an element of the function space ${{\text{L}}^{2}}[0,1]$.   As such it is convenient to think of it as a point in the space (the whole function is the point, not just values of it).    In this particular space, you can think of the points as vectors in an uncountably-infinite-dimensional space. (Ideas like that weird some people out. Do not worry if you are one of them. If you keep on doing math, function spaces will seem ordinary. They are OK by me, except that I think they come in entirely too many different kinds which I can never keep straight.) As a vector, $f$ has a norm, which you can think of as its length. The norm of $f$ is about $0.81$.

The discussion above shows many examples of thinking of a function as an object. You are thinking about it as an undivided whole, as a chunk, just as you think of the number $3$ (or $\pi$) as just a thing. You think the same way about your bicycle as a whole when you say, “I’ll ride my bike to the library”. But if the transmission jams, then you have to put it down on the grass and observe its individual pieces and their relation to each other (the chain came off a gear or whatever), in much the same way as noticing that the function $g(x)=x^3$ goes through the origin and looks kind of flat there, but at $(2,8)$ it is really rather steep. Phrases like “steep” and “goes through the origin” are a clue that you are thinking of the function as a curve that goes left to right and levels off in one place and goes up fast in another — you are thinking in a dynamic, not a static way like the dry bones of a math object.

Send to Kindle
abstractmath.org, exposition, language of math, math, representations, understanding math

The definition of “function”

1 Comment

 

This is the new version of the abstractmath article on the definition of function. I had to adapt the formatting and some of it looks weird, but legible. It is prettier on abstractmath.org.

I expect to announce new revisions of other abmath articles on this blog, with links, but not to publish them here. This article brings out a new point of view about defining functions that I wanted to call attention to, so I am publishing it here, as well.

 

FUNCTIONS: SPECIFICATION AND DEFINITION

It is essential that you understand many of the images, metaphors and terminology that mathe­maticians use when they think and talk about functions. For many purposes, the precise mathematical definition of "function" does not play much of a role when you are trying to understand particular kinds of functions. But there is one point of view about functions that has resulted in fundamental progress in math:

 

 

A function is a mathematical object.

To deal with functions in that way you need a precise definition of "function". That is what this article gives you.

  • The article starts by giving a specification of "function".
  • After that, we get into the technicalities of the definitions of the general concept of function.
  • Things get complicated because there are several inequivalent definitions of "function" in common use.

Specification of "function"

A function $f$ is a mathematical object which determines and is completely determined by the following data:

(DOM) $f$ has a domain, which is a set. The domain may be denoted by $\text{dom} f$.

(COD) $f$ has a codomain, which is also a set and may be denoted by $\text{cod} f$.

(VAL) For each element $a$ of the domain of $f$, $f$ has a value at $a$, denoted by $f(a)$.

(FP) The value of $f$ at $a$ is completely determined by $a$ and $f$.

(VIC) The value of $f$ at $a$ must be an element of the codomain of $f$.

  • The operation of finding $f(a)$ given $f$ and $a$ is called evaluation.
  • "FP" means functional property.
  • "VIC" means "value in codomain".

Examples

The examples of functions chapter contains many examples. The two I give here provide immediate examples.

A finite function

Let $F$ be the function defined on the set $\left\{1,\,2,3,6 \right\}$ as follows: $F(1)=3,\,\,\,F(2)=3,\,\,\,F(3)=2,\,\,\,F(6)=1$. This is the function called "Finite'' in the chapter on examples of functions.

  • The definition of $F$ says "$F$ is defined on the set $\left\{1,\,2,\,3,\,6 \right\}$". That phrase means that the domain is that set.
  • The value of $F$ at each element of the domain is given explicitly. The value at 3, for example, is 2, because the definition says that $F(2) = 3$. No other reason needs to be given. Mathematical definitions can be arbitrary.
  • The codomain of $F$ is not specified, but must include the set $\{1,2,3\}$. The codomain of a function is often not specified when it is not important — which is most of the time in freshman calculus (for example).

A real-valued function

Let $G$ be the real-valued function defined by the formula $G(x)={{x}^{2}}+2x+5$.

  • The definition of $G$ gives the value at each element of the domain by a formula. The value at $3$, for example, is $G(3)=3^2+2\cdot3+5=20$.
  • The definition of $G$ does not specify the domain. The convention in the case of functions defined on the real numbers by a formula is to take the domain to be all real numbers at which the formula is defined. In this case, that is every real number, so the domain is $\mathbb{R}$.
  • The definition does not specify the codomain, either. However, must include all real numbers greater than or equal to 4. (Why?)

What the specification means

  • The specification guarantees that a function satisfies all five of the properties listed.
  • The specification does not define a mathematical structure in the way mathematical structures have been defined in the past: In particular, it does not require a function to be one or more sets with structure.
  • Even so, it is useful to have the specification, because:

     

     

    Many mathematical definitions
    introduce extraneous technical elements
    which clutter up your thinking
    about the object they define.

     

     

    I will say more about this when I give the various definitions that are in use.

History

Until late in the nineteenth century, functions were usually thought of as defined by formulas (including infinite series). Problems arose in the theory of harmonic analysis which made mathematicians require a more general notion of function. They came up with the concept of function as a set of ordered pairs with the functional property (discussed below), and that understanding revolutionized our understanding of math.

This discussion is an over­simpli­fication of the history of mathe­matics, which many people have written thick books about. A book relevant to these ideas is Plato's Ghost, by Jeremy Gray.

In particular, this definition, along with the use of set theory, enabled abstract math (ahem) to become a common tool for understanding math and proving theorems. It is conceivable that some of you may wish it hadn't. Well, tough.

The more modern definition of function given here (which builds on the older definition) came into use beginning in the 1950's. The strict version became necessary in algebraic topology and is widely used in many fields today.

The concept of function as a formula never disappeared entirely, but was studied mostly by logicians who generalized it to the study of function-as-algorithm. Of course, the study of algorithms is one of the central topics of modern computing science, so the notion of function-as-formula (updated to function-as-algorithm) has achieved a new importance in recent years.

To state both the old abstract definition and the modern one, we need a preliminary idea.

The functional property

A set $P$ of ordered pairs has the functional property if two pairs in $P$ with the same first coordinate have to have the same second coordinate (which means they are the same pair). In other words, if $(x,a)$ and $(x,b)$ are both in $P$, then $a=b$.

How to think about the functional property

The point of the functional property is that for any pair in the set of ordered pairs, the first coordinate determines what the second one is. That's why you can write "$G(x)$'' for any $x $ in the domain of $G$ and not be ambiguous.

Examples

  • The set $\{(1,2), (2,4), (3,2), (5,8)\}$ has the functional property, since no two different pairs have the same first coordinate. Note that there are two different pairs with the same second coordinate. This is irrelevant to the functional property.
  • The set $\{(1,2), (2,4), (3,2), (2,8)\}$ does not have the functional property. There are two different pairs with first coordinate 2.
  • The empty set $\emptyset$ has the function property vacuously.

Graph of a function.

Example: graph of a function defined by a formula

In calculus books, a picture like this one (of part of $y=x^2+2x+5$) is called a graph. Here I use the word "graph" to denote the set of ordered pairs \[\left\{ (x,{{x}^{2}}+2x+5)\,\mathsf{|}\,x\in \mathbb{R } \right\}\] which is a mathematical object rather than some ink on a page or pixels on a screen.

The graph of any function studied in beginning calculus has the functional property. For example, the set of ordered pairs above has the functional property because if $x$ is any real number, the formula ${{x}^{2}}+2x+5$ defines a specific real number.

  • if $x = 0$, then ${{x}^{2}}+2x+5=5$, so the pair $(0, 5)$ is an element of the graph of $G$. Each time you plug in $0$ in the formula you get 5.
  • if $x = 1$, then ${{x}^{2}}+2x+5=8$.
  • if $x = -2$, then ${{x}^{2}}+2x+5=5$.

You can measure where the point $\{-2,5\}$ is on the (picture of) the graph and see that it is on the blue curve as it should be. No other pair whose first coordinate is $-2$ is in the graph of $G$, only $(-2, 5)$. That is because when you plug $-2$ into the formula ${{x}^{2}}+2x+5$, you get $5$ and nothing else. Of course, $(0, 5)$ is in the graph, but that does not contradict the functional property. $(0, 5)$ and $(-2, 5)$ have the same second coordinate, but that is OK.

Modern mathematical definition of function

A function $f$ is a mathematical structure consisting of the following objects:

  • A set called the domain of $f$, denoted by $\text{dom} f$.
  • A set called the codomain of $f$, denoted by $\text{cod} f$.
  • A set of ordered pairs called the graph of $ f$, with the following properties:
  • $\text{dom} f$ is the set of all first coordinates of pairs in the graph of $f$.
  • Every second coordinate of a pair in the graph of $f$ is in $\text{cod} f$ (but $\text{cod} f$ may contain other elements).
  • The graph of $f$ has the functional property.

Using arrow notation, this implies that $f:A\to B$.

Remark

The main difference between the specification of function given previously and this definition is that the definition replaces the statement "$f$ has a value at $a$" by introducing a set of ordered pairs (the graph) with the functional property.

  • This set of ordered pairs is extra structure introduced by the definition mainly in order to make the definition a classical sets-with-structure, which makes the graph, which should be a concept derived from the concept of function, into an apparently necessary part of the function.
  • That suggests incorrectly that the graph is more of a primary intuition that other intuitions such as function as relocator, function as transformer, and other points of view discussed in the article Intuitions and metaphors for functions.

Examples

  • Let $F$ have graph $\{(1,2), (2,4), (3,2), (5,8)\}$ and define $A = \{1, 2, 3, 5\}$ and $B = \{2, 4, 8\}$. Then $F:A\to B$ is a function. In speaking, we would usually say, "$F$ is a function from $A$ to $B$."
  • Let $G$ have graph $\{(1,2), (2,4), (3,2), (5,8)\}$ (same as above), and define $A = \{1, 2, 3, 5\}$ and $C = \{2, 4, 8, 9, 11, \pi, 3/2\}$. Then $G:A\to C$ is a (admittedly ridiculous) function. Note that all the second coordinates of the graph are in $C$, along with a bunch of miscellaneous suspicious characters that are not second coordinates of pairs in the graph.
  • Let $H$ have graph $\{(1,2), (2,4), (3,2), (5,8)\}$. Then $H:A\to \mathbb{R}$ is a function, since $2$, $4$ and $8$ are all real numbers.
  • Let $D = \{1, 2, 5\}$ and $E = \{1, 2, 3, 4, 5\}$. Then there is no function $D\to A$ and no function $E\to A$ with graph $\{(1,2), (2,4), (3,2), (5,8)\}$. Neither $D$ nor $E$ has exactly the same elements as the first coordinates of the graph.

Identity and inclusion

Suppose we have two sets  A and  B with $A\subseteq B$.

  • The identity function on A is the function ${{\operatorname{id}}_{A}}:A\to A$ defined by ${{\operatorname{id}}_{A}}(x)=x$ for all $x\in A$. (Many authors call it ${{1}_{A}}$).
  • When $A\subseteq B$, the inclusion function from $A$ to $B$ is the function $i:A\to B$ defined by $i(x)=x$ for all $x\in A$. Note that there is a different function for each pair of sets $A$ and $B$ for which $A\subseteq B$. Some authors call it ${{i}_{A,\,B}}$ or $\text{in}{{\text{c}}_{A,\,B}}$.

The identity function and an inclusion function for the same set $A$ have exactly the same graph, namely $\left\{ (a,a)|a\in A \right\}$. More about this below.

Other definitions of function

Original abstract definition of function

Definition

Remarks

Possible confusion

Some confusion can result because of the presence of these two different definitions.

Multivalued function

Some older mathematical papers in com­plex func­tion theory do not tell you that their functions are multi­valued. There was a time when com­plex func­tion theory was such a Big Deal in research mathe­matics that the phrase "func­tion theory" meant complex func­tion theory and all the cogno­scenti knew that their functions were multi­valued.

The phrase multivalued function refers to an object that is like a function $f:S\to T$ except that for $s\in S$, $f(s)$ may denote more than one value.

Examples

  • Multivalued functions arose in considering complex functions. In common practice, the symbol $\sqrt{4}$ denoted $2$, although $-2$ is also a square root of $4$. But in complex function theory, the square root function takes on both the values $2$ and $-2$. This is discussed in detail in Wikipedia.
  • The antiderivative is an example of a multivalued operator. For any constant $C$, $\frac{x^3}{3}+C$ is an antiderivative of $x^2$.

A multivalued function $f:S\to T$ can be modeled as a function with domain $S$ and codomain the set of all subsets of $T$. The two meanings are equivalent in a strong sense (naturally equivalent}). Even so, it seems to me that they represent two differ­ent ways of thinking about multivalued functions. ("The value may be any of these things…" as opposed to "The value is this whole set of things.")

The phrases "multivalued function" and "partial function" upset some picky types who say things like, "But a multi­valued func­tion is not a func­tion!". A step­mother is not a mother, either. See the Hand­book article on radial category.

Partial function

A partial function $f:S\to T$ is just like a function except that its input may be defined on only a subset of $S$. For example, the function $f(x)=\frac{1}{x}$ is a partial function from the real numbers to the real numbers.

This models the behavior of computer programs (algorithms): if you consider a program with one input and one output as a function, it may not be defined on some inputs because for them it runs forever (or gives an error message).

In some texts in computing science and mathematical logic, a function is by convention a partial function, and this fact may not be mentioned explicitly, especially in research papers.

New approaches to functions

All the definitions of function given here produce mathematical structures, using the traditional way to define mathematical objects in terms of sets. Such definitions have disadvantages.

Mathematicians have many ways to think about functions. That a function is a set of ordered pairs with a certain property (functional) and possibly some ancillary ideas (domain, codomain, and others) is not the way we usually think about them$\ldots$Except when we need to reduce the thing we are studying to its absolutely most abstract form to make sure our proofs are correct. That most abstract form is what I have called the rigorous view or the dry bones and it is when that reasoning is needed that the sets-with-structure approach has succeeded.

Our practice of abstraction has led us to new approaches to talking about functions. The most important one currently is category theory. Roughly, a category is a bunch of objects together with some arrows going between them that can be composed head to tail. Functions between sets are examples of this: the sets are the objects and the functions the arrows.

This abstracts the idea of function in a way that brings out common ideas in various branches of math. Research papers in many branches of mathematics now routinely use the language of category theory. Categories now appear in some undergraduate math courses, meaning that Someone needs to write a chapter on category theory for abstractmath.org.

Besides category theory, computing scientists have come up with other abstract ways of dealing with functions, for example type theory. It has not come as far along as category theory, but has shown recent signs of major progress.

Both category theory and type theory define math objects in terms of their effect on and relationship with other math objects. This makes it possible to do abstract math entirely without using sets-with-structure as a means of defining concepts.

 

Send to Kindle
exposition, language of math, math, understanding math

Function and codomain

Leave a comment

I recently posted the following information in the talk page of the Wikipedia article on functions, where they were arguing about whether "function" means a set of ordered pairs with the functional property or a structure with a domain $D$, a codomain $C$, and a graph $G$ which is a subset of $D\times C$ with the functional property.

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)
 
 

Send to Kindle
abstracting algebra, abstractmath.org, exposition

Conceptual and Computational

Leave a comment

I have posted a revision of the article Conceptual and Computational on abstractmath.org.

  • 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.

Send to Kindle
exposition, math, representations, understanding math

The power of being naive

Leave a comment

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 MM Def Deriv.nb, which is available for free use under a Creative Commons Attribution-ShareAlike 2.5 License. See How to manipulate the diagrams for more information on what you can do with them. The notebook can be read by CDF Player if you cannot make the embedded versions in this post work.

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?

Concept Prob

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.

 

Send to Kindle
abstractmath.org, exposition

Writing math for the web

2 Comments

Abstractmath

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.

Send to Kindle
abstracting algebra, category theory, computer science, exposition, math, representations, understanding math

Monads for High School III: Algebras

1 Comment

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