An analysis of Spector Classes associated with quasi-inductive definitions

点击翻译按钮获取中文摘要

Various authors have responded in differing ways to the results of Tarski and Goedel on theundefinability of truth and incompleteness of formal systems, which ruled out the possibility that one can have a formula in a deductive system that defines truth completely. These theories left open the door to the possibility that we can partially define truth by some formula. The two most widely known approaches to this were designed by Kripke in the 70's and Gupta and Belnap in the 80's and 90's. It is also well known that we can give a description of the sets of sentences definably true in a system such as Kripke's by using two person perfect information infinite games. (A strategy for one of the players tells them how to move. A winning strategy ensures they will always win even if there are infinitely many moves on the board.) An 'open game' is one essentially in which one player can win in finitely many stages (although the other player - playing in to the `closed' set - may have to play infinitely often in order to win).These are known to be 'determined' (that is one of the players must have a winning strategy). Kripke's truth sets can be characterised by means of such simple open games.The proposer has looked at how Gupta & Belnap's theory of circular definitions, a form of 'quasi-inductive' definition, can be embedded in a theory involving determinacystatements for games of greater complexity than open/closed in the arithmetic hierarchy. We thus know there is a level of the arithmetic hierarchy whose determinacy allows such circular definitions as those of Gupta-Benap to take place. One mathematical question we should like to address is to give a proper answer as to how much infinity is required for thetheory of quasi-inductive definitions to work . This is made precise through asking for precise games whose determinacy allows such definitions to close-off or reach a stable state ( fixed points in general cannot occur). A second mathematical question asks how we can reverse the first question: assuming Gupta and Belnap's revision theory of circular definitions always stabilizes, then how strong is this in terms of theories of analysis?Both the theory of generalised inductive definitions, and the theories of truth mentionedhas been seen quite recently to be formally equivalent with a transfinite computational model.This is an exciting occurrence of `convergence' between radically different areas, coming as they do from quite different disciplines. Here we imagine a standard Turing machine or computer, being allowed to run over tranfinite lengths of time. What could such a conceptual or 'virtual' machine compute? Just as for ordinary Turing machines, we can delimit their computational power. The analysis of what is computable turns out to be one of a class of sets called Spector Classes .The project will analysis the Spector class of sets of real numbers associated with thesegames, or equivalently these computational models, or again, these philosophical theories of truth.