Logic and Set Theory G_delta-sigma determinacy and generalized recursion: I Overview

11 October 2016, 3.00 PM - 11 October 2016, 4.30 PM

Philip Welch

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.

Edit this page