Teoria PCF

Teoria PCF (od ang. possible cofinalities), teoria możliwych współkońcowości – dział teorii mnogości związany z arytmetyką liczb kardynalnych. Jednym z centralnych obiektów rozważanych w tej teorii jest zbiór współkońcowości pewnych zredukowanych porządków produktowych.

Stworzył ją izraelski matematyk Saharon Shelah w latach 80. XX wieku i do dziś jest ona rozwijana, głównie przez niego. Wyniki tej teorii demonstrują, że – mimo dużej kolekcji twierdzeń niezależnościowych w arytmetyce liczb kardynalnych – wciąż można dowieść wielu własności na gruncie aksjomatyki Zermela-Fraenkla (ZFC), o ile zadaje się właściwe pytania. Z teorii możliwych współkońcowości można także wywnioskować nowe prawa klasycznej arytmetyki liczb kardynalnych.

Rys historyczny

W 1970 roku, rozwijając metodę forsingu, William Easton udowodnił następujące twierdzenie. Przypuśćmy, że F jest rosnącą funkcją określoną na wszystkich regularnych liczbach kardynalnych, której wartościami są nieskończone liczby kardynalne i taką, że $\kappa <\mathrm {cf} (\mathbf {F} (\kappa ))$ dla wszystkich regularnych $\kappa .$ Wówczas jest niesprzecznym z ZFC, że $2^{\kappa }=\mathbf {F} (\kappa )$ dla wszystkich regularnych liczb kardynalnych $\kappa .$
Twierdzenie Eastona przesunęło środek ciężkości badań w arytmetyce kardynalnej w kierunku hipotezy liczb singularnych (SCH) i jej naruszeń. SCH to zdanie stwierdzające, że dla każdej nieskończonej liczby kardynalnej $\kappa ,$ jeśli $2^{\mathrm {cf} (\kappa )}<\kappa$ to $\kappa ^{\mathrm {cf} (\kappa )}=\kappa ^{+}$ . Przy założeniu SCH, potęgi liczb kardynalnych są wyznaczone przez funkcję $\kappa \mapsto 2^{\kappa }$ dla liczb regularnych. Z naruszenia SCH można znaleźć pewne duże liczby kardynalne, ale też z dużych liczb można wywnioskować niesprzeczność ¬SCH.
Z wyników Karola Prikrego i Jacka Silvera wynika, że jeśli istnieje liczba superzwarta, to istnieje pojęcie forsingu, które forsuje, że dla pewnej silnie granicznej singularnej liczby kardynalnej $\kappa$ mamy $\kappa ^{+}<2^{\kappa }.$ Wielu matematyków zaczęło w latach 70. XX wieku sądzić, że w arytmetyce liczb kardynalnych wszystkie twierdzenia ZFC są już odkryte i wszystko, co nie jest przez te stwierdzenia zdeterminowane, jest niezależne od ZFC (być może, zakładając istnienie odpowiednio dużych liczb kardynalnych).
W 1978 Shelah opublikował pracę, w której użył nowatorskich metod do budowy pewnych algebr mocy $\aleph _{\omega +1}$ . Metody te były zwiastunem nowej teorii: teorii PCF. W kolejnych latach Shelah systematycznie prowadził badania w tym kierunku, z czasem wykazując, że ciągle jeszcze istnieją nieodkryte (i zdumiewające) twierdzenia ZFC.
W 1994 Shelah opublikował systematyczny i kompleksowy wykład teorii PCF.
Czytelnik nieprzyzwyczajony do bardzo trudnego stylu publikacji Shelaha, a zainteresowany głębszym zrozumieniem tej teorii, może więcej skorzystać z przeglądowego artykułu Maxa Burkego i Menachema Magidora lub monografii M. Holza, K. Steffensa i E. Weitza. Bardzo godnym polecenia jest też artykuł przeglądowy Uriego Abrahama i Menachema Magidora.

Podstawowe pojęcia

Pojęcia wstępne

