Logic and Set Theory G_delta-sigma determinacy and generalized recursion: I Overview
Howard House 4th Floor Seminar Room
It has been known since the Davis theorem (1965) that determinacy (thus the existence of winning strategies) of 2 person perfect information games on the G_delta-sigma sets of reals is provable in analysis. Such strategies must exist in the set theoretic universe. But where are they? This seminar locates them. Moreover, it gives a characterisation in terms of generalized Kleene recursion in higher types. The 'halting problem' for a certain kind of higher type recursion is shown to have the same informational content as a listing of the games which player 1 can win. We thus determine the lengths of G-Sigma^0_3-monotone inductions. Kleene, Moschovakis et al. showed that a) recursively open games won by Player 1 have hyperarithmetic strategies, and thus are recursive in Kleene's original sense; b) the complete semi-decidable set is essentially Kleene's O. We lift these results to the G_delta.sigma level: we show that such strategies are all 'recursive' in our sense, and b) the 'complete semi-decidable' set codes the wellfounded parts of computation trees.
Part 1 gives an overview of these results, Part 2 in the following week gives some details of the construction of the recursion.