Hacker News Reader

Comment by cvoss | Hacker News Reader

I find it helpful to think of countability in terms of the following game: You have a set of items in mind. You propose a (non-terminating) scheme for listing all the items in the set. An adversary attempts to name any item X, hoping your scheme misses it. However, you then show your scheme does, in fact, get to X after a _finite_ amount of time. The set is said to be countable if you prove that your adversary cannot win this game.

Yes, the counting process is non-terminating. But every item gets counted after only finite time.

View on HN

Since it is non-terminating, you didn't really prove every item gets counted after finite time, did you?

Refer to my other reply, you asserted a requirement of predefined (describable) counting scheme here. Why that requirement has any relevance here (in the context of infinity)?

If I start at 0 and successively add 1, do you agree that I eventually hit any positive integer you could pick after a finite number of steps? Does that not prove to you that I hit every positive integers? Which one do I not hit?

You will only eventually hit any given integer after finite steps. It does not prove you will hit every positive integer. You'll miss those that one never can finish giving you -- for example, I'll start with digit 1, and I'll infinitely adding 1 behind it (never finishing). It is an infinite natural number that you can't hit within any finite number of steps.

The game itself is certainly not the proof that is required. The proof in question is a proof that the game cannot be won by the adversary. By no means do you need to play all possible rounds of the game to conclude this.

The discussion really helps me understand the problem. Real numbers are infinity in disguise. Because infinity is not really defined, real numbers are not really defined. Just saying infinity is not finite does not make much sense (in the sense of adding anything helpful). Any real number that you can finitely describe can be included in a finitely described counting scheme. Let's use the counting schemes of rational numbers, I'll hit arbitrary numbers to arbitrary precisions. Taking a limit, it is not clear that I miss any numbers (including pi). To defeat this scheme, the adversary has to keep adding digits to his real number, as well as keep shrinking his allowed precision infinitely. Now both the number (that is being infinitely being described) and my counting process is infinite, we didn't and can't prove anything. There is simply no conclusions to be drawn.

> you didn't really prove every item gets counted in finite time

The proof that the adversary cannot name such an item is logically the same as a proof that every item gets counted. This is a fundamental logical truth, namely de Morgan's law for universal/existential quantifiers: (not exists x such that P(x)) is the same as (forall x, not P(x))

> Why that requirement has any relevance here

'A counting scheme' is an intuitive way of providing a 'one-to-one correspondence to the natural numbers,' which is used in the technical definition of countability.

Reply on news.ycombinator.com