News for hackers. Stuff that matters.
Re:How many real numbers exist? New proof moves closer to an... by BoiledCabbage on Thursday July 15, 2021 @12:18PM (#27846449)
Why does forcing work? To me it seems flawed (which obviously means I don't understand it fully).

For diagonalization argument: 1) Assume every real can be assigned a natural number. 2) Do a bunch of steps that essentially find a new real that differs from any real you have listed from step 1. 3) Conclude that either your steps are flawed, or your initial assumption is wrong 4). Because your steps aren't flawed then your initial assumption (that every real can map to a natural number) is flawed.

That all makes sense to me. Forcing seems broken though: 1) Capture of list/set of all real numbers 2) Do a bunch of steps that essentially find a new real that differs from any real you have listed from step 1. 3) Conclude that either your steps are flawed, or your initial assumption is wrong 4). Because your steps aren't flawed then your initial assumption (that you can produce a list of every real number) is flawed.

Now you're left in an odd situation. Didn't you just conclude that it's impossible to have a set of all real numbers? Which isn't what you're trying to prove at all.

Re:How many real numbers exist? New proof moves closer to an... by jerf on Thursday July 15, 2021 @12:27PM (#27846549)
"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?

Re:How many real numbers exist? New proof moves closer to an... by avz on Thursday July 15, 2021 @12:55PM (#27846864)
> 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.

Re:How many real numbers exist? New proof moves closer to an... by jerf on Thursday July 15, 2021 @01:08PM (#27847022)
Thank you. I accept this.
Re:How many real numbers exist? New proof moves closer to an... by BoiledCabbage on Thursday July 15, 2021 @12:42PM (#27846724)
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.

Re:How many real numbers exist? New proof moves closer to an... by finnh on Thursday July 15, 2021 @02:32PM (#27848321)
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.

Re:How many real numbers exist? New proof moves closer to an... by dwohnitmok on Thursday July 15, 2021 @03:58PM (#27849376)
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.

Re:How many real numbers exist? New proof moves closer to an... by CamperBob2 on Thursday July 15, 2021 @07:02PM (#27851120)
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.

Re:How many real numbers exist? New proof moves closer to an... by dwohnitmok on Thursday July 15, 2021 @07:55PM (#27851546)
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."

Re:How many real numbers exist? New proof moves closer to an... by glial on Thursday July 15, 2021 @12:36PM (#27846659)
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.

Re:How many real numbers exist? New proof moves closer to an... by jerf on Thursday July 15, 2021 @01:07PM (#27847016)
Yes, thank you, that was a typo.
Re:How many real numbers exist? New proof moves closer to an... by scotty79 on Thursday July 15, 2021 @02:50PM (#27848558)
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."

Re:How many real numbers exist? New proof moves closer to an... by mdoms on Thursday July 15, 2021 @04:22PM (#27849636)
This is covered in the article.
Re:How many real numbers exist? New proof moves closer to an... by HotHotLava on Friday July 16, 2021 @11:15AM (#27857116)
The illustration in the article doesn't start with the whole set of all real numbers, but with just "a" set containing an uncountable number of reals, so there is no contradiction in that sense.

I'm assuming there's some unmentioned technical condition on which sets you are allowed to choose in order for the procedure to work, otherwise the argument would indeed seem to lead to a contradiction when choosing the set of all real numbers.

Re:How many real numbers exist? New proof moves closer to an... by cevi on Saturday July 17, 2021 @03:24PM (#27868114)
This assumption is correct - the quanta article left out quite a bit of detail about how forcing actually works, while trying to give some hint of the philosophy behind it.

As it turns out, you can still apply the forcing technique even if you start with the whole set of all real numbers. What happens in this case is a bit surprising: since there's no legitimate way to add new real numbers that weren't there previously, the forcing procedure cheats by pretending that real numbers have nonstandardly long decimal expansions.

To make the way it cheats a bit more concrete, we start by first imagining that there are "nonstandard integers" n which are bigger than all of the "true" integers from our starting model. Once we assume that these integers exist, we have to commit ourselves to providing answers to questions like, "what is the nth digit of pi?", "what is the n+1th digit of pi?", and so on in a consistent way. By answering these questions, we embed all of the original real numbers from our starting universe into the new universe. But the point is that now that we have all of these extra digits to play with, all of the original real numbers only fill up a tiny subset of the potential "real" numbers in the new universe, and we can happily go back to forcing new ones in.

Of course, adding nonstandard integers to our universe is quite a violent change, so we also have to worry about whether we've accidentally screwed up the way that the ordinals work in the process (for instance, the "first infinite ordinal" in the new universe now contains all of the nonstandard integers we added), and we need to worry about this again when we get around to forcing the new reals in. So a whole lot of technical details need to be ironed out carefully, using a few clever combinatorial arguments, to make the whole charade come together.

All of this cheating happens under the hood in a way that is not obvious at all when you first go through the technical details of the forcing construction. I only learned about the full perspective from Joel David Hamkins's "naturalistic account of forcing".

Re:How many real numbers exist? New proof moves closer to an... by cwzwarich on Thursday July 15, 2021 @12:48PM (#27846792)
In a forcing-based consistency proof of a proposition P, you start with a model of ZFC (or a sufficiently large subset of ZFC, depending on the exact formalism being used), approximate a witness to P (e.g. a bijection between a set of reals and aleph_2) within the starting model, and then apply the forcing machinery to construct a new model of ZFC where P holds. Unlike the diagonalization argument, it's inherently metamathematical.
Re:How many real numbers exist? New proof moves closer to an... by myhf on Thursday July 15, 2021 @04:23PM (#27849651)
> 2) Do a bunch of steps

It's not just a bunch of steps. It's an infinite number of steps. It requires the axiom of choice.