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

Random Thought: LC Theorem

I finally have an answer to "who's your favorite singer?"

My Top Tip for Helping People Get Started Programming


Random paper on angles

An Image is Worth 16x16 Words

Random stuff

Lossless Data Compression with Neural Networks by Fabrice Bellard

Downscaling Numerical Weather Models With GANs (My CI 2019 Paper)

Learning Differential Forms and Questions