[Math] Proof that a function is bijective if and only if it is both surjective and injective

elementary-set-theoryfunctionsproof-verification

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?

Best Answer

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$.

Related Question