1
$\begingroup$

From what I understand, one-to-oneness means every element in $A$ is mapped to a unique element in $B$. To be onto, means for every $y$ in $B$, there exist at least one $x$ in $A$ from which it can be derived in a function ($f$, per say). As $g\circ f$ is a bijection, it is both one to one and onto.

How can I use this information to prove $f$ is one to one and $g$ is onto? Can I have some help?

Homework question in proofs class.

I think I've found the proof that $f$ is one to one:

Suppose $f(x) = f(y)$.

Then $g(f(x)) = g(f(y))$ Then $g\circ f(x) = g\circ f(y)$

Since $g\circ f$ is a bijection, $x = y$. Therefore, $f$ is one to one.

Can I have some help proving $g$ is onto?

$\endgroup$
1
  • $\begingroup$ how you conclude, that $g(x)=g(y)$? $\endgroup$ Commented May 5, 2014 at 23:21

4 Answers 4

1
$\begingroup$

Your proof is flawed. I can see this just by "type checking": you apply $f$ to $x$, then you apply $g$ to it. But you can only apply $f$ to things in $A$, and you can only apply $g$ to things in $B$, and you have no idea if any things are in both.

Can you answer the question when $g \circ f$ is actually the identity function? (in which case $C = A$).

The form of the proofs would be:

  • $f$ is one-to-one: pick $x,y \in A$. Assume $f(x) = f(y)$. Can you show $x = y$?
  • $g$ is onto: pick $y \in C$ (i.e. $A$). Can you find $x \in B$ such that $g(x) = y$?

Thinking about that type checking I did earlier, mostly these proofs are the only possible thing they can be: all you can do to elements of $A$ is apply $f$, and all you can do to elements of $B$ is apply $g$, so there's really not many ways forward here. This means that you really don't have many possible situations to check, so the answer can't be very well hidden. Abstract proofs are actually the easiest, once you've got the hang of them!

If you can get those proofs sorted, then return to the case where $g \circ f$ (let's call it $h$) is merely a bijection, and see if you can fix the proofs by inserting $h^{-1}$ in appropriate places.

$\endgroup$
2
  • $\begingroup$ Would this be a valid proof for proving g is onto? : Let $c$ be an element of $C$. Since $f$ is one to one, when $f(x)=f(y), x=y$. Since $gof$ is onto, there exists an $a$ in $A$ such that $gof(a)=c$. Thus $f(a)$ is an element of B, and g(f(a))=C. $\endgroup$
    – user122661
    Commented May 6, 2014 at 3:58
  • $\begingroup$ @user122661: your comment about $f$ being one-to-one is unnecessary, otherwise yes, your proof is correct. $\endgroup$ Commented May 6, 2014 at 22:54
0
$\begingroup$

In general if f is not one-to-one which means f(x1)=f(x2) and x1 and x2 are different. so gf(x1)=gf(x2) with x1 and x2 are different. Contradict to gf is one-to-one.

IF g is not onto then there exist c in C. For any b in B g(b) not equal to c. Then, for any a in A gf(a) could not equal to c f(a) is in B. Contradict to gf is onto

$\endgroup$
0
$\begingroup$

If $(g\circ f):A\longrightarrow B$ is a bijection, then remember that if $(x,z)\in (g\circ f)$ then there is $y$, such that $(x,y)\in f$ and $(y,z)\in g$.

Is easy show that $g$ is onto, how $(g\circ f)$ is onto, then for all $z\in C$ there is a $x\in A$, with $(x,z)\in (g\circ f)$, but by definition of composition, then for all $z$ there is a $y\in B$ with $(y,z)\in g$, then $g$ is onto.

$\endgroup$
0
$\begingroup$

Let $ h = g \circ f$. In order for $h$ to be a bijection, it needs to be

  1. Onto, which means that for every $c \in C$, $h(x) = c$ for some $x \in A$. Since $h = g \circ f$, $c = h(x) = g(f(x))$, which means that $g$ must be onto in order for $h$ to be onto.

  2. One-to-one, which means that for every $a, b \in A$, if $h(a) = h(b)$, then $a = b$ (for every element in the image of the function, there is at most one element from the domain that maps to it). Assume that $h$ is one-to-one, and that $f$ isn't. This means that there is some $x,y \in A$ such that $f(x) = f(y)$ but $x \neq y$. This in turn means that $h(x) = g(f(x)) = h(y) = g(f(y))$, while $x \neq y$. But this is a contradiction; $h$ can't be one-to-one if $f$ isn't one-to-one. This means that $f$ has to be one-to-one if $h$ is one-to-one.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .