Is composition of functions associative?
Well, of course it is.
[Notes in italics added 30/7/12: In spite of the 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 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 and be sets, and suppose that we are given functions
We show that as follows.
Let . Then
for all , we have
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 . Perhaps we are happy at least with the definition : after all, there doesn’t seem to be any ambiguity there. Still, let’s see this another way.
Given , set , and then set . Then the function is the function , where is defined in terms of as above.
How can this possibly help? Well, if we return to the composition of functions, let’s see what the new definitions of
Let . Set , set and set .
Examining our definitions above, we discover that
where , and so
(and you could rewrite this in longhand in English if you want to avoid some of the brackets round the functions!)
and , giving us
(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 …
[Feedback so far suggests that I may be in a minority of one with my concerns about the standard proof!]