## 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:**

- 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.

### Like this:

Like Loading...

*Related*

or leave a trackback:

Trackback URL.