Test your intuition: bijections

Posted on March 3, 2020 by Brent

Suppose we have sets A and B and a function f : A \to B (that is, f’s domain is A and its codomain is B). Suppose there is another function g : B \to A such that g(f(a)) = a for every a \in A. Is f necessarily a bijection? That is, does f necessarily match up each element of A with a unique element of B and vice versa? Or put yet another way, is f necessarily invertible?

  • If yes, prove it!
  • If no, provide a counterexample! For bonus points, what additional assumptions could we impose to make it true?

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in logic and tagged , , , . Bookmark the permalink.

12 Responses to Test your intuition: bijections

  1. Sylvain B. says:
    March 3, 2020 at 9:25 am

    There is no restriction regarding the cardinality of domain and codomain?

    • Brent says:
      March 3, 2020 at 1:28 pm

      No, as stated they can be any sets. But if you think it would help/make a difference to restrict their cardinality then that would be an interesting observation.

  2. designerspaces says:
    March 3, 2020 at 11:42 am

    f : Nat -> Int is the usual inclusion and g : Int -> Nat is the absolute value. Then we have:
    g (f n_Nat) = |n _ Int| = n_Nat

    General comments which Brent well knows: In this case g is a left inverse and such a map f is called a split monomorphism (it makes sense in an arbitrary category to talk functions with left inverses). We have the implication that split mono => mono but not conversely. In Set we have:

    injective monomorphism split monomorphism
    In general in a category it is the case that being a mono + epi does not imply being an isomorphism but it is the case that split mono + epi iso (this is straight forward because the pre-composition function for such an f : X -> Y, Hom (Y, Z) -> Hom (X, Z) is a bijection).

    One additional heavy-handed way to make it true: Have A = B and both finite. This then follows by the pigeonhole principle. By the above we can also ask that f additionally be surjective!

  3. Michael Paul Goldenberg says:
    March 3, 2020 at 12:37 pm

    Perhaps I’m being naive, but wouldn’t it suffice to have the co-domain contain elements that aren’t hit by f? Then g would return every element in the co-domain to a in A, but there would be elements in B that aren’t equal to f(a) for any a; that would mean that g(b) might not be defined for one or more elements in B. No bijection in that case. To guarantee a bijection, f would have to be injective and surjective for B,

    • Brent says:
      March 4, 2020 at 9:11 am

      Not naive at all, this is exactly the right kind of idea. However, note that by saying g : B \to A I am implicitly claiming that g is in fact defined on all the elements of B. But f still wouldn’t be a bijection in that case.

  4. Buddha Buck says:
    March 3, 2020 at 6:22 pm

    Let A be a singleton set, and B be any set with 2 or more elements. Then any pair of functions f:A\to B, g:B\to A form a counter-example. There is only one possible g, which maps all elements of B to the single element in A, so no matter the value of f(a), you will have g(f(a)) = a. Yet there is clearly no bijection between A, B.

  5. Pingback: One-sided inverses, surjections, and injections | The Math Less Traveled

Comments are closed.