The Moschovakis coding lemma is a lemma from descriptive

set theory Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly conce ...

involving sets of

real number In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every ...

s under the

axiom of determinacy In mathematics, the axiom of determinacy (abbreviated as AD) is a possible axiom for set theory introduced by Jan Mycielski and Hugo Steinhaus in 1962. It refers to certain two-person topological games of length ω. AD states that every game of ...

(the principle — incompatible with

choice A choice is the range of different things from which a being can choose. The arrival at a choice may incorporate motivators and models. For example, a traveler might choose a route for a journey based on the preference of arriving at a give ...

— that every two-player integer game is determined). The lemma was developed and named after the mathematician

Yiannis N. Moschovakis Yiannis Nicholas Moschovakis ( el, Γιάννης Μοσχοβάκης; born January 18, 1938) is a set theorist, descriptive set theorist, and recursion (computability) theorist, at UCLA. His book ''Descriptive Set Theory'' (North-Holland) is ...

. The lemma may be expressed generally as follows: :Let be a non-selfdual

pointclass In the mathematical field of descriptive set theory, a pointclass is a collection of sets of points, where a ''point'' is ordinarily understood to be an element of some perfect Polish space. In practice, a pointclass is usually characterized by ...

closed under real quantification and , and a -well-founded relation on of rank . Let be such that . Then there is a -set which is a choice set for R , that is: # . # . A proof runs as follows: suppose for contradiction is a minimal counterexample, and fix , , and a good universal set for the -subsets of . Easily, must be a limit ordinal. For , we say codes a -choice set provided the property (1) holds for using and property (2) holds for where we replace with . By minimality of , for all , there are -choice sets. Now, play a game where players I, II select points and II wins when coding a -choice set for some implies codes a -choice set for some . A winning strategy for I defines a set of reals encoding -choice sets for arbitrarily large . Define then :, which easily works. On the other hand, suppose is a winning strategy for II. From the s-m-n theorem, let be continuous such that for all , , , and , :. By the recursion theorem, there exists such that . A straightforward induction on for shows that :, and :. So let :.

References

Axioms of set theory Determinacy Large cardinals Lemmas in set theory {{math-stub