मॉस्कोवैसिस कोडिंग लेम्मा

मॉस्कोवैसिस कोडिंग लेम्मा वर्णनात्मक समुच्चय सिद्धांत से एक लेम्मा (गणित) है जिसमें नियतत्व के स्वयंसिद्ध के अंतर्गत वास्तविक संख्याओं के समुच्चय सम्मलित होते हैं (सिद्धांत - वरण के साथ असंगत - कि प्रत्येक दो-वादक पूर्णांक खेल निर्धारित होते है)। लेम्मा को विकसित किया गया था और इसका नाम गणितज्ञ यियानिस एन मोस्कोवाकिस के नाम पर रखा गया था।

लेम्मा को सामान्यतः निम्नानुसार व्यक्त किया जा सकता है:

होने देना Γ क्वांटिफायर (तर्क) # क्वांटिफिकेशन की रेंज और के अंतर्गत बंद एक गैर-स्वयं दोहरी बिंदु वर्ग बनें ∧, और ≺ ए Γ-अच्छी तरह से स्थापित संबंध {{math|ω^ω}रैंक का θ ∈ ON. होने देना R ⊆ dom(≺) × ω^ω ऐसा हो (∀x∈dom(≺))(∃y)(x R y). फिर एक है Γ-तय करना A ⊆ dom(≺) × ω^ω जो R के लिए एक विकल्प समुच्चय है, वह है:

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

एक प्रमाण इस प्रकार चलता है: विरोधाभास के लिए मान लीजिए θ एक न्यूनतम प्रति उदाहरण है, और ठीक करें ≺, R, और एक अच्छा सार्वभौमिक समुच्चय U ⊆ (ω^ω)³ के लिए Γ-के उपसमुच्चय (ω^ω)². आसानी से, θ एक सीमा क्रमसूचक होना चाहिए। के लिए δ < θ, हम कहते हैं u ∈ ω^ω कोड ए δ-चॉइस समुच्चय प्रदान किया गया संपत्ति (1) रखती है α ≤ δ का उपयोग करना A = U u और संपत्ति (2) के लिए रखती है A = U u जहां हम प्रतिस्थापित करते हैं x ∈ dom(≺) साथ x ∈ dom(≺) ∧ |x| ≺ [≤δ]. कम से कम θ, सभी के लिए δ < θ, वहाँ हैं δ-विकल्प समुच्चय।

अब, एक खेल खेलें जहाँ खिलाड़ी I, II अंक चुनते हैं u,v ∈ ω^ω और II कब जीतता है u कोडिंग ए δ₁-विकल्प कुछ के लिए निर्धारित है δ₁ < θ तात्पर्य v कोड ए δ₂-विकल्प कुछ के लिए निर्धारित है δ₂ > δ₁. I के लिए एक जीतने की रणनीति परिभाषित करती है Σ¹
₁ तय करना {{mvar|B}वास्तविक एन्कोडिंग की } δ-विकल्प मनमाने ढंग से बड़े के लिए समुच्चय करता है δ < θ. तब परिभाषित करें

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

जो आसानी से काम करता है। दूसरी ओर, मान लीजिए τ II के लिए जीतने की रणनीति है। एस-एम-एन प्रमेय से, चलो s:(ω^ω)² → ω^ω निरंतर ऐसा हो कि सभी के लिए ϵ, 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)). एक सीधा इंडक्शन ऑन |x|_≺ के लिए x ∈ dom(≺) पता चलता है कि

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

और

(∀x∈dom(≺),z)(U(ϵ₀,x,z) → z encodes a choice set of ordinal ≥|x|_≺).

तो चलो

x A y ↔ (∃z∈dom(≺),w)(U(ϵ₀,z,w) ∧ U(w,x,y)).