Comment by btilly

Comment by btilly 5 days ago

As I pointed out at 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 5 days 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.

Reply View 2 replies

btilly 5 days 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.

Reply View | 0 replies
skissane 5 days 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.)

Reply View | 0 replies

gylterud 5 days 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).

Reply View 11 replies

skissane 5 days 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

Reply View | 10 replies
- IngoBlechschmid 5 days 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.
  
  Reply View | 8 replies
  
  skissane 5 days 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?
  
  Reply View | 7 replies
- gylterud 4 days ago
  
  Bringing in computability from an external point of view is a mistake here. Markov had no issue with a. He would only disagree with b.
  
  Reply View | 0 replies