Logic and Set Theory: G_delta-sigma Determinacy and generalized recursion
Philip Welch University of Bristol
Howard House 4th Floor Seminar Room
G_delta-sigma Determinacy and generalized recursion 2 The Construction
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 this sense, and b) the complete 'semi-deciable' set codes the wellfounded parts of computation trees.
This week's Part 2 gives some details of the construction of the recursion.