Composition of surjective functions

1. Jul 16, 2014

Korisnik

I'm learning maths myself, but I'm going to university in 2 months. This is my first try at proving anything.

1. The problem statement, all variables and given/known data
Prove that the composition of surjective functions is also a surjection.

2. Relevant equations
A definition of surjective function:
If $f:S_1\rightarrow S_2$ is a surjection:
$\forall y\in S_2\exists x\in S_1:y=f(x)$.

A definition of composition of functions:
If $f:S_1\rightarrow S_2$ and $g:S_2\rightarrow S_3$ are functions, then $h:S_1\rightarrow S_3$ is the composition of functions f and g:
$g\circ f(x)=g[f(x)]=g(y)=z$.

3. The attempt at a solution
I've read some of the texts that talk about proofs, and all of them made sense to me, for example the proving of an irrational number and square roots, but I can't say if this proof is "enough".

If $f:S_1\rightarrow S_2$ and $g:S_2\rightarrow S_3$ are surjections by definitions:

$\forall y\in S_2\exists x\in S_1:y=f(x)\ \ \ \ (1)$
$\forall z\in S_3\exists y\in S_2:z=g(y)\ \ \ \ (2)$,

composition of these two functions $g\circ f(x)$ is also a surjection.

We have to prove:
$\forall z\in S_3\exists x\in S_1:z=g\circ f(x)$.

Let $z\in S_3$, then there is a particular $y\in S_2$ such that $z=g(y)$ by the $(2)$ axiom and there is a particular $x\in S_1$ such that $y=f(x)$ by the $(1)$ axiom. It follows that $z=g(y)=g[f(x)]=g\circ f(x)$ which is by the definition, the composite of functions $f$ and $g$. This means that for all $z$ we've found a particular $x$ for which the statement is true.

Last edited: Jul 16, 2014
2. Jul 16, 2014

jbunniii

Your proof is fine. I noticed one typo: you wrote $g : S_1 \rightarrow S_2$ when it should be $g : S_2 \rightarrow S_3$. Also, a minor notational observation: the "mapsto" arrow $\mapsto$ is usually used to indicate how elements are mapped, whereas the "rightarrow" arrow $\rightarrow$ is used for the domain and codomain. Example: the function $f : \mathbb{R} \rightarrow \mathbb{R}$ defined by $x \mapsto x^2$.

3. Jul 16, 2014

jbunniii

By the way, a good practice to help understand a theorem and its proof is to consider what happens if one of the hypotheses is excluded. Can you come up with examples where only one of $f$ or $g$ is a surjection, and $g \circ f$ fails to be a surjection?

4. Jul 16, 2014

Korisnik

Yes, it was a typo indeed, I kept checking, but this scheme-text (3 parts of asking a homework question) kept popping up so I had to delete it.

I've been told to use the "mapsto" when I used "rightarrow"... even though in the book the "rightarrow" is used. Sorry for that.

Isn't a surjection just a matter of defining sets (domain and co-domain), therefore if a function is defined otherwise, I can claim it's (not) a surjection.
(For example, $f(x)=x^2, f:\mathbb{R}\rightarrow\mathbb{R^+}$ is a surjection, whereas if it was defined as $f:\mathbb{R}\rightarrow\mathbb{R}$ it wouldn't be a surjection.)

Example where $f$ and $g$ are not both surjections:

$f(x)=2x\space (1)\\g(y)=y^2\space (2)\\g\circ f(x)=4x^2\space (3)$

$(1)$ is a surjective, $(2)$ isn't, and so $(3)$ isn't.

5. Jul 16, 2014

jbunniii

It's not a big deal, if your instructor prefers "mapsto" then go ahead and use that.

Yes, this is all correct.
Right, assuming the codomain of $g$ is something larger than $\mathbb{R}^+$ (for example $\mathbb{R}$).

How about if $g$ is a surjection but $f$ is not? Do you see what goes wrong in that case?

6. Jul 16, 2014

Korisnik

I hope so, I'll try to illustrate.

Using the same functions but switching names (assuming: $f:\mathbb{R}\rightarrow \mathbb{R}$ for $f(x)=x^2$ and $g:\mathbb{R}\rightarrow\mathbb{R}$ for $g(y)=2y$).

$g\circ f(x)=2x^2$, which again isn't a surjection (if it was, it would be $g\circ f:\mathbb{R}\rightarrow\mathbb{R}$), because in reality:

$g\circ f(x)=g\circ f(\mathbb{R})=g[f(\mathbb{R})]=g(\mathbb{R^+})=\mathbb{R^+}\Rightarrow g\circ f:\mathbb{R}\rightarrow\mathbb{R^+}$.

Therefore condition ($g\circ f:\mathbb{R}\rightarrow\mathbb{R}$) isn't fulfilled, and it's not a surjection.

If that's what You meant.

7. Jul 16, 2014

jbunniii

Yes, that's what I meant, although be careful about the statement that $g\circ f:\mathbb{R}\rightarrow\mathbb{R^+}$. The set to the right of the $\rightarrow$ is the codomain, not necessarily the image. Indeed, we must have $g\circ f:\mathbb{R}\rightarrow\mathbb{R}$ because the codomain of $g \circ f$ is the same as the codomain of $g$ (by definition). However, $g \circ f$ is not a surjection because $g(f(\mathbb{R})) = \mathbb{R^+}$, which is a strict subset of the codomain $\mathbb{R}$.

8. Jul 17, 2014

Korisnik

Yes but I wrote "in reality"... hahah. It was a quazi-conclusion about "real" codomain to make it easier to compare what has to be compared. Thanks for everything!

9. Jul 17, 2014

jbunniii

Yes, I understood what you meant. Just wanted to point out that the "right" way to say it is that $g(f(\mathbb{R})) = \mathbb{R^+}$, not $g\circ f:\mathbb{R}\rightarrow\mathbb{R^+}$. Mathematicians (probably including the ones grading your homework once you get to your university) are pretty pedantic about notation.