Przypuśćmy, że $(\mathbb {P} ,\sqsubseteq )$ jest praporządkiem. Definiujemy współkońcowość $\mathrm {cf} (\mathbb {P} )$ praporządku $\mathbb {P}$ jako

\mathrm {cf} (\mathbb {P} )=\min\{|A|:A\subseteq \mathbb {P} \ \wedge \ (\forall p\in \mathbb {P} )(\exists a\in A)(p\sqsubseteq a)\}.

Przypuśćmy, że $S$ jest niepustym zbiorem i dla $s\in S$ mamy daną liczbę porządkową $\delta _{s}\in \mathbf {ON} .$ Dalej przypuśćmy, że $I$ jest ideałem podzbiorów zbioru $S.$ Definiujemy praporządek $\leqslant _{I}$ na $\prod \limits _{s\in S}\delta _{s}$ przez

f\leqslant _{I}g

wtedy i tylko wtedy gdy

\{s\in S:f(s)>g(s)\}\in I.

Wybrane definicje z teorii PCF

Dla liczb kardynalnych $\kappa \geqslant \lambda \geqslant \mu$ określamy współczynnik pokryciowy $\mathrm {cov} (\kappa ,\lambda ,\mu )$ jako najmniejszą możliwą moc rodziny ${\mathcal {A}}\subseteq [\kappa ]^{<\lambda }$ (czyli elementy rodziny ${\mathcal {A}}$ są podzbiorami zbioru $\kappa$ mocy mniejszej niż $\lambda$ ) takiej, że

(\forall B\in [\kappa ]^{<\mu })(\exists A\in {\mathcal {A}})(B\subseteq A).

Niech ${\mathfrak {a}}$ będzie niepustym zbiorem regularnych liczb kardynalnych. Określamy:

$\prod {\mathfrak {a}}=\prod _{\kappa \in {\mathfrak {a}}}\kappa$ jest zbiorem wszystkich takich funkcji $f:{\mathfrak {a}}\longrightarrow \mathbf {ON} ,$ że $(\forall \kappa \in {\mathfrak {a}})(f(\kappa )<\kappa );$
jeśli $I$ jest ideałem na ${\mathfrak {a}},$ to $\prod {\mathfrak {a}}/I$ oznacza porządek częściowy otrzymany w kanoniczny sposób z praporządku $\leqslant _{I}$ na $\prod {\mathfrak {a}};$
$\mathrm {pcf} ({\mathfrak {a}})=\{\mathrm {cf} \left(\prod {\mathfrak {a}}/I\right):I$ jest ideałem maksymalnym na ${\mathfrak {a}}\}.$

Niech $\lambda$ będzie singularną liczbą kardynalną. Zdefiniujmy zbiór $P^{\lambda }$ jako

\{\mathrm {cf} \left(\prod {\mathfrak {a}}/I\right):{\mathfrak {a}}\subseteq \lambda

jest zbiorem liczb regularnych,

\sup({\mathfrak {a}})=\lambda ,

|{\mathfrak {a}}|=\mathrm {cf} (\lambda )

oraz

I

jest maksymalnym ideałem na

{\mathfrak {a}}

zawierającym wszystkie ograniczone podzbiory

{\mathfrak {a}}\}.

Kładziemy

\mathrm {pp} (\lambda )=\sup(P^{\lambda }).

Przykładowe twierdzenia teorii PCF

Przypuśćmy, że $\delta$ jest graniczną liczbą porządkową oraz że $\delta <\aleph _{\delta }$ (czyli $\delta$ nie jest punktem stałym skali alefów). Wówczas $\mathrm {cov} (\aleph _{\delta },|\delta |^{+},\mathrm {cf} (\delta )^{+})<\aleph _{(|\delta |^{\mathrm {cf} (\delta )})^{+}}$ a stąd $\aleph _{\delta }^{\mathrm {cf} (\delta )}<\aleph _{(|\delta |^{\mathrm {cf} (\delta )})^{+}}.$

