MHB Proving Onto and 1-1 Properties of Function Compositions

[JProgrammer]

I am trying to prove this function theorem:

Let F:X→Y and G:Y→Z be functions. Then
a. If F and G are both 1 – 1 then G∘F is 1 – 1.
b. If F and G are both onto then G∘F is onto.
c. If F and G are both 1 – 1 correspondences then G∘F is a 1 – 1 correspondence.

Part a has already been proven, but I need to prove parts b and c. This is as far as I got on part b:Part b: If F is onto, then that means that each y has at least one x. If G is onto, then that each z has at least one y.

I do know that I need to prove b before c can be proven.

If someone could show me how b and c would be proven I would really appreciate it.

Thank you.

 

[Evgeny.Makarov]

I am trying to prove this function theorem:

Let F:X→Y and G:Y→Z be functions. Then
a. If F and G are both 1 – 1 then G∘F is 1 – 1.
b. If F and G are both onto then G∘F is onto.
c. If F and G are both 1 – 1 correspondences then G∘F is a 1 – 1 correspondence.
...
Part b: If F is onto, then that means that each y has at least one x. If G is onto, then that each z has at least one y.

It is incorrect to say "each y has at least one x". Here $x$ and $y$ are elements of sets $X$, $Y$, $Z$. They can very well be numbers. What does it mean to say, for example, that 5 has 3?

The fact that $G\circ F$ is onto means, by definition, that for every $z\in Z$ there exists an $x\in X$ such that
\[
(G\circ F)(x)\overset{\text{def}}{=}G(F(x))=z.\qquad (*)
\]
Proofs of statements of the form "For every $z\in Z$..." start with the phrase "Fix an arbitrary $z\in Z$". We know that $G$ is onto, i.e., for each $z\in Z$ there exists a $y\in Y$ such that $G(y)=z$. Apply this fact to the $z$ we fixed. This gives us some $y\in Y$ such that $G(y)=z$. Now apply the fact that $F$ is onto to that $y$ and recall that our goal is (*).

 

[HallsofIvy]

Let z be any member of Z. Then, since G is onto, there exist y in Y such that G(y)= z. Further, since F is onto there exist ...

For (c), what is the definition of "1-1 correspondence"?

 

[JProgrammer]

For (c), what is the definition of "1-1 correspondence"?

1 -1 correspondence means that the function is both 1 - 1 and onto.

 

[HallsofIvy]

1 -1 correspondence means that the function is both 1 - 1 and onto.

Good! So once you have done (a) and (b), (c) follows immediately.