Comment by gylterud

Comment by 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).

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
  
  btilly 5 days ago
  
  It should be true in the stronger sense.
  Suppose that you've written down a function enumerate, that maps all natural numbers to functions that themselves map all natural numbers to booleans. We then can write down the following program.
  (defn unenumerated (n) (not ((enumerate n) n)))
  This function can be recognized as Cantor diagonalization, written out as a program.
  If enumerate actually works as advertised, then it can't ever find unenumerated. Because if (enumerate N) is unenumerated, then ((enumerate N) N) will hit infinite recursion and therefore doesn't return a boolean.
  This argument is, of course, just Cantor's diagonalization argument. From an enumeration, it produces something that can't be in that enumeration.
  
  Reply View | 6 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