Na przykład

\aleph _{\omega }^{\aleph _{0}}<\aleph _{{\mathfrak {c}}^{+}}

(gdzie

{\mathfrak {c}}=2^{\aleph _{0}}

).

Jeśli ${\mathfrak {a}}$ ${\mathfrak {a}}$ jest przedziałem liczb regularnych i $|{\mathfrak {a}}|<\min({\mathfrak {a}}),$ $|{\mathfrak {a}}|<\min({\mathfrak {a}}),$ to $\mathrm {pcf} ({\mathfrak {a}})$ $\mathrm {pcf} ({\mathfrak {a}})$ jest również przedziałem liczb regularnych, który zawiera element największy oraz $\left|\mathrm {pcf} ({\mathfrak {a}})\right|\leqslant |{\mathfrak {a}}|^{+++}$ $\left|\mathrm {pcf} ({\mathfrak {a}})\right|\leqslant |{\mathfrak {a}}|^{+++}$ i też $\left|\mathrm {pcf} ({\mathfrak {a}})\right|\leqslant 2^{|{\mathfrak {a}}|}$ $\left|\mathrm {pcf} ({\mathfrak {a}})\right|\leqslant 2^{|{\mathfrak {a}}|}$
- Hipoteza PCF mówi, że nawet $\left|\mathrm {pcf} ({\mathfrak {a}})\right|\leqslant {|{\mathfrak {a}}|}$ jeśli ${\mathfrak {a}}$ jest przedziałem liczb regularnych i $\sup {\mathfrak {a}}=\delta <\aleph _{\delta }.$
Jeśli $\kappa$ jest nieskończoną liczbą kardynalną, $\lambda =\kappa ^{+\alpha },$ $1\leqslant \alpha <\kappa ,$ to $\mathrm {cf} \left([\lambda ]^{\leqslant \kappa },\subseteq \right)=\max \left(\mathrm {pcf} (\{\kappa ^{+(\beta +1)}:\beta <\alpha \})\right).$
Z powyższych wyników możemy wywnioskować np. że:

(a) jeśli

\delta <\aleph _{\delta }

gdzie

\delta

jest graniczną liczbą porządkową, to

\mathrm {cf} \left([\aleph _{\delta }]^{|\delta |},\subseteq \right)<\aleph _{|\delta |^{+4}},

(b) jeśli

|\delta |^{\mathrm {cf} (\delta )}<\aleph _{\delta }

gdzie

\delta

jest graniczną liczbą porządkową, to

\aleph _{\delta }^{\mathrm {cf} (\delta )}<\aleph _{|\delta |^{+4}}.

W szczególności, jeśli

2^{\aleph _{0}}<\aleph _{\omega },

to

\aleph _{\omega }^{\aleph _{0}}<\aleph _{\omega _{4}}.

Jeśli hipoteza PCF jest prawdziwa, to nawet

\aleph _{\omega }^{\aleph _{0}}<\aleph _{\omega _{1}}.

