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.

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.

share|improve this question
3  
I'm sorry to say that neither of the arguments you present is a valid proof; they are both just examples of the situation, and not proofs that the results hold in general. An example does not constitute a proof that the result always hold (does the fact that you are named Krysten mean that everyone is named Krysten?). So, no; neither is valid. –  Arturo Magidin Feb 17 '11 at 22:48
2  
But nonetheless, +1 for showing you're trying. By the way, if this is homework, please tag it with the [homework] tag. Thank you. –  Arturo Magidin Feb 17 '11 at 22:49
    
No. These are statements about general $f$ and $g$. You can't prove them by giving examples for which they are true. You can only use a counterexample to show that a statement is false, not an example to show that it's true. You'll need to reason about $f$ and $g$ independent of specific examples. –  joriki Feb 17 '11 at 22:50
    
I edited my proof for a. Please confirm that this is valid. –  Krysten Feb 17 '11 at 23:14
    
I think your proof for (a) is correct, but you should perhaps specify what $f(4)$ is. As for (b), I editted my answer and included some helpful tips. –  Myself Feb 17 '11 at 23:58

3 Answers 3

up vote 4 down vote accepted

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!

share|improve this answer
    
thanks. it makes sense to create a proof that includes all possible cases. –  Krysten Feb 18 '11 at 3:11
    
@Krysten: This is the major drive of mathematicians, to be as general as possible so that the theorem will be applicable to as many cases as possible. Sometimes some limitations must be included, but even then mathematicians always look for the most general terms available. –  Asaf Karagila Feb 18 '11 at 10:36

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 proof 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.
share|improve this answer

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.

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.