Kiegészítés a halmazelméleti anyaghoz

Definíció T egy Aronszajn-fa, ha ω_{1} magas, minden szintje megszámlálható és nincs benne ω_{1} hosszú ág.

Tétel Létezik Aronszajn-fa.

Biz. A fát indukcióval építjük fel. A fa minden csúcsába egy racionális számot írunk úgy, hogy egy ágon felfelé menve ezek a számok nőjenek. Ezzel garantáljuk azt, hogy a fában nincs ω_{1} hosszú ág, hiszen az ág minden csúcsához más racionális számot írtunk.

A fa “emeleteit” egyeséve építjük fel. Tegyük fel, hogy a fa már az α-adik szintig elkészült és most akarjuk az α-adik szintet rátenni. Feltesszük még, hogy a fa az alábbi feltételeket is teljesíti:

(i) Minden eddigi szint megszámlálható, tehát az egész fa is megszámlálható. (ii) Minden csúcshoz egy racionális számot írtuk úgy, hogy ha c-hez írt szám q, akkor a c

fölötti csúcsokhoz q-nál nagyobb számokat írtunk. (iii) Ha a c csúcs a β-adik szinten van és hozzá a q számot írtuk, akkor minden β < γ < α

szintre és q < r racionális számra a c csúcsból fel tudunk menni a γ-adik szinten egy olyan d csúcsba, ahová r-et írtunk. Ha most α rákövetkező, vagyis az eddig megkonstruált fának van “teteje”, akkor

a legfelső szinten minden csúcsra ráteszünk megszámlálható sok új csúcsot, és azokat a csúcshoz írt racionális számnál nagyobb racionális számokkal megcimkézzük. Ezzel a fenti indukciós feltételek továbbra is teljesülnek.

Ha pedig α limesz, akkor vegyük sorra az eddig elkészített fa összes csúcsát. Mondjuk ez a csúcs c és a hozzá írt szám q. Most vegyünk az összes lehetséges módon egy q-nál nagyobb r racionális számot. c fölött az α-adik emeleten teszünk egy csúcsot, amihez az r számot írjuk. Ezt megtehetjük, mert válasszunk egy q-nál nagyobb racionális számokból álló, szigorúan növő és r-hez tartó r_{n} sorozatot, valamint egy α-hoz tartó α_{n} rendszámsorozatot. Válasszunk c fölött az α_{1} szinten olyan csúcsot, amihez írt szám r_{1} (az indukciós feltevés szerint ilyen van). Majd c_{1} fölött az α_{2}-edik szinten olyan c_{2} csúcsot, amihez írt szám r_{2}, stb. Végül a c, c_{1}, …, csúcsok által meghatározott ág tetejére tegyünk fel az α-adik szinten egy pontot.

Mivel az α-adik szint alatt megszámlálható sok csúcs volt, és minden csúcshoz megszámlálható sok másikat rendeltünk az α-adik szinten, azért az α-adik szintre is megszámlálható sok csúcs került. A többi indukciós feltétel is nyilván teljesül.

Definíció A λ számosság gyengén kompakt ha λ → (λ)_{2}^{2}.

Állítás Ha λ gyengén kompakt, akkor erősen elérhetetlen.

Biz. Ha cf(λ) = μ < λ, akkor legyen λ = ∑_{ξ<μ} λ_{x}i, ahol λ_{x}i < λ. Legyen α és β szine 0 ha ugyanabba az intervallumba esnek, és 1 ha különbözőbe. Minden 0 színben homogén halmaz számossága λ_{ξ}, és minden 1 színben homogén halmaz számossága μ.

Ha κ < λ és 2^{κ} ≥ λ, akkor 2^{κ} ↛ (κ^{+})_{2}^{2} miatt 2^{κ} párjait, és így λ párjait is lehet úgy színezni, hogy ne legyen benne κ-s homogén, és így λ-s homogén sem lehet.

Állítás Ha λ gyengén kompakt, akkor nincs κ-Aronszajn fa.

