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 I feel about ebooks

List of places where the US has been involved in regime change, with multiplicity

Accuracy vs Precision

Handy command line benchmarking tool

Stan Rogers

Ultimate Hot Couch Guy

Quote on Java Generics

The Programmer Tendency

Figure out undocumented JSON with gron

Mental Model of Dental Hygiene