kararlılık - Determinacy

Belirlilik , bir oyunun bir veya diğer oyuncusunun kazanma stratejisine sahip olduğu koşulları ve bu stratejilerin varlığının sonuçlarını inceleyen bir matematik dalı olan küme teorisinin bir alt alanıdır . Alternatif ve benzer şekilde, "belirlilik", böyle bir stratejinin var olduğu bir oyunun özelliğidir.

Küme teorisinde çalışılan oyunlar genellikle Gale –Stewart oyunlarıdır - oyuncuların sonsuz sayıda hamle yaptığı ve beraberlik olmadığı iki oyunculu mükemmel bilgi oyunlarıdır . Oyun teorisi alanı, tic-tac-toe , satranç veya sonsuz satranç gibi beraberlik içeren oyunlar veya poker gibi kusurlu bilgilere sahip oyunlar da dahil olmak üzere daha genel oyun türlerini inceler .

Temel kavramlar

Oyunlar

Ele alacağımız ilk oyun türü , oyuncuların doğal sayıları oynadığı, uzunluğu ω olan mükemmel bilgi içeren iki oyunculu oyundur . Bu oyunlara genellikle Gale-Stewart oyunları denir.

Bu tür bir oyunda, genellikle I ve II olarak adlandırılan iki oyuncu vardır ve bu oyuncular sırayla doğal sayılarla oynar ve önce I başlar . "Sonsuza kadar" oynuyorlar; yani oyunları doğal sayılarla endekslenir. Bitirdiklerinde, önceden belirlenmiş bir koşul hangi oyuncunun kazanacağına karar verir. Bu koşulun herhangi bir tanımlanabilir kural tarafından belirtilmesine gerek yoktur ; belirli bir oyun dizisinde kimin kazandığını söyleyen rastgele (sonsuz uzunlukta) bir arama tablosu olabilir .

Daha teorik bir alt kümesi dikkate A ve Baire uzay ; ikincisinin doğal sayıların tüm ω-dizilerinden oluştuğunu hatırlayın. Daha sonra oyun G _A , I , bir doğal sayı oynayan bir ₀ , daha sonra II oynayan bir ₁ , daha sonra bir oynayan bir ₂ , vb. Sonra ben oyunu kazanır ve ancak eğer

${\displaystyle \langle a_{0},a_{1},a_{2},\ldots \rangle \in A}$

ve aksi takdirde II kazanır. A , G _A'nın ödeme kümesi olarak adlandırılır .

Her oyuncunun her hamlesinden önceki tüm hamleleri görebildiği ve ayrıca kazanma koşulunu bildiği varsayılır.

stratejiler

Gayri resmi olarak, bir oyuncu için bir strateji , oyunlarının tamamen yukarıdaki oyunlar tarafından belirlendiği bir oynama şeklidir. Yine, böyle bir "yol", açıklanabilir herhangi bir "kural" tarafından yakalanma yeteneğine sahip olmak zorunda değildir, ancak sadece bir arama tablosu olabilir.

Daha resmi olarak, oyuncu I için bir strateji (önceki alt bölüm anlamında bir oyun için), çift uzunluktaki herhangi bir sonlu doğal sayı dizisini argüman olarak kabul eden ve bir doğal sayı döndüren bir fonksiyondur. Eğer σ böyle bir stratejidir ve <a ₀ ,...,a _2n-1> oyunlarının dizisidir ardından σ (<a ₀ ,...,a _2n-1> ) olan bir sonraki oyun ben yapacak eğer ben strateji takip ediyor σ . II için stratejiler tamamen aynıdır, "çift" yerine "tek" kelimesini kullanır.

Bir stratejinin herhangi bir şekilde iyi olup olmadığı hakkında henüz hiçbir şey söylemediğimizi unutmayın . Bir strateji, bir oyuncuyu agresif bir şekilde kötü hamleler yapmaya yönlendirebilir ve yine de bir strateji olacaktır. Aslında bir oyun için kazanma koşulunu bilmek, oyun için hangi stratejilerin mevcut olduğunu bilmek bile gerekli değildir.

