Moschovakis coding lemma

The Moschovakis coding lemma is a lemma from descriptive set theory involving sets of real numbers in the Axiom of determinacy (the principle 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 point- class closed under ∃ ω ω and ∧ , and ≺ a Γ well-founded relation on ω ω of rank θ ∈ ON. Let R ⊆ dom( ≺ ) × ω ω be such that ∀ x ∈ dom( ≺ ) ∃ y R ( x,y ) . Then there is a Γ set A ⊆ dom( ≺ ) × ω ω which is a choice set for R , that is: 1. ∀ α < θ ∃ x ∈ dom( ≺ ) ∃ y [ | x | ≺ = α ∧ A ( x,y )] . 2. ∀ x ∀ y A ( x,y ) → [ x ∈ dom( ≺ ) ∧ R ( x,y )] . Proof. We may assume θ is minimal so that the theorem fails, and fix ≺ , R , and a good universal set U ⊆ ( ω ω ) 3 for the Γ subsets of ( ω ω ) 2 . Easily, θ is a limit ordinal. For δ < θ , say u ∈ ω ω codes a δ -choice set provided (1) holds for α ≤ δ using A = U u , and (2) holds for A = U u where we replace x ∈ dom( ≺ ) with x ∈ dom( ≺ ) ∧| x | ≺ ≤ δ . By minimality of θ , for all δ < θ there are δ -choice sets. Play the game where I, II play out u,v ∈ ω ω , and II wins provided that if u codes a δ 1 -choice set for some δ 1 < θ , then v codes a δ 2 -choice set for some δ 2 > δ 1 . If I has a winning strategy, we get a Σ 1 1 set B of reals coding δ -choice sets for arbitrarily large δ < θ . Define then A ( x,y ) ↔∃ w ∈ B U ( w,x,y ), which easily works. Suppose now τ is a winning strategy for II. From the s - m - n theorem, let s : ( ω ω ) 2 → ω ω be continuous such that for all ϵ,x,t,w, U ( s (ϵ,x ) ,t,w ) ↔ ∃ y ∃ z [ y ≺ x ∧ U (ϵ,y,z ) ∧ U ( z,t,w )]. By the recursion theorem, let ϵ 0 be such that U (ϵ0 ,x,z ) ↔ z = τ ( s (ϵ0 ,x )). A straightforward induction on | x | ≺ for x ∈ dom( ≺ ) shows that ∀ x ∈ dom( ≺ ) ∃ ! z U ( ϵ0 ,x,z ), and ∀ x ∈ dom( ≺ ) ∀ z [ U ( ϵ0 ,x,z ) → z codes a ≥| x | ≺ -choice set]. Let A ( x,y ) ↔∃ z ∈ dom( ≺ ) ∃ w [ U ( ϵ0 ,z,w ) ∧ U ( w,x,y )]., ,

External links

• | Yiannis N. Moschovakis homepage