Abstract
Diagonalization is a proof technique that formal learning theorists use to show that inductive problems are unsolvable. The technique intuitively requires the construction of the mathematical equivalent of a “Cartesian demon” that fools the scientist no matter how he proceeds. A natural question that arises is whether diagonalization iscomplete. That is, given an arbitrary unsolvable inductive problem, does an invincible demon exist?
The answer to that question tunas out to depend upon what axioms of set theory we adopt. The two main results of the paper show that if we assume Zermelo-Fraenkel set theory plus AC and CH, there exist undetermined inductive games. The existence of such games entails that diagonalization is incomplete. On the other hand, if we assume the Axiom of Determinacy, or even a weaker axiom known as Wadge Determinacy, then diagonalization is complete.
In order to prove the results, inductive inquiry is viewed as an infinitary game played between the scientist and nature. Such games have been studied extensively by descriptive set theorists. Analogues to the results above are mentioned, in which both the scientist and the demon are restricted to computable strategies.
The results exhibit a surprising connection between inductive methodology and the foundations of set theory.
Similar content being viewed by others
References
Angluin, D. ‘Inductive inference of formal languages from positive data’,Information and Control 45: 117–135, 1980.
Case, J. and C. Smith, ‘Comparison of Identification Criteria for Machine Inductive Inference’,Theoretical Computer Science 25: 193–220, 1983.
Gold, E. M. ‘Limiting Recursion’,JSL 30, 1, 1965.
Kelly, K. ‘Formal Learning Theory as Generalized Descriptive Set Theory’, forthcoming inLogic and Computation, 1993.
Moschovakis, Y. A.Descriptive Set Theory, North-Holland, 1980.
Osherson, D., M. Stob and S. Weinstein,Systems that Learn, MIT Press, 1986.
Putnam, H. “Trial and Error Predicates and the Solution to a Problem of Mostowski’,JSL 30, 1, 1965.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Juhl, C. Is Gold-Putnam diagonalization complete?. J Philos Logic 24, 117–138 (1995). https://doi.org/10.1007/BF01048528
Issue Date:
DOI: https://doi.org/10.1007/BF01048528