Kazanma stratejileri

Rakibi ne oynarsa oynasın, onu takip eden oyuncunun mutlaka kazanması gerekiyorsa bir strateji kazanıyor . Örneğin, σ için bir stratejidir I , o σ için kazanan bir stratejidir I oyun G _bir doğal sayı herhangi bir sekans tarafından oynatılacak için, eğer II <a ki ₁ , bir ₃ , bir ₅ ,. ..>, üretilen oyunlarının dizisi σ zaman II , yani, bu şekilde oynar

${\displaystyle \langle \sigma (\langle \rangle ),a_{1},\sigma (\langle \sigma (\langle \rangle ),a_{1}\rangle ),a_{3},\ldots \rangle }$

A'nın bir elemanıdır .

Belirlenen oyunlar

Oyunun tüm durumları için oyunculardan biri için bir kazanma stratejisi varsa (her örnek için aynı oyuncu olması gerekmez ) bir oyun (sınıf) belirlenir . Aynı oyun için her iki oyuncu için de kazanan bir strateji olamayacağına dikkat edin, eğer öyle olsaydı, iki strateji birbirine karşı oynanabilirdi. Ortaya çıkan sonuç, hipoteze göre, her iki oyuncu için de bir kazanç olacaktır ki bu imkansızdır.

Temel hususlardan kararlılık

Beraberliklerin olmadığı tüm sonlu mükemmel bilgi oyunları belirlenir.

tic-tac-toe , satranç veya sonsuz satranç gibi mükemmel bilgi içeren gerçek dünya oyunları her zaman sınırlı sayıda hamlede tamamlanır (satranç oyunlarında bu, 50 hamle kuralının uygulandığını varsayar). Böyle bir oyun, oyunun berabere olarak adlandırılacağı herhangi bir koşulda belirli bir oyuncunun kazanması için değiştirilirse, o zaman her zaman belirlenir. Seti bu oyun her zaman sona erdiğini koşul topolojik durumuna hamle karşılık gelir sonlu sayıda (aynı oyuncu için galibiyette sonlu pozisyon sonucu tüm olası uzantıları yani) A G kazanan koşulunu veren _A olduğunu clopen içinde topoloji arasında Baire uzay .

Örneğin, berabere oynanan oyunları Siyah için bir kazanç haline getirmek için satrancın kurallarını değiştirmek, satrancı kararlı bir oyun haline getirir. Olduğu gibi, satrancın sınırlı sayıda pozisyonu ve tekrarlı beraberlik kuralları vardır, bu nedenle, bu değiştirilmiş kurallarla, eğer Beyaz kazanmadan oyun yeterince uzun sürerse, o zaman Siyah sonunda bir galibiyete zorlayabilir (beraberlik değişikliği nedeniyle) = siyah için kazan).

Bu tür oyunların belirlendiğinin kanıtı oldukça basittir: Oyuncu I sadece kaybetmemek için oynar ; olduğunu, oyuncu ben oyuncu olduğundan emin olmak için çalış II kazanan bir strateji yok sonra ben' ın hareket. Oyuncu I bunu yapamıyorsa , oyuncu II'nin başından beri bir kazanma stratejisi olduğu anlamına gelir . Oyuncunun Diğer taraftan, ben yapabilirsiniz bu şekilde oynamak, o zaman ben oyun hamle bazı sonlu sayısının ardından bitecek çünkü kazanmalıdır ve oyuncu ben o noktada kaybetmiş olamaz.

Bu ispat aslında oyunun her zaman sonlu sayıda hamlede bitmesini gerektirmez , sadece II kazandığında sonlu sayıda hamlede bitmesini gerektirir . Bu durum, topolojik olarak, set olmasıdır A edilmektedir kapalı . Tüm kapalı oyunların belirlendiği bu gerçeğe Gale-Stewart teoremi denir . Simetri ile tüm açık oyunların da belirlendiğini unutmayın. (Bir oyun açık eğer ben sadece hamle sonlu sayıda kazanarak kazanabilir.)

