Wersja z 01:39, 8 lut 2019 edytuj Beno (dyskusja \| edycje) Redaktorzy, Administratorzy interfejsu, Administratorzy 133 325 edycji m WP:SK+Bn ← poprzednia edycja		Wersja z 21:23, 29 lip 2019 edytuj anuluj edycję Beno (dyskusja \| edycje) Redaktorzy, Administratorzy interfejsu, Administratorzy 133 325 edycji m WP:SK+Bn następna edycja →
Linia 6: == Definicje == === Gry długości ω o posunięciach z ustalonego zbioru === Niech <math>\mathcal X</math> będzie zbiorem o przynajmniej dwóch elementach oraz niech <math>A\subseteq {\mathcal X}^\omega</math> będzie zbiorem, którego elementy są [[ciąg (matematyka)\|ciągami]] nieskończonymi <math>\eta=\langle\eta(n)\colon n\in\omega\rangle</math> o wyrazach w <math>\mathcal X</math> (tzn. <math>\eta(n)\in {\mathcal X}</math> dla wszystkich liczb naturalnych <math>n\in\omega</math>). Określamy '''grę nieskończoną <math>\Game^{\mathcal X}(A)</math> dwóch graczy, I i II, na zbiór ''A'' o posunięciach ze zbioru <math>\mathcal X</math>''' jako proces, w wyniku którego dwie osoby konstruują ciąg nieskończony <math>\eta=\langle\eta(n)\colon n\in\omega\rangle\in {\mathcal X}^\omega</math> o wyrazach w <math>\mathcal X</math> w taki sposób, że po tym, jak już <math>\eta\upharpoonright n=\langle\eta(k)\colon k<n\rangle</math> zostało wybrane, to : jeśli <math>n</math> jest parzyste, to gracz I wybiera <math>\eta(n),</math> a : jeśli <math>n</math> jest nieparzyste, to gracz II wybiera <math>\eta(n).</math> Linia 12: Po wykonaniu wszystkich ω kroków, kiedy gracze zbudowali ciąg <math>\eta=\langle\eta(n)\colon n\in\omega\rangle\in {\mathcal X}^\omega,</math> powiemy, że ''gracz I wygrał partię η'', jeśli <math>\eta\in A.</math> '''Strategia dla gracza I''' to funkcja σ, której dziedziną jest zbiór wszystkich ciągów o parzystej długości i wyrazach w <math>\mathcal X</math> i której wartości są elementami zbioru <math>{\mathcal X};</math> tak więc <math>\sigma\colon \bigcup\limits_{k\in\omega} {\mathcal X}^{2k}\longrightarrow {\mathcal X}.</math> Powiemy, że ciąg <math>\eta\in {\mathcal X}^\omega</math> '''jest zgodny ze strategią σ''', jeśli <math>(\forall k\in\omega)(\eta(2k)=\sigma(\eta\upharpoonright 2k)).</math> Strategia σ dla gracza I jest '''strategią zwycięską gracza I w <math>\Game^{\mathcal X}(A)</math>''', jeśli każdy ciąg η zgodny z σ należy do zbioru ''A''. '''Strategia dla gracza II''' to funkcja τ, której dziedziną jest zbiór wszystkich ciągów o nieparzystej długości i wyrazach w <math>\mathcal X</math> i której wartości są elementami zbioru <math>\mathcal X</math>;, tak więc <math>\tau\colon \bigcup\limits_{k\in\omega} {\mathcal X}^{2k+1}\longrightarrow {\mathcal X}.</math> Powiemy, że ciąg <math>\eta\in {\mathcal X}^\omega</math> '''jest zgodny ze strategią τ''', jeśli <math>(\forall k\in\omega)(\eta(2k+1)=\tau(\eta\upharpoonright (2k+1))).</math> Strategia τ dla gracza II jest '''strategią zwycięską gracza II w <math>\Game^{\mathcal X}(A)</math>''', jeśli żaden ciąg η zgodny z τ nie należy do zbioru ''A''. Powiemy, że '''gra <math>\Game^{\mathcal X}(A)</math> jest zdeterminowana''', jeśli jeden z graczy ma strategię zwycięską. === Bardziej skomplikowane gry długości ω === Linia 26: * dla każdego ciągu <math>\nu\in {\mathcal T}</math> długości <math>\mathrm{lh}(\nu)=n</math> istnieje ciąg <math>\rho\in {\mathcal T}</math> długości <math>\mathrm{lh}(\rho)=n+1,</math> który wydłuża ν. Połóżmy <math>[{\mathcal T}]=\{\eta:\eta</math> jest ciągiem nieskończonym takim że <math>(\forall n\in \omega)(\eta\upharpoonright n\in {\mathcal T})\}.</math> Niech <math>A\subseteq [T].</math> Określamy '''grę nieskończoną <math>\Game_{\mathcal T}(A)</math> dwóch graczy, I i II, na zbiór ''A'' o posunięciach w drzewie <math>\mathcal T</math>''' jako proces w wyniku którego dwie osoby konstruują ciąg nieskończony <math>\eta\in [{\mathcal T}]</math> w taki sposób, że po tym jak już <math>\eta\upharpoonright n=\langle\eta(k)\colon k<n\rangle\in {\mathcal T}</math> zostało wybrane, to : jeśli <math>n</math> jest parzyste, to gracz I wybiera <math>\eta(n)</math> tak że <math>\langle\eta(k)\colon k\leqslant n\rangle\in {\mathcal T},</math> a : jeśli <math>n</math> jest nieparzyste, to gracz II wybiera <math>\eta(n)</math> tak aby <math>\langle\eta(k)\colon k\leqslant n\rangle\in {\mathcal T}.</math> Linia 37: Rozważa się również gry długości większej niż ω. W takim przypadku często wprowadza się dodatkowy parametr ''S'' opisujący, które posunięcia są wykonywane przez gracza I (pozostałe wybory są dokonywane przez gracza II). Niech α będzie nieskończoną liczbą porządkową oraz <math>S\subseteq\alpha.</math> Niech <math>\mathcal X</math> będzie zbiorem o przynajmniej dwóch elementach oraz niech <math>A\subseteq {\mathcal X}^\alpha.</math> Określamy '''grę długości α <math>\Game^{\mathcal ~~X}_~~X_\alpha(A)</math> dwóch graczy, I i II, na zbiór ''A'' o posunięciach ze zbioru <math>\mathcal X</math>''' jako proces, w wyniku którego dwie osoby konstruują pozaskończony ciąg <math>\eta=\langle\eta(\beta)\colon \beta<\alpha\rangle\in {\mathcal X}^\alpha</math> o wyrazach w <math>\mathcal X</math> w taki sposób, że po tym jak już <math>\eta\upharpoonright \beta=\langle\eta(\gamma)\colon \gamma<\beta\rangle</math> zostało wybrane, to: : jeśli <math>\beta\in S,</math> to gracz I wybiera <math>\eta(\beta),</math> a : jeśli <math>\beta\in\alpha\setminus S,</math> to gracz II wybiera <math>\eta(\beta).</math> Linia 70: === Gra Banacha-Mazura === Pierwsza gra nieskończona była opisana w [[1930]] przez polskiego matematyka [[Stanisław Mazur\|Stanisława Mazura]] w Problemie 43 w [[Księga ~~Szkocka~~szkocka\|Księdze Szkockiej]]. Niech <math>Z\subseteq {\mathbb R}.</math> Rozważmy następującą grę <math>\Game^\mathrm{BM}(Z)</math> dwóch graczy, których nazwiemy Graczem A i Graczem B. Gra składa się z nieskończenie wielu posunięć ponumerowanych liczbami naturalnymi <math>n=1,2,3,\dots.</math> Oponenci zaczynają w ten sposób, że Gracz A wybiera niepusty przedział otwarty <math>I_1,</math> a Gracz B odpowiada przez wskazanie niepustego otwartego przedziału <math>I_2\subseteq I_1.</math> Kiedy gracze dochodzą do <math>n</math>-tego kroku w grze, to mają skontruowany zstępujący ciąg niepustych przedziałów otwartych <math>I_1\supseteq I_2\supseteq \ldots I_{2n-2}\supseteq I_{2n-1}.</math> Na <math>n</math> tym etapie gry najpierw Gracz A wybiera niepusty przedział otwarty <math>I_{2n}\subseteq I_{2n-1},</math> a potem Gracz B wskazuje niepusty otwarty przedział <math>I_{2n+1}\subseteq I_{2n}.</math> Kiedy gracze wykonają już wszystkie posunięcia (jest ich nieskończenie wiele!), to decydujemy, że Gracz B wygrał partię <math>\langle I_n\colon n=1,2,3,4,\dots\rangle</math> wtedy i tylko wtedy, gdy <math>\bigcap\limits_{n=1}^\infty I_n\subseteq Z.</math> Linia 85: === Strategiczna domkniętość === Niech <math>{\mathbb P}=({\mathbb P},\leqslant)</math> będzie [[pojęcie forsingu\|pojęciem forsingu]] oraz niech λ będzie regularną [[moc zbioru\|liczbą kardynalną]]. Definiujemy następującą grę <math>\Game_\lambda^{\mathbb P}</math> długości λ pomiędzy graczami I i II. W czasie gry gracze budują ciąg <math>\langle p_\alpha,q_\alpha\colon \alpha<\lambda\rangle\subseteq {\mathbb P}</math> tak, że na kroku <math>\alpha<\lambda{:}</math> : najpierw gracz I wybiera warunek <math>p_\alpha\in {\mathbb P}</math> taki że :: jeśli ciąg <math>\langle p_\beta,q_\beta\colon \beta<\alpha\rangle</math> ma ograniczenie dolne, to <math>(\forall\beta<\alpha)(p_\beta\~~geq~~geqslant p_\alpha\ \wedge q_\beta\~~geq~~geqslant p_\alpha),</math> : a potem gracz II wybiera warunek <math>q_\alpha\leqslant p_\alpha.</math> Po skończonej partii, gdy gracze skonstruowali ciąg <math>\langle p_\alpha,q_\alpha\colon \alpha<\lambda\rangle</math> decydujemy, że gracz II wygrał tę partię wtedy i tylko wtedy, gdy ciąg ten jest malejący (tzn. gdy <math>(\forall\beta<\alpha<\lambda)(p_\beta\~~geq~~geqslant q_\beta\~~geq~~geqslant p_\alpha\~~geq~~geqslant q_\alpha)</math>). Mówimy, że pojęcie forsingu <math>\mathbb P</math> jest ''<math>(<\lambda)</math>-strategicznie domknięte'', jeśli gracz II ma strategię zwycięską w grze <math>\Game_\lambda^{\mathbb P}.</math> Ta własność pojęć forsingu jest dość ważna w teorii [[forsing]]u, jako że * <math>(<\lambda)</math>-strategicznie domknięte pojęcia forsingu nie kolapsują liczb kardynalnych <math>\leqslant\lambda</math> oraz * iteracje z nośnikami mocy λ<math>\lambda</math> pojęć forsingu, które są <math>(<\lambda)</math>-strategicznie domknięte są <math>(<\lambda)</math>-strategicznie domknięte. == Determinacja == Linia 101: Aksjomaty determinacji były rozważane po raz pierwszy przez polskich matematyków [[Jan Mycielski (matematyk)\|Jana Mycielskiego]] i [[Hugo Steinhaus\|Hugo Steinhuasa]]<ref>Mycielski, Jan; Steinhaus, H.: ''A mathematical axiom contradicting the axiom of choice''. „Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys.” 10 (1962), s. 1–3.</ref> i były one intensywnie studiowane na początku [[lata 60. XX wieku\|lat 60. XX wieku]] przez Mycielskiego i Stanisława Świerczkowskiego<ref>Mycielski, Jan i Świerczkowski, Stanisław: ''On the Lebesgue measurability and the axiom of determinateness''. „[[Fundamenta Mathematicae]]”. 54 (1964), s. 67–71.</ref><ref>Mycielski, Jan: ''On the axiom of determinateness''. „Fundamenta Mathematicae” 53 (1963/1964), s. 205–224.</ref><ref>Mycielski, Jan: ''On the axiom of determinateness. II''. „Fundamenta Mathematicae” 59 (1966), s. 203–212.</ref>. W latach [[lata 90. XX wieku\|90. XX wieku]] w wyniku szeregu spektakularnych rezultatów amerykańskiego matematyka [[W. Hugh Woodin\|Hugh Woodina]] znacznie wzrosło zainteresowanie aksjomatami tego typu<ref>Woodin, W. Hugh: ''The axiom of determinacy, forcing axioms, and the nonstationary ideal.'' „de Gruyter Series in Logic and its Applications”, 1. Walter de Gruyter & Co., Berlin, 1999. {{ISBN\|3-11-015708-X}}.</ref>. Dla głębszego rozwinięcia tego tematu odsyłamy czytelnika do hasła o [[Aksjomat determinacji\|aksjomatach determinacji]]. Zauważmy tylko jeszcze, że jeśli <math>A\subseteq \omega^\omega</math> jest [[zbiór borelowski\|zbiorem borelowskim]], to gra <math>\Game^\omega(A)</math> jest zdeterminowana<ref>Martin, Donald A.: ''Borel determinacy.'' „Ann. of Math.” (2) 102 (1975), nr 2, s. 363–371.</ref>. Jeśli istnieje [[liczba mierzalna]] oraz <math>A\subseteq \omega^\omega</math> jest [[zbiór analityczny\|zbiorem analitycznym]], to gra <math>\Game^\omega(A)</math> jest zdeterminowana<ref>Martin, Donald A.: ''Measurable cardinals and analytic games''. „Fund. Math.” 66 (1969/1970), s. 287–291.</ref>. Przy założeniu istnienia znacznie większych [[Duże liczby kardynalne\|dużych liczb kardynalnych]] można wykazać, że gry na zbiory z wyższych [[zbiór rzutowy\|klas rzutowych]] też są zdeterminowane<ref>Woodin, W. Hugh: ''Supercompact cardinals, sets of reals, and weakly homogeneous trees.'' „Proc. Nat. Acad. Sci. U.S.A.” 85 (1988), s. 6587–6591.</ref><ref>Martin, Donald A., Steel, John R.: ''A proof of projective determinacy''. „J. Amer. Math. Soc.” 2 (1989), s. 1, ~~71-125~~71–125.</ref>. == Zobacz też ==

Gry nieskończone: Różnice pomiędzy wersjami