Show that Function Compositions Are Associative

Question

My intent is to show that a composition of bijections is also a bijection by showing the existence of an inverse. But my approach requires the associativity of function composition.

Let $f: X \rightarrow Y, g: Y \rightarrow Z, h: Z \rightarrow W$ be functions.
$((f \circ g) \circ h)(x) = h((f \circ g)(x)) = h(g(f(x)))$, and $(f \circ (g \circ h))(x) = (g \circ h)(f(x)) = h(g(f(x)))$.

However, I am having problems in justifying that the two compositions, $(f \circ g) \circ h$ and $f \circ (g \circ h)$, have the same domain and range. When I consulted ProofWiki, whose link is at the bottom, I got even more confused. Specifically, for $(f \circ g) \circ h = f \circ (g \circ h)$ to be defined, ProofWiki requires that dom$g =$ codom$f$ and dom$h =$ codom$g$.

First of all, I think that it should be dom$g =$ range$f$ .... Moreover, as you can see in the example below, you actually have to adjust domains and ranges of $f, g, h$ for the requirement to hold true.
Let $f: \mathbb R \rightarrow \mathbb R$ be $f(x) = 2x$, $g: \mathbb R^+ \rightarrow \mathbb R$ be $g(y) = ln(y)$, $h: \mathbb R \rightarrow \mathbb R$ be $h(z) = z - 10$.
Then $((f \circ g) \circ h)(x) = ln(2x) - 10 = (f \circ (g \circ h))(x)$, with dom$((f \circ g) \circ h) = \mathbb R^+$ = dom$(f \circ (g \circ h))$. As a result, we need to set dom$f = \mathbb R^+$, range$f = \mathbb R^+$; dom$g$, range$g$, dom$h$, and range$h$ remain the same. Am I allowed to do that?

This adjustment implies that when we say dom$f = X$, $f$ must be defined for all elements in $X$, but $X$ may not be the entire set of elements for which $f$ is defined.

http://www.proofwiki.org/wiki/Composition_of_Mappings_is_Associative

Answer 1

Usually, when $f\colon X\to Y$ and $g\colon Y\to Z$ are maps, their composition is written $g\circ f$, rather than $f\circ g$: in this way you write $$ g\circ f(x)=g(f(x)) $$ by definition.

You seem to confuse codomain and range. The range, or image, of $f$ is the subset of the codomain $Y$ consisting of the elements $f(x)$, for $x\in X$. The range has no role whatsoever when composition of maps is considered. At least, when maps are supposed to be defined on the whole domain as is the case when talking of surjectivity or bijectivity.

Associativity is almost obvious. If you have another function $h\colon Z\to W$, you have, by definition, that $g\circ f\colon X\to Z$ and $h\circ g\colon Y\to W$. Thus one can consider also the compositions $$ h\circ(g\circ f) \qquad\text{and}\qquad (h\circ g)\circ f $$ and both are maps $X\to W$, so it makes sense to ask if they are equal. They are, because for each $x\in X$ we have $$ h\circ(g\circ f)(x)=h(g\circ f(x))= h(g(f(x))=h\circ g(f(x))=(h\circ g)\circ f(x). $$ If you can't parse this, just set $y=f(x)$, $z=g(y)$, $F=g\circ f$ and $G=h\circ g$, so that $F(x)=g(f(x))=g(y)=z$. Then $$ h\circ(g\circ f)(x)=h\circ F(x)=h(F(x))=h(z) $$ and $$ (h\circ g)\circ f(x)=G\circ f(x)=G(y)=h\circ g(y)=h(g(y))=h(z) $$ so the two elements are the same.

Answer 2

You have $$(f\circ g)\circ h(x) = f\circ g(h(x)) = f(g(h(x)),$$ and $$f\circ(g\circ h(x)) = f(g \circ h (x)) = f(g(h(x)).$$ The associativity you seek now follows.

Answer 3

Perhaps it's EVEN easier (clearer?) to reason about a more general construction (with heavy inspiration both from the definition of a category, the excellent answer of mcg256, and the helpful comment of Milan)?

We can view a relation R(A,B) as a collection of paths so that each path has a unique initial point in the set A and a unique terminal point in the set B.

In the special case of a relation a path is determined by its endpoints, but this is NOT a necessary assumption.

Thus, to define composition more generally, we can view the starting data as two collections of arrows M(A,B) and M(B,C), every arrow in M(X,Y) has source in X and target in Y, and we can concoct a third collection of arrows M(A,B)*M(B,C)=M(A,B,C) via cancatenation, we can combine two arrows precisely if the target of the first is the source of the second.

To check associativity, given the starting data M(A,B) M(B,C) and M(C,D), we must show that M(A,B,C)*M(C,D) ``='' M(A,B)*M(B,C,D). We are at risk of having a canonical isomorphism rather than equality, and hence the quotes around the symbol =.

Precisely the same input is needed to manufacture a typical arrow in each side of the previous equation.

The pictures one might draw to illustrate a typical arrow in the respective calculations are

(A->B-->C)--->D and A->(B-->C--->D).

Thus, if we define M(A,B,C,D) as the collection of all diagrams A->B-->C--->D, (so that the target of -> is the source of --> etc..) then the 3 collections at hand are all canonically isomorphic.

Have we shown that composition is associative?

Perhaps we have at least gotten to the heart of the matter, and established a precise sense in which 3 formally different things are the same.

It is tempting to say that in the special case of functions and relations, that the 3 formaly different things are precisely the same, but even here perhaps we should be careful, since we are perhaps relying on canonical isomorphisms among products of finite sets:

(AxB)xC is canonically isomorphic to Ax(BxC) which in turn is canonically isomorphic to the collection of all ordered triples (a,b,c) from the respective factors.

It is also tempting to say that in practice, no confusion arises, if our biggest crime is conflating canonically isomorphic things.

However the vector (a,b,c) reminds me of a purported proof of a VERY famous conjecture in number theory, which according to my extremely pedestrian grasp of the opinion of experts, is perhaps problematic, due in part the conflation of: thing versus thing up to isomorphism or perhaps isomorphic copy of thing.

Attempted summary of the post at hand: The candidate isomorphism from the types (xy)z and x(yz) is in fact an isomorphism, rendering a sense in which xyz is unambiguous.

But, much like the composer of this post, https://explainingmaths.wordpress.com/2012/04/01/is-composition-of-functions-associative/,

I am unsatisfied with the post at hand. It is obvious that function composition is/(must be) associative, but attempts at modest generalization, leave me questioning where, if anywhere, there might be a bit of sleight of hand.

It would be fun to have a long thoughtful discussion leading to the agreement that indeed all the matters at are trivially obvious, obviously trivial, and that nowhere has there been any sleight of hand after all.