Dan belirlilik ZFC

David Gale ve FM Stewart, açık ve kapalı oyunların belirlendiğini kanıtladı. Borel hiyerarşi oyunlarının ikinci seviyesi için kararlılık Wolfe tarafından 1955'te gösterildi. Takip eden 20 yıl boyunca, giderek daha karmaşık argümanlar kullanan ek araştırmalar, Borel hiyerarşisinin üçüncü ve dördüncü seviyelerinin belirlendiğini ortaya koydu.

1975 yılında Donald A. Martin , tüm Borel oyunlarının kararlı olduğunu kanıtladı ; yani, A , Baire uzayının bir Borel alt kümesiyse, G _A belirlenir. Borel belirlenimi olarak bilinen bu sonuç, bir sonraki yüksek Wadge sınıfının belirleniminin ZFC'de kanıtlanamaması anlamında ZFC'de kanıtlanabilecek en iyi olası belirleme sonucudur .

Martin onun kanıtı elde önce 1971 yılında, Harvey Friedman Borel belirlilik ilgili bir kanıt kullanması gerektiğini gösterdi değiştirme belitini yineleme için, önemli bir şekilde Powerset aksiyomu transfinitely sık. Friedman'ın çalışması, Borel hiyerarşisinin her bir düzeyinde belirliliği garanti etmek için güç kümesi aksiyomunun kaç yinelemesinin gerekli olduğunu ayrıntılandıran düzeyde düzey bir sonuç verir .

Her tamsayı için n , ZFC \ P içinde belirsizliği kanıtlıyor n farkı hiyerarşisinin inci seviyede setleri, ancak ZFC \ P her tamsayı için kanıtlamaz n n farkı hiyerarşisinin inci seviyede belirlenir setleri. İkinci dereceden aritmetiğin belirlenimi ve alt sistemleri arasındaki diğer ilişkiler için ters matematiğe bakın . ${\displaystyle \mathbf {\Pi } _{3}^{0}}$ ${\displaystyle \Pi _{3}^{0}}$

Kararlılık ve büyük kardinaller

Belirlilik ve büyük kardinaller arasında yakın bir ilişki vardır . Genel olarak, daha güçlü büyük kardinal aksiyomlar , Wadge hiyerarşisinde daha yüksek olan daha büyük nokta sınıflarının belirlenimini kanıtlar ve bu tür nokta sınıflarının belirliliği, sırayla, belirliliklerini kanıtlamak için kullanılanlardan biraz daha zayıf büyük kardinal aksiyomların iç modellerinin varlığını kanıtlar . ilk etapta pointclass.

ölçülebilir kardinaller

Ölçülebilir bir kardinalin varlığından, her analitik oyunun (aynı zamanda Σ ¹ ₁ oyunu olarak da adlandırılır ) belirlendiği veya eşdeğer olarak her koanalitik (veya Π ¹ ₁ ) oyunun belirlendiği sonucu çıkar. ( Tanımlar için Projektif hiyerarşiye bakın .)

Aslında ölçülebilir bir kardinal fazlasıyla yeterli. Daha zayıf bir ilke — 0 ^#' nin varlığı, koanalitik belirliliği kanıtlamak için yeterlidir ve biraz daha fazlası: Kesin sonuç, 0 ^#' nin varlığının , ω ² seviyesinin altındaki fark hiyerarşisinin tüm seviyelerinin kararlılığına eşdeğer olmasıdır , yani ω·n- Π ¹ her için ₁ belirlilik . ${\görüntüleme stili n}$

Ölçülebilir bir kardinalden, bunu çok az ω ² - Π ¹ ₁ belirliliğe kadar iyileştirebiliriz . Daha ölçülebilir kardinallerin varlığından, Π ¹ ₁ üzerinde fark hiyerarşisinin daha fazla seviyesinin belirlendiği kanıtlanabilir .

