On Counting (countable) Infinite Sets

Computability and LogicThis is an especially vivid illustration from the third edition of Boolos and Jeffrey’s Computability and Logic:

If a set is enumerable, Zeus can enumerate it in one second by writing out an infinite list faster and faster. He spends 1/2 second writing the first entry in the list; 1/4 second writing the second entry; 1/8 second writing the third; and in general, he writes each entry in half the time he spent on its predecessor. At no point during the one second interval has he written out the whole list, but when one second has passed, the list is compete!

Pg. 14.

Advertisements