Jeśli $\aleph _{1}\leqslant \mathrm {cf} (\kappa )<\kappa$ oraz zbiór ${\displaystyle \{\lambda <\kappa$ jest stacjonarny w $\kappa ,$ to $\mathrm {pp} (\kappa )=\kappa ^{+}.$

Powszechnie znaną (choć niekoniecznie popieraną) tezą Shelaha jest, że jeśli zinterpretujemy właściwie pierwszy problem Hilberta (używając podejścia motywowanego przez teorię PCF), to ma on odpowiedź pozytywną. Podstawą do tej tezy jest następujące twierdzenie, nazywane revised GCH.

Dla liczb kardynalnych

\lambda ,\kappa

określamy

\lambda ^{[\kappa ]}=\min\{|{\mathcal {P}}|:{\mathcal {P}}\subseteq [\lambda ]^{\leqslant \kappa }

oraz dla każdego zbioru

A\subseteq \lambda

mocy

\kappa

można znaleźć zbiór

{\mathcal {A}}\subseteq {\mathcal {P}}

taki że

|{\mathcal {A}}|<\kappa

oraz

A=\bigcup {\mathcal {A}}\}.

Revised GCH: Jeśli $\mu$ jest silnie graniczną liczbą nieprzeliczalną, to dla każdej liczby kardynalnej $\lambda \geqslant \mu$ można znaleźć $\kappa _{0}<\mu$ takie, że

\kappa _{0}<\kappa <\mu

implikuje

\lambda ^{[\kappa ]}=\lambda .

Przypisy

↑ Easton, William B.: Powers of regular cardinals. „Ann. Math. Logic” 1 (1970), s. 139–178.
↑ Prikry, Karel L.: Changing measurable into accessible cardinals. „Dissertationes Math. / Rozprawy Mat.” 68 (1970).
↑ Shelah, Saharon: Jonsson algebras in successor cardinals. „Israel J. Math.” 30 (1978), s. 57–64.
↑ Shelah, Saharon: Cardinal arithmetic. „Oxford Logic Guides”, 29. Oxford Science Publications. The Clarendon Press, Oxford University Press, New York, 1994. ISBN 0-19-853785-9.
↑ Burke, Maxim R.; Magidor, Menachem: Shelah’s pcf theory and its applications. „Ann. Pure Appl. Logic” 50 (1990), s. 207–254.
↑ Holz, M.; Steffens, K.; Weitz, E.: Introduction to cardinal arithmetic. „Birkhäuser Advanced Texts: Basler Lehrbücher”. Birkhäuser Verlag, Basel, 1999. ISBN 3-7643-6124-7.
↑ Abraham, Uri; Magidor, Menachem: Cardinal Arithmetic, w: Handbook of Set Theory pod red. M. Foremana, A. Kanamoriego i M. Magidora, w druku. Dostępne w formacie dvi na stronach pierwszego autora.
↑ Shelah, Saharon: The generalized continuum hypothesis revisited. „Israel J. Math.” 116 (2000), s. 285–321.

[1] Easton, William B.: Powers of regular cardinals. „Ann. Math. Logic” 1 (1970), s. 139–178.

[2] Prikry, Karel L.: Changing measurable into accessible cardinals. „Dissertationes Math. / Rozprawy Mat.” 68 (1970).

[3] Shelah, Saharon: Jonsson algebras in successor cardinals. „Israel J. Math.” 30 (1978), s. 57–64.

[4] Shelah, Saharon: Cardinal arithmetic. „Oxford Logic Guides”, 29. Oxford Science Publications. The Clarendon Press, Oxford University Press, New York, 1994. ISBN 0-19-853785-9.

[5] Burke, Maxim R.; Magidor, Menachem: Shelah’s pcf theory and its applications. „Ann. Pure Appl. Logic” 50 (1990), s. 207–254.

[6] Holz, M.; Steffens, K.; Weitz, E.: Introduction to cardinal arithmetic. „Birkhäuser Advanced Texts: Basler Lehrbücher”. Birkhäuser Verlag, Basel, 1999. ISBN 3-7643-6124-7.

[7] Abraham, Uri; Magidor, Menachem: Cardinal Arithmetic, w: Handbook of Set Theory pod red. M. Foremana, A. Kanamoriego i M. Magidora, w druku. Dostępne w formacie dvi na stronach pierwszego autora.

[8] Shelah, Saharon: The generalized continuum hypothesis revisited. „Israel J. Math.” 116 (2000), s. 285–321.

logika matematyczna	algebraiczna(inne języki) mereologia rachunek zdań teoria dowodu teoria modeli teoria rekursji teoria typów
metamatematyka	metalogika
teoria mnogości	opisowa algebra zbiorów arytmetyka liczb kardynalnych arytmetyka liczb porządkowych teoria PCF
teoria obliczeń	teoria obliczalności teoria złożoności
inne	teoria kategorii filozofia matematyki