Keskin nişancılardan kararlılık kanıtı

Her gerçek sayı r için , belirlilik r ^#' nin varlığına eşdeğerdir . Büyük kardinallerin nasıl belirliliğe yol açtığını göstermek için, burada r ^{# 'nin} varlığı verilen bir belirliliğin kanıtı . ${\görüntüleme stili \Sigma _{1}^{1}(r)}$${\görüntüleme stili \Sigma _{1}^{1}(r)}$

A , Baire uzayının bir alt kümesi olsun . (ω, ω) üzerinde bazı T ağacı ( r 'den oluşturulabilir ) için A = p[ T ] . (Yani x∈A IFF bir ila y , üzerinden bir yol T .) ${\görüntüleme stili \Sigma _{1}^{1}(r)}$${\displaystyle ((x_{0},y_{0}),(x_{1},y_{1}),...)}$

Kısmi bir oynatma s verildiğinde , max(y ₀ ,y ₁ ,...,y _len(s)-1 )<len(s)' ye tabi olan s ile tutarlı T'nin alt ağacı olsun . Ek koşul, bunun sonlu olmasını sağlar . Tutarlılık, içinden geçen her yolun , s'nin ilk segmenti olduğu biçimde olduğu anlamına gelir . ${\ Displaystyle T_{s}}$${\ Displaystyle T_{s}}$${\ Displaystyle T_{s}}$${\displaystyle ((x_{0},y_{0}),(x_{1},y_{1}),...,(x_{i},y_{i}))}$${\displaystyle (x_{0},x_{1},...,x_{i})}$

A'nın belirlendiğini kanıtlamak için, yardımcı oyunu aşağıdaki gibi tanımlayın:
Sıradan hamlelere ek olarak, 2. oyuncu , sıra sayıları (yeterince büyük bir κ değerinin altında) eşleştirmesi yapmalıdır . ${\ Displaystyle T_{s}}$

• her yeni hareket önceki eşlemeyi genişletir ve
• ordinals sıralaması hemfikir Kleene-Brouwer sipariş üzerine .${\ Displaystyle T_{s}}$

Eğer geri çağırma bu Kleene-Brouwer sırası hariç sözlük sırasını gibidir s doğru uzanan t sonra s < t . Ağaç sağlamsa, iyi bir düzendir.

Yardımcı oyun açıktır. Kanıt: 2. oyuncu sonlu bir aşamada kaybetmezse, o zaman hepsinin birleşimi (ki bu oyuna karşılık gelen ağaçtır) sağlam temellere dayanmaktadır ve dolayısıyla yardımcı olmayan oyunun sonucu A'da değildir. ${\ Displaystyle T_{s}}$

Böylece yardımcı oyun belirlenir. Kanıt: Sınır ötesi tümevarımla, her bir sıra için, 1. oyuncunun α adımlarında kazanmaya zorlayabileceği, 2. oyuncunun hareket edeceği bir pozisyonun α adımlarında kaybedeceği (oyuncu 2 için) konumların kümesini hesaplayın. konum α adımdan daha az bir sürede kaybediyor. 1. oyuncu için bir strateji, her pozisyonda α'yı azaltmaktır (diyelim ki en az α'yı seçip en az hamleyi seçerek bağları koparmak) ve 2. oyuncu için bir strateji, sonuç getirmeyen en az (aslında herhangi biri işe yarar) hamleyi seçmektir. α atanmış bir konuma. Not, L ( R ) pozisyonlarını olarak yukarıda verilen kazanan stratejiler kazanma kümesi içerir.

Orijinal oyunda oyuncu 2 için bir kazanma stratejisi, yardımcı oyunda kazanma stratejisine yol açar: Kazanma stratejisine karşılık gelen T'nin alt ağacı sağlam temellidir, bu nedenle oyuncu 2, ağacın Kleene-Brouwer sırasına göre sıraları seçebilir. Ayrıca, önemsiz bir şekilde, yardımcı oyunda 2. oyuncu için bir kazanma stratejisi, orijinal oyunda 2. oyuncu için bir kazanma stratejisi verir.

