Moschovakis lemmani kodlaydi - Moschovakis coding lemma

The Moschovakis lemmani kodlaydi a lemma tavsiflovchi to'plam nazariyasi to'plamlarini o'z ichiga olgan haqiqiy raqamlar ostida qat'iyatlilik aksiomasi (printsip - mos kelmaydi tanlov - har ikki o'yinchi butun o'yin aniqlanishi). Lemma ishlab chiqilgan va matematik nomiga berilgan Yiannis N. Moschovakis.

Lemma odatda quyidagicha ifodalanishi mumkin:

Ruxsat bering Γ o'ziga xos bo'lmagan shaxs bo'ling nuqta klassi ostida yopilgan haqiqiy miqdoriy miqdor va ∧va ≺ a Γ- asosli munosabat ωω daraja θ ∈ YOQ. Ruxsat bering R ⊆ dom (≺) × ωω shunday bo'ling (∀x∈dom (≺)) (∃y)(x R y). Keyin bor Γ- sozlash A ⊆ dom (≺) × ωω bu tanlov to'plami R uchun, ya'ni:
  1. (∀a<θ)(∃xDom (≺),y)(|x|≺=a ∧ x A y).
  2. (∀x,y)(x A y → x R y).

Dalil quyidagicha ishlaydi: qarama-qarshilikni taxmin qiling θ bu minimal qarshi namuna va tuzatish ≺, Rva yaxshi universal to'plam U ⊆ (ωω)3 uchun Γ-subets (ωω)2. Osonlik bilan, θ chegara tartibli bo'lishi kerak.[1] Uchun δ < θ, deymiz siz ∈ ωω kodlari a δ(1) xususiyatiga ega bo'lish sharti bilan tanlov to'plami a ≤ δ foydalanish A = U va mulk (2) egalik qiladi A = U biz qaerda almashtiramiz x ∈ dom (≺) bilan x ∈ dom (≺) ∧ |x| ≺ [≤δ]. Minimalligi bo'yicha θ, Barcha uchun δ < θ, lar bor δ- tanlov to'plamlari.

Endi I, II o'yinchilar ochko tanlaydigan o'yin o'ynang siz,v ∈ ωω va qachon II yutadi siz kodlash a δ1- kimdir uchun tanlov δ1 < θ nazarda tutadi v kodlari a δ2- kimdir uchun tanlov δ2 > δ1. Men uchun g'olib strategiya a ni belgilaydi Σ1
1 o'rnatilgan B realizatsiya kodlash δ- o'zboshimchalik bilan katta uchun tanlov to'plamlari δ < θ. Keyin aniqlang

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

bu oson ishlaydi. Boshqa tomondan, deylik τ II uchun yutuqli strategiya. Dan s-m-n teoremasi, ruxsat bering s:(ωω)2 → ωω hamma uchun shunday uzluksiz bo'ling ϵ, x, tva w,

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

Rekursiya teoremasi bo'yicha mavjud ϵ0 shu kabi U(ϵ0,x,z) ↔ z = τ(s(ϵ0,x)). To'g'ridan to'g'ri indüksiyon |x|≺ uchun x ∈ dom (≺) buni ko'rsatadi

(∀xDom (≺)) (∃!z)U(ϵ0,x,z),

va

(∀xDom (≺),z)(U(ϵ0,x,z) → z inal | tartibli tanlov to'plamini kodlaydix|≺).

Shunday qilib, ruxsat bering

x A y ↔ (∃zDom (≺),w)(U(ϵ0,z,w) ∧ U(w,x,y)).[2][3][4]

Adabiyotlar

  1. ^ Foydalanuvchi 16278263789; Shveber, Nuh (2011 yil 9 oktyabr). "tavsiflovchi to'plam nazariyasi - Moschovakis kodlash Lemma". MathOverflow. Olingan 2020-04-06.
  2. ^ Babinkostova, Liljana (2011). Nazariyani va uning qo'llanilishini o'rnating. Amerika matematik jamiyati. ISBN  978-0821848128.
  3. ^ Usta, Metyu; Kanamori, Akixiro (2005 yil 27 oktyabr). To'plamlar nazariyasi qo'llanmasi (PDF). Springer. p. 2230. ISBN  978-1402048432.
  4. ^ Moschovakis, Yiannis (2006 yil 4 oktyabr). "Oddiy o'yinlar va o'ynoqi modellar". Aleksandr S. Kechrisda; Donald A. Martin; Yiannis N. Moschovakis (tahr.). Kabal seminari 77 - 79: Ish yuritish, Caltech-UCLA mantiqiy seminari 1977 - 79. Matematikadan ma'ruza matnlari. 839. Berlin: Springer. 169–201 betlar. doi:10.1007 / BFb0090241. ISBN  978-3-540-38422-9.