In this little post we are going to quickly and formally prove that the function we built in Infinity and Beyond - Part 2 is in fact a bijection. This post is only for those who are really interested to see the formal proof, as we have already informally proven this in the original article.

The function

The function we created looked like this.

Remember that and .

Injection

Mathematical definition of injections.

Read as "For all and all from A, implies ."

We can show this easily by starting on one side and working our way over to the other side.

Surjection

Mathematical definition of surjections.

Read as "For all y in B there exists an x in A such that f(x) = y"

We can't show this directly, so we try to invert the function and prove that the inverted function is correct.

This leads to the inverse function . For it to be correct the following must hold.

Again, we can easily show this by working from one side to the other.

Q.E.D.

Conclusion

We just proved that our function is both an injection and a surjection, which makes it a bijection.

1. Injection Definition - https://en.wikipedia.org/wiki/Injective_function
2. Surjection Definition - https://en.wikipedia.org/wiki/Surjective_function

PS: The abbreviation "Q.E.D." stands for the Latin phrase "quod erat demonstrandum" and translates to "what was to be demonstrated".^Source It is often found under mathematical proof. Think of it as the mathematical way of saying "The End".