Hacker News Reader

Comment by AnkhMorporkian | Hacker News Reader

Surely it must be by induction. Since n+1 is always countable, n+2 must similarly be.

It is not. The induction you speak of only works to prove for finite values. For example, let A be some countable set; with induction you could show that A^n is countable for any particular n = 1, 2, ...

However, this doesn't work for the product of A with itself countably-many times. Your induction never "reaches" infinity; it only shows that it works for any finite number n. Sure, there are infinitely-many such n, but every single natural number is finite.

Right. A simple example to show that induction does not work to infinity:

    0 < 1
    For any natural n, if n-1 < n, then n < n+1
    (proof: add 1 to both sides of the given inequality)
    By induction, for all natural n, n < n+1

But clearly this does not work for infinity, because ∞-1 = ∞ = ∞+1. So induction proves something about all natural numbers, but ∞ is not a natural number.

I'm not a math wizard, but everything I was taught in all of my calculus classes made me believe that infinity isn't an actual tangible concept outside of the alephs, and only applicable in limits, which surely follows the rules of induction. Am I missing something here?

Induction suffices to show that (oo)^n is countable for every n a natural number, but that does not suffice to show that (oo)^(oo) is countable, because the power is not a natural number. The induction you have only proves the step that if X^n is countable then X^(n+1) is countable. That never proves the case X^(oo)

There is a thing called transfinite induction, and there you have to show the separate case that if predicate P holds for all n_i then it holds for the limit. As stated elsewhere you can't do that in this case because it's not true. 2^(oo) is uncountable.

  > Am I missing something here?

Yes. You are forming perfectly reasonable conjectures based on limited experience, but those conjectures turn out to be false when you study the subject in its own right, instead of just those bits you need for the limited version of calculus that you've done. It's a problem I often have when teaching people this stuff that they have only ever dealt with "nice" functions and "easy" situations. I wrote a little about that here:

http://www.solipsys.co.uk/new/PokingTheDustyCorners.html?HN_...

I really appreciate that explanation and link. Thanks so much!

Reply on news.ycombinator.com