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

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

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

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.

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!

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,

Not naive at all, this is exactly the right kind of idea. However, note that by saying 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.

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

That’s a nice, simple counterexample! Though (depending on your comfort level with functions out of an empty set) you could make it even simpler by making A empty and B a singleton set. =)

I’m fine with functions out of an empty set. The existence of g to an empty set on the other hand…

Oh! Of course, that doesn’t work, how silly of me.

How about ? I am not sure it is possible to get simpler than that.

I think your original formulation (which didn’t need to mention specific elements of A or B at all) was simpler!

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