Several commenters correctly answered the question from my previous post: if we have a function and such that for every , then is not necessarily invertible. Here are a few counterexamples:
Commenter Buddha Buck came up with probably the simplest counterexample: let be a set with a single element, and a set with two elements. It does not even matter what the elements are! There’s only one possible function , which sends both elements of to the single element of . No matter what does on that single element (there are two choices, of course), . But clearly is not a bijection.
Another counterexample is from commenter designerspaces: let be the function that includes the natural numbers in the integers—that is, it acts as the identity on all the natural numbers (i.e. nonnegative integers) and is undefined on negative integers. can be the absolute value function. Then whenever is a natural number, but is not a bijection, since it doesn’t match up the negative integers with anything.
Unlike the previous example, in this case it is actually possible to make a bijection between and , for example, the function that sends even to and odd to .
Another simple example would be the function defined by . Then the function satisfies the condition, but is not a bijection, again, because it leaves out a bunch of elements.
Can you come up with an example defined on the real numbers (along with a corresponding )? Bonus points if your example function is continuous.
All these examples have something in common, namely, one or more elements of the codomain that are not “hit” by . Michael Paul Goldenberg noted this phenomenon in general. And in fact we can make this intuition precise.
Theorem. If and such that for all , then is injective (one-to-one).
Proof. Suppose for some we have . Then applying to both sides of this equation yields , but because for all , this in turn means that . Hence is injective.
Corollary. since bijections are exactly those functions which are both injective (one-to-one) and surjective (onto), any such function which is not a bijection must not be surjective.
And what about the opposite case, when there are functions and such that for all ? As you might guess, such functions are guaranteed to be surjective—can you see why?
Pingback: Ways to prove a bijection | The Math Less Traveled