Talk:Cantor's diagonal argument/Archive 3

Archive 1

Archive 2

Archive 3

Constructivist interpretations

The late User:Futonchild added a problematic section which I tried to shape into something that was at least meaningful, but frankly it's still problematic. It goes like this at present:

The interpretation of Cantor's result will depend upon one's view of mathematics, and more specifically on how one thinks of mathematical functions. In the context of classical mathematics, functions need not be computable, and hence the diagonal argument establishes that, there are more infinite sequences of ones and zeros than there are natural numbers. To those constructivists who countenance only computable functions, Cantor's proof (merely) shows that there is no recursively enumerable set of indices (for example, Gödel numbers) for the programs computing them.

Now, I think it is true that constructivists, or at least some of them, do not accept the "quantity" interpretation of the argument. It seems to me, though, that to deny the quantity interpretation, they're pretty much obliged by the argument to deny that the sequences of zeroes and ones can be collected into a completed totality. They are not really saying, that is, that there are only as many sequences of zeroes and ones as there are natural numbers, even if the only sequences they accept are the computable ones, because for coherency's sake the only enumeration of sequences they could accept is a computable one (say, a computable enumeration of Turing machines that produce total sequences, or a global computable function giving the nth bit of the mth sequence), and Cantor's argument (which by the way is intuitionistically valid) excludes that possibility. (I don't know any intuitionistic proof, on the other hand, that there's no injection from the sequences into the naturals; it's conceivable that some intuitionists believe that the existence of such an injection is "not false".)

Anyway, I think the current text is unsatisfactory, but I don't want to just delete it out of hand; there probably are constructivist interpretations that deny the proof is about "quantity", and they should be fairly represented. Can anyone help out here, especially with versions that might be attributed to specific constructivist/intuitionist thinkers? --Trovatore 07:00, 14 March 2007 (UTC)

Your parenthetical remark about injections is close. I'm not sure but I think your proposed injection is still inconsistent, on the other hand it is quite consistent to assert a partial surjection from the naturals to the infinite bit sequences, i.e. that the infinite bit sequences are subcountable. Clearly this contradicts the "quantity interpretation" because although the naturals and infinite bit sequences are not in bijection, each one can be seen as a partial image of the other. Now pardon me while I fix this redlink. --99.234.59.230 (talk) 03:34, 4 January 2008 (UTC)

Could someone explain how $f:s\rightarrow T$ can have a partial surjection (i.e. be subcountable)? If the proof shows that there exists $T_{x}$ such that there does not exist a corresponding $s_{x},$ doesn't that mean that f is not surjective? If I'm understanding partial surjection correctly, it just means that the function is surjective and it is also a partial function. If f is not surjective, how can it have a partial surjection? StardustInTheDark (talk) 15:10, 25 November 2017 (UTC)