Composition of surjective functions

[Korisnik]

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

Homework Statement

Prove that the composition of surjective functions is also a surjection.

Homework 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$.

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.

 

[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$.

 

[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?

 

[Korisnik]

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$.

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.

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?

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.

 

[jbunniii]

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

It's not a big deal, if your instructor prefers "mapsto" then go ahead and use 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.)

Yes, this is all correct.

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.

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?

 

[Korisnik]

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

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.

 

[jbunniii]

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.

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}$.

 

[Korisnik]

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}$.

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!

 

[jbunniii]

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!

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.