The Power of a Certain Counting Argument

The reason that bijective functions between sets imply that those sets are of the same size is because of a generalized version of a counting argument. If a function is injective, its target must be at least as big as its source, or else there isn’t enough “room” for points to map uniquely (google “Pigeonhole Principle”). For surjectivity, the target must be smaller or equal to the source because otherwise the function can’t fully cover the target since the target is too big. Each point in the source can only cover one point in the target. So if a function is to meet both, the sets must be less than or equal to in size as well as greater than or equal to in size. this means that they’re of the same size.

This kind of counting argument leads to Cantor’s proofs about the different sizes of infinity. This kind of argument is extremely powerful because you can say a lot with little extra machinery.

For example, most real numbers aren’t computable because the set of algorithms is equal in size to the set of all finite length strings, which is countable. But the reals are not countable. So most reals aren’t computable.

It still amazes me that you can know something like that without actually doing any computation.

Related Posts

How to Disable Disqus Ads on your Blog

Derivation of Reservoir Sampling

Fun with Python Iterators: Linked Lists Made Easy

Notes for November 11, 2018

Underrated Vim Option: undofile and undodir

Hot Take on Solo Travel: Starve

Alan Perlis

Book Notes: The Map of My Life by Goro Shimura


Way to remember the definition of local finiteness