We want to prove that composition of functions is associative.
Suppose we have
Base input: w
x = h(w)
y = g(x)
z = f(y)
We can form the ordered pair (w,z). This reflects composition of the functions where we take the input w, then feed it into h, take the output of h and feed it into g and then take the output of g and feed it into f to get z.
We have at this point (w,z) = (w,f(g(x)).
Suppose we form a function A by taking ordered pairs
where A(b) = f(g(b))
So we have pairs of the form (b,f(g(b)).
We want to show that when b = h(w) that
(w,A(b)) = (w,z)
When b = h(w), then b = x, since x = h(w).
A(b) = A(x) = f(g(x))
(w,A(x)) = (w,f(g(x)))
We have from our initial discussion
(w,z) = (w,f(g(x)))
So by transitivity
(w,A(x)) = (w,z)
Thus composition of functions is associative.
The following blog post stimulated this post.
I interpret this as being by Joel Feinstein.
As reference, the following provides a proof that looks more like the standard proof. See page 41 and 42. Page 42 helps make it easier to follow.
Dedekind does the proof of associativity of functions in his 1888 essay, “The Nature and Meaning of Numbers”, Paragraph Number 25 (see page 30 of PDF this link). Dedekind does not use ordered pairs as given above in this blog post, but his proof is closer in flavor to this one.
There is a kind of subtle simplification in the above proof that comes from Dedekind. This is to key on x. Dedekind does not even have a symbol in his derivation beyond the x above. He uses the equivalent of w and x only, and the function names. His function names are Greek letters. (For w Dedekind uses s and for x, Dedekind uses s’.)
Also an interesting version of Peano Axioms based on sets and the von Neumann construction.
If you click on a theorem, you can see its proof.
There is a fake quality to associativity of functions. In a calculation sense, there is only one order of doing the calculations. You can’t do the last calculation first for an individual pass.
In function terms, we can think of each function as existing with all its ordered pairs. When we think of it this way, then we get a thread through the sequence of functions. However, there is still only one thread when we think of it this way.
Base input: w = fertilizer
nectar = x = h(w) = plant(fertilizer)
insect = y = g(x) = sips(nectar)
bird = z = f(y) = eats(insect)
So we start with fertilizer that is converted into nectar by the plant function, and the insect eats the nectar. The bird eats the insect. This can’t really get started until each one does his work first.
Of course, if instead of the bird getting the insect, the insect turned into fertilizer, then we would have a diagram where we could start where we wanted.
In the proof above, we concentrate on what happens not at input w, but once we get to x. It is from that point on we are doing our manipulations to prove associativity. This was realized by Dedekind in his 1888 proof.
So where we define the function A in terms of pairs (b,A(b)) = (b, f(g(b)).
Exercise: Restate the proof in terms of the fertilizer to bird example given. The proof then relates to a thread from a specific pile of fertilizer through a particular plant to an indicated bit of nectar through a definite insect to a special bird.
Exercise: Add another link at the start or the end. For example, a dog gets the bird. Prove that combining the first two pairs of functions and the second two pairs separately and then combining those equals doing the functions in order from fertilizer onwards.
Exercise: Contrast function associativity with addition. (2+3) + 4 = 2+(3+4). In addition, we can evaluate 2+3 first and also 3+4 first. This is contrast with composition of functions, where we need to know what value to use as input for the outer layers. Write a short discussion contrasting these.
As we consider generalizations, we have the problem that we might have distinct composition sequences that are not equivalent. This is even possible with 3 functions. There are compatibility issues that arise. For the following questions we are really thinking of equivalents to a single path of function evaluations.
Exercise: The questions given here may be sloppily posed. Identify this in each case, and add the additional restrictions to make them properly posed. This can refer to compatibility of the input and output sets, or restricting the equivalence claimed to equivalence to a particular thread.
Exercise: Enumerate all possible ways to compose functions with 4 functions that are equivalent to a given initial path of function evaluations. This in effect requires stating a condition that amounts to evaluating from inside to outside in what will end up being the same order. Prove the possible equivalent ways you identify are equal in result.
Exercise: Enumerate all possible equivalent ways to compose functions with 5 functions equivalent to a given initial path of function evaluations. This again means maintaining the same order of evaluation in the end. Prove they are equal.
Exercise: State a condition for composition of n functions to be equivalent. Prove by induction that with n functions, all the different combinations allowed by your condition are equal.