Biz. Legyen T egy ellenpélda, azaz T egy λ magas fa amiben minden szint λ-nál kisebb, és nincs benne végig ág. Rendezzük a fa csúcsait minden szinten tetszőlegesen, továbbá definiáljunk a T fa teljes ágain egy rendezést a következőképpen: ha a b és c ágak az α-adik szinten válnak el, akkor b kisebb mint c ha az α +1-edik szinten levő pontjaik közül az ezen a szinten érvényes rendezés szerint a b-hez tartozó csúcs a kisebb. (Ezt hívják a fa préselésének – squash.) Mivel T -nek λ teljes ága van, így kapunk egy λ számosságú halmazon egy teljes rendezést, amiben nincs sem λ-s növő, sem λ-s csökkenő sorozat.

Tegyük fel ugyanis, hogy b_{α} mondjuk egy λ-s növő, ebből definiálunk egy λ hosszú ágat T -ben. Tegyük fel hogy már definiáltuk T -beli csúcsok egy növő c_{ξ} sorozatát úgy, hogy minden ξ-hez van olyan β_{ξ}, hogy α > β_{ξ} esetén a b_{α} ág átmegy c_{ξ}-n. Most a ξ + 1edik szinten λ-nál kevesebb csúcs van, és a β_{ξ}-nél nagyobb indexű ágak erre a szintre eső pontjai egy (nem feltétlenül monoton) sorozatot határoznak meg. A sorozatnak kell maximális elemének lennie, egyébként egy λ-val kofinális részt adnának (pedig λ reguláris). A maximális elemen az ágak közül egy végszelet megy át. Ha pedig ξ limesz, akkor a korábbi {c_{η} : η < ξ} csúcsokhoz tartozó β_{η} indexek szuprémumával mondhatjuk el a fenti gondolatmenetet.

Másrészt megmutatjuk, hogy minden λ-s rendezésben van vagy λ-s növő vagy λ-s csökkenő. Legyen ez a rendezés <, és legyen ≻ az alaphalmaz egy jólrendezése. Legyen az (α, β) pár színe 0 ha a kétféle rendezésben ugyanúgy vannak rendezve, és 1 egyébként. Egy λ-s homogén a < rendezésben vagy egy λ-s csökkenő (ha 1 színű) vagy egy λ-s növő (ha az 0 színű) részt ad meg.

Állítás Legyen λ > ω reguláris és n ∈ ω-ra f_{n} olyan függvények, melyek λ véges részeihez rendelnek λ-beli elemet. Ekkor van olyan C ⊂ λ kof. zárt, hogy minden α ∈ C zárt az összes f_{n} függvényre.

Biz. Álljon C ⊂ λ az összes olyan α < λ rendszámból, ami zárt az összes f_{n} függvényre. Először is C zárt. Valóban, ha c_{ξ} egy növő C-beli elemekből álló sorozat és limesze c < λ, akkor a c is zárt az összes f_{n}-re. Ha kiveszünk véges sok c-nél kisebb argumentumot, akkor azok már valamennyien egy c_{ξ}-nél is kisebbek, tehát az ezen a helyen felvett f_{n} értékek is kisebbek c_{ξ}-nél, tehát c-nél is.

Másrészt C kofinális. Ha adott α_{0}, akkor nézzük az összes f_{n} értékét az α_{0}-nál kisebb helyeken. Ezekből λ-nál kevesebb van, λ reguláris, ezért a függvényértékek korlátosak, mondjuk mind kisebb mint α_{1}. Most ha az argumentumokat csak α_{1} alatt vesszük, a függvényértékek minden α_{2} alatt maradnak, stb. Végül legyen α az α_{i} sorozat limesze, ez zárt mindegyik f_{n}-re.

Definíció Az S ⊂ λ halmaz nem tükröző, ha S stacionárius, de minden α < λ limesz rendszámra S ∩ α nem stacionárius.

Tétel (Stevo Todorčevič, 1984) Tegyük fel, hogy λ > ω reguláris és van S ⊂ λ nem tükröző halmaz. Ekkor λ ↛ (λ)_{λ}^{2}.

Biz. Feltehetjük, hogy 0 ∉ S. Minden α < λ limesz rendszámhoz a feltétel szerint van olyan C_{α} (α-ban) kofinális zárt halmaz, hogy C_{α} ∩ S = ∅. Ezek segítségével definiáljuk minden α < β < λ-ra a β-ból α-ba menő sétát a kövektezőképpen.

