1

I have this problem on my hands right now:

Let $$f:A\to B$$ and $$g:B\to A$$ be two functions. If $$g \circ f(a) = a, \forall a\in A$$ and if $$f \circ g(b) = b, \forall b\in B$$ then $f$ is a bijection.

Here are the things that are needed for $f$ to be a bijection:

It has to be injective meaning: $$F(x)=F(y)\implies x=y$$ and it has to be surjective meaning: $$\forall b\in B, \exists a\in A : F(a)=b$$

If this is true, could anyone give me a head start on how to approach this with Induction? Or how to set this up. I have searched on the internet, but have not found this specific problem and I have no idea how to approach this.. Thank you.

an4s
  • 3,716
TypeR
  • 15
  • I assume $g$ is a function from $B$ to $A$, rather than from $A$ to $B$? Aslo, why do you believe induction will help you? – Bram28 Mar 09 '18 at 00:42
  • 2
    You can't prove this with induction as for induction you need a order – Q the Platypus Mar 09 '18 at 00:43
  • Oh yes, sorry that was a typo – TypeR Mar 09 '18 at 00:47
  • 1
    You can't set this up on induction as there is nothing here pertaining to natural numbers at all. – fleablood Mar 09 '18 at 00:48
  • In class we were going over induction and my professor made it sound like, we have to use Induction to prove all the proofs that she gave us... If it is not possible to prove this by Induction, then what would be a good approach? – TypeR Mar 09 '18 at 00:52
  • "If it is not possible to prove this by Induction, then what would be a good approach?" Just follow the definitions. Prove if $f(x) = f(y)$ then $x =y$ (you are told that $g(f(x)) =x$ and $g(f(y)) = y$). And prove if $y \in B$ then there is an $x$ so that $f(x) = y$. (you are told that $f(g(y)) = y$.) – fleablood Mar 09 '18 at 00:59

1 Answers1

1

So... you have the definition. So do it.

we have to prove:

1) $f$ is an injection.

we must prove if $f(x) =f(y)$ then $x = y$..

If $f(x) = f(y)$ then $g\circ f(x) = g\circ f(y)$. But we are told that $g\circ f(x) = x$ and $g\circ f(y) = y$. So $x=g\circ f(x) = g\circ f(y) = y$.

2) $f$ is a surjection.

we must prove if $y \in B$ there is an $x \in A$ so that $f(x) = y$.

We are told that $f\circ g(y) = y$ for all $y \in B$ so just let $x =g(y) \in A$. Then $f(x) = f\circ g(y) = y$.

fleablood
  • 124,253
  • Thank you for the help! What would this method be called, by doing it like this? My professor wants the method names in the Introduction. I was thinking this is a Direct Method of proof, maybe? – TypeR Mar 09 '18 at 01:45
  • "Thank you for the help! What would this method be called, by doing it like this? My professor wants the method names in the Introduction."... Beats the heck out of me. I never had a professor who cared what you called methods or wanted you to recite names of things rather than simply understanding them. – fleablood Mar 09 '18 at 02:09