next up previous
Next: Objection 3 Up: Objections Previous: Objection 1

Objection 2

``Ah! You concede then that you have a decision procedure for $\cal S$I. But uncountably infinite sets like R, the reals, are not decidable!"

This objection is anemic (though I have had it earnestly expressed to me). And the reason it is, of course, is that I need only maintain that $\cal S$I is effectively decidable, not that there is some program (or Turing Machine, etc.) that can decide this set. (CT is the customary justification given for identifying effective decidability with formal decidability, but of course one can hardly invoke CT in the present context without falling prey to a petitio.)

Though Objection 2 is misguided, it does suggest an interesting parallel for Arg3:

Arg3'
(9') If R $\in \Sigma_1$ (or R $\in \Sigma_0$), then there exists a procedure P which adapts programs for deciding members of R so as to yield programs for enumerating members of R.
(10') There's no procedure P which adapts programs for deciding members of R so as to yield programs for enumerating members of R.
.$^\cdot$. (11') R $\not\in \Sigma_1$ (or R $\not\in \Sigma_0$). 10, 11
(12') R $\in$ AH.
.$^\cdot$. (13') R $\in \Pi_1$ (or above in the AH). disj syll
(14') R is effectively decidable.
.$^\cdot$. (15') CT is false. reductio

As we know by now, premise (9') is an instantiation of a simple theorem of elementary computability theory; (11') and (13') are simply intermediate conclusions; (15) does indeed follow from (13') and (14'), since these two propositions counter-example CT's ``only if" part; and the other two inferences are unassailable. Everything boils down to (10') and (14'). But we know that in the case of the reals, (11') is true (and, of course, so is (10')), but we don't need it), and the technique of getting R from N (the natural numbers) via (e.g.)  (e.g.) Dedekind cuts constitutes a proof of (12'). Of course, it's doubtful that R or a subset thereof is effectively decidable. Such is not the case, as I've explained, with $\cal S$I.


next up previous
Next: Objection 3 Up: Objections Previous: Objection 1
Selmer Bringsjord
1998-06-13