Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

For a bijection $\alpha:A\rightarrow B$ define a bijection $\beta: B\rightarrow A$ such that $\alpha \beta $ is the identity function $I:A\rightarrow A$ and $\beta\alpha $ is the identity function $I:B\rightarrow B$.

Prove that $\alpha\beta$ or $\beta\alpha $ determines $\beta $ uniquely.

I am stonewalled here. I can understand the premise before the prove that, but I have no idea how to approach this.


The motivation of the question in the book is to show that bijections have two sided inverses. Later questions ask to show that surjections have left inverses and injections have right inverses etc,

share|improve this question
    
If $\alpha\beta$ is the identity on $A$ and $\beta\alpha$ is the identity on $B$, I don't see how either one can determine $\beta$. That would imply there is only one bijection from $B\to A$. –  robjohn Sep 10 '11 at 16:20
    
robjohn, this is the whole point - there is only ONE such bijection, and usually this is called the 'inverse' of $\alpha$. What one needs to do is suppose that there is another map $\beta'$ with the same properties and conclude that $\beta=\beta'$. –  Per Sep 10 '11 at 16:43
    
@Per: but the question posits that the one of the identities determines $\beta$ uniquely (without reference to $\alpha$). "Prove that $\alpha\beta$ or $\beta\alpha $ determines $\beta $ uniquely." Perhaps I am misreading the question. –  robjohn Sep 10 '11 at 17:46
    
Are you trying to show that $\beta=\alpha^{-1}$? If so, then I'd go with Thomas Rot's answer. –  robjohn Sep 10 '11 at 17:53
1  
@kuch I suppose it will be more informative to title the post something like "Proof that a bijection has unique two-sided inverse". –  Srivatsan Sep 10 '11 at 22:34

3 Answers 3

up vote 5 down vote accepted

I will use the notation $f$ and $g$ instead of $\alpha$ and $\beta$ respectively, for reasons that will be clear shortly.

Existence. I find viewing functions as relations to be the most transparent approach here. Here's a brief review of the required definitions. A function $f : A \to B$ is a essentially a relation $F \subseteq A \times B$ such that any $x$ in the codomain $A$ appears as the first element in exactly one ordered pair $(x,y)$ of $F$. In what follows, we represent a function by a small-case letter, and the corresponding relation by the corresponding capital-case. In this view, the notation $y = f(x)$ is just another way to say $(x,y) \in F$.

For any relation $F$, we can define the inverse relation $F^{-1} \subseteq B \times A$ as transpose relation $F^{T} \subseteq B \times A$ as: $$ F^{T} := \{ (y,x) \,:\, (x,y) \in F \}. $$ (Edit: Per Qiaochu Yuan's suggestion, I have changed the term "inverse relation" to "transpose relation".) The nice thing about relations is that we get some notion of inverse for free. Of course, the transpose relation is not necessarily a function always. However, this is the case under the conditions posed in the question.

Assume that $f$ is a bijection. We define the transpose relation $G = F^{T}$ as above. It remains to verify that this relation $G$ actually defines a function with the desired properties.

  • $G$ defines a function: For any $y \in B$, there is at least one $x \in A$ such that $(x,y) \in F$. (Why?) Moreover, such an $x$ is unique. (Why?) That is, for each $y \in F$, there exists exactly one $x \in A$ such that $(y,x) \in G$. Hence, $G$ represents a function, call this $g$.

  • $g$ is surjective: Take $x \in A$ and define $y = f(x)$. Verify that this $y$ satisfies $(y,x) \in G$, which implies the claim.

  • $g$ is injective: Suppose $y_1, y_2 \in B$ are such that $g(y_1) = x$ and $g(y_2) = x$. Unrolling the definition, we get $(x,y_1) \in F$ and $(x,y_2) \in F$. Now, since $F$ represents the function, we must have $y_1 = y_2$.

  • $g$ is bijective. Follows from injectivity and surjectivity.

  • Left inverse: We now show that $gf$ is the identity function $1_A: A \to A$. Fix $x \in A$, and define $y \in B$ as $y = f(x)$. By definition of $F$, $(x,y) \in F$. Again, by definition of $G$, we have $(y,x) \in G$. Therefore, $x = g(y)$. Plugging in $y = f(x)$ in the final equation, we get $x = g(f(x))$, which is what we wanted to show.

  • Right inverse: Here we want to show that $fg$ is the identity function $1_B : B \to B$. This is very similar to the previous part; can you complete this proof?


Uniqueness. The hard of the proof is done. But we still want to show that $g$ is the unique left and right inverse of $f$.

  • Left inverse: Suppose $h : B \to A$ is some left inverse of $f$; i.e., $hf$ is the identity function $1_A : A \to A$. This is similar to Thomas's answer. Start from: $$ 1_A = hf. $$ The trick is to do a right-composition with $g$: $$ g = 1_A g = (hf)g = h(fg) = h1_B = h, $$ which shows that $h$ is the same as $g$.

  • Right inverse: This again is very similar to the previous part. I am sure you can complete this proof.

share|improve this answer
    
Calling this the inverse for general relations is misleading; we don't have $F^{-1} \circ F = \text{id}_A$ in general. It makes more sense to call it the transpose. The fact that these agree for bijections is a manifestation of the fact that bijections are "unitary." –  Qiaochu Yuan Sep 10 '11 at 23:25
    
@Qia Unfortunately, that terminology is well-established: en.wikipedia.org/wiki/Inverse_relation. And I had always known it as an inverse relation when I learned this. But I agree with you; I'll edit my answer. Btw what does "bijections are unitary" mean? –  Srivatsan Sep 10 '11 at 23:31
    
It means that the inverse and the transpose agree. This notion is defined in any dagger category. It's a funny fact that in $\text{Rel}$ any isomorphism is automatically unitary, but this isn't true in general dagger categories, such as $\text{Hilb}$ (morphisms the bounded linear maps). –  Qiaochu Yuan Sep 10 '11 at 23:35
    
@Qia I am following only vaguely :), but thanks for the clarification. –  Srivatsan Sep 10 '11 at 23:38

