モスコバキス符号化補題

モスコバキス符号化補題は、記述集合論における補題であり、決定性公理（選択とは相容れない原理で、すべての2人対戦整数ゲームは決定可能であるという原理）の下での実数の集合に関するものである。この補題は、数学者ヤニス・N・モスコバキスにちなんで考案され、命名された。

この補題は、一般的に次のように表すことができる。

Γ を^実数化と∧の下で閉じた非自己双対点クラスとし、≺ をランクθ ∈ ONのω ω上のΓ整礎関係とする。R ⊆ dom(≺) × ω ^ωを(∀ x ∈dom(≺))(∃ y )( x R y )を満たすものとする。このとき、R の選択集合であるΓ集合A ⊆ dom(≺) × ω ^ωが存在する。すなわち、次のようになる。

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

証明は次のようになります。矛盾を導くために、θが最小の反例であると仮定し、≺、R 、および( ω ^ω ) ²のΓ部分集合に対する良い普遍集合U ⊆ ( ω ^ω ) ^{3 を}固定します。容易に、θ は極限順序数でなければなりません。δ < θの場合、A = U u^を使用してα ≤ δに対して性質 (1) が成り立ち、x ∈ dom ( ≺ ) をx ∈ dom (≺ ) ∧ | x | ≺ [≤ δ ]に置き換えるA = U uに対して性質 (2) が成り立つ場合、u ∈ ω ω はδ選択集合をコード化すると言います。θ の最小性により、すべてのδ < θに対して、 δ選択集合が存在します。

ここで、プレイヤー I、II が点u、v ∈ ω ^ωを選択するゲームを考えます。uが何らかのδ ₁ < θに対してδ ₁選択集合を符号化する場合、vが何らかのδ ₂ > δ _{1に対して}δ ₂選択集合を符号化する場合に II が勝利します。I の勝利戦略は、任意の大きなδ < θに対してδ選択集合を符号化する実数の集合Σ ¹ ₁を定義することです。次に、と定義します。

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

これは簡単に機能します。一方、τ がII の勝ち戦略であると仮定します。S m n 定理から、s :(   ω ω ) 2 → ^ω ω^がすべての^ϵ、 x 、 t 、およびwに対して連続であるとします。

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

再帰定理により、U ( ϵ ₀ , x , z ) ↔ z = τ ( s ( ϵ ₀ , x ))となるようなϵ _{0が存在する。x ∈} dom (≺)に対する| x | _≺に関する簡単な帰納法により、

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

そして

(∀ x ∈dom(≺), z )( U ( ϵ ₀ , x , z ) → z は順序数 ≥ | x | _≺の選択セットをエンコードします)。

だから

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