3 ms·

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 ass

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.

jerf 5y ago
"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?
- glial 5y ago
  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.
  - jerf 5y ago
    Yes, thank you, that was a typo.
- BoiledCabbage 5y ago
  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.
  - finnh 5y ago
    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.
    - deleted 5y ago
      [deleted]
    - dwohnitmok 5y ago
      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.
      - CamperBob2 5y ago
        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.
- avz 5y ago
  > 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.
  - jerf 5y ago
    Thank you. I accept this.
- scotty79 5y ago
  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 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."
  - mdoms 5y ago
    This is covered in the article.
- Layke1123 5y ago
  Cantor's diagonalization proof was never a proof to begin with. You can't construct a number that isn't on an infinite list of all numbers because you can't list all the numbers, otherwise you'd eventually find your number. It's honestly kind of ridiculous that this proof hasn't been subjected to more rigor than just handwaving away the problems.
cwzwarich 5y ago
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.
myhf 5y ago
> 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.
HotHotLava 5y ago
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.
- cevi 5y ago
  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".

jerf 5y ago

"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?

glial 5y ago
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.
- jerf 5y ago
  Yes, thank you, that was a typo.
BoiledCabbage 5y ago
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.
- finnh 5y ago
  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.
  - deleted 5y ago
    [deleted]
  - dwohnitmok 5y ago
    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.
    - CamperBob2 5y ago
      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.
avz 5y ago
> 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.
- jerf 5y ago
  Thank you. I accept this.
scotty79 5y ago
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 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."
- mdoms 5y ago
  This is covered in the article.
Layke1123 5y ago
Cantor's diagonalization proof was never a proof to begin with. You can't construct a number that isn't on an infinite list of all numbers because you can't list all the numbers, otherwise you'd eventually find your number. It's honestly kind of ridiculous that this proof hasn't been subjected to more rigor than just handwaving away the problems.

cwzwarich 5y ago

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.

myhf 5y ago

> 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.

HotHotLava 5y ago

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.

cevi 5y ago
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".