In fact, we have the following:

Theorem. Let $f\colon A\to B$ be a function. The following are equivalent:

  1. $f$ is one-to-one.
  2. $f$ is left-cancellable: if $C$ is any set, and $g,h\colon C\to A$ are functions such that $f\circ g = f\circ h$, then $g=h$.

The following condition implies that $f$ is one-to-one:

  • $f$ has a left inverse, $h\colon B\to A$ such that $h\circ f=\mathrm{id}_A$.

If, moreover, $A\neq\emptyset$, then $f$ is one-to-one if and only if $f$ has an left inverse.

Dually:

Theorem. Let $f\colon A\to B$ be a function. The following are equivalent:

  1. $f$ is onto $B$.
  2. $f$ is right-cancellable: if $C$ is any set, and $g,h\colon B\to C$ are such that $g\circ f = h\circ f$, then $g=h$.

The following condition implies that $f$ if onto:

  • $f$ has a right inverse, $g\colon B\to A$ such that $f\circ g = \mathrm{id}_B$.

In addition, the Axiom of Choice is equivalent to "if $f$ is surjective, then $f$ has a right inverse."

Proposition. Let $f\colon A\to B$ be a function If $g$ is a left inverse of $f$ and $h$ is a right inverse of $f$, then $g=h$. In particular, a function is bijective if and only if it has a two-sided inverse.

Proof. $g = g\circ\mathrm{id}_B = g\circ(f\circ h) = (g\circ f)\circ h = \mathrm{id}_A\circ h = h.$ $\Box$

This is the same proof used to show that the left and right inverses of an element in a group must be equal, that a left and right multiplicative inverse in a ring must be equal, etc.

The last proposition holds even without assuming the Axiom of Choice: the small missing piece would be to show that a bijective function always has a right inverse, but this is easily done even without AC.

share|improve this answer

Am I missing something? You can precompose or postcompose with $\alpha^{-1}$. Thus $\alpha^{-1}\circ (\alpha\circ\beta)=\beta$, and $(\beta\circ\alpha)\circ\alpha^{-1}=\beta$ as well.

share|improve this answer
    
Although the OP does not say this clearly, my guess is that this exercise is just a preparation for showing that every bijective map has a unique inverse that is also a bijection. –  Srivatsan Sep 10 '11 at 16:28
1  
Thomas, $\beta=\alpha^{-1}$. I think that this is the main goal of the exercise. The unique map that they look for is nothing but the inverse. –  Per Sep 10 '11 at 16:45
    
@Per: I think this resolves my confusion. I was looking in the wrong direction. –  robjohn Sep 10 '11 at 17:57
    
@Per: sure that was my thought as well... –  Thomas Rot Sep 10 '11 at 20:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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