Injective and Surjective Functions

Question

Let $f$ and $g$ be functions such that $f\colon A\to B$ and $g\colon B\to C$. Prove or disprove the following

a) If $g\circ f$ is injective, then $g$ is injective

Here's my proof that this is true. Let $A = \{4,5\}$, $B = \{3,9\}$, $C = \{1,2\}$ $f(4) = 3$; $f(5) = 9$ $g\circ f(4) = 1$ and $g\circ f(5) = 2$ Since no 2 elements map to the same element in the range $g\circ f$ and $g$ are both injective.

b) If $f$ and $g$ are surjective, then $g\circ f$ is surjective.

Here's my proof that this is true. Let $A = \{1,2\}$, $B = \{4\}$, $C = \{5\}$, $f(1) = 4$; $f(2) = 4$ $g\circ f(1) = 5$ and $g\circ f(2) = 5$. Since no elements are left unmapped then $g\circ f$ and $f$ and $g$ are surjective

Are these proofs valid?

**Edit: Ok so I revised my proof for a. I will disprove it using a counterexample. Let A = {4}, B = {3,9}, C={1}. g∘f(4) = 1 and g(3) = 1 and g(9) = 1 g∘f is injective but g is not injective because 3 and 9 both map to 1. Is that a valid disproof?

Now I'm just having some trouble disproving or proving b. If anyone could lend some tips. Also this is not homework. Just reviewing for an exam.

Answer 1

The idea of a mathematical proof is that without dependence of a specific input, if certain properties are true, then the conclusion is also true.

In this case, if the composition is injective then it has to be that the "outer" function is injective, and that if the functions are surjective then their composition is as such.

Showing a specific case is a valid method for disproving a claim, as it shows that at a certain time the properties hold but the conclusion is false.

For example, consider $A=\{0\}$ and $B=\{1,2\}$ and $C=\{0\}$ and $f(0)=1$ and $g(1)=0, g(2)=0$.

The composition $g\circ f$ is a function from $A$ to $C$, since $A$ is a singleton every function is injective. However $g$ is clearly not injective.

This is a counterexample to the claim, thus disproving it.

The proof for the second one, if both functions are surjective then so is their composition, let us check this.

Let $A,B,C$ any sets, and $f,g$ functions as required. To show that $g\circ f$ is surjective we want to show that every element of $C$ is in the range of $g\circ f$. Assume $c\in C$ then there is some element $b\in B$ such that $g(b)=c$. Since $f$ is surjective we have some $a\in A$ such that $f(a)=b$. It follows that $g\circ f (a) = c$ and therefore the composition of surjective functions is surjective.

Now, consider this proof. There was nothing to limit ourself. I did not require anything from $A,B,C$ other than them being sets, and I did not require anything from $f,g$ other than them being functions from/onto the required set in the premise of the claim. Furthermore, I did not check the surjective-ness of the composition by choosing a certain element. I picked and arbitrary element, from a set which was also arbitrary. Using this sort of argument assures us that the property is not dependent on any of the characteristics of the set (for example, some things are only true on finite, or infinite, or other certain sets). This allows us to have a very general theorem. Whenever we have three sets, and two functions which are surjective between them, then the composition is also surjective!

Answer 2

Theorem. If $n$ is a number, then $n^2 = 2n$.

Proof. Set $n = 2$. Then $n^2 = 4$ and $2n = 4$. Therefore $n^2 = 2n$.

... Hold on a second. For $n=3$ we have that $3^2 = 9$, but $2\cdot 3 = 6$, and $6\neq 9$. So the statement isn't valid after all! Can you see what went wrong?

The same thing applies for your statements. Instead of proving them in one particular case, you should prove them for every possible $f$ and $g$ you can think of.

[edit] Here's some help with case (b), I suggest you stop reading after every step and try to complete the proof yourself. If it doesn't work, read the next hint.

• We have to show that $g\circ f$ is surjective. Give any $c\in C$, we must show there is some $x\in A$ such that $g(f(x)) = (g\circ f)(x) = c$.
• We know that $g$ is surjective, therefore there exists some $b\in B$ such that $g(b) = c$.
• We know that $f$ is surjective, therefore there exists some $a\in A$ such that $f(a) = b$.
• Now $c = g(b) = g(f(a))$.
• We conclude that such $x$ exists indeed, it is precisely the element $a$ that we have constructed.

Answer 3

Let us consider statement a).

This is interpreted as

If $f: A \to B $ and $g: B \to C$ are functions such $ g \circ f$ is injective, then $g$ is injective.

If this statement were to be true,

it means that for any functions $f,g$ such that $g \circ f$ is injective it must be the case that $g$ is injective.

What you have done is shown a specific example of $f$ and $g$ for which this is true.

So basically you have proved:

There are some $f$, $g$ such that $g \circ f$ and $g$ are injective.

Consider the statement:

"If a dog has four legs then it has a tail".

To prove this, you have to show that every dog which has four legs also has a tail.

What you have done is you have just taken a specific example of a dog...

Now if the statement had been

"No dog with four legs has a tail".

Then by demonstrating a four-legged dog with a tail, you have disproven that statement.

So if you can find a specific case of $f$, $g$ such that $g \circ f$ is injective, but $g$ is not, then you have a valid proof (called proof by counter-example) that the statement is false.

Answer 4

You're assuming too much, bro. A proof shows something is true or false for all the assumptions you make, so your first proof shows that "If $g \circ f$ is injective, then $g$ is injective" is true but only for the functions and sets you defined. You have to show "If $g \circ f$ is injective, then $g$ is injective" is true for more general/abstract functions and sets (that just means you have assume less about them). As it turns out, "If $g \circ f$ is injective, then $g$ is injective" is false because you can find an example that doesn't satisfy it. Remember, too, that most propositions in Math have underlying Universal Quantifiers, so the proposition "If $g \circ f$ is injective, then $g$ is injective" has the underlying quantifiers: for all functions $f$ and $g$. So if you assume too much about them, you're gonna end up picking specific functions and so your proof is gonna show (if it shows anything) facts about them only. Your second proof has the same mistake. (Btw, unlike what others are saying, your proofs ARE indeed proofs, they just aren't showing what you were asked to show).

Here's a proof for the second proposition (which is true).

Pick an arbitrary element of $C$, $z$. Since $g$ is surjective, $z=g(y)$ for some $y \in B$. Since $f$ is surjective, $y=f(x)$ for some $x \in A$. So, $z=g(f(x))$ for some $x \in A$, and $g \circ f$ is surjective.

What I'm showing above is that for an arbitrary element of C, there exists a corresponding element in A that is being mapped to it (to the arbitrary element of C) by $g \circ f$.