Geriye, r ^# kullanılarak , yardımcı oyunda oyuncu 1 için yukarıda bahsedilen kazanma stratejisinin, orijinal oyunda bir kazanma stratejisine dönüştürülebileceğini göstermek kalıyor . r ^# , ( L ( r ), ∈, r ) ayırt edilemez sıraların uygun bir I sınıfını verir . Eğer indiscernibility olarak, κ ve yardımcı yanıtta sıra sayıları olan I , ardından oyuncu 1 ile hareket eder yardımcı hamle (veya bağımlı olmayan k ) ve strateji (orijinal oyun için bir strateji dönüştürülebilir böylece çünkü oyuncu 2, herhangi bir sonlu sayıda adım için ayırt edilemezlerle dayanabilir). 1. oyuncunun orijinal oyunda kaybettiğini varsayalım. O halde, bir oyuna karşılık gelen ağaç sağlam temellidir. Bu nedenle, oyuncu 2, ayırt edilemezlere dayalı yardımcı hamleler kullanarak yardımcı oyunu kazanabilir (çünkü ayırt edilemezlerin sıra türü ağacın Kleene-Brouwer sırasını aşıyor), bu da oyuncu 1'in yardımcı oyunu kazanmasıyla çelişiyor.

Woodin kardinaller

Üzerinde ölçülebilir bir kardinal olan bir Woodin kardinali varsa, Π ¹ ₂ belirliliği geçerlidir. Daha genel olarak, hepsinin üzerinde ölçülebilir bir kardinali olan n Woodin kardinali varsa , o zaman Π ¹ _n+1 belirliliği geçerlidir. Kaynaktan tt ¹ _{n + 1} belirlilik, bir olduğu aşağıdaki geçişli iç modeli ihtiva eden n- Woodin kardinal.

${\displaystyle \Delta _{2}^{1}}$(ışık yüzlü) belirlenimi, bir Woodin kardinaliyle eşdeğerdir. Eğer belirlilik geçerliyse, o zaman x'in bir Turing konisi için (yani, yeterince yüksek Turing derecesine sahip her gerçek x için ), L[ x ] OD-belirlenimini sağlar (yani, ω uzunluğundaki tamsayılar üzerindeki oyunların belirlenimi ve sırasal olarak tanımlanabilir getiri) , ve HOD'da ^{L[ x ]} bir Woodin kardinaldir. ${\displaystyle \Delta _{2}^{1}}$ ${\displaystyle \omega _{2}^{L[x]}}$

projektif kararlılık

Sonsuz sayıda Woodin kardinali varsa, o zaman yansıtmalı belirlenim geçerlidir; yani kazanma koşulu projektif küme olan her oyun belirlenir. Projektif belirlenimden, her n doğal sayısı için , n tane Woodin kardinali olduğunu sağlayan bir geçişli iç model olduğu sonucu çıkar.

belirlenim aksiyomu

Belirlilik beliti veya AD , iddia her oyuncu naturals oynadığı uzunluğu w, mükemmel bilginin iki oyunculu oyun belirlenir.

AD, ZFC'den kanıtlanabilir şekilde yanlıştır; seçim aksiyomunu kullanarak, belirlenmemiş bir oyunun varlığı kanıtlanabilir. Bununla birlikte, hepsinin üzerinde ölçülebilir olan sonsuz sayıda Woodin kardinali varsa, o zaman L(R) , AD'yi karşılayan bir ZF modelidir .

Kararlılığın sonuçları

Gerçek kümeleri için düzenlilik özellikleri

Eğer bir Baire uzay bir alt kümesi olacak şekilde Banach-Mazur oyunu için A belirlenir, ardından ya II durumda olan bir kazanma stratejisi vardır bir olan yetersiz ya ben dava ettiği bir kazanma stratejisi vardır bir olan comeager bazı mahalle aç.

