4 ms·

As I pointed out at https://news.ycombinator.com/item?id=44271589 https://news.ycombinator.com/item?id=44271589, there are systems that can accept Cantor's argu

by btilly 1y ago

As I pointed out at https://news.ycombinator.com/item?id=44271589 https://news.ycombinator.com/item?id=44271589, there are systems that can accept Cantor's argument, without concluding that there are more reals than rational numbers. As you point out, there are many mathematical systems that contain all of the numbers in the high school mathematics concept of "reals". Since those with a high school understanding of reals do not know which of those systems they would agree with, they should not be asked to accept as true, any results that hold in only some of those systems. And that is why I don't like mathematicians telling lay audiences that there are more reals than rationals.

zozbot234 1y ago
"Cantor's diagonalization argument" is best understood as a mere special case of Lawvere's fixed-point theorem. Lawvere's theorem is really the meat of the argument, and it's also the part that is very easy for exotic systems to "accept", since it's close to a purely logical argument. Whether these systems truly accept "Cantor's argument" is perhaps only a matter of perception and intuition, that people may perhaps disagree about.
- btilly 1y ago
  It does not matter what your best understanding of Cantor's diagonalization argument is. In some mathematical systems it means, "there are more reals than natural numbers", and in others it means, "the reals encode self-reference in a more direct way than the natural numbers do". The result is that it is possible for the acceptance of the argument to lead to very different consequences about what we then conclude.
- skissane 1y ago
  > "Cantor's diagonalization argument" is best understood as a mere special case of Lawvere's fixed-point theorem. Lawvere's theorem is really the meat of the argument, and it's also the part that is very easy for exotic systems to "accept", since it's close to a purely logical argument. Okay, but can you prove Lawvere’s theorem in NFU+AxCount? And even if you can, since NFU+AxCount proves that the reals are countable, if NFU+AxCount proves Lawvere, then (to echo what btilly says in a sibling comment) NFU+AxCount+Lawvere couldn’t entail the countability of the reals, since that would render NFU+AxCount trivially inconsistent, and we know it is isn’t trivially inconsistent (as with any formal system, consistency is ultimately unprovable, but if a system is taken seriously as an object of mathematical research, then any inconsistency must be highly non-trivial.)
gylterud 1y ago
I agree, but I also want to clarify that cantors argument was about subsets of the naturals (N), or more precisely functions from N to Bool (the decidable subsets). This is where the diagonal argument makes sense. So to conclude that there are more reals than naturals, the classical mathematical argument is: a) There are more functions N to Bool than naturals. b) There are as many reals as functions from N to Bool. Now, we of course agree the mistake is in b) not in a).
- skissane 1y ago
  > So to conclude that there are more reals than naturals, the classical mathematical argument is: > a) There are more functions N to Bool than naturals. > b) There are as many reals as functions from N to Bool. > Now, we of course agree the mistake is in b) not in a). Given certain foundations, (a) is false. For example, in the Russian constructivist school (as in Andrey Markov Jr), functions only exist if they are computable, and there are only countably many computable functions from N to Bool. More generally, viewing functions as sets, if you sufficiently restrict the axiom schema of separation/specification, then only countably many sets encoding functions N-to-Bool exist, rendering (a) false
  - IngoBlechschmid 1y ago
    Indeed, what you write is true from an external point of view; just note that within this flavor of constructive mathematics, the set of functions from N to Bool is uncountable again. There is no paradox: Externally, there is an enumeration of all computable functions N -> Bool, but no such enumeration is computable.
    - skissane 1y ago
      Is it internally uncountable in the strong sense that the system can actually prove the theorem “this set is uncountable”, or only in the weaker sense that it can’t prove the theorem “this set is countable”, but can’t prove its negation either? If the latter, what happens if you add to it the (admittedly non-constructive) axiom that the set in question is countable?

by btilly 1y ago

zozbot234 1y ago

"Cantor's diagonalization argument" is best understood as a mere special case of Lawvere's fixed-point theorem. Lawvere's theorem is really the meat of the argument, and it's also the part that is very easy for exotic systems to "accept", since it's close to a purely logical argument. Whether these systems truly accept "Cantor's argument" is perhaps only a matter of perception and intuition, that people may perhaps disagree about.

btilly 1y ago
It does not matter what your best understanding of Cantor's diagonalization argument is. In some mathematical systems it means, "there are more reals than natural numbers", and in others it means, "the reals encode self-reference in a more direct way than the natural numbers do". The result is that it is possible for the acceptance of the argument to lead to very different consequences about what we then conclude.
skissane 1y ago
> "Cantor's diagonalization argument" is best understood as a mere special case of Lawvere's fixed-point theorem. Lawvere's theorem is really the meat of the argument, and it's also the part that is very easy for exotic systems to "accept", since it's close to a purely logical argument. Okay, but can you prove Lawvere’s theorem in NFU+AxCount? And even if you can, since NFU+AxCount proves that the reals are countable, if NFU+AxCount proves Lawvere, then (to echo what btilly says in a sibling comment) NFU+AxCount+Lawvere couldn’t entail the countability of the reals, since that would render NFU+AxCount trivially inconsistent, and we know it is isn’t trivially inconsistent (as with any formal system, consistency is ultimately unprovable, but if a system is taken seriously as an object of mathematical research, then any inconsistency must be highly non-trivial.)

gylterud 1y ago

I agree, but I also want to clarify that cantors argument was about subsets of the naturals (N), or more precisely functions from N to Bool (the decidable subsets). This is where the diagonal argument makes sense. So to conclude that there are more reals than naturals, the classical mathematical argument is: a) There are more functions N to Bool than naturals. b) There are as many reals as functions from N to Bool. Now, we of course agree the mistake is in b) not in a).

skissane 1y ago
> So to conclude that there are more reals than naturals, the classical mathematical argument is: > a) There are more functions N to Bool than naturals. > b) There are as many reals as functions from N to Bool. > Now, we of course agree the mistake is in b) not in a). Given certain foundations, (a) is false. For example, in the Russian constructivist school (as in Andrey Markov Jr), functions only exist if they are computable, and there are only countably many computable functions from N to Bool. More generally, viewing functions as sets, if you sufficiently restrict the axiom schema of separation/specification, then only countably many sets encoding functions N-to-Bool exist, rendering (a) false
- IngoBlechschmid 1y ago
  Indeed, what you write is true from an external point of view; just note that within this flavor of constructive mathematics, the set of functions from N to Bool is uncountable again. There is no paradox: Externally, there is an enumeration of all computable functions N -> Bool, but no such enumeration is computable.
  - skissane 1y ago
    Is it internally uncountable in the strong sense that the system can actually prove the theorem “this set is uncountable”, or only in the weaker sense that it can’t prove the theorem “this set is countable”, but can’t prove its negation either? If the latter, what happens if you add to it the (admittedly non-constructive) axiom that the set in question is countable?