## A Fun, Quick Theorem

I like this theorem, and it’s pretty straightforward to prove since I’ve done all the leg room in previous posts.

Theorem: There are sets of natural numbers that no computer program can enumerate.

Proof:

1. There set of all computer programs is enumerable (countably infinite). (Proof here)
2. The set of all sets of natural numbers in not enumerable (uncountably infinite). (Proof here)
3. Therefore there are more sets of natural numbers than there are computer programs to enumerate them.
4. Therefore there are sets of natural numbers that no computer program can enumerate.

$\Box$

Nothing too earth-shattering, I just thought it was cute.

Oh yeah, did I mention there are different sizes of infinities? I guess I should talk about that next time.