Moschovakis Coding Lemma

(Lemmas In Set Theory)


Lemmas In Set Theory
Link to Dbpedia

What is Moschovakis coding lemma?

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)(|x|≺=α ∧ x A y). 2. * (∀x,y)(x A y → x 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. 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(≺) ∧ |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 ↔ (∃w∈B)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)(y ≺ x ∧ U(ϵ,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 |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 ≥|x|≺). So let x A y ↔ (∃z∈dom(≺),w)(U(ϵ0,z,w) ∧ U(w,x,y)).

Technology Types

axioms of set theorydeterminacylarge cardinallemmas in set theory


Moschovakis' coding lemmaMoschovakis's coding lemma

Tech Info

Source: [object Object]
 — Date merged: 11/6/2021, 1:32:50 PM
 — Date scraped: 5/20/2021, 6:21:39 PM