Bu, A'nın Baire özelliğine sahip olduğu anlamına gelmez , ancak yaklaşır: Argümanın basit bir modifikasyonu, eğer Γ, Γ'deki her oyun belirlenecek şekilde yeterli bir nokta sınıfıysa , o zaman Γ'deki her gerçek kümesinin aşağıdakilere sahip olduğunu gösterir. Baire'nin mülkü.

Aslında bu sonuç optimal değildir; Açılmamış Banach-Mazur oyununu göz önünde bulundurarak, Γ'nin (yeterli kapatma özelliklerine sahip Γ için) belirleniminin, Γ'deki bir kümenin izdüşümü olan her gerçek kümesinin Baire özelliğine sahip olduğunu ima ettiğini gösterebiliriz . Örneğin, ölçülebilir bir kardinalin varlığı Π ¹ ₁ belirliliği ima eder , bu da sırayla her Σ ¹ ₂ gerçel kümesinin Baire özelliğine sahip olduğunu ima eder .

Diğer oyunları göz önünde bulundurarak, Π ¹ _n belirleniminin her Σ ¹ _{n +1} gerçel kümesinin Baire özelliğine sahip olduğunu, Lebesgue ile ölçülebilir (aslında evrensel olarak ölçülebilir ) ve mükemmel küme özelliğine sahip olduğunu ima ettiğini gösterebiliriz .

periyodiklik teoremleri

• İlk dönemsellik teoremi Her doğal sayı için, ima n ise, Δ ¹ _{2 n 1} belirlilik sonra, tutan Π ¹ _{2 n 1} ve Σ ¹ _{2 n 2} var prewellordering özelliği (ve bu Σ ¹ _{2 n 1} ve Π ¹ _{2 n 2} do not prewellordering özelliğine sahip değil, sahip ayırma özelliği ).
• İkinci teoremi periyodik Her doğal sayı için ifade eder, n , eğer Ô ¹ _{2 , n + 1} belirlilik tutar, ardından Π ¹ _{2 , n + 1} ve Σ ¹ _{2 N} olması ölçekli özelliği . Özellikle, yansıtmalı belirlenim geçerliyse, o zaman her yansıtmalı ilişkinin yansıtmalı bir tekbiçimliliği vardır .
• Üçüncü dönemsellik teoremi bir oyun tanımlanabilir kazanan stratejisi olması için yeterli bir koşul verir.

Belirli ikinci dereceden teorilerin karar verilebilirlik uygulamaları

1969 yılında, Michael O. Rabin kanıtladı ikinci dereceden teorisi ve n, ardılları olan Karar verilebilen . İspatın önemli bir bileşeni , Borel hiyerarşisinin üçüncü seviyesinde yer alan parite oyunlarının kararlılığının gösterilmesini gerektirir .

Wadge kararlılığı

Wadge belirlenimi , Baire uzayının alt kümelerinin tüm A , B çiftleri için Wadge oyunu G( A , B ) belirlendiğinin ifadesidir . Benzer şekilde, bir Γ, Γ nokta sınıfı için Wadge belirlenimi, Γ'deki tüm A , B kümeleri için Wadge oyunu G( A , B )'nin belirlendiği ifadesidir .

Wadge belirlenimi , Wadge düzeni için yarı doğrusal sıralama ilkesini ifade eder . Wadge belirleniminin bir başka sonucu da mükemmel küme özelliğidir .

Genel olarak, Wadge belirlenimi, Γ'deki Boolean küme kombinasyonlarının belirleniminin bir sonucudur. Olarak yansıtmalı hiyerarşi , Π ¹ ₁ Wadge belirlilik eşdeğerdir tt ¹ ₁ olarak kanıtlanmıştır belirlilik, Leo Harrington . Bu sonuç Hjorth tarafından Π ¹ ₂ Wadge belirleniminin (ve aslında Π ¹ ₂ için yarı-doğrusal sıralama ilkesinin ) zaten Π ¹ ₂ belirliliği ima ettiğini kanıtlamak için genişletildi .

