Hacker News Reader

Comment by H8crilA | Hacker News Reader

If you want an explanation: the set is countable from "outside", that is the entire model is countable. But inside the model there really isn't a bijection between the sets of naturals and reals. This function is not an element of the model, and had you manually added it you'd experience serious problems.

It's not too surprising, after all the set of reals that can be named is obviously countable (there is at most one real number per name), regardless of the complexity of the naming scheme.

This theorem is a solid mathematical take on the old trope of "perhaps it's all a simulation".

View on HN

I think it's a little deeper than that. The new idea here is that if we change the background logic from classical to something else, we can get a logic in which Cantor's theorem doesn't hold, since it apparently requires something like excluded middle.

> But inside the model there really isn't a bijection between the sets of naturals and reals

No. Inside the model, there is exactly such a surjection. We don't care what happens outside of it.

Maybe you already knew this, but to clarify: "Countable" means that there exists a surjection, not necessarily a bijection. For instance, the set {a,b,c} is countable, but there is clearly no bijection Nat -> {a,b,c} as one set is infinite and the other's finite.

> It's not too surprising

On the contrary: It's a ground-breaking result IMO.

As always, this depends on your definitions, e.g. see https://encyclopediaofmath.org/wiki/Countable_set

By the definition you link, combined with its subdefinition for uncountable, finite sets are uncountable.

That is a pretty big leap from accepted terminology.

The set of real numbers with finite names is countable.

does one half and two fourths have the same name? I thought reducing to simplest form was one of those things that made it tough to go from naturals to rationals.

A number can have more than one name of course. In fact every number usually has an infinite number of names (just add some meaningless junk to the name).

(From my understanding) this result actually relies on this lack of unique representations. Phrased in terms of diagonalisation, the classic argument is this:

- We write a function 'diagonal: List[List[Digit]] -> List[Digit]' which returns the first entry of the first list, followed by the second entry of the second list, and so on for the ith entry of the ith list

- The function 'map (+1) ∘ diagonal' will accept a List[List[Digit]] and return a List[Digit] which is guaranteed to not appear in that given input, even if the lists extend forever

This new approach replaces that List[Digit] representation; instead representing a real number as a set of all 'oracles' which output that number's digits. As you say, there will be numbers with multiple oracles (outputting different digits, which nevertheless correspond to the same number, e.g. 0.1999... and 0.2000...).

The new result is that there are no such functions which treat all of a number's oracles the same; i.e. that return the same sequence of digits for '0.1999...' as for '0.2000...', etc.

Reply on news.ycombinator.com