Hacker News Reader

Comment by jerf | Hacker News Reader

"Didn't you just conclude that it's impossible to have a set of all real numbers?"

Cantor's diagonalization proof proves that it's impossible to list all the real numbers with a list of size aleph-0, which is the cardinality of the set of natural numbers.

The forcing proof is an attempt to prove you also can't do it with the a list of the size aleph-1, which is the size of the power set of aleph-0. It purports to prove that you need a list of size aleph-2, which is the size of the powerset of aleph-1.

You can kind of think of this not so much as whether "Can Crysis run?" ("can you have a set of all real numbers?") but "Can Crysis run on this machine?" Do the real numbers need aleph-1 "resources", or aleph-2 "resources" to list?

View on HN

> aleph-1, which is the size of the power set of aleph-0

In ZFC, aleph-1 is not the size of the powerset of aleph-0. Instead, aleph-1 is the next larger cardinal number after aleph-0. The size of the powerset of aleph-0 is called continuum or beth-1. In ZFC, we can show that the size of the set of real numbers equals continuum, but it is not possible to relate continuum to a specific aleph-k (though some can be ruled out using Easton's theorem).

Now, the statement that aleph-1 is the size of the powerset of aleph-0 is known as the Continuum Hypothesis (CH) and is independent of the axioms of ZFC. Therefore, your claim that aleph-1 is the size of the powerset of aleph-0 cannot be made in ZFC. The statement can be made in ZFC+CH, but then the question which aleph-k is the size of the real numbers has a straightforward answer: aleph-1.

Thank you. I accept this.

Thanks for the reply. Question though. in Cantor's argument we explicitly mapped the reals to aleph-0 so it makes sense that our conclusion decides that mapping to aleph-0 is too small so it's size must be larger.

Where in the forcing process do we even "use" aleph-1? If we used aleph-1 then it could see the parallels and the argument would make sense - but all I see in the forcing process is "start with a set of all reals". Nothing about trying to map them to aleph-1. Maybe it's implicit, but couldn't I have just changed step 1 to instead be "start with a list of size aleph-90, then use forcing to prove that the reals are larger than aleph-90." In Cantor's argument it feels like we "used" the natural numbers. Here it seems more like we said take an arbitrary number of them and see this one isn't in it. But that arbitrary number of them (aleph-1) could've been any arbitrary number of them because we never really used any property of the set being aleph-1 vs aleph-90.

Great question, I have no answer.

The article explained forcing in such a way as to simply restate what I thought we already knew: given a real, there is no "next" real. (ie, there are a non-countable-infinite number of reals between any two reals).

I don't see the newness that forcing brings to this.

Forcing is about a completely different question.

The question is not where there are reals between reals, it's a question of the size of sets. In particular is there a set strictly larger than the natural numbers, but strictly smaller than the reals? Forcing allows us to construct such a set in ZFC.

Not a mathematician, so this probably has an obvious answer, but who says that "size" is a necessary universal property of a set? It doesn't seem any more rational to speak of size as a required property of a set than it would be to treat color or weight that way. Some sets have those attributes, but not all.

It seems perfectly reasonable to say that the set of real numbers is one of those sets that doesn't have a "size" property.

Size is a hand-wavy way of saying it. What we're really asking is given two sets A and B, is there a function from A to B such that no two elements from A are mapped to a single element in B?

It turns out if you use ZFC (in particular choice) then one direction must hold. Either such a function exists from A to B or from B to A. This means that we can order all sets using the existence of these functions, and so in that sense size is a "universal property."

I think this is a typo:

> aleph-0, which is the cardinality of the set of real numbers.

aleph-0 is the cardinality of the set of natural numbers, and (as you say) is not the cardinality of the real numbers.

Yes, thank you, that was a typo.

That's weird. I thought that it was proven that existence of sets larger than aleph-0 but smaller than the number of real numbers is undecidable and you can add it (or negation of it) as additional axiom to math.

https://en.wikipedia.org/wiki/Cardinality_of_the_continuum

"The continuum hypothesis, which asserts that there are no sets whose cardinality is strictly between aleph-0 and c=aleph-1. The truth or falsity of this hypothesis is undecidable and cannot be proven within the widely used ZFC system of axioms."

This is covered in the article.

Reply on news.ycombinator.com