Logic and Set Theory: G_delta-sigma Determinacy and generalized recursion

18 October 2016, 3.00 PM - 18 October 2016, 4.30 PM

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.

Contact information

Philip Welch

Edit this page