Comment by gylterud
1 month 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).
> 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
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.
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?
7 replies →
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.