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

Use of emphasis in speech

Generating a lot of language data with a theorem prover

"Litany Against Fear" in Present Tense

When it's time to party we will party hard

these are people who died

divine carrot

the frog

what it’s like to get nail phenolization

Why 0 to the power of 0 is 1

Lines and Points are Circles