Daha genel oyunlar

Oynanan nesnelerin doğal sayı olmadığı oyunlar

Sıralı tanımlanabilen hesaplaşma ve uzunluğu ile sıra sayısı oyunların belirlilik ω gerektirir ki, her düzenli kardinal için κ > ω hiçbir sıralı tanımlanabilen ayrık durağan alt kümeleri arasında var k cofinality w ait ordinals yapılmış. Belirlilik hipotezinin tutarlılık gücü bilinmemekle birlikte çok yüksek olması beklenmektedir.

Ağaçlarda oynanan oyunlar

uzun oyunlar

ω ₁ Woodin kardinallerinin varlığı, her sayılabilir sıra α için, α uzunluğundaki tamsayılar üzerindeki tüm oyunların ve projektif ödemenin belirlendiği anlamına gelir. Kabaca söylemek gerekirse, α Woodin kardinalleri, α uzunluğundaki gerçekler üzerinde oyunların belirlenmesine karşılık gelir (basit bir getiri seti ile). Woodin kardinallerinin κ limitinin o( κ )= κ ⁺⁺ ve ω Woodin kardinallerinin κ ' nin üzerinde olduğu varsayıldığında , oyunun uzunluğu oyun çizgisine göre kabul edilebilir olduğu anda ve projektif getiri ile sona erdiği değişken sayılabilir uzunluktaki oyunlardır. azimli. Belirli bir yinelenebilirlik varsayımının kanıtlanabilir olduğunu varsayarsak, ölçülebilir bir Woodin kardinalinin varlığı, ω ₁ uzunluğunda açık oyunların ve yansıtmalı ödemenin belirlendiğini ima eder . (Bu oyunlarda, ilk oyuncu için kazanma koşulu sayılabilir bir aşamada tetiklenir, bu nedenle getiri bir dizi gerçek olarak kodlanabilir.)

Woodin kardinallerinin bir Woodin limitine ve bunların üzerinde ölçülebilir bir değere göre, uzunluğu ω ₁ olan tamsayılar üzerindeki her oyunun ve sıralı tanımlanabilir getirinin belirlenmesi tutarlıdır . Belirlilik hipotezinin, Woodin kardinallerinin bir Woodin limiti ile eşit tutarda olduğu tahmin edilmektedir. ω ₁ , ω ₁ +ω uzunluğunda ve sıralı tanımlanabilir getiri tamsayılarında belirsiz oyunlar olduğu için maksimumdur .

Eksik bilgi oyunları

Eksik bilgi içeren herhangi bir ilginç oyunda , kazanan bir strateji karma bir strateji olacaktır : yani, aynı duruma farklı tepkiler verme olasılığı verecektir. Her iki oyuncunun da optimal stratejileri karma stratejilerse, oyunun sonucu kesinlikle belirleyici olamaz ( saf stratejilerde olduğu gibi , çünkü bunlar deterministiktir ). Ancak sonuçların karşıt karma stratejilere göre olasılık dağılımı hesaplanabilir. Karma stratejiler gerektiren bir oyun, belirli bir değeri aşan (olası karşı stratejiler üzerinde) minimum bir beklenen değer sağlayan bir stratejinin mevcut olması durumunda belirlenir . Bu tanıma karşı, tüm sonlu iki oyunculu sıfır toplamlı oyunlar açıkça belirlenir. Bununla birlikte, sonsuz kusurlu bilgi oyunlarının (Blackwell oyunları) belirlenimi daha az açıktır.

