3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ "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. $\endgroup$ – Doug M Nov 20 '17 at 21:46
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Tyron Nov 20 '17 at 21:48
  • $\begingroup$ No. Since $g$ is well-defined, it is necessarily the case that $f$ is both injective and surjective. $\endgroup$ – Asaf Karagila Nov 20 '17 at 21:49
  • $\begingroup$ 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? $\endgroup$ – Tyron Nov 20 '17 at 21:52
  • $\begingroup$ You know that it is a function. Therefore you know that it is a well-defined function. $\endgroup$ – Asaf Karagila Nov 20 '17 at 21:52
  • $\begingroup$ 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. $\endgroup$ – Tyron Nov 20 '17 at 22:04
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.