# Proof that a function is bijective if and only if it is both surjective and injective

I am given the usual definitions for surjectivity and injectivity, but I am introduced with an alternative formulation of bijectivity:

Suppose $X$ and $Y$ are sets and $f:X\rightarrow Y$ a mapping. This mapping is said to be bijective if $\exists g:Y\rightarrow X$ such that $\forall x\in X,\ y\in Y$, $f(g(y))=y$ and $g(f(x))=x$.

I have to proof that in this sense, bijectivity is equivalent to simultaneous injectivity and surjectivity. Now from bijectivity, I found it quite easy to prove the other two conditions. The other way around, however, poses some difficulty. My proof:

Suppose $f:X\rightarrow Y$ is surjective and injective. I define the function $g:Y\rightarrow X$ by $g(y)=x\Longleftrightarrow f(x)=y$. Surjectivity of $f$ implies $\forall y\in Y\ \exists x\in X$ such that $f(x)=y$, thus $f(g(y))=y$. Now suppose $x,z\in X$ and $f(x)=f(z)$. Along with the definition of $g$ this implies $g(f(z))=x$. From injectivity follows $x=z$, thus $g(f(x))=x$.

First of all, initially, I have not shown that $g$ is well-defined. I am not sure how to actually prove this, or if it is even necessary here. However, using surjectivity of $f$ is it easy to see that $g$ maps every value of $Y$. Can I conclude from this that the function is well-defined, or is there more to say on the matter? I suppose I would also have to show that $g$ cannot take on two different values of $x$ for the same $y$. Also, suppose I have proven that $g$ is indeed well-defined, is my proof as presented above correct? Thank you for your help!

EDIT:

From a discussion in the comments of an answer, I have come to realise that perhaps I have misused the term "well-defined". Since I don't really understand the formal definition, I will re-state a part of my question as follows: can I directly use $g$ as defined above, or do I have to prove that it is "okay" to use it? I'm really not sure how to say this anymore... intuitively, I would say that "okay" means that the definition itself does not produce any inconsistencies. If it is necessary to prove something about it prior to using it, what is it?

• "I suppose I would also have to show that $g$ cannot take on two different values of $x$ for the same $y$." Absolutely true, but this is a consequence of $f$ being an injection. – Doug M Nov 20 '17 at 21:46

You're on the right track. If $f$ is not surjective, then $g$ cannot be defined on $Y$, since $f(g(y))$ is not defined if $y\notin\operatorname{rng}(f)$. As for injectivity, what can you say about $g(f(x))$ and $g(f(x'))$, when can they be equal?

In both cases, if $f$ is not an injective and surjective function, then $g$ is not well-defined. But since we are given that $g$ is a well-defined function, this would be impossible.

• Hey, thanks for your answer! So if I understand it correctly, you show that $f$ not being either a injection or surjection implies that $g$ is not well defined, which contradicts the fact that $f$ is both (by assumption), thus $g$ is well defined. Correct? Also, what about the rest of my proof? – Tyron Nov 20 '17 at 21:48
• No. Since $g$ is well-defined, it is necessarily the case that $f$ is both injective and surjective. – Asaf Karagila Nov 20 '17 at 21:49
• Hmm, but we know nothing about $g$ initially. I just defined it in a certain way and first have to prove that it is well-defined. Am I missing something here? – Tyron Nov 20 '17 at 21:52
• You know that it is a function. Therefore you know that it is a well-defined function. – Asaf Karagila Nov 20 '17 at 21:52
• Could it be that I misused the word "function" for "mapping" then, and these things mean something else? I don't really understand how you can say it this straightforward in any case. For example suppose I would consider the function (or mapping) $f:\{0\}\rightarrow\{0,1\}$ by $f(x)=x$ and I would define $g:\{0,1\}\rightarrow\{0\}$ the same way as above, then it seems to me that $g$ does not map $1$ to anything. If this is still okay, let $f(x)=1$ for real $x$, then $g$ (again, as above) maps $1$ to several elements. To my knowledge these are both examples of non well-defined functions. – Tyron Nov 20 '17 at 22:04

By definition a function $f:X\to Y$ is a subset of $X\times Y=\{\langle x,y\rangle\mid x\in X\wedge y\in Y\}$ such that for every $x\in X$ there is a unique $y\in Y$ such that $\langle x,y\rangle\in f$.

Now define $g:=\{\langle y,x\rangle\mid \langle x,y\rangle\in f\}\subseteq Y\times X$.

On base of injectivity and surjectivity of $f$ we will prove that $g$ is a function, i.e. that for every $y\in Y$ there is a unique $x\in X$ with $\langle y,x\rangle\in g$ or equivalently $\langle x,y\rangle\in f$.

Let $y\in Y$.

The surjectivity of $f$ guarantees that some $x\in X$ exists with $\langle x,y\rangle\in f$.

The injectivity of $f$ guarantees that this $x$ is unique, and proved is now that $g$ is indeed a function.

It remains to check whether we have indeed $f(g(y))=y$ for every $y\in Y$ and $g(f(x))=x$ for every $x\in X$.

For $y\in Y$ the following statements are equivalent:

• $f(g(y))=y$
• $\langle g(y),y\rangle\in f$
• $\exists z[z=g(y)\wedge\langle z,y\rangle\in f]$
• $\exists z[\langle y,z\rangle\in g\wedge\langle z,y\rangle\in f]$
• $\exists z[\langle y,z\rangle\in g\wedge\langle y,z\rangle\in g]$
• $\exists z[\langle y,z\rangle\in g]$

And it is obvious that the last statement is true because $g$ is a function on $Y$.

For $x\in X$ the following statements are equivalent:

• $g(f(x))=x$
• $\langle f(x),x\rangle\in g$
• $\exists z[z=f(x)\wedge\langle z,x\rangle\in g]$
• $\exists z[\langle x,z\rangle\in f\wedge\langle z,x\rangle\in g]$
• $\exists z[\langle x,z\rangle\in f\wedge\langle x,z\rangle\in f]$
• $\exists z[\langle x,z\rangle\in f]$

And it is obvious that the last statement is true because $f$ is a function on $X$.