Definíció A séta kezdőpontja β_{0} = β, és tegyük fel, hogy már eljutottunk az α < β_{i} pontba. Ha

• Ha β_{i} rákövetkező, akkor lépünk a közvetlenül megelőző rendszámba; ilyenkor a séta bal oldali eleme a 0.

• Ha β_{i} limesz, akkor ugrunk. Ha α ∈ C_{β_{i}}, akkor a séta következő és egyben utolsó eleme α. Ha nem, akkor megkeressük a C_{β_{i}} (kof. zárt) sorozatban azt az intervallumot, amely α-t tartalmazza. Ennek jobb oldali vége lesz β_{i+1}, bal oldali vége pedig a “bal oldali” elem.

Egy β-ból induló séta szigorúan csökkenő rendszámokon megy át, mindig α fölött marad, és csak α-ban fejeződik be. Mivel rendszámoknak nincs végtelen csökkenő sorozata, azért minden séta véges. A séta hossza az a természetes szám, ami megmondja, hogy hányadik lépésben érünk β-ból α-ba.

Most a séta néhány elemi tulajdonságát soroljuk fel.

Állítás Ha ξ ∈ S, akkor egy séta folyamán ξ-be csak lépéssel ξ + 1-ből juthatunk el.

Biz. Valóban, hiszen ekkor ξ ∉ C_{β_{i}}.

Állítás Ha az β-ból α-ba való séta első n lépésénél a bal oldalak b_{0}, …, b_{n−1}, továbbá ε kisebb mint α de nagyobb mint az összes b_{i}, akkor β-ból ε-ba való séta első n lépése ugyanaz.

Biz. Definíció szerint ilyenkor α és ε a C_{β_{i}} sorozatnak mindig ugyanabba az intervallumába esik.

Állítás Legyen ε < α és nagyobb, mint az β-ból α-ba való séta bal oldalainak maximuma. Ha még α ∉ S, akkor β-ból ε-be menő séta átmegy α-n is.

Biz. Az előzőek szerint a β → ε séta α előtt megegyzik a β → α sétával. Láttuk, hogy α-ba csak lépni lehet, tehát a β → α séta utolsó előtti pontja α + 1, ezért a β → ε sétának is pontja α + 1.

Ezek után definiáljuk a d : [λ]^{2} → λ szinezést, ami mutatni fogja, hogy λ ↛ (λ)_{λ}^{2}, azaz λ-nak nincs λ számosságú homogén része. Ennél erősebbet igazolunk: λ-nak minden λ számosságú A részhalmazában minden szinnek elő kell fordulnia.

Legyen tehát β′ < β két λ-nál kisebb rendszám, meg akarjuk tudni, mi lesz ennek a párnak a színe. Solovay tétele értelmében az S stacionárius halmaz felbomlik λ darab diszjunkt S_{ξ} stacionárius halmaz uniójára, ezt a felbontást rögzítjük.

Tekintsük a β-ból β′-be menő sétát, legyen α ennek egy (közbülső), mondjuk k-adik eleme. Most α jó, ha a séta első k − 1 bal oldali elemének maximumát ε-nal jelölve a β-ból ε-ba menő séta első k − 1 bal oldali eleme és a β′-ből ε-ba menő séta első k − 1 bal oldali eleme megegyezik (persze ez megegyezik a β-ból β′-be menő séta első k −1 bal oldali elemével).

Ha a sétának nincs jó eleme, akkor legyen a (β′, β) pár színe 0. Ha van jó eleme, akkor nézzük a sétában legutolsó (azaz legkisebb) jó elemet, legyen ez α. Ha α ∈ S_{ξ} valamilyen ξ < λ értékkel, akkor legyen d(β′, β) = ξ, egyébként (azaz ha α ∉ S) legyen ismét d(β′, β) = 0.

Legyen tehát A ⊂ λ egy λ számosságú halmaz és ξ ∈ λ adott, keresnünk kell A-ban két β′ és β elemeket, melyek színe éppen ξ. Ehhez definiálunk két tulajdonságot.

