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:
- There set of all computer programs is enumerable (countably infinite). (Proof here)
- The set of all sets of natural numbers in not enumerable (uncountably infinite). (Proof here)
- Therefore there are more sets of natural numbers than there are computer programs to enumerate them.
- Therefore there are sets of natural numbers that no computer program can enumerate.
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.
