Injection, Surjection, and Bijection

If you have studied high-school algebra, you probably already know about injective, surjective, and bijective functions, just not by those names.

Imagine that I have a function f. Recall what it means for a function to be “1-to–1”. This means that for every point in the input of f, the output is unique. To put it another way: f(x1) = f(x2) => x1 = x2, if two points have the same height on a graph, they are the same point. The technical way of saying this is that f is an injective function.

That was simple. What about surjective functions?

A surjective function, sometimes called an “onto” function, is one where there is an input corresponding to every possible output. For example, f(x) = x + 3 (where f is a function on the real numbers) is a surjective function, because every real number has a preimage - an x such that f(x) is the number.

What about bijective functions?

A bijective function is just a function that is both injective and surjective.

Huh. So why is this important?

Well, if I have a bijective function f between a set A and a set B, then I can show that A and B have the same number of elements, because I know that every element in A corresponds to exactly one element in B. This is cool, but less useful for finite sets. It becomes really important for infinite sets - like the natural numbers.

The set of the natural numbers ({1, 2, 3, 4, ...}) has infinitely many items. But I can show that it has the same number of items as the set B = {-5, -4, -3, -2, -1, 0, 1, 2, ...}. My proof: f(x) = x+6 is a bijective function from B to the natural numbers. Thus, the two sets have the same number of elements. We know it is bijective, because it is injective (no overlaps) and surjective (no gaps).

You can even go further, and show that the integers ({... -4, -3, -2, -1, 0, 1, 2, 3, ...}) has the same number of elements as the natural numbers. You can also show that there is no bijection between the natural numbers and the real numbers - the real numbers are ‘bigger’ than the natural numbers. On the other hand, there is a bijection between (0,1) and the real numbers (f(x) = 2/pi*arctan(x), if you’re curious) so (0,1) is just as ‘big’ as the real numbers.

There’s one more week of Math, so hold onto your seats for 7 more days before finals!