Hilbert's Grand JavaScript School (2015 Edition) | Hacker News Reader

Hilbert's Grand JavaScript School (2015 Edition)

raganwald.com

39 pointsjessaustin12 comments

Yeah, an infinity cubed is countable. Just iterate over the infinite number of finite diagonals, like you did for the square (a diagonal is any set of points where the coordinates sum to a particular constant).

Similarly, an infinity to the 4th power is countable, as is an infinity to the n'th power for any finite n. Interesting question - is an infinity to an infinitieth power still countable?

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!

"is an infinity to an infinitieth power still countable?"

The countable product of even finite sets is not, in general, countable. For example, we can identify a real number with a binary sequence; in particular we can form a bijection between the set of all real numbers and a subset of the space of infinite binary sequences. If the product of the set {0,1} with itself countably-many times was countable, there would be countably-many real numbers, which we know is not true.

> is an infinity to an infinitieth power still countable?

It shouldn't be. You can use the same principle as showing that reals aren't countable:

Suppose you have an ordered (infinite) set of the infinite-dimensional vectors. Doesn't matter the ordering.

Then construct another vector by the following: the Nth dimension of the vector is different from the Nth dimension of the Nth element of the set. Could be +1, could be -1, could be whatever, long as it's different.

Note that this doesn't actually require infinity^infinity, it's just {any set of >1 element}^infinity.

The new vector is, by definition, different from every element of the set, as the Nth dimension's value is different than the Nth element of the set's Nth value, for all N. Hence the new vector isn't in the set.

(Alternatively, you can biject {0-9}^infinity with the reals between 0 and 1. And the reals between 0 and 1 aren't countable.)

It looks like Dr. Hilbert “Bertie” David reads Hacker News:

https://gist.github.com/raganwald/0880ccce85eafd60d38f

Is it just me, or does this JavaScript style fill you with dread? JS already has about 1000 ways to do things, and with new syntax that's going up a few orders of magnitude....

Why not use scheme streams and the SICP chapter 4 query language? This was done in the 1980s.

http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-24.html...

3.5.2 Infinite Streams

Reply on news.ycombinator.com