Lema de codificación de Moschovakis

El lema de codificación de Moschovakis es un lema de la teoría descriptiva de conjuntos que involucra conjuntos de números reales bajo el axioma de determinación (el principio —incompatible con la elección— de que cada juego de números enteros entre dos jugadores está determinado). El lema fue desarrollado y nombrado en honor al matemático Yiannis N. Moschovakis .

El lema puede expresarse de manera general de la siguiente manera:

Sea Γ una clase puntual no autodual cerrada bajo cuantificación real y ∧ , y ≺ una relación Γ -bien fundada en ω ^ω de rango θ ∈ ON . Sea R ⊆ dom(≺) × ω ^ω tal que (∀ x ∈dom(≺))(∃ y )( x R y ) . Entonces hay un Γ -conjunto A ⊆ dom(≺) × ω ^ω que es un conjunto de elección para R, es decir:

1. (∀ α < θ )(∃ x ∈dom(≺), y )(| x | _≺ = α ∧ x A y ) .
2. (∀ x , y )( x A y → x R y ) .

Una prueba se ejecuta como sigue: supongamos por contradicción que θ es un contraejemplo minimal, y fijamos ≺ , R , y un buen conjunto universal U ⊆ ( ω ^ω ) ³ para los Γ -subconjuntos de ( ω ^ω ) ² . Fácilmente, θ debe ser un ordinal límite. Para δ < θ , decimos que u ∈ ω ^ω codifica un conjunto de δ -elección siempre que la propiedad (1) se cumpla para α ≤ δ usando A = U u y la propiedad (2) se cumpla para A = U u donde reemplazamos x ∈ dom(≺) con x ∈ dom(≺) ∧ | x | ≺ [≤ δ ] . Por minimalidad de θ , para todo δ < θ , hay conjuntos de δ -elección.

Ahora, juegue un juego donde los jugadores I, II seleccionan los puntos u , v ∈ ω ^ω y II gana cuando u codifica un conjunto de opciones δ ₁ para algún δ ₁ < θ implica que v codifica un conjunto de opciones δ ₂ para algún δ ₂ > δ ₁ . Una estrategia ganadora para I define un Σ¹
₁conjunto B de números reales que codifican conjuntos de elección δ para valores arbitrariamente grandes de δ < θ . Definamos entonces

x A y ↔ (∃ w ∈ B ) U ( w , x , y ) ,

lo cual funciona fácilmente. Por otro lado, supongamos que τ es una estrategia ganadora para II. Del teorema smn , sea s :( ω ^ω ) ² → ω ^ω continua tal que para todo ϵ , x , t y w ,

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

Por el teorema de recursión, existe ϵ ₀ tal que U ( ϵ ₀ , x , z ) ↔ z = τ ( s ( ϵ ₀ , x )) . Una inducción directa sobre | x | _≺ para x ∈ dom(≺) muestra que

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

y

(∀ x ∈dom(≺), z )( U ( ϵ ₀ , x , z ) → z codifica un conjunto de elección de ordinal ≥| x | _≺ ) .

Así que dejemoslo

x A y ↔ (∃ z ∈dom(≺), w )( U ( ϵ ₀ , z , w ) ∧ U ( w , x , y )) . ^{[1] [2] [3]}