Composition of functions is associative

-
This post was first published on my WordPress blog on April 1 2012 with the title Is composition of functions associative?
In fact, at the time of writing, that post is still my most popular blog post so far, for some reason!
Because of the date of the post, it was mistaken by some people as a joke. I certainly doubt that many people share my concerns at all. Nevertheless, for anyone who is even remotely worried about the theory hidden behind the mathematical interpretation of nested brackets, the approach here does give a slightly different way to think about this proof. I may be almost alone in finding this reassuring! Meanwhile, I still continue to give the standard proof of associativity of composition of functions in my first-year introductory pure maths module at the University of Nottingham.

Is composition of functions associative?

Well, of course it is.

[Notes in italics added 30/7/12: In spite of the [original] date of this post, it is not intended to be a joke (except in as much as my concerns here may appear amusing!). However, the [original] title of the post might be somewhat misleading. I am not suggesting that there is actually any doubt about the truth of these standard results, namely that composition of functions is associative, and that evaluation of expressions with nested brackets is unambiguous. What I am really asking is whether the standard proof of the fact that composition of functions is associative is a fully convincing one.]

I'm sure you have seen the standard proof that composition of functions is associative, but let me remind you how it goes.

Let \(W,X,Y\) and \(Z\) be sets, and suppose that we are given functions

\(h:W\to X\), \(g:X\to Y\) and \(f:Y\to Z\)

We show that \((f\circ g)\circ h = f\circ (g\circ h)\) as follows.

Let \(w\in W\). Then

\(((f\circ g)\circ h)(w) = (f\circ g)(h(w)) = f(g(h(w)))\)

and

\((f\circ (g\circ h))(w) = f( (g\circ h)(w)) = f(g(h(w)))\).

Since \(((f\circ g)\circ h)(w) = (f\circ (g\circ h))(w)\)

for all \(w\in W\), we have

\((f\circ g)\circ h = f\circ (g\circ h)\,.\)

Now perhaps it is just me, but I suspect that seeing so many brackets around here might make for some initial confusion for the students. But is there more to it than that? As mathematicians, we know how to evaluate expressions involving lots of brackets. In fact we all learned how to prioritize brackets over the other mathematical operations when we were at school. But somewhere implicit in this is a confidence that we know how to evaluate expressions involving nested brackets and that these expressions are unambiguous.

But how do we know that evaluating expressions with nested brackets is unambiguous? Are we assuming here that composition of functions is associative? [Or maybe we need, at some earlier stage, to perform a check that is essentially equivalent to proving that composition of functions is associative?] That would then lead to circularity in the argument above. [Or at least it might render the standard proof less satisfactory?]

Here is my suggestion for breaking out of this possible problem.

First of all, how else could we define the function \(f\circ g\). Perhaps we are happy at least with the definition \((f\circ g)(x) = f(g(x))\): after all, there doesn't seem to be any ambiguity there. Still, let's see this another way.

Given \(x\in X\), set \(y = g(x)\in Y\), and then set \(z = f(y)\in Z\). Then the function \(f\circ g\) is the function \(x\mapsto z\), where \(z\) is defined in terms of \(x\) as above.

How can this possibly help? Well, if we return to the composition of functions, let's see what the new definitions of

\((f\circ g)\circ h\) and \(f\circ (g\circ h)\)

look like.

Let \(w\in W\). Set \(x=h(w)\in X\), set \(y=g(x)\in Y\) and set \(z=f(y)\in Z\).

Examining our definitions above, we discover that

\(z= (f\circ g)(x)\) where \(x=h(w)\), and so

\(z = ((f\circ g)\circ h)(w)\)

(and you could rewrite this in longhand in English if you want to avoid some of the brackets round the functions!)

Similarly

\(y = (g\circ h)(w)\) and \(z = f(y)\), giving us

\(z= (f\circ (g\circ h))(w)\)

(and again, we can rewrite everything in English to avoid some of the brackets round the functions).

The rest of the proof is as before.

I'm not really sure whether this helps, or hinders in general! But perhaps there are a few more people like me out there who might be glad to see that there isn't really any circularity in the proof after all. That is, if I haven't introduced some new problems above ...

[Most people I have spoken to think that it is obvious that unambiguous evaluation of nested brackets can't possibly depend on associativity of function composition. It is not so obvious to me. I would have to look carefully at the inductive definition needed to explain how to evaluate complex mathematical expressions in order to be sure what was used where. I am sure that it is fine in the end, but that inductive construction is not something that a first-year undergraduate will have met. 
See also comments on the original WordPress post
https://explainingmaths.wordpress.com/2012/04/01/is-composition-of-functions-associative/]



Comments

Post a Comment

Popular posts from this blog

An introduction to the Hahn-Banach extension theorem: Part VI

-
In this post we sketch a second proof of the Hahn-Banach Extension Theorem for continuous linear functionals on real normed spaces, this time using transfinite induction. We omit some of the details, which the reader can fill in. In particular, some of the details are similar to those involved in proving the claim made in Part V (when we obtained an upper bound for a chain). For a non-zero ordinal $\gamma$, recall that, with ordinal interval notation, we have $\gamma=[0,\gamma)$. That is, $\gamma$ is equal to the set of all ordinals which are strictly less than $\gamma$. However, we use ordinal interval notation throughout. If you prefer to use $\gamma$ instead of $[0,\gamma)$ that is fine, of course! Looking at the Wikipedia page on the Hahn-Banach Theorem , apparently both Hahn and Banach (independently) used transfinite induction in their proofs, rather than Zorn's Lemma. Theorem (Hahn-Banach Extension Theorem for linear functionals on normed spaces over $\R$)  Let $(E,\jnorm)$ ...
Read more

Discussion of the proof that the uniform norm really is a norm

-
In response to a request on Piazza, I gave a detailed proof that the uniform really is a norm, including some comments and warnings on possible pitfalls along the way. Here (essentially) is what I said. Let’s have a look at \(\|\cdot\|_\infty\) on the bounded, real-valued functions on \([0,1]\) (but you can also work with bounded functions on any non-empty set you like, and the same proof will work). We define \(\ell_\infty([0,1]) = \{f: f \textrm{ is a bounded, real-valued function on }[0,1]\,\}\,,\) and this is the set/space we will look at. So we set \(Y=\ell_\infty([0,1])\). Then you can check for yourselves that \(Y\) really is a vector space over \(\mathbb{R}\) (using the usual "pointwise" operations for functions). Note that the zero element in this vector space is the constant function \(0\) (from \([0,1]\) to \(\mathbb{R}\)), which I'll denote by \(\mathbf{0}\) here for clarity. (We also used \(Z\) for this function in one of the exercises.) I'll first give...
Read more

An introduction to the Weierstrass M-test: Part I

-
In order to make these posts accessible to first-year undergraduate students, I am going to be working with real-valued functions defined on intervals in $\R$. I'm also going to avoid focusing on uniform convergence for sequences of functions, and instead focus on absolute convergence of series of functions, and how this fits with continuity. I'll then start to look at differentiability. For those interested in my approach to teaching uniform convergence for sequences of functions, I have a video about this on YouTube (at  https://www.youtube.com/watch?v=mB4Yny0T3HA ). Students watching this video should be warned that my non-standard notion of " absorption " (intended to help students understand convergence of sequences properly) has not really caught on! Other lecturers are unlikely to know about this notion of absorption, and so you should avoid using that terminology unless you explain it locally. However, if you want to know more about my absorption approach, s...
Read more