[Math] Prove the following function is injective/surjective

discrete mathematics

I have the following problem using notation and terms I do not fully understand.

Let f: X $\to$ Y be a function. Prove that:

If there exists a function g: Y$\to$X such that g$\circ$f = 1$_X$, then f: X$\to$Y is injective

If there exists a function h: Y$\to$X such that f$\circ$h = 1$_Y$, then f: X$\to$Y is surjective

My problem starts with understanding what injective and surjective. These terms haven't been used in class, so I am not sure what the question is ultimately asking.

Secondly, I do not know what 1$_Y$ is equivalent to, or what it is in reference to.

Lastly, the prof gave us this bit of information that I do not fully understand:

f: X$\to$Y. If there exists g:Y$\to$X and h:Y$\to$X $\in$ g$\circ$f then f:X$\to$Y is bijective.

What makes this true? What does it mean for something to be bijective? I would assume that it means both subjective and surjective, but I cannot be certain.

Best Answer

There are colloquial terms often used for "injective" and "surjective". They are "one-to-one" and "onto" respectively. "Bijective" just means "both injective and surjective", or "one-to-one and onto".

To understand them, we need to back up and look again at the definition of a function. Recall that a function actually consists of 3 objects $(f, A, B)$. $A$ is a set, called the domain of the function, $B$ is a set, called the codomain of the function, and $f$ itself is a rule that matches each $a \in A$ with exactly one $b$ in $B$. If $a$ is matched to $b$, then we use the symbolry $f(a)$ to mean $b$.

Some important things to note about that definition:

  • $f$ is required to match every element of $A$ with something in $B$.
  • $f$ is NOT required to match every element of $B$ with anything in $A$.
  • for each $a \in A$, there is only one $b \in B$ that is matched to it.
  • for each $b \in B$, $b$ may be the match of any number (including zero) of different $a\in A$.

So for example I can define $f : \{1,2,3\} \to \{4, 5, 6, 7\}$ by $f(1)=4, f(2) = 6, f(3) = 6$. This is a function. $1, 2, 3$ are each carried to only one element of the codomain. But $f(2) = f(3)$, while $4$ and $7$ are not the image of anything under $f$. The codomain of $f$ is actually bigger than is needed. This is allowed in our definition of function, because there are many times when such functions are useful. For example, $f : \Bbb R \to \Bbb R, f(x) = x^2$ would not count as a function if we did not allow these.

The terms Injective, surjective and bijective are introduced for those times when we don't want to allow this to happen. They are further conditions on functions that forbid it:

  • A function $f : A \to B$ is injective if for every $x, y \in A$, if $x \ne y$, then $f(x) \ne f(y)$. An equivalent way of stating this is: for every $x, y \in A$, if $f(x) = f(y)$, then $x = y$. So no element of $A$ is matched to more than one element of $B$ (because $f$ is a function) and no element of $B$ is matched to more than one element of $A$ (because $f$ is injective). So this condition is also called "one-to-one".
  • A function $f : A \to B$ is surjective if for every $b \in B$, there is some $a \in A$ such that $f(a) = b$. Surjective just means the codomain $B$ isn't any bigger than it needs to be. There is nothing in it that is missed by $f$. Thus $f$ is said to be "onto $B$".
  • A function is bijective if it is both one-to-one and onto.

On any set $A$, $1_A$ denotes the identity function: $1_A : A \to A : a \mapsto a$. That is, for each $a \in A, 1_A(a) = a$.

Now, you are given a function $f:X\to Y$. The first question is:

  • Show that if there exists $g : Y \to X$ such that $g\circ f = 1_X$, then $f$ is injective.

Translated: you are given that there is a $g : Y \to X$ such that for all $x \in X, g(f(x)) = x$. From this, prove that for all $x \in X, r \in X$, if $f(x) = f(r)$, then $x = r$.

The second question is:

  • Show that if there exists $h : Y \to X$ such that $f \circ h = 1_Y$, then $f$ is surjective.

Translated: you are givent that there is an $h : Y \to X$ such that for all $y \in Y, f(h(y)) = y$. From this, prove that for all $y \in Y$, there is an $x \in X$ such that $f(x) = y$.

Finally, your last statement is incomplete. It should be: If there exists $g : Y \to X, h : Y \to X$ such that $g \circ f = 1_X$ and $f \circ h = 1_Y$, then $f$ is bijective.

This follows automatically from the previous statements.

If you think about each of these statements, you will see that $g$ "undoes" $f$, so it can be used to prove that $x = r$. And $h(y)$ provides you with the value $x$ you need for $f(x) = y$.

(And once you get those, see if you can go one step farther and prove that if $f$ is bijective, then $g = h$.)

Related Question