Moschovakis coding lemma

From HandWiki

The Moschovakis coding lemma is a lemma from descriptive set theory involving sets of real numbers under the axiom of determinacy (the principle — incompatible with choice — that every two-player integer game is determined). The lemma was developed and named after the mathematician Yiannis N. Moschovakis. The lemma may be expressed generally as follows:

Let Γ be a non-selfdual pointclass closed under real quantification and , and a Γ-well-founded relation on ωω of rank θ ∈ ON. Let R ⊆ dom(≺) × ωω be such that (∀x∈dom(≺))(∃y)(x R y). Then there is a Γ-set A ⊆ dom(≺) × ωω which is a choice set for R , that is:
  1. (∀α<θ)(∃x∈dom(≺),y)(‹See Tfd›|x|=αx A y).
  2. (∀x,y)(x A yx R y).

A proof runs as follows: suppose for contradiction θ is a minimal counterexample, and fix , R, and a good universal set U ⊆ (ωω)3 for the Γ-subsets of (ωω)2. Easily, θ must be a limit ordinal.[1] For δ < θ, we say uωω codes a δ-choice set provided the property (1) holds for αδ using A = U u and property (2) holds for A = U u where we replace x ∈ dom(≺) with x ∈ dom(≺) ∧ ‹See Tfd›|x| ≺ [≤δ]. By minimality of θ, for all δ < θ, there are δ-choice sets.

Now, play a game where players I, II select points u,vωω and II wins when u coding a δ1-choice set for some δ1 < θ implies v codes a δ2-choice set for some δ2 > δ1. A winning strategy for I defines a Σ11 set B of reals encoding δ-choice sets for arbitrarily large δ < θ. Define then

x A y ↔ (∃wB)U(w,x,y),

which easily works. On the other hand, suppose τ is a winning strategy for II. From the s-m-n theorem, let s:(ωω)2ωω be continuous such that for all ϵ, x, t, and w,

U(s(ϵ,x),t,w) ↔ (∃y,z)(yxU(ϵ,y,z) ∧ U(z,t,w)).

By the recursion theorem, there exists ϵ0 such that U(ϵ0,x,z) ↔ z = τ(s(ϵ0,x)). A straightforward induction on ‹See Tfd›|x| for x ∈ dom(≺) shows that

(∀x∈dom(≺))(∃!z)U(ϵ0,x,z),

and

(∀x∈dom(≺),z)(U(ϵ0,x,z) → z encodes a choice set of ordinal ≥‹See Tfd›|x|).

So let

x A y ↔ (∃z∈dom(≺),w)(U(ϵ0,z,w) ∧ U(w,x,y)).[2][3][4]

References

  1. User 16278263789; Schweber, Noah (9 October 2011). "descriptive set theory - Moschovakis Coding Lemma". https://mathoverflow.net/questions/77573/moschovakis-coding-lemma. 
  2. Babinkostova, Liljana (2011) (in English). Set Theory and Its Applications. American Mathematical Society. ISBN 978-0821848128. 
  3. Foreman, Matthew; Kanamori, Akihiro (October 27, 2005). Handbook of Set Theory. Springer. pp. 2230. ISBN 978-1402048432. http://www.math.unt.edu/~sjackson/papers/strad_27.pdf. 
  4. Moschovakis, Yiannis (October 4, 2006). "Ordinal games and playful models". Cabal Seminar 77 – 79: Proceedings, Caltech-UCLA Logic Seminar 1977 – 79. Lecture Notes in Mathematics. 839. Berlin: Springer. pp. 169–201. doi:10.1007/BFb0090241. ISBN 978-3-540-38422-9.