Definíció Azt mondjuk, hogy az ⟨c_{1}, …, c_{n}, y, x⟩ rendezett (n + 2)-es Φ tulajdonságú, ha x eleme A-nak, az x-ből y-ba menő séta pontosan n hosszú, és a séta bal oldali elemei rendre c_{1}, …, c_{n}. Azt mondjuk, hogy a ⟨c_{1}, …, c_{n}, y⟩ rendezett (n + 1)-es Ψ tulajdonságú, ha a λ-nak az {x ∈ λ : Φ(c_{1}, …, c_{n}, y, x)} részhalmaza nem korlátos λ-ban.

Definiálunk még négy függvényt is:

f(c_{1}, …, c_{n}, y, γ) = \{ \begin{matrix}min\{x ∈ A : x > γ és Φ(c_{1}, …, c_{n}, y, x)\} & ha van ilyen x \\ 0 & egyébként \end{matrix}
f^{∗}(c_{1}, …, c_{n}, y) = \{ \begin{matrix}sup\{x ∈ A : x > y és Φ(c_{1}, …, c_{n}, y, x)\} & ha ez korlátos λ-ban \\ 0 & egyébként \end{matrix}
g(c_{1}, …, c_{n}, γ) = \{ \begin{matrix}min\{y ∈ λ : y > γ és Ψ(c_{1}, …, c_{n}, y)\} & ha van ilyen y \\ 0 & egyébként \end{matrix}
g^{∗}(c_{1}, …, c_{n}) = \{ \begin{matrix}sup\{y ∈ λ : Ψ(c_{1}, …, c_{n}, y)\} & ha ez korlátos λ-ban \\ 0 & egyébként. \end{matrix}

Előző megjegyzésünk szerint van olyan C ⊂ λ kof. zárt halmaz, hogy ennek minden eleme zárt az f, f^{∗}, g és g^{∗} függvényekre, továbbá az α ↦ α + . 1 függvényre is. Vegyük észre, hogy ez utóbbi feltétel miatt C elemei mind limeszpontok. Mivel S_{ξ} stacionárius halmaz volt, azért van α ∈ C ∩ S_{ξ}. Mivel C kofinális, van α-nál nagyobb eleme, mondjuk η, és mivel A λ számosságú, azért van A-nak η-nál nagyobb eleme, legyen ez β.

Tekintsük a β-ból α-ba menő sétát. Legyen ez éppen n hosszú, és a séta bal oldali elemei legyenek \overline{c} = ⟨c_{1}, …, c_{n}⟩. Most Φ(\overline{c}, α, x) azt jelenti, hogy az x-ből α-ba menő séta pontosan n hosszú és bal oldali elemeit \overline{c} adja meg: c_{1}, …, c_{n}.

Tudjuk, hogy c_{1}, …, c_{n} valamint α kisebb mint η, ami zárt az f^{∗} függvényre. Így ha nincs akármilyen nagy x ∈ A, amiből α-ba sétálva a séta bal oldala éppen \overline{c}, akkor az ilyen x-ekre f^{∗}(\overline{c}, α) < η felső korlát, vagyis ilyen x egyátalán nincs η fölött. Ám az általunk választott β nagyobb mint η, vagyis a megfelelő x-ek nem korlátosak, ezért Ψ(\overline{c}, α) teljesül.

Ha most g^{∗}(\overline{c}) nem nulla, akkor lévén mindegyik c_{i} < α és α zárt g^{∗}-ra, az értéke is kisebb α-nál. Ekkor viszont nem lehet olyan y ≥ α, amire Ψ(\overline{c}, y) állna – noha láttuk, hogy Ψ(\overline{c}, α) igaz. Így g^{∗}(\overline{c}) = 0, vagyis g(\overline{c}, γ) soha nem 0. Legyen max\{c_{1}, …, c_{n}\} = ε < α. Mivel α zárt a g függvényre is, ezért például α′ = g(\overline{c}, ε) < α, és ezzel Ψ(\overline{c}, α′). Ez pedig azt jelenti, hogy az f(\overline{c}, α′, γ) függvény soha nem nulla; mindig ad egy olyan értéket, hogy onnan α′-be sétálva a bal oldal éppen \overline{c}.

Az α-hoz tartozó C_{α} kof. zárt halmaznak vegyünk egy α′-nél nagyobb γ elemét, és legyen β′ = f(\overline{c}, α′, γ). Ez azt teszi, hogy β′ < α, β′ ∈ A és a β′-ből α′-be menő séta szintén n hosszú és bal oldali elemei \overline{c} = ⟨c_{1}, …, c_{n}⟩.

Vannak tehát a \overline{c} ≤ ε < α′ < γ < β′ < α < β rendszámaink, és β′ és β egyarán A-beli. Az állítjuk hogy a (β′, beta) pár színe éppen ξ, amivel Todorčevič tételét igazoltuk.

Először is α ∉ S miatt α eleme a β-ból β′-be menő sétának. α ennek a sétának “jó” eleme, hiszen a β → α séta bal oldali elemeinek maximuma éppen ε, és a β → ε valamint β′ → ε séta első n bal oldali eleme megyezik (hiszen ezek ugyanazok, mint a β → α illetve β′ → α′ bal oldali elemei). Továbbá α ∈ S_{ξ}, tehát csak azt kell megmutatnunk, hogy a β → β′ sétának nincs α utáni (azaz α-nál kisebb) jó eleme. A séta α utáni elemét úgy kapjuk, hogy C_{α}-nak megkeressük a β′-t tartalmazó legszűkebb intervallumát. Mivel γ ∈ C_{α}, azért ennek az intervallumnak a bal oldala biztosan ≥ mint γ, és így a bal oldalak maximuma, amit most ε′ jelöl, szintén ≥ γ > α′. Most a β → ε′ séta első n bal oldali eleme persze még mindig \overline{c} = ⟨c_{1}, …, c_{n}⟩. A β′ → ε′ séta első n bal oldali eleme között viszont lesz α′-nél nagyobb is, nevezetesen akkor, mikor a β′ → α′ séta átmegy ε′ fölött. Ekkor ugyanis a β′ → ε′ séta következő elemének kiszámításakor az ε′-t tartalmazó legszűkebb intervallum alsó végpontja az α′-t tartalmazó intervallum felső végpontjánál lesz nagyobb vagy egyenlő (illetve ha lépünk, akkor a séta itt véget is érne). Ez mutatja, hogy a β → β′ sétának tényleg nincs α utáni jó eleme, amivel a tételt bizonyítottuk.

Vizsga tematika

1. Számosságműveletek definíciói, tulajdonságok (36)

2. Jólrendezett halmazok tulajdonságai, rendszámok definíciója; a rendszámok osztálya jólrendezett (50)

3. Transzfinit indukció és rekurzió tételek (77)

4. A kiválasztási axióma és ekvivalensei (80)

5. Kőnig tétele, hatványozás tulajdonságai, hatványfüggvény ÁKH esetén (104)

6. Kofinalitás definíciója, ekvivalensei. Hausdorff tétel (95–101)

7. Kof. zárt és stacionárius halmazok definíciója, stac halmazon regresszív függvény konstans egy stac részen (Neumer tétele)

8. κ^{+}-on minden stac halmaz felbonlik κ diszjunkt stac uniójára (Solovay tétel speciális esete) (164)

9. Δ-rendszeres tétel (170)

10. Ramsey-tétel: ω → (ω)_{r}^{k} (177)

11. Erdős-Rado-tétel: κ → (κ, (λ)_{τ−1})_{τ}^{2} (183)

12. Sierpiñski-tétel, általában 2^{κ} ↛ (κ^{+})_{2}^{2} (182)

13. Erdős-tétel: a kontinuum-hipotézis ekvivalens azzal, hogy van A ⊂ IR^{2} ami minden vizszintes egyenesből csak megszámlálható sokat tartalmaz, minden függőlegesből csak megszámlálható sokat hagy ki.

14. ω-n van 2^{2^{ω}} különböző ultrafilter.

15. Létezik ω_{1}-es Aronszajn-fa.

16. Gyengén kompakt számosság, néhány tulajdonsága (227)

17. Todorčevič tétele.