6

If I have a function (binary relation), $f: X \to Y:x \mapsto y$ and I show that it is well defined and I show that its inverse is well defined. Then have I shown that $f$ is a bijection? (That it is one to one, and onto)

By show that it is well defined I mean show that is is actually a function, not something masquerading as one. So that $\forall a,b \in X, a=b \implies f(a)=f(b)$ and that $\forall x \in X, \exists y \in Y$ such that $f(x)=y$

Or are there invertable functions that are not bijections? I am fairly sure there are not.

Frames Catherine White
  • 1,570
  • This requires a bit of context. Are you looking at functions as binary relations? If so, what does it mean for the inverse of $f$ to be well defined? Does it mean that the inverse relation is a function? – Git Gud Jun 17 '14 at 14:13
  • Invertible has a very specific definition. Namely, $f\colon A\to B$ is invertible if and only if there exists a $g\colon B\to A$ such that $f\circ g=\mbox{Id}_B$ and $g\circ f=\mbox{Id}_A$. If such an inverse $g$ exists for $f$, can you show that $f$ must be injective and surjective? Hint: use contradiction. – Dan Rust Jun 17 '14 at 14:15
  • Your function is certainly a bijection between $X$ and $\text{range}(f)$. It will be a bijection between $X$ and $Y$ only if $f$ is surjective, i.e. $\text{range}(f)=Y$. – Mark McClure Jun 17 '14 at 14:22
  • Something isn't right with what you're doing, the formula $\forall a,b \in X, a=b \implies f(a)=f(b)$ is either a triviality or senseless, depending on whether $f$ is a function or not. – Git Gud Jun 17 '14 at 14:26
  • No its not. Consider the "function" defined on the cross product of the quotient groups of some Group G and its subgroup N. $f:G/N\times G/N \to G/N:(Na,Nb)\mapsto Nab$ is not "well defined" (and thus is not truely a function) by my above definition unless N is normal. (There are multiple different values $Na=Na'$ for $a\ne a'$). It is nontrivial to specify a distinct element of $G/N$. Thus the requirement to check, that it is actually a function by doing the above check) – Frames Catherine White Jun 17 '14 at 14:36
  • @oxinabox did my hint help? I've supressed the 'well-definedness' in the comment because if a function exists we assume it is well-defined implicitly (obviously). – Dan Rust Jun 17 '14 at 14:42
  • @oxinabox The requirement to check is that "Given $(N_a, N_b), (N_c, N_d)\in (G/N)\times (G/N)$ such that $N_a=N_c\land N_b=N_d$, it holds that $N_{ab}=N_{cd}$". Notice that there is no mention of $f$ in this.You only earn the right to write $f(a)$ when $f$ is a function and $a\in \text{dom}(f)$. I allude to this in the third paragraph of this answer. – Git Gud Jun 17 '14 at 14:43
  • Git Gud: Sounds like semanitics to me. That is the requirement I am expressing, that it is well defined to its variables rather than merely to the representation of its variables (as you eloquence put it). I'm not sure why I can't use $f$ to do so. – Frames Catherine White Jun 17 '14 at 14:49
  • @DanielRust : It is quiet late here, I will poke at it tomorrow. (If you like you can post an answer (to get some delicious rep), I am fairly certain your suggestion will put me on the line to solve it myself.) – Frames Catherine White Jun 17 '14 at 14:50
  • It sounds like you'd gain more by attempting the exercise by yourself so feel free to let me know if you need some more prodding in the right direction. It's a good idea to prove the converse as well, that is "If $f$ is a bijection, then there exists an inverse $g$ of $f$" The other thing you might like to prove is that if $f$ has an inverse $g$, then $g$ is unique, that is, if $h$ is also an inverse of $f$, then $h=g$ (here use the definition of the identity functions). – Dan Rust Jun 17 '14 at 14:55
  • I'm sure I would, as I said I will give it a shot tomorrow. But on this site, I so often feel bad answering my own questions, based on a hint someone gave me in the comments. (As I would rather be awarding them the Rep). I do fully intent to do the proof as an exercise, with your hint. (I suspect I have done it before several years ago) – Frames Catherine White Jun 17 '14 at 14:58

1 Answers1

5

I'll expand on my comment a little.

The usual definition of an invertible function is the following

A function $f\colon A\to B$ is invertible if and only if there exists a function $g\colon B\to A$ such that the compositions $f\circ g=\mbox{Id}_B$ and $g\circ f=\mbox{Id}_A$ hold, where $\mbox{Id}_X\colon X\to X$ is the identity function on $X$.

Recall that the definition of the identity function $\mbox{Id}_X$ is the (it turns out unique) function such that for all $\alpha\colon X\to Y$ and for all $\beta\colon Z\to X$, it holds that $\mbox{Id}_X\circ\alpha=\alpha$ and $\beta\circ\mbox{Id}_X=\beta$. This is equivalent to defining $\mbox{Id}_X(x)=x$ for all $x\in X$.

It's a useful exercise to show that if $f$ has an inverse $g$, then $g$ is unique, that is, if $h$ is also an inverse of $f$, then $h=g$ (here use the definition of the identity functions to prove this).

Now, how can we show that if $f\colon A\to B$ is invertible, then $f$ must be a bijection? Well contradiction is a reasonable method to attempt. Suppose $f$ has inverse $g$ but that $f$ is not surjective. That means there exists an element $b\in B$ such that there exists no $a\in A$ with $f(a)=b$. Now, consider what this says about the function $f\circ g$. Why can this function not be equal to the identity on $B$?

What happens if we suppose that $f$ has inverse $g$ but that $f$ is not injective? That means there exist $a,a'\in A$ with $a\neq a'$ and such that $f(a)=f(a')$. Can you see how this would lead to the fact that $a=a'$? (hint: $g\circ f=\mbox{Id}_A$).

That's all there is to it. It's also another useful exercise to show the converse of the above proposition, namely that if $f$ is a bijection, then $f$ is invertible, and hence these are actually equivalent statements. Here, a more direct approach is in order to show this. So given an element $b$ in the codomain, define where the inverse should map $b$, and show that this mapping is a well-defined function in the sense that every element in the codomain of $f$ has a unique element in the domain of $f$ to which it is mapped. Here you'll need to use the fact that $f$ is surjective and injective respectively.

Dan Rust
  • 30,108