How to Understand Injective Functions, Surjective Functions, and Bijective Functions

One way to think of functions

Functions are easily thought of as a way of matching up numbers from one set with numbers of another. The function f(x)=x+3, for example, is just a way of saying that I'm matching up the number 1 with the number 4, the number 2 with the number 5, etc. A different example would be the absolute value function which matches both -4 and +4 to the number +4. Think of functions as matchmakers.

Functions may be "injective" (or "one-to-one")

An injective function is a matchmaker that is not from Utah. There are no polyamorous matches like the absolute value function, there are just one-to-one matches like f(x)=x+3.

Lets take two sets of numbers A and B. Say we know an injective function exists between them. That means we know every number in A has a single unique match in B. But, we don't know whether there are any numbers in B that are "left out" and aren't matched to anything. If you think about it, this implies the size of set A must be less than or equal to the size of set B. That's an important consequence of injective functions, which is one reason they come up a lot.

Example:f(x) = x! (the factorial function) where both sets A and B are the set of all positive integers (1, 2, 3...).

Why it's injective:Everything in set A matches to something in B because factorials only produce positive integers. And no duplicate matches exist, because 1! < 2! < 3! < 4!... meaning none of the factorials will be the same number. Note that in this example, there are numbers in B which are unmatched (e.g. 3, 4, 5, or 7). Remember that injective functions don't mind whether some of B gets "left out".

Functions may be "surjective" (or "onto")

There are also surjective functions. Surjective functions are matchmakers who make sure they find a match for all of set B, and who don't mind using polyamory to do it. So, if you know a surjective function exists between set A and B, that means every number in B is matched to one or more numbers in A. Again if you think about it, this implies that the size of set A must be greater than or equal to the size of set B. Another important consequence.

Example:f(x) = x2 where A is the set of real numbers and B is the set of non-negative real numbers.

Why it's surjective:The entirety of set B is matched because every non-negative real number has a real number which squares to it (namely, its square root). Note that in this example, polyamory is pervasive, because nearly all numbers in B have 2 matches from A (the positive and negative square root).

Bijective Functions

Finally, a bijective function is one that is both injective and surjective. If a bijective function exists between A and B, then you know that the size of A is less than or equal to B (from being injective), and that the size of A is also greater than or equal to B (from being surjective). The only possibility then is that the size of A must in fact be exactly equal to the size of B. Just like if a value x is less than or equal to 5, and also greater than or equal to 5, then it can only be 5.

Example:f(x) = 2x where A is the set of integers and B is the set of even integers.

Why it's bijective:All of A has a match in B because every integer when doubled becomes even. This match is unique because when we take half of any particular even number, there is only one possible result. This makes the function injective. The function is also surjective because nothing in B is "left over", that is, there is no even integer that can't be found by doubling some other integer. Since the matching function is both injective and surjective, that means it's bijective, and consequently, both A and B are exactly the same size. If you think about what A and B contain, intuition would lead to the assumption that B might be half the size of A. But surprisingly, intuition turns out to be wrong here. And this leads to our conclusion...

How this relates to infinite sets

So, for any two sets where you can find a bijective function between them, you know the sets are exactly the same size. Even infinite sets. This is how Georg Cantor was able to show which infinite sets were the same size. He found bijections between them.

Cantor was able to show which infinite sets were strictly smaller than others by demonstrating how any possible injective function existing between them still left unmatched numbers in the second set. In other words, any function which used up all of A in uniquely matching to B still didn't use up all of B. Therefore, B must be bigger in size.

Cantor proceeded to show there were an infinite number of sizes of infinite sets! But perhaps I'll save that remarkable piece of mathematics for another time.

Posted 1/25/2013