Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
You wrote your compositions in an unusual order. Normally, the flow is right-to-left, $(f\circ g)(x) = f (g(x))$. Some people write left-to-right, but then the argument should also be written to the left of the function. –  Daniel Fischer Oct 12 '13 at 21:43

3 Answers 3

up vote 2 down vote accepted

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.

share|improve this answer
    
So in my example above, for the purpose of creating a composition, I am supposed to set dom$f$, range$f = \mathbb R^+$. Otherwise, there is no way for the definition to work. –  Andy Tam Oct 13 '13 at 15:27
    
@AndyTam What do you mean by "range"? In your example you can't do $g\circ f$, because the domain of $g$ is not the same as the codomain of $f$. Chaining functions in calculus uses different language and conventions. –  egreg Oct 13 '13 at 15:28
    
@ egreg: Range is indeed the image, or a subset of the codomain. $g(y) = ln(y)$, so dom$g = \mathbb R^+$. So I should set range$f = \mathbb R^+$. I feel that it is more accurate to talk about range$f$ because you are feeding something into $f$ first, then $g$ .... –  Andy Tam Oct 13 '13 at 15:33
    
@AndyTam That's what I suspected. With calculus conventions, composition of functions follows quite different rules, because you always have to determine the domain; when the notation $f\colon X\to Y$ is used it is usually assumed that $f$ is defined on the whole set $X$. So, with this convention, $g\circ f$ is not defined when $f\colon\mathbb{R}\to\mathbb{R}^+$ and $g\colon\mathbb{R}\to\mathbb{R}$. –  egreg Oct 13 '13 at 15:39
    
@ egreg: The question then boils down to whether I am allowed to reset the domains and codomains. In this particular question, it does not matter, because I am dealing with bijections. TY. –  Andy Tam Oct 13 '13 at 15:45

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 (h (x)) = f(g(h(x)).$$ The associativity you seek now follows.

share|improve this answer
    
you (still) have a typo in the middle of the second formula –  vadim123 Oct 12 '13 at 21:56

I found it easier to reason about composition using the following notation and definitions.

Infix notation for functions

$$(x,y)\in f \leftrightarrow x \space \boldsymbol f \space y $$ and let $$(x,b)\in f \wedge (b,y) \in g \leftrightarrow x \space \boldsymbol f \space b \space \boldsymbol g \space y$$ then

Definition of $(g \circ f)$

If $f,g$ are functions, then $(g \circ f)$ is the relation $$(x,y)\in(g\circ f)\leftrightarrow \exists b: x \space \boldsymbol f \space b \space \boldsymbol g \space y$$


Composition ($\circ$) is associative

If $h,g,f$ are functions, then $$(h \circ g) \circ f = h \circ (g \circ f)$$ Proof. $(x,y)\in(h \circ g) \circ f \leftrightarrow \exists b:x\space\boldsymbol f\space b\space\boldsymbol (\boldsymbol h \boldsymbol\circ \boldsymbol g \boldsymbol )\space y$. Where $b\space\boldsymbol (\boldsymbol h \boldsymbol\circ \boldsymbol g \boldsymbol )\space y \leftrightarrow (b,y)\in (h \circ g)\leftrightarrow \exists b': b\space\boldsymbol g \space b' \space\boldsymbol h \space y.$ Then the membership rule becomes $$(x,y)\in(h \circ g) \circ f \leftrightarrow \exists b,b': x\space\boldsymbol f\space b\space\boldsymbol g \space b' \space\boldsymbol h \space y$$ The other direction is again two applications of the definition of composition. $(x,y)\in h\circ (g \circ f) \leftrightarrow \exists b:x\space\boldsymbol (\boldsymbol g \boldsymbol \circ \boldsymbol f \boldsymbol) \space b \space \boldsymbol h \space y$. But $x\space\boldsymbol (\boldsymbol g \boldsymbol \circ \boldsymbol f \boldsymbol) \space b \leftrightarrow (x,b) \in (g \circ f) \leftrightarrow \exists b': x\space\boldsymbol f \space b' \space\boldsymbol g \space b$. Thus, $$(x,y)\in h \circ (g \circ f) \leftrightarrow \exists b,b': x\space\boldsymbol f\space b'\space\boldsymbol g \space b \space\boldsymbol h \space y$$ And so, $$(x,y) \in (h \circ g) \circ f \leftrightarrow (x,y)\in h \circ ( g \circ f)$$ Which implies $$(h \circ g) \circ f=h \circ ( g \circ f)$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.