1969'da David Blackwell , bazı "kusurlu bilgi içeren sonsuz oyunların" (şimdi "Blackwell oyunları" olarak adlandırılır) belirlendiğini kanıtladı ve 1998'de Donald A. Martin , kalın bir nokta sınıfı için sıradan (mükemmel bilgi oyunu) belirliliğin Blackwell kararlılığını ima ettiğini kanıtladı . nokta sınıfı. Bu, Martin'in Borel belirlenim teoremi ile birleştiğinde, Borel getiri fonksiyonlarına sahip tüm Blackwell oyunlarının belirlendiği anlamına gelir. Martin, sonsuz oyunlar için sıradan belirlilik ve Blackwell belirliliğinin güçlü bir anlamda eşdeğer olduğunu tahmin etti (yani, kalın bir nokta sınıfı için Blackwell kararlılığının sırayla o nokta sınıfı için sıradan belirliliği ima ettiği), ancak 2010 itibariyle, Blackwell belirliliğinin ima ettiği kanıtlanmadı. mükemmel bilgi oyunu kararlılığı.

Quasistratejiler ve yarı-belirlilik

Ayrıca bakınız

• ω-otomat
• Çözülmüş oyun
• Kesinlikle belirlenmiş oyun
• topolojik oyun

Dipnotlar

1. ^ Bu varsayarbenkimin benzersiz eleman bir unsurdur a tek olmak oynanan mahallelerin kavşak almaya çalışıyorA. Bazı yazarlar bunun yerine oyuncuII'yihedef haline getirir; bu kullanım, yukarıdaki açıklamaların buna göre değiştirilmesini gerektirir.

Referanslar

• Gale, David ve Stewart, FM (1953). Kuhn, HW; Tucker, AW (ed.). Mükemmel bilgilerle sonsuz oyunlar . Oyun Teorisine Katkılar, Cilt II . Annals of Mathematics Studies 28. Princeton University Press. s. 245–266. ISBN'si 9780691079356.CS1 bakımı: birden çok ad: yazar listesi ( bağlantı )
• Harrington, Leo (Ocak 1978). "Analitik kararlılık ve 0#". Sembolik Mantık Dergisi . 43 (4): 685-693. doi : 10.2307/2273508 . JSTOR  2273508 .
• Hjorth, Greg (Ocak 1996). " Π ¹ ₂ Wadge derecesi" . Saf ve Uygulamalı Mantık Annals . 77 : 53-74. doi : 10.1016/0168-0072(95)00011-9 .
• Jech, Thomas (2002). Küme teorisi, üçüncü binyıl baskısı (gözden geçirilmiş ve genişletilmiş) . Springer. ISBN'si 978-3-540-44085-7.
• Martin, Donald A. (1975). "Borel kararlılığı". Matematik Annals . İkinci Seri. 102 (2): 363-371. doi : 10.2307/1971035 . JSTOR  1971035 .
• Martin, Donald A. ve John R. Steel (Ocak 1989). "Bir Projektif Kararlılık Kanıtı" . Amerikan Matematik Derneği Dergisi . 2 (1): 71–125. doi : 10.2307/1990913 . JSTOR  1990913 .
• Moschovakis, Yiannis N. (1980). Tanımlayıcı Küme Teorisi . Kuzey Hollanda. ISBN'si 978-0-444-70199-2.
• Woodin, W. Hugh (1988). "Süper kompakt kardinaller, gerçek kümeler ve zayıf homojen ağaçlar" . Amerika Birleşik Devletleri Ulusal Bilimler Akademisi Bildirileri . 85 (18): 6587-6591. Bibcode : 1988PNAS...85.6587W . doi : 10.1073/pnas.85.18.6587 . PMC  282022 . PMID  16593979 .
• Martin, Donald A. (2003). "Belirliliğin Lebesgue ölçülebilirliğini ima ettiğine dair basit bir kanıt". Parçala. Sem. Mat. Üniv. Pol. Torino . 61 (4): 393-399. ( PDF )
• Wolfe, P. (1955). "Bazı sonsuz oyunların katı belirliliği" . Pasifik J. Matematik . 5 (5): Ek I:841-847. doi : 10.2140/pjm.1955.5.841 .

Dış bağlantılar

• "Büyük Kardinaller ve durumlarının belirlenmesi" de Felsefe Stanford Encyclopedia