UNIVERZITET U NOVOM SADU PRIRODNO-MATEMATIČKI FAKULTET

DEPARTMAN ZA MATEMATIKU I INFORMATIKU

Boris Šobot

Ultrafiltri i ultraproizvodi

-magistarska teza-

Novi Sad, 2004.

Sadržaj

1 Ultrafilteri 5 1.1 Osnovni pojmovi i tvrd¯ enja . . . . . . . . . . . . . . . . . . . 5 1.2 Vrste ultrafiltera . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.2.1 Glavni i neglavni ultrafilteri . . . . . . . . . . . . . . . 8 1.2.2 Uniformni ultrafilteri . . . . . . . . . . . . . . . . . . . 9 1.2.3 κ-kompletni ultrafilteri . . . . . . . . . . . . . . . . . . 9 1.2.4 α-opadajuće kompletni ultrafilteri . . . . . . . . . . . . 10 1.2.5 Regularni ultrafilteri . . . . . . . . . . . . . . . . . . . 12 1.2.6 Dobri ultrafilteri . . . . . . . . . . . . . . . . . . . . . 15

1.3 Egzistencija i broj ultrafiltera na nekom skupu . . . . . . . . . 16 1.3.1 O uniformnim, regularnim i dobrim ultrafilterima … 16 1.3.2 Familije velike oscilacije . . . . . . . . . . . . . . . . . 18 1.3.3 Broj ultrafiltera . . . . . . . . . . . . . . . . . . . . . . 19 1.3.4 Merljivi kardinali . . . . . . . . . . . . . . . . . . . . . 21

1.4 Neke topološke osobine ultrafiltera . . . . . . . . . . . . . . . . 24 1.4.1 Stoneova dualnost . . . . . . . . . . . . . . . . . . . . . 24 1.4.2 Stone-Čechova kompaktifikacija . . . . . . . . . . . . . 25

2 Ultraproizvodi 27 2.1 Definicija i osnovne osobine . . . . . . . . . . . . . . . . . . . 27 2.2 Fundamentalna teorema . . . . . . . . . . . . . . . . . . . . . 30 2.3 Jedna važna teorema . . . . . . . . . . . . . . . . . . . . . . . 33 2.4 Σ_{1}^{1} formule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.5 Jezik L_{κλ} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.6 Kvantifikatori Q_{α} . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.7 Changov kvantifikator . . . . . . . . . . . . . . . . . . . . . . 40 3 Kardinalnost i zasićenost ultraproizvoda 42

3.1 Kardinalnost ultraproizvoda . . . . . . . . . . . . . . . . . . . 42 3.1.1 Kardinalnost ultraproizvoda po regularnim ultrafilterima 44 3.1.2 Kardinalnost ultraproizvoda po uniformnim ultrafilte-

rima . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.1.3 Kardinalnost ultraproizvoda konačnih skupova . . . . . 47 3.1.4 Kardinalnost ultraproizvoda beskonačnih skupova … 49

3.2 Zasićenost ultraproizvoda . . . . . . . . . . . . . . . . . . . . 50 3.2.1 Zasićenost ultraproizvoda po regularnim ultrafilterima 50 3.2.2 Zasićenost ultraproizvoda po dobrim ured¯ enjima …. 53

4 Ultraproizvodi parcijalnih ured¯ enja 55 4.1 Uopšteno o parcijalnim ured¯ enjima . . . . . . . . . . . . . . . 55 4.2 Dobra ured¯ enja . . . . . . . . . . . . . . . . . . . . . . . . . . 56

4.2.1 Osnovno tvrd¯ enje . . . . . . . . . . . . . . . . . . . . . 56 4.2.2 Fiksne tačke višeg reda normalnih funkcija . . . . . . . 58 4.2.3 Najmanji zanimljiv dobro ured¯ en ultrastepen ordinala . 61 4.2.4 Još neka tvrd¯ enja . . . . . . . . . . . . . . . . . . . . . 68

4.3 Drveta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 4.3.1 Definicije i osnovna teorema . . . . . . . . . . . . . . . 70 4.3.2 Grane ultrastepena drveta . . . . . . . . . . . . . . . . 72 4.3.3 Nivoi ultraproizvoda drveta . . . . . . . . . . . . . . . 74 4.3.4 Neke važne vrste drveta . . . . . . . . . . . . . . . . . 75

4.4 Boolove algebre . . . . . . . . . . . . . . . . . . . . . . . . . . 79 4.4.1 Celularnost . . . . . . . . . . . . . . . . . . . . . . . . 79 4.4.2 Neuporedivost . . . . . . . . . . . . . . . . . . . . . . . 84 4.4.3 Dužina . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 4.4.4 Dubina . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 4.4.5 Topološka gustina . . . . . . . . . . . . . . . . . . . . . 87 4.4.6 Algebarska gustina . . . . . . . . . . . . . . . . . . . . 88

Predgovor

Ultraproizvodi su jedan od najvažnijih i najmoćnijih načina za konstruisanje modela. Stoga su oni nezaobilazna tema za svakog ko se bavi teorijom modela. Evo, u najkraćim crtama, pregleda sadržaja ovog magistarskog rada. Kako je za proučavanje ultraproizvoda najpre neophodno dobro upoznati razne vrste ultrafiltera, oni su tema prve glave. U njoj su date osnovne definicije, a zatim pregled najvažnijih vrsta ultrafiltera i njihovih osobina. Nakon toga slede tvrd¯ enja koja nam garantuju postojanje tih vrsta ultrafiltera, kao i tvrd¯ enja o broju ultrafiltera na nekom skupu. U drugoj glavi uvodi se pojam ultraproizvoda, a potom i fundamentalna teorema Łoša i njene verzije za razna proširenja jezika. Tu su i neka tvrd¯ enja koja objašnjavaju prirodu ultraproizvoda. Treća glava pokriva tvrd¯ enja o kardinalnosti ultraproizvoda, u zavisnosti od kardinalnosti modela od kojih je on formiran i vrste ultrafiltera, a tu su i neki rezultati o zasićenim modelima, oblasti u kojoj ultraproizvodi igraju veoma važnu ulogu. Konačno, poslednja glava obrad¯ uje i glavnu temu ovog rada: ultraproizvode raznih parcijalnih ured¯ enja. Podrobno se ispituju dobra ured¯ enja, drveta i Bulove algebre, dakle neka od ured¯ enja koja su od velike važnosti za teoriju skupova. Tu su sadržani i svi originalni rezultati koje nosi ovaj rad. Potrebno predznanje za teoriju skupova može se naći u [7] ili [20] (mada to nisu knjige za prvi susret sa teorijom skupova), za teoriju modela u [2], a za topologiju u [22]. Čitaoca zainteresovanog za ultrafiltere upućujemo na [3], a o nekim drugim aspektima ultraproizvoda dosta se može naći u [1]. Na kraju, želim da se zahvalim prvenstveno svom mentoru, prof. Milanu Gruloviću, koji me je i zainteresovao za ovu oblast. Sama ideja o temi ovog rada potiče od njega, a njegovi saveti i primedbe bili su dragoceni pri izradi. Želim da se zahvalim i prof. Milošu Kuriliću, koji mi je mnogo puta pomogao u razrešavanju nekih dilema iz teorije skupova, i na kraju takod¯ e pažljivo pregledao rad, kao i prof. Aleksandru Jovanoviću čija su ranija istraživanja u ovoj oblasti bila veoma korisna.

Novi Sad, 24. 5. 2004. Boris Šobot

Notacija

U ovom tekstu ordinali će biti najčešće označavani grčkim slovima α, β, γ, … a ponekad, posebno kada služe kao indeksi nekih nizova, označavaćemo ih i sa ξ, ζ, η. Kardinale specijalno označavamo slovima κ, λ, μ, ν. Sve ovo nećemo u tekstu posebno naglašavati. Za filtere rezervišemo slova F, G. Ako je |X| ≥ λ, skup podskupova skupa X kardinalnosti λ označavamo [X]^{λ}, a skup podskupova kardinalnosti manje od λ sa [X]^{<λ}. Skup preslikavanja iz skupa A u skup B označavamo sa ^{A}B. Sve operacije u tekstu (sabiranje, množenje, stepenovanje) su kardinalne operacije, osim gde je drugačije naznačeno. Takod¯ e, koristimo i oznaku κ^{<λ} = ∑_{μ<λ} κ^{μ}. Pomenimo još, da bismo izbegli zabunu, da ⊆ označava relaciju “biti podskup”, a ⊂ relaciju “biti strogo sadržan u”.

Glava 1

Ultrafilteri

1.1 Osnovni pojmovi i tvrd¯ enja

Krećemo od pojma (ultra)filtera, koji će biti jedan od najvažnijih u ovom radu.

Definicija 1.1.1 Filter na skupu I je neprazna familija F ⊂ P(I) koja zadovoljava sledeće uslove:

(i) ako X, Y ∈ F, onda X ∩ Y ∈ F;

(ii) ako X ∈ F i X ⊆ Y ⊆ I, onda Y ∈ F.

Primetimo odmah da iz drugog uslova i toga što je F neprazan skup sledi da I ∈ F. Takod¯ e, lako je videti da filter ne sadrži ∅, jer bi u suprotnom bilo F = P(I).

Napomena. Može se dati i mnogo opštija definicija filtera na proizvoljnoj Bulovoj algebri. Nju ćemo i dati u poslednjem odeljku ove glave, gde će nam jedino i biti potrebna.

Primer. Ako je X ⊆ I, skup {Y ⊆ I : X ⊆ Y } je filter na I, takozvani glavni filter generisan sa X. Filteri koji nisu ovog oblika nazivaju se neglavni.

Primer. Ako je I beskonačan skup, {X ⊆ I : |I \ X| < ω} je filter nad I, tzv. Frechétov filter.

Iz prethodnog primera vidimo da na svakom beskonačnom skupu postoji neglavni filter. Ispostaviće se da su nam upravo neglavni ultrafilteri od velike važnosti, pa će ta egzistencija biti veoma značajna.

Primer. Neka je E ⊆ P(I). Obeležimo

F (E) = ⋂{F : E ⊆ F ∧ F je filter nad I}.

Nije teško uvideti da, ako je F (E) ≠ P(I), onda je F (E) najmanji (u odnosu na relaciju ⊆) filter koji sadrži familiju E, i da je on jednak skupu {X ⊆ I : (∃G ∈ [E]^{<ℵ_{0}})(⋂ G ⊆ X)}. Zovemo ga filter generisan skupom E.

Definicija 1.1.2 Filter F na skupu I je ultrafilter ako je maksimalan u odnosu na relaciju ⊆, odnosno ako na tom skupu ne postoji filter F_{1} ⊃ F.

Teorema 1.1 Sledeći uslovi su ekvivalentni za filter F na skupu I:

(a) F je ultrafilter;

(b) za svako X ⊆ I važi tačno jedna od relacija X ∈ F i I \ X ∈ F;

(c) ako X ∪ Y ∈ F, onda važi bar jedna od relacija X ∈ F i Y ∈ F.

Dokaz.

(a ⇒ c) Primetimo da je dovoljno tvrd¯ enje dokazati u slučaju kada su X i Y disjunktni (u suprotnom, radimo sa X i Y \ X). Pretpostavimo da X ∪ Y ∈ F, ali X ∉ F i Y ∉ F. Neka je G filter generisan sa F ∪ {X}. (G ≠ P(I) jer G ne sadrži Y: ako bi bilo Y ∈ G, Y bi sadržao presek nekih konačno mnogo skupova iz F ∪ {X}, dakle i iz F pošto je disjunktan sa X, te bi on morao pripadati F). Takod¯ e, on strogo sadrži F, što je u kontradikciji sa maksimalnošću F.

(c ⇒ b) Pretpostavimo da X ∉ F i I \ X ∉ F. Tada prema (c) dobijamo I = X ∪ (I \ X) ∉ F, kontradikcija.

(b ⇒ a) Najpre primetimo da u filteru ne može važiti X ∈ F i I \ X ∈ F, jer bi tada i ∅ = X ∪ (I \ X) bilo u F. Neka je sada G filter nad I takav da F ⊂ G. To znači da postoji X ∈ G \ F. Kako X ∉ F, sledi I \ X ∈ F, pa i I \ X ∈ G, tj. G nije filter, kontradikcija. □

Definicija 1.1.3 Za familiju E ⊆ P(I) kažemo da ima svojstvo konačnog preseka (skraćeno: s.k.p.) ako je presek svakog njenog konačnog podskupa neprazan.

Lema 1.1.1 Svaka familija E koja ima s.k.p. može se dopuniti do filtera, odnosno postoji filter F ⊇ E.

Dokaz. Dovoljno je uzeti filter F (E) generisan sa E. Treba samo dokazati da je F (E) ≠ P(I). Ali ako to ne bi bilo tačno, važilo bi ∅ ∈ F (E), pa bi postojalo konačno mnogo elemenata iz E čiji je presek prazan, što nije tačno jer E ima s.k.p. □

Lema 1.1.2 Svaki filter sadržan je u nekom ultrafilteru.

Dokaz. Neka je F filter. Definišimo

P = {G ⊆ P(I) : G je filter ∧ F ⊆ G}.

(P, ⊆) je parcijalno ured¯ en skup. Neka je L lanac u tom ured¯ enju, i G^{∗} = ⋃ L. Dokažimo G^{∗} ∈ P. Očigledno je F ⊆ G^{∗}. Dokažimo da je G^{∗} filter: očigledno je G^{∗} neprazan, pa ostaje da pokažemo da važe uslovi (i) i (ii).

(i) Neka X, Y ∈ G^{∗}. Tada za neke F_{1}, F_{2} ∈ L važi X ∈ F_{1} i Y ∈ F_{2}. Neka npr. F_{1} ⊆ F_{2}. Tada X, Y ∈ F_{2}, pa i X ∩ Y ∈ F_{2} ⊆ G^{∗}.

(ii) Neka X ∈ G^{∗} i X ⊆ Y ⊆ I. Tada za neko F_{1} ∈ L važi X ∈ F_{1}, pa i Y ∈ F_{1} ⊆ G^{∗}.

Dakle, u (P, ⊆) svaki lanac ima gornje ograničenje, pa po lemi Zorna to ured¯ enje ima maksimalni element G_{0}. G_{0} je filter koji sadrži F, ali i ultrafilter: ako bi za neki filter G važilo G_{0} ⊂ G, imali bismo F ⊆ G, pa i G ∈ P, te G_{0} ne bi bio maksimalan. □

Iz prethodne dve leme sledi

Teorema 1.2 Svaki familija koja ima s.k.p. sadržana je u nekom ultrafilteru.

1.2 Vrste ultrafiltera

1.2.1 Glavni i neglavni ultrafilteri

Podsetimo se, filter F je glavni ako nije oblika {Y ⊆ I : X ⊆ Y } za neki skup X ⊆ I.

Lema 1.2.1 Filter F je glavni akko ⋂ F ∈ F.

Dokaz. Ako je F glavni filter generisan skupom X, onda ⋂ F = X ∈ F. Obratno, ako ⋂ F = X ∈ F, tada za sve Y ∈ F važi X ⊆ Y, a po uslovu (ii) iz definicije filtera svi skupovi Y ⊇ X pripadaju F. Sledi da je F = {Y ⊆ I : X ⊆ Y }. □

Nije teško zaključiti da je glavni filter ultrafilter akko je generisan jednoelementnim skupom, i da je ultrafilter glavni akko njegov presek ima jedan element. Videćemo kasnije (posledica teoreme 2.4) da ovo dovodi do toga da, bar što se tiče konstrukcije ultraproizvoda, glavni ultrafilteri nisu od značaja.

Lema 1.2.2 Neglavni ultrafilter ne sadrži konačne skupove.

Dokaz. Neka je X skup najmanje kardinalnosti u F, i pretpostavimo da je on konačan. X sadrži tačno jedan element, jer bismo ga inače mogli podeliti u dva skupa manje kardinalnosti od kojih bi bar jedan pripadao F (teorema 1.1). Zato je F glavni ultrafilter generisan sa X, kontradikcija. □

Lema 1.2.3 Neka je skup I prebrojiv i F neglavni ultrafilter na I. Tada postoji niz ⟨X_{n} : n ∈ ω⟩ elemenata ultrafiltera F takav da je:

1. X_{0} = I;

2. za sve n ∈ ω je X_{n+1} ⊂ X_{n} i X_{n} \ X_{n+1} je beskonačan;

3. ⋂_{n∈ω} X_{n} = ∅.

Dokaz. Neka je I = {i_{n} : n ∈ ω}. Definišimo traženi niz rekurzivno tako da zadovoljava prva dva uslova i da za sve n ∈ ω važi i_{n} ∉ X_{n+1}. Počećemo sa X_{0} = I. Neka je X_{m} definisano za m ≤ n, i neka su A_{n} i B_{n} disjunktni beskonačni skupovi takvi da A_{n} ∪ B_{n} = X_{n}. Pošto X_{n} ∈ F, tačno jedan od skupova A_{n}, B_{n} pripada F (videti teoremu 1.1). Neka je to npr. A_{n}. Tada i X_{n+1} = A_{n} \ {i_{n}} ∈ F. Time je traženi niz definisan. Primetimo još da važi

⋂_{n∈ω} X_{n} = ∅, jer za sve i_{n} ∈ I imamo i_{n} ∉ X_{n+1}, pa i i_{n} ∉ ⋂_{n∈ω} X_{n}. □

1.2.2 Uniformni ultrafilteri

Definicija 1.2.1 Filter F je uniforman ako su mu svi elementi iste kardinalnosti.

Očigledno, svaki uniforman ultrafilter je neglavni, jer ne može sadržati jednoelementne skupove. Kasnije ćemo videti (posledica 2.3.2) da je, ustvari, za ispitivanje svih značajnih osobina ultraproizvoda dovoljno posmatrati samo ultraproizvode po uniformnim ultrafilterima.

1.2.3 κ-kompletni ultrafilteri

Definicija 1.2.2 Filter F je κ-kompletan ako je presek svakog skupa od manje od κ elemenata iz F takod̄e u F, odnosno ako iz E ∈ [F]^{<κ} sledi ⋂ E ∈ F. Filter koji nije κ-kompletan naziva se κ-nekompletan.

Neke jednostavne posledice ove definicije sadržane su u sledećoj lemi:

Lema 1.2.4 (a) Svaki filter je ω-kompletan;

(b) Filter je κ-kompletan za sve kardinale κ akko je glavni;

(c) Ako je κ < λ, svaki λ-kompletan filter je i κ-kompletan.

Za neke osobine je nebitno da li razmatramo filter nad skupom I kardinalnosti κ ili nad samim skupom κ, pa ćemo često, radi jednostavnosti, radije činiti ovo drugo.

Lema 1.2.5 Ne postoji neglavni κ^{+}-kompletan filter nad κ.

Dokaz. Pretpostavimo suprotno: neka je F neglavni κ^{+}-kompletan filter nad κ i E = {κ \ {α} : α < κ}. Tada E ⊆ F (jer su komplementi elemenata iz E konačni, pa ne mogu pripadati F). Ali onda sledi ∅ = ⋂ E ∈ F, kontradikcija. □

Lema 1.2.6 Svaki neglavni κ-kompletan ultrafilter nad κ je uniforman.

Dokaz. Pretpostavimo suprotno, da je F neglavni κ-kompletan ultrafilter nad κ i da za neki X ∈ F važi |X| < κ. Za svako x ∈ X postoji A_{x} ∈ F takvo da x ∉ A_{x} (npr. A_{x} = κ\{x}). Tada ⋂_{x∈X} A_{x} ∩X = ∅, kontradikcija. □

Particijom skupa I zovemo familiju nepraznih po parovima disjunktnih podskupova skupa I čija je unija ceo I.

Lema 1.2.7 Ultrafilter F nad skupom I je κ-kompletan akko za svako λ < κ i svaku particiju {X_{ξ} : ξ < λ} tačno jedan njen element X_{ξ} pripada F.

Dokaz.

(⇒) Neka je λ < κ i {X_{ξ} : ξ < λ} jedna takva particija. Iz κ-kompletnosti sledi da, ako nijedan X_{ξ} ne bi pripadao F, tj. svi I \X_{ξ} bi mu pripadali, tada ∅ = ⋂_{ξ<λ}(I\X_{ξ}) ∈ F, što je nemoguće. Dakle, bar jedan X_{ξ} pripada

F. Ako bi i neki X_{η} pripadao F, imali bismo ∅ = X_{ξ} ∩ X_{η} ∈ F, kontradikcija.

(⇐) Neka je E ∈ [F]^{<κ}, npr. E = {Y_{ξ} : ξ < λ}. Definišimo skupove X_{ξ} za ξ < λ ovako: X_{0} = I \Y_{0}, X_{ξ} = (I \Y_{ξ})\ ⋃_{η<ξ} X_{η}. Dakle, u X_{ξ} stavljamo

sve i ∈ I takve da za η < ξ važi i ∈ Y_{η}, ali i ∉ Y_{ξ}. Konačno, stavimo X_{λ} = ⋂_{ξ<λ} Y_{ξ}. Jasno, {X_{ξ} : ξ ≤ λ} je particija skupa I, pa jedan od

skupova X_{ξ} mora pripadati F. To ne može biti ispunjeno za ξ < λ, jer bi iz X_{ξ} ∈ F sledilo I \ Y_{ξ} ∈ F, što je nemoguće zbog Y_{ξ} ∈ F. Dakle,

X_{λ} = ⋂_{ξ<λ} Y_{ξ} ∈ F. □

1.2.4 α-opadajuće kompletni ultrafilteri

Definicija 1.2.3 Ultrafilter F je α-opadajuće nekompletan ako postoji niz

⟨X_{ξ} : ξ < α⟩ elemenata iz F takav da X_{ξ} ⊇ X_{η} za ξ < η < α i ⋂_{ξ<α} X_{ξ} = ∅.

Ako takav niz ne postoji, ultrafilter je α-opadajuće kompletan.

Lema 1.2.8 Ultrafilter je α-opadajuće nekompletan akko je cf(α)-opadajuće nekompletan.

Dokaz. Neka je ⟨a_{ξ} : ξ < cf(α)⟩ rastući niz kofinalan u α i bez umanjenja opštosti a_{0} = 0. Ako je F α-opadajuće nekompletan i ⟨X_{η} : η < α⟩ opadajući niz elemenata iz F čiji je presek prazan, ⟨X_{a_{ξ}} : ξ < cf(α)⟩ takod¯ e zadovoljava te uslove, pa je F i cf(α)-opadajuće nekompletan. Obratno, ako je F cf(α)- opadajuće nekompletan i ⟨X_{η} : η < cf(α)⟩ niz koji zadovoljava gornje uslove, definišimo za η < α Y_{η} = X_{ξ} ako je a_{ξ} ≤ η < a_{ξ+1}. Tada je ⟨Y_{η} : η < α⟩ opadajući niz elemenata iz F čiji je presek prazan, tj. F je α-opadajuće nekompletan. □

Očigledno je svaki κ^{+}-kompletan ultrafilter i κ-opadajuće kompletan.

Lema 1.2.9 Neka je κ najmanji kardinal takav da je ultrafilter F κ^{+}-ne-kompletan. Tada je F κ-opadajuće nekompletan.

Dokaz. Zbog κ^{+}-nekompletnosti postoji familija {Y_{ξ} : ξ < κ} elemenata iz F takva da Y = ⋂_{ξ<κ} Y_{ξ} ∉ F. Stoga I \ Y ∈ F. Definišimo za ξ < κ:

X_{ξ} = (I \ Y) ∩ ⋂_{η<ξ} Y_{η}. Kako je |ξ| < κ, F je |ξ|^{+}-kompletan, pa X_{ξ} ∈ F.

Ovaj niz očito zadovoljava zahteve definicije . □

Navodimo jedno tvrd¯ enje iz [21].

Lema 1.2.10 Ako je κ regularan kardinal, svaki κ-opadajuće kompletan ultrafilter je κ^{+}-opadajuće kompletan.

Lema 1.2.3 kaže da je na prebrojivom skupu svaki neglavni ultrafilter ω-opadajuće nekompletan. Još neki rezultati o vezi uniformnih i opadajuće nekompletnih ultrafiltera mogu se naći u [3], 8.35. i 8.36. Mi uvodimo još jednu vrstu ultrafiltera koja je tesno povezana sa opadajućom nekompletnošću.

Definicija 1.2.4 Filter F je κ-rastavljiv ako postoji familija {X_{ξ} : ξ < κ} takva da

(i) X_{ξ_{1}} ∩ X_{ξ_{2}} = ∅ za ξ_{1} < ξ_{2} < κ;

(ii) ⋃{X_{ξ} : ξ < κ} = I;

(iii) ako J ∈ [κ]^{<κ}, onda ⋃{X_{ξ} : ξ ∈ J} ∉ F.

Lema 1.2.11 (a) Svaki κ-rastavljiv ultrafilter je κ-opadajuće nekompletan;

(b) ako je κ regularan kardinal, ultrafilter je κ-rastavljiv akko je κ-opadajuće nekompletan.

Dokaz.

(a) Ako je {X_{ξ} : ξ < κ} familija iz definicije κ-rastavljivosti, definišimo za η < κ: Y_{η} = ⋃_{η<ξ<κ} X_{ξ}. Jasno, niz {Y_{η} : η < κ} je opadajući i

⋂_{η<κ} Y_{η} = ∅, kao i Y_{η} = I \ ⋃_{ξ≤η} X_{ξ} ∈ F (ova konstrukcija poznata je kao

dijagonalizacija i koristićemo je više puta u ovom radu).

(b) Obratno, ako je {Y_{ξ} : ξ < κ} opadajuća familija elemenata ultrafiltera sa praznim presekom, definišimo X_{0} = I \ Y_{0} i, za 0 < ξ < κ, X_{ξ} = ⋂_{η<ξ} Y_{η} \ Y_{ξ}. Tada familija {X_{ξ} : ξ < κ} zadovoljava uslove prethodne

definicije: uslovi (i) i (ii) su očigledno zadovoljeni, a ako je J ∈ [κ]^{<κ}, iz činjenice da je κ regularan sledi da, ako obeležimo α = sup J, važi α < κ. Ali tada ⋃{X_{ξ} : ξ ∈ J} ⊆ I \ Y_{α+1}, pa ⋃{X_{ξ} : ξ ∈ J} ∉ F. □

1.2.5 Regularni ultrafilteri

Definicija 1.2.5 Filter F nad I je (λ, κ)-regularan akko postoji E ∈ [F]^{κ} takav da za svaki G ∈ [E]^{λ} važi ⋂ G = ∅. Za (ω, κ)-regularan filter kažemo i da je κ-regularan, a ako je |I| = κ, κ-regularan filter nad I zovemo samo regularan.

Familiju E iz prethodne definicije zvaćemo (λ, κ)-regularna familija za F. Kako osobina regularnosti ne zavisi od strukture skupa I već samo od njegove kardinalnosti, često ćemo moći u tvd¯ enjima pretpostaviti da je I neki kardinal.

Sledeće tvrd¯ enje je iz [12], i upravo taj potreban i dovoljan uslov za (λ, κ)- regularnost je poslužio kao prvobitna definicija u pomenutom radu.

Lema 1.2.12 Ultrafilter F nad μ je (λ, κ)-regularan akko postoji funkcija f : μ → [κ]^{<λ} takva da za sve α ∈ κ važi {β ∈ μ : α ∈ f(β)} ∈ F.

Dokaz.

(⇒) Neka je F (λ, κ)-regularan i E = {X_{α} : α < κ} (λ, κ)-regularna familija za F. Definišimo preslikavanje f : μ → [κ]^{<λ} ovako: f(β) = {α ∈ κ : β ∈ X_{α}}. Kako je presek svakih λ skupova familije E prazan, za svako β ∈ μ imamo |f(β)| < λ. Pošto α ∈ f(β) akko β ∈ X_{α}, dobijamo da je {β ∈ μ : α ∈ f(β)} = X_{α} ∈ F;

(⇐) Neka je f : μ → [κ]^{<λ} funkcija takva da su za α < κ skupovi X_{α} = {β ∈ μ : α ∈ f(β)} u F. Tada je E = {X_{α} : α < κ} familija kardinalnosti κ i, pošto β ∈ X_{α} akko α ∈ f(β), a |f(β)| < λ, svako β ∈ μ je u manje od λ elemenata familije E. □

U [1] je regularnost definisana takod¯ e pomoću osobine opisane u prethodnoj lemi, ali je traženo i da f bude bijekcija. To, med¯ utim, nije opšte prihvaćeno.

Lema 1.2.13 Svaki ω-regularan filter je ω_{1}-nekompletan. Ultrafilter je ωregularan akko je ω_{1}-nekompletan.

Dokaz. Neka je F ω-regularan filter nad I i E prebrojiv podskup skupa F takav da svako i ∈ I pripada samo konačnom broju X ∈ F. Tada ⋂ E = ∅ ∉ F. Obratno, ako je F ω_{1}-nekompletan ultrafilter, neka je ⟨X_{n} : n < ω⟩ niz čija je konstrukcija opisana u dokazu leme 1.2.9 (za κ = ω). Očigledno svaki i ∈ I pripada samo konačnom broju skupova X_{n}. □

Lema 1.2.14 Ako je F (λ, κ)-regularan ultrafilter, ω ≤ λ ≤ λ′ i ω ≤ κ′ ≤ κ, onda je F i (λ′, κ′)-regularan ultrafilter.

Dokaz. Bilo koji podskup (λ, κ)-regularne familije za F kardinalnosti κ′ je (λ′, κ′)-regularna familija za F. □

Lema 1.2.15 (a) Svaki κ-opadajuće nekompletan ultrafilter je (κ, κ)-regu-laran.

(b) Ako je κ regularan kardinal, ultrafilter je κ-opadajuće nekompletan akko je (κ, κ)-regularan.

(c) Svaki κ-regularan ultrafilter, je κ-opadajuće nekompletan.

Dokaz.

(a) Neka je E = {X_{ξ} : ξ < κ} opadajuća familija elemenata ultrafiltera F sa praznim presekom; dokažimo da je to (κ, κ)-regularna familija za F. Pretpostavimo suprotno, da postoji E′ ∈ [E]^{κ} takvo da ⋂ E′ ≠ ∅, npr. i ∈ ⋂ E′. Neka je η najmanje takvo da i ∉ X_{η}. Tada i ∉ X_{ξ} za sve ξ ≥ η, pa |E′| ≤ |η| < κ, kontradikcija.

(b) Neka je {X_{ξ} : ξ < κ} (κ, κ)-regularna familija za F. Primenjujući ponovo dijagonalizaciju, tj. stavljajući za ξ < κ Y_{ξ} = ⋃_{ξ<η<κ} X_{η} dobi-

jamo opadajuću familiju {Y_{ξ} : ξ < κ} elemenata iz F čiji je presek prazan (jer za svako i ∈ I, zbog regularnosti κ, postoji ξ < κ takvo da za η > ξ važi i ∉ X_{η}).

(c) Analogno dokazu (b), s tim što se umesto regularnosti κ koristi da je cf(κ) ≥ ω. □

Lema 1.2.16 Svaki (cf(κ), cf(κ))-regularan ultrafilter je i (κ, κ)-regularan.

Dokaz. Tvrd¯ enje je posledica prethodne leme i leme 1.2.8: ultrafilter koji je (cf(κ), cf(κ))-regularan je i cf(κ)-opadajuće nekompletan, dakle i κ-opadajuće nekompletan, pa i (κ, κ)-regularan. □

Još jedan rezultat tog tipa dokazan je u [23]:

Lema 1.2.17 Svaki (λ^{+}, κ^{+})-regularan ultrafilter je (λ, κ)-regularan.

Lema 1.2.18 Svaki regularan ultrafilter nad skupom I beskonačne kardinalnosti κ je uniforman.

Dokaz. Neka je f funkcija čije smo postojanje dokazali u lemi 1.2.12, i pretpostavimo da je X ⊆ I takav da |X| < |I|. Tada je i | ⋃_{i∈X} f(i)| < |I|, pa

postoji j ∈ I \ ⋃_{i∈X} f(i). Za sve i ∈ I za koje j ∈ f(i) važi i ∉ X. Sledi:

{i ∈ I : j ∈ f(i)} ⊆ I \ X, pa kako {i ∈ I : j ∈ f(i)} ∈ F, imamo I \ X ∈ F, odakle X ∉ F. Dakle, F je uniforman. □

Lema 1.2.19 Svaki uniforman ultrafilter nad κ je (cf(κ), cf(κ))-regularan.

Dokaz. Neka je ⟨α_{ξ} : ξ < cf(κ)⟩ niz kofinalan u κ. Tada je {κ\α_{ξ} : ξ < cf(κ)} (cf(κ), cf(κ))-regularna familija za bilo koji uniforman ultrafilter nad κ. □

Teorema 1.3 Nad prebrojivim skupom skupovi neglavnih, ω_{1}-nekompletnih, ω-opadajuće nekompletnih, uniformnih i regularnih ultrafiltera se poklapaju.

Dokaz. Lema 1.2.3 kaže da je svaki neglavni ultrafilter nad prebrojivim skupom i ω-opadajuće nekompletan, lema 1.2.15 utvrd¯ uje ekvivalenciju ωopadajuće nekompletnosti i regularnosti, a lema 1.2.9 ekvivalenciju ω-opada-juće nekompletnosti i ω_{1}-nekompletnosti. Konačno, iz 1.2.18 sledi da je svaki regularan ultrafilter nad prebrojivim skupom i uniforman, a svaki uniforman je očigledno neglavni.

1.2.6 Dobri ultrafilteri

Definicija 1.2.6 Neka su X i Y familije skupova. Za funkciju f : X → Y kažemo da je

• monotona ako iz x_{1}, x_{2} ∈ X i x_{1} ⊆ x_{2} sledi f(x_{2}) ⊆ f(x_{1});

• multiplikativna ako iz x_{1}, x_{2} ∈ X i x_{1} ∪ x_{2} ∈ X sledi f(x_{1} ∪ x_{2}) = f(x_{1}) ∩ f(x_{2}).

Ako su g i h funkcije čiji su domeni jednaki, pišemo g ≤ h da označimo da za sve elemente x njihovog domena važi g(x) ⊆ h(x).

Definicija 1.2.7 Za ultrafilter F kažemo da je κ-dobar ako za svako λ < κ i svaku monotonu funkciju f : [λ]^{<ω} → F postoji multiplikativna funkcija h : [λ]^{<ω} → F takva da h ≤ f. Ultrafilter F nad I je dobar ako je |I|^{+}-dobar.

Lema 1.2.20 Ako je κ beskonačan kardinal i F ultrafilter, F je κ^{+}-dobar akko za svaku monotonu funkciju f : [κ]^{<ω} → F postoji multiplikativna funkcija h : [κ]^{<ω} → F takva da h ≤ f.

Dokaz. Iz definicije direktno sledi da svaki κ^{+}-dobar ultrafilter zadovoljava uslov sa desne strane ekvivalencije. Pretpostavimo stoga da važi taj uslov i da je λ ≤ κ. Neka je f : [λ]^{<ω} → F monotona funkcija. Definišimo f′ : [κ]^{<ω} → F ovako: f′(X) = f(X ∩λ). Jasno, i f′ je monotona, pa sledi da postoji multiplikativna funkcija g′ : [κ]^{<ω} → F takva da g′ ≤ f′. Konačno, neka je e : [λ]^{<ω} → [κ]^{<ω} prirodna inkluzija (e(X) = X za X ∈ [λ]^{<ω}) i g = g′ ∘ e. Očigledno je g multiplikativna i g ≤ f. □

Lema 1.2.21 Svaki ultrafilter je ω_{1}-dobar.

Dokaz. Neka je F ultrafilter. Prema prethodnoj lemi, dovoljno je posmatrati monotone funkcije f : [ω]^{<ω} → F. Za X ∈ [ω]^{<ω} definišimo n(X) = min{n < ω : X ⊆ n}. Kako je n(X) ∈ [ω]^{<ω}, možemo definisati g : [ω]^{<ω} → F ovako: g(X) = f(n(X)). Iz monotonosti funkcije f i X ⊆ n(X) sledi g(X) = f(n(X)) ⊆ f(X) za X ∈ [ω]^{<ω}, odnosno g ≤ f. Treba još dokazati da je g multiplikativna. Neka X, Y ∈ [ω]^{<ω}; tada g(X ∪ Y) = f(n(X ∪ Y)) = f(n(X) ∪ n(Y)) = f(n(X)) ∩ f(n(Y)) = g(X) ∩ g(Y). □

Lema 1.2.22 Svaki ω_{1}-nekompletan κ^{+}-dobar ultrafilter je κ-regularan. Specijalno, svaki ω_{1}-nekompletan dobar ultrafilter je regularan.

Dokaz. Neka je ⟨A_{n} : n < ω⟩ opadajući niz elemenata ultrafiltera F nad λ čiji je presek prazan (videti lemu 1.2.9) i uzmimo baš A_{0} = λ. Definišimo f : [κ]^{<ω} → F ovako: f(X) = A_{|X|}. Jasno, f je monotona, te postoji multiplikativna funkcija g : [κ]^{<ω} → F takva da g ≤ f. Za ξ < λ neka je ϕ(ξ) = {η < κ : ξ ∈ g({η})}. Takod¯ e, neka je n(ξ) = min{n < ω : ξ ∉ A_{n}} (n(ξ) je dakle konačno). Pretpostavimo da za neko ξ < λ važi |ϕ(ξ)| ≥ n(ξ). Tada postoji B ⊆ ϕ(ξ) takvo da |B| = n(ξ), pa pošto je g multiplikativna imamo

ξ ∈ ⋂_{η∈B} g({η}) = g(B) ⊆ f(B) = A_{n(ξ)},

što je kontradikcija. Dakle, ϕ(ξ) je konačno, pa je presek bilo kojih beskonačno mnogo elemenata niza {g({η}) : η < κ} prazan; dakle F je κ-regularan. □

1.3 Egzistencija i broj ultrafiltera na nekom skupu

1.3.1 O uniformnim, regularnim i dobrim ultrafilterima

Da bismo pokazali egzistenciju uniformnih ultrafiltera, koristićemo pojam koji je uopštenje osobine s.k.p.

1.3. EGZISTENCIJA I BROJ ULTRAFILTERA NA NEKOM SKUPU 17

Definicija 1.3.1 Neprazna familija E ⊆ P(X) ima κ-uniformno svojstvo konačnog preseka ako | ⋂ A| ≥ κ za svaku familiju A ∈ [E]^{<ℵ_{0}}. E ⊆ P(κ) ima uniformno svojstvo konačnog preseka (skraćeno: u.s.k.p.) ako ima κuniformno svojstvo konačnog preseka.

Sledeća lema je analogon teoreme 1.2 za uniformne ultrafiltere.

Lema 1.3.1 (a) Svaka familija koja ima u.s.k.p. sadržana je u nekom uniformnom ultrafilteru;

(b) na svakom beskonačnom skupu postoji uniforman ultrafilter.

Dokaz.

(a) Neka je |I| = κ i K = {X ⊆ I : |I \ X| < κ}. Ako familija E ima u.s.k.p, jasno je da i E ∪ K ima u.s.k.p: ako su X_{1}, X_{2}, …, X_{k} ∈ E i

Y_{1}, Y_{2}, …, Y_{l} ∈ K, | ⋂_{i=1}^{k} X_{i}| ≥ κ a |I \ ⋂_{i=1}^{l} Y_{i}| < κ pa | ⋂_{i=1}^{k} X_{i} ∩ ⋂_{i=1}^{l} Y_{i}| ≥ κ.

Kada E ∪ K proširimo do ultrafiltra on ne može sadržati nijedan skup kardinalnosti manje od κ jer sadrži sve njihove komplemente.

(b) Dovoljno je da primenimo prethodnu lemu na familiju E = ∅. □

Teorema 1.4 Nad svakim beskonačnim skupom postoji regularan ultrafilter.

Dokaz. Dovoljno je pokazati da za svako κ nad nekim skupom kardinalnosti κ postoji regularan ultrafilter. Neka je I = [κ]^{<ω}, i za sve β ∈ κ neka je X_{β} = {i ∈ I : β ∈ i}. Skup E = {X_{β} : β ∈ κ} ima s.k.p. pa se po teoremi 1.2 može proširiti do ultrafiltera F. Ali u njemu postoji skup E kardinalnosti κ takav da svaki i ∈ I pripada samo konačnom broju X_{β} ∈ E, pa je F regularan. □

Iako bi se na prvi pogled reklo da je uslov regularnosti veoma jak, veći problem predstavlja egzistencija ultrafiltera koji nisu regularni. Jedan od prvih rezultata o tome dao je Silver: nad realno merljivim kardinalom κ postoji uniforman ultrafilter F takav da za sve λ < κ takve da cf(λ) ≠ ℵ_{0} F nije (λ, λ)-regularan (dokaz se može naći u [10]). Interesantan rezultat u tom pravcu dat je i u [24]: ako pretpostavimo GCH i egzistenciju velikog kardinala, postoji ultrafilter nad ω_{3} koji nije (ω_{1}, ω_{3})-regularan, a takod¯ e i ultrafilter nad ω_{2} koji nije (ω, ω_{2})-regularan.

1.3.2 Familije velike oscilacije

Za dokaze tvrd¯ enja o broju ultrafiltera na nekom skupu biće nam potreban sledeći pojam:

Definicija 1.3.2 Familija S ⊆ ^{λ}μ je familija κ-velike oscilacije ako važi: ako ν < κ, ⟨f_{ξ} : ξ < ν⟩ je niz različitih elemenata iz S i ⟨α_{ξ} : ξ < ν⟩ niz elemenata iz μ, onda postoji η < λ takvo da f_{ξ}(η) = α_{ξ} za ξ < ν.

Uočimo da iz definicije direktno sledi da su svi elementi familije velike oscilacije sirjektivna preslikavanja.

Teorema 1.5 Za ω ≤ κ ≤ λ ekvivalentni su uslovi:

(a) λ = λ^{<κ};

(b) postoji familija κ-velike oscilacije S ⊆ ^{λ}λ takva da |S| = 2^{λ};

Dokaz.

(a⇒ b) Definišimo

F = {(P, Q, s) : P ∈ [λ]^{<κ} ∧ Q ∈ [P(P)]^{<κ} ∧ s ∈ ^{Q}λ}.

Za P ∈ P(λ), ako |P | = μ < κ važi |[P(P)]^{<κ}| ≤ (2^{μ})^{<κ} ≤ (λ^{μ})^{<κ} = λ^{<κ} = λ. Takod¯ e, za Q ∈ [P(P)]^{<κ} imamo |^{Q}λ| ≤ λ^{<κ} = λ. Stoga |F| = λ^{<κ} · λ · λ = λ. Dovoljno je, dakle, naći S ⊆ ^{F}λ koja je familija κ-velike oscilacije. Definišimo za A ⊆ λ funkciju f_{A} : F → λ ovako:

f_{A}((P, Q, s)) = \{ \begin{matrix}s(A ∩ P), & ako A ∩ P ∈ Q \\ 0, & inače \end{matrix}

Dokažimo da je S = {f_{A} : A ⊆ λ} familija κ-velike oscilacije kardinalnosti 2^{λ}. Svake dve funkcije f_{A}, f_{B} ∈ S za A ≠ B su različite: ako npr. α ∈ A \ B stavimo P = {α}, Q = {{α}} i s({α}) = 1; tada f_{A}((P, Q, s)) = 1 i f_{B}((P, Q, s)) = 0. Zaključujemo da je |S| = 2^{λ}. Neka je μ < κ i ⟨A_{ξ} : ξ < μ⟩ niz različitih podskupova skupa λ (tj. ⟨f_{A_{ξ}} : ξ < μ⟩ je niz različitih elemenata iz S), i ⟨α_{ξ} : ξ < μ⟩ niz elemenata iz λ. Za ξ < ξ′ < μ izaberimo a_{ξ,ξ′} ∈ (A_{ξ} \ A_{ξ′}) ∪ (A_{ξ′} \ A_{ξ}). Zatim definišimo P = {a_{ξ,ξ′} : ξ < ξ′ < μ}, Q = {A_{ξ} ∩ P : ξ < μ} i funkciju s : Q → λ ovako: s(A_{ξ} ∩P) = α_{ξ}. s je dobro definisana jer iz ξ < ξ′ < μ sledi A_{ξ} ∩ P ≠ A_{ξ′} ∩ P. Imamo f_{A_{ξ}}((P, Q, s)) = s(A_{ξ} ∩ P) = α_{ξ}, što znači da je S familija κ-velike oscilacije. □

Dokaz drugog smera (koji nama i nije potreban) je znatno komplikovaniji i može se naći u [3] (teorema 3.16), gde je dato još nekoliko ekvivalenata.

Posledica 1.3.1 Neka je ω ≤ κ ≤ λ = λ^{<κ} i 2 ≤ μ ≤ λ. Tada postoji familija κ-velike oscilacije S ⊆ ^{λ}μ takva da |S| = 2^{λ}.

Dokaz. Neka je S′ ⊆ ^{λ}λ familija κ-velike oscilacije koju daje teorema 1.5. Neka je π : λ → μ proizvoljna sirjekcija. Za f ∈ S′ definišimo g_{f} : λ → μ ovako: g_{f} = π ∘ f. Tada je i S = {g_{f} : f ∈ S′} familija κ-velike oscilacije kardinalnosti 2^{λ}. Zaista, ako je ν < κ, ⟨g_{ξ} : ξ < ν⟩ niz elemenata iz S i ⟨α_{ξ} : ξ < ν⟩ niz elemenata iz μ, neka je za ξ < ν g_{ξ} = π ∘ f_{ξ} i δ_{ξ} < λ takvo da π(δ_{ξ}) = α_{ξ}. Postoji η ∈ μ takvo da f_{ξ}(η) = δ_{ξ} za ξ < ν. Tada je g_{ξ}(η) = α_{ξ} za ξ < ν. □

1.3.3 Broj ultrafiltera

Lema 1.3.2 Neka je ω ≤ κ ≤ λ = λ^{<κ}. Postoji familija ϕ κ-kompletnih filtera na λ takvih da |ϕ| = 2^{2^{λ}} i ako F, G ∈ ϕ i F ≠ G, tada postoji A ∈ P(λ) takav da A ∈ F i λ \ A ∈ G.

Dokaz. Prema posledici teoreme 1.5 postoji familija S ⊆ ^{λ}2 κ-velike oscilacije takva da |S| = 2^{λ}. Za L ⊆ S definišimo

g(L) = {f^{−1}({0}) : f ∈ L} ∪ {f^{−1}({1}) : f ∈ S \ L}.

Svaki g(L) za L ⊆ S ima svojstvo κ-preseka jer je S familija κ-velike oscilacije: ako μ_{1}, μ_{2} < κ i F = {f_{ξ}^{−1}({0}) : ξ < μ_{1}} ∪ {g_{ξ}^{−1}({1}) : ξ < μ_{2}} podskup familije g(L) kardinalnosti manje od κ, tada postoji η < λ takav da f_{ξ}(η) = 0 za ξ < μ_{1} i g_{ξ}(η) = 1 za ξ < μ_{2}, tj. η ∈ ⋂ F. Stoga se može (videti lemu 1.3.4) proširiti do κ-kompletnog filtera F (L). Familija ϕ = {F (L) : L ⊆ S} je tražena; zaista, ako su L_{1} i L_{2} različiti podskupovi familije S, postoji npr. f ∈ L_{1} \ L_{2}. Tada f^{−1}({0}) ∈ g(L_{1}) ⊆ F (L_{1}) i λ \ f^{−1}({0}) = f^{−1}({1}) ∈ g(L_{2}) ⊆ F (L_{2}) (f^{−1}({0}) i f^{−1}({1}) su neprazni jer je f sirjekcija). □

Teorema 1.6 Ako je λ ≥ ω, broj ultrafiltera na λ je 2^{2^{λ}}.

Dokaz. S jedne strane, pošto su svi ultrafilteri na λ elementi skupa P(P(λ)), njihov broj je najviše 2^{2^{λ}}. Obratno, ako je ϕ familija iz prethodne teoreme, svaki filter iz ϕ možemo dopuniti do ultrafiltera. Ako su F_{0}, F_{1} ∈ ϕ i G_{0} ⊇ F_{0}, G_{1} ⊇ F_{1} ultrafilteri, tada postoji A ∈ P(λ) takav da A ∈ F_{0} ⊆ G_{0} i λ \ A ∈ F_{1} ⊆ G_{1}, odakle G_{0} ≠ G_{1}. Dakle, postoji 2^{2^{λ}} različitih ultrafiltera na λ. □

Lema 1.3.3 (Disjunktnog profinjenja) Neka je κ ≥ ω i {A_{ξ} : ξ < κ} familija skupova takva da |A_{ξ}| = κ za ξ < κ. Tada postoji familija {B_{ξ} : ξ < κ} skupova takvih da B_{ξ} ⊆ A_{ξ} i |B_{ξ}| = κ za ξ < κ, kao i B_{ξ} ∩ B_{η} = ∅ za ξ < η < κ.

Dokaz. Definišimo familiju {p_{ξ′,ξ} : ξ′ ≤ ξ < κ} rekurzivno: izaberemo p_{0,0} ∈ A_{0} proizvoljno. Ako je η < κ i definisali smo p_{ξ′,ξ} za ξ′ ≤ ξ < η, biramo p_{η′,η} za η′ ≤ η tako da p_{η′,η} ∈ A_{η′} \ {p_{ξ′,ξ} : ξ′ ≤ ξ < η} i p_{η′,η} ≠ p_{η′′,η} za η′′ < η′ ≤ η. Konačno, neka B_{ξ} = {p_{ξ,η} : ξ ≤ η < κ} za ξ < κ. Familija {B_{ξ} : ξ < κ} očigledno zadovoljava zadate uslove. □

Teorema 1.7 Neka je κ ≥ ω i F ⊆ P(κ) familija kardinalnosti najviše κ koja ima u.s.k.p. Tada postoji 2^{2^{κ}} različitih uniformnih ultrafiltera na κ koji sadrže F.

Dokaz. Bez umanjenja opštosti možemo pretpostaviti da je F zatvoreno za konačne preseke (u suprotnom, umesto nje posmatramo familiju svih konačnih preseka elemenata iz F). Takod¯ e možemo pretpostaviti da je |F| = κ, jer u protivnom možemo F dopuniti sa κ nadskupova nekog X ∈ F. Neka je {A_{ξ} : ξ < κ} jedno dobro ured¯ enje familije F i {B_{ξ} : ξ < κ} familija koju daje lema disjunktnog profinjenja. Svaki od skupova B_{ξ} podelimo na κ disjunktnih podskupova kardinalnosti κ; tako dobijamo familiju {C_{ξ,η} : ξ < κ, η < κ} takvu da C_{ξ,η} ⊆ A_{ξ}, C_{ξ,η} ∩ C_{ξ′,η′} = ∅ za (ξ, η) ≠ (ξ′, η′) i |C_{ξ,η}| = κ za sve ξ, η < κ. Neka je dalje F proizvoljan ultrafilter na κ (takvih prema teoremi 1.6 ima 2^{2^{κ}}). Definišimo F_{F} = F ∪ {⋃{C_{ξ,η} : ξ < κ, η ∈ X} : X ∈ F } i pokažimo da F_{F} ima u.s.k.p. Zato izaberimo A_{ξ_{1}}, A_{ξ_{2}}, …, A_{ξ_{m}} ∈ F i X_{1}, X_{2}, …, X_{n} ∈ F; ako je A_{ξ′} = ⋂_{i=1}^{m} A_{ξ_{i}} i X = ⋂_{i=1}^{n} X_{i}, zbog X ∈ F postoji η′ ∈ X, pa, kako je

⋃{C_{ξ,η} : ξ < κ, η ∈ X} =

⋃{C_{ξ,η} : ξ < κ, η ∈ X_{1}} ∩ … ∩ ⋃{C_{ξ,η} : ξ < κ, η ∈ X_{n}},

dobijamo C_{ξ′,η′} ⊆ A_{ξ′} ∩ ⋃{C_{ξ,η} : ξ < κ, η ∈ X}, što znači |A_{ξ′} ∩ ⋃{C_{ξ,η} : ξ < κ, η ∈ X}| ≥ κ. Dalje, prema lemi 1.3.1 za svaki ultrafilter F na κ postoji uniforman ultrafilter F̄ ⊇ F_{F}. Mad¯ utim, ako su F_{1} i F_{2} različiti ultrafilteri, F_{1} i F_{2} sadrže komplementarne podskupove X_{1} i X_{2} skupa κ, odakle F̄_{1} i F̄_{2} sadrže disjunktne skupove ⋃{C_{ξ,η} : ξ < κ, η ∈ X_{1}} i ⋃{C_{ξ,η} : ξ < κ, η ∈ X_{2}}, pa moraju biti različiti. Dakle, uniformnih ultrafiltera na κ ima bar 2^{2^{κ}}. □

Egzistenciju, kao i procenu broja dobrih ultrafiltera utvrd¯ uje sledeća teorema, čiji se dokaz može naći u [3] (teorema 10.4.).

Teorema 1.8 (Kunen) Ako je κ ≥ ω, postoji bar 2^{κ} ω_{1}-nekompletnih dobrih ultrafiltera nad κ.

1.3.4 Merljivi kardinali

Evo još jednog pojačanja svojstva s.k.p.

Definicija 1.3.3 Kažemo da neka familija ima svojstvo κ-preseka ako je presek svakog njenog podskupa kardinalnosti manje od κ neprazan.

Lema 1.3.4 Svaka familija koja ima svojstvo κ-preseka može se proširiti do κ-kompletnog filtera.

Dakle, važi analogon leme 1.1.1. Nažalost, tvrd¯ enje analogno lemi 1.1.2 ne važi za svojstvo κ-preseka. Štaviše, za razliku od ostalih značajnih vrsta ultrafiltera čiju śmo egzistenciju dokazivali, za neglavne kompletne ultrafiltere to nije moguće.

Definicija 1.3.4 Kardinal κ je merljiv ako postoji κ-kompletan neglavni ultrafilter nad κ. Kardinal κ je Ulam-merljiv ako postoji ω_{1}-kompletan neglavni ultrafilter nad κ.

Lema 1.3.5 Svaki merljiv kardinal je regularan.

Dokaz. Pretpostavimo suprotno, da je κ merljiv i cf(κ) = λ < κ i F κkompletan ultrafilter nad κ. Neka je ⟨α_{ξ} : ξ < λ⟩ niz kofinalan u κ i X_{ξ} = {β < κ : β > α_{ξ}}. Kako je |κ \ X_{ξ}| < κ, iz leme 1.2.6 sledi X_{ξ} ∈ F. Med¯ utim, ⋂_{ξ<λ} X_{ξ} = ∅, kontradikcija. □

Jedini kardinal za koji je moguće dokazati (i očigledno je) da je merljiv je ω. On med¯ utim nije Ulam-merljiv zbog leme 1.2.5. Postojanje neprebrojivih merljivih kardinala ne može se dokazati u ZFC; štaviše, nije moguće dokazati ni konsistentnost aksiome ”postoji neprebrojiv merljiv kardinal” sa ZFC. Ako postoje, merljivi kardinali moraju biti veoma veliki. Izmed¯ u ostalog, svaki merljiv kardinal mora biti nedostižan i slabo kompaktan (videti [2], 4.2.14. i 4.2.12). Više o velikim kardinalima može se naći npr. u [4]. O vezi merljivih i Ulam-merljivih kardinala govori sledeća teorema.

Teorema 1.9 Kardinal je Ulam-merljiv akko je veći ili jednak od najmanjeg neprebrojivog merljivog kardinala.

Dokaz. Dokažimo prvo: ako je κ Ulam-merljiv, i svaki kardinal λ ≥ κ je Ulam-merljiv. Zaista, neka je F ω_{1}-kompletan ultrafilter nad κ. Definišimo G = {X ⊆ λ : X ∩ κ ∈ F }. G je očigledno ω_{1}-kompletan ultrafilter nad λ. Ostaje da dokažemo da je najmanji Ulam-merljiv kardinal κ i merljiv. Neka je F ω_{1}-kompletan neglavni ultrafilter nad κ. Neka je λ najmanji kardinal takav da F nije λ^{+}-kompletan, i pretpostavimo λ < κ. Prema lemi 1.2.7 postoji familija {Z_{ξ} : ξ < λ} takva da:

• ⋃_{ξ<λ} Z_{ξ} = κ;

• Z_{ξ} ∩ Z_{η} = ∅ za ξ < η < λ;

• Z_{ξ} ∉ F za ξ < λ.

Definišimo G = {Y ⊆ λ : ⋃_{ξ∈Y} Z_{ξ} ∈ F }. Očigledno, G je neglavni ultrafil-

ter nad λ. Pokažimo da je ω_{1}-kompletan što će biti kontradikcija sa pret-

postavkom λ < κ. Neka je {C_{n} : n < ω} ⊆ G. Iz ⋃_{ξ∈C_{n}} Z_{ξ} ∈ F za n < ω

i ω_{1}-kompletnosti F sledi da i ⋂_{n<ω} ⋃_{ξ∈C_{n}} Z_{ξ} ∈ F. Kako svaki x ∈ ⋂_{n<ω} ⋃_{ξ∈C_{n}} Z_{ξ}

može pripadati samo jednom Z_{ξ}, za to ξ imamo ξ ∈ C_{n} za sve n < ω tako da, ako obeležimo D = ⋂_{n<ω} C_{n}, onda ⋃_{ξ∈D} Z_{ξ} ∈ F, dakle D ∈ G. Time je dokaz

završen. □

Dakle, egzistencija neprebrojivih merljivih kardinala ekvivalentna je sa egzistencijom Ulam-merljivih kardinala.

Teorema 1.10 Ako je F neglavni ultrafilter, postoji najveći kardinal κ takav da je F κ-kompletan, i κ je merljiv.

Dokaz. Kako je F neglavni, postoji najmanji kardinal λ takav da je F λnekompletan. To znači da postoji familija od μ < λ elemenata iz F čiji presek nije u F, pa λ ne može biti granični, jer bi F bio i μ^{+}-nekompletan, i μ^{+} < λ. Dakle, λ = κ^{+} za neko κ, i κ je najveći kardinal takav da je F κ-kompletan. Dalje, postoji particija I = ⋃_{ξ<κ} X_{ξ} takva da nijedan od skupova X_{ξ} nije u

F. Definišimo funkciju f : I → κ ovako: f(i) = ξ gde i ∈ X_{ξ}. Pokažimo da je G = {S ⊆ κ : f^{−1}(S) ∈ F } κ-kompletan neglavni ultrafilter nad κ, što će značiti da je κ merljiv. Očigledno, G jeste ultrafilter. Ako je ν < κ i {S_{ξ} : ξ < ν} familija elemenata iz G, tada f^{−1}(S_{ξ}) ∈ F za ξ < ν, pa

i f^{−1}( ⋂_{ξ<ν} S_{ξ}) = ⋂_{ξ<ν} f^{−1}(S_{ξ}) ∈ F, odakle ⋂_{ξ<ν} S_{ξ} ∈ G. G je neglavni, jer

bi u suprotnom neki jednoelementni skup {α} pripadao G, pa bismo imali X_{α} = f^{−1}({α}) ∈ F, kontradikcija. □

Posledica 1.3.2 Ako je κ najmanji merljiv kardinal, i ultrafilter F je ω_{1}- kompletan, on je i κ-kompletan.

Definicija 1.3.5 Beskonačan kardinal κ je jako kompaktan ako se za svaki beskonačan kardinal λ svaki κ-kompletan filter nad λ može proširiti do κkompletnog ultrafiltera.

Definicija 1.3.6 Beskonačan kardinal κ je jako merljiv ako je regularan i svaki κ-kompletan filter nad κ se može proširiti do κ-kompletnog ultrafiltera.

Primetimo prvo da i jako kompaktni i jako merljivi kardinali moraju biti merljivi. Dalje, kako je svaki merljiv kardinal i regularan, sledi da su jako kompaktni kardinali i jako merljivi. Skup λ-kompletnih ultrafiltera nad κ označimo sa K_{λ}(κ). Dokaz sledećeg tvrd¯ enja može se naći u [3].

Teorema 1.11 (a) Ako je κ merljiv, tada 2^{κ} ≤ |K_{κ}(κ)| ≤ 2^{2^{κ}}.

(b) Ako je ω ≤ λ ≤ κ = κ^{<λ} i svaki λ-kompletan filter nad κ se može proširiti do λ-kompletnog ultrafiltera, tada |K_{λ}(κ)| = 2^{2^{κ}}.

(c) Ako je ω ≤ λ ≤ κ = κ^{<λ} i κ je jako kompaktan, tada |K_{λ}(κ)| = 2^{2^{κ}}.

(d) Ako je κ jako merljiv, tada |K_{κ}(κ)| = 2^{2^{κ}}.

1.4 Neke topološke osobine ultrafiltera

Ultrafilteri su veoma značajni u topologiji, a kako su neke njihove topološke osobine interesantne i za ovaj rad, napravićemo kratak pregled nekih od njih.

1.4.1 Stoneova dualnost

Pojam (ultra)filtera može se definisati na proizvoljnoj Bulovoj algebri, dok smo mi to učinili samo za algebru (P(I), ∩, ∪,^{c} , ∅, I).

Definicija 1.4.1 Neka je B = (B, ∧, ∨,^{c} , 0, 1) Bulova algebra. Skup F ⊆ B je filter u B akko važi:

1 ∈ F i 0 ∉ F,  (F 1)
(∀x, y ∈ F)x ∧ y ∈ F,  (F 2)
(∀x ∈ F)(∀y ∈ B)(y ≥ x ⇒ y ∈ F).  (F 3)

Maksimalne filtere ponovo zovemo ultrafilteri. Većina rezultata iz prvog odeljka ove glave važi i za ovako definisane ultrafiltere. Skup otvoreno-zatvorenih skupova topološkog prostora (X, O) označavaćemo sa Clop(X). Ako je B Bulova algebra, sa Ult(B) ćemo označavati skup ultrafiltera te algebre.

Lema 1.4.1 Ako je (X, O) topološki prostor, (Clop(X), ∩, ∪,^{c} , ∅, X) je Bulova algebra.

Dokaz. Očigledno je Clop(X) ≠ ∅, i iz U, V ∈ Clop(X) sledi U ∩ V ∈ Clop(X) i U^{c} ∈ Clop(X). Zato je Clop(X) podalgebra algebre P(X), pa je i sama Bulova algebra. □

Definicija 1.4.2 Topološki prostor je nuladimenzionalan ako je T_{2} i ima bazu koja se sastoji od otvoreno-zatvorenih skupova. Topološki prostor je Bulov akko je kompaktan i nuladimenzionalan.

Ako je B Bulova algebra, za p ∈ B definišemo B_{p} = {F ∈ Ult(B) : p ∈ F }.

Lema 1.4.2 Ako je B Bulova algebra, {B_{p} : p ∈ B} je baza neke topologije O na Ult(B) i (Ult(B), O) je Bulov prostor.

Teorema 1.12 (Stone) (a) Za sve Bulove algebre B važi Clop(Ult(B)) ≅ B;

(b) Za sve Bulove prostore (X, O) važi Ult(Clop(X)) ≅ X.

U prethodnoj teoremi prvo ≅ označava izomorfizam Bulovih algebri, a drugo ≅ homeomorfizam topoloških prostora. Dokaz ovog tvrd¯ enja i više o Stoneovoj dualnosti može se naći npr. u [35]. Uopšte, čitaoca zainteresovanog za topologiju upućujemo na [5].

1.4.2 Stone-Čechova kompaktifikacija

Definicija 1.4.3 Neka je (X, O) T_{3 \frac{1}{2}} -topološki prostor. Stone-Čechova kompaktifikacija tog prostora je prostor Ult(X) svih ultrafiltera nad X sa topologijom čija je podbaza {{F ∈ Ult(X) : A ∉ F } : A ∈ Z(X)}, gde je Z(X) familija svih nula-skupova iz X, tj. inverznih slika nule pri neprekidnim preslikavanjima X u skup realnih brojeva.

Razjasnimo ovo malo: ako je (X, O) topološki prostor, njegova kompaktifikacija je kompaktan prostor u kojem je X gust. Med¯ utim, ona nije jedinstvena. Na skupu kompaktifikacija stoga se uvodi poredak u kojem je baš Stone-Čechova kompaktifikacija maksimalna. Odatle i njen značaj.

Za kraj ovog kratkog pregleda, evo dve interesantne topološke činjenice. U njima se skupovi uniformnih (U_{κ}), odnosno κ-kompletnih (K_{κ}) ultrafiltera na κ posmatraju kao potprostori prostora Ult(κ) (i naravno, ovaj drugi je potprostor prvog). Dokazi se mogu naći u [3].

Lema 1.4.3 U_{κ} je kompaktan potprostor prostora Ult(κ)

Lema 1.4.4 Ako je κ merljiv kardinal, prostor K_{κ} je gust potprostor prostora U_{κ}.

Ultraproizvodi

2.1 Definicija i osnovne osobine

Neka su A_{i} modeli nekog jezika L sa domenima A_{i} (i ∈ I) i F filter nad I. Dalje, neka je A = ∏_{i∈I} A_{i} kartezijanski proizvod skupova A_{i}. Kao što znamo,

elementi skupa A su funkcije f : I → ⋃_{i∈I} A_{i} takve da f(i) ∈ A_{i} za sve i ∈ I.

Na skupu A možemo definisati relaciju ∼_{F}:

f ∼_{F} g akko {i ∈ I : f(i) = g(i)} ∈ F.

Lema 2.1.1 ∼_{F} je relacija ekvivalencije na skupu A.

Dokaz.

R: Za sve f ∈ A je {i ∈ I : f(i) = f(i)} = I ∈ F;

S: ako f ∼_{F} g, odnosno {i ∈ I : f(i) = g(i)} ∈ F, onda i {i ∈ I : g(i) = f(i)} ∈ F, odnosno g ∼_{F} f;

T: ako f ∼_{F} g i g ∼_{F} h, onda {i ∈ I : f(i) = g(i)} ∈ F i {i ∈ I : g(i) = h(i)} ∈ F, pa i {i ∈ I : f(i) = h(i)} ∈ F (jer {i ∈ I : f(i) = h(i)} ⊆ {i ∈ I : f(i) = g(i)} ∩ {i ∈ I : g(i) = h(i)}), odnosno f ∼_{F} h. □

Obeležimo klasu ekvivalencije elementa f sa f^{F}, za sve f ∈ A. Na skupu A/ ∼_{F} svih klasa ekvivalencije relacije ∼_{F} definisaćemo sada interpretacije svih znakova relacija, konstanti i funkcija jezika L:

• ako je R n-arno relacijsko slovo, interpretiramo ga relacijom R̄ definisanom ovako:

R̄(f_{1}^{F} , f_{2}^{F} , …, f_{n}^{F}) akko {i ∈ I : R̄_{i}(f_{1}(i), f_{2}(i), …, f_{n}(i))} ∈ F,

gde je R̄_{i} interpretacija slova R u modelu A_{i};

• ako je c znak konstante, interpretiramo ga elementom c̄ definisanim

ovako:

c̄ = ⟨c̄_{i} : i ∈ I⟩^{F}

gde je c̄_{i} interpretacija slova c u modelu A_{i};

• ako je G n-arno funkcijsko slovo, interpretiramo ga funkcijom Ḡ definisanom ovako:

Ḡ(f_{1}^{F} , f_{2}^{F} , …, f_{n}^{F}) = ⟨Ḡ_{i}(f_{1}(i), f_{2}(i), …, f_{n}(i)) : i ∈ I⟩^{F} ,

gde je Ḡ_{i} interpretacija slova G u modelu A_{i}.

Definicija 2.1.1 Model sa domenom A/∼_{F} na kom su znaci relacija, konstanti i funkcija interpretirane na gore opisani način naziva se redukovani proizvod modela A_{i} po filteru F i obeležava se sa ∏_{i∈I} A_{i}/F ili kraće ∏_{F} A_{i}.

Ako je F ultrafilter, ∏_{F} A_{i} se naziva ultraproizvod modela A_{i} po ultrafilteru

F. Ako su još i svi modeli A_{i} jednaki nekom modelu A, ∏_{F} A se naziva ultraste-

pen modela A po ultrafilteru F i obeležava sa A^{I}/F.

Lema 2.1.2 Neka su A_{i} modeli jezika L, f_{1}, f_{2}, …, f_{n}, g_{1}, g_{2}, …, g_{n} ∈ ∏_{i∈I} A_{i}

i f_{1} ∼_{F} g_{1}, f_{2} ∼_{F} g_{2}, …, f_{n} ∼_{F} g_{n}. Tada:

(a) za svako relacijsko slovo R jezika L važi:

{i ∈ I : R̄_{i}(f_{1}(i), f_{2}(i), …, f_{n}(i))} ∈ F
akko {i ∈ I : R̄_{i}(g_{1}(i), g_{2}(i), …, g_{n}(i))} ∈ F;

(b) za svako funkcijsko slovo G jezika L važi:

⟨Ḡ_{i}(f_{1}(i), f_{2}(i), …, f_{n}(i)) : i ∈ I⟩
∼_{F} ⟨Ḡ_{i}(g_{1}(i), g_{2}(i), …, g_{n}(i)) : i ∈ I⟩.

Dokaz.

(a) Pretpostavimo da X = {i ∈ I : R̄_{i}(f_{1}(i), f_{2}(i), …, f_{n}(i))} ∈ F. Kako je f_{1} ∼_{F} g_{1}, f_{2} ∼_{F} g_{2}, …, f_{n} ∼_{F} g_{n}, skupovi {i ∈ I : f_{1}(i) = g_{1}(i)}, {i ∈ I : f_{2}(i) = g_{2}(i)}, …, {i ∈ I : f_{n}(i) = g_{n}(i)} su takod¯ e u F, pa je i njihov presek Y = {i ∈ I : f_{1}(i) = g_{1}(i) ∧ f_{2}(i) = g_{2}(i) ∧ … ∧ f_{n}(i) = g_{n}(i)} u F. Zato je i X ∩ Y ∈ F, pa pošto X ∩ Y ⊆ {i ∈ I : R̄_{i}(g_{1}(i), g_{2}(i), …, g_{n}(i))}, i {i ∈ I : R̄_{i}(g_{1}(i), g_{2}(i), …, g_{n}(i))} ∈ F. Za drugu implikaciju dokaz je analogan.

(b) Obeležimo radi kraćeg zapisa f = ⟨Ḡ_{i}(f_{1}(i), f_{2}(i), …, f_{n}(i)) : i ∈ I⟩ i g = ⟨Ḡ_{i}(g_{1}(i), g_{2}(i), …, g_{n}(i)) : i ∈ I⟩. Kako su skupovi {i ∈ I : f_{1}(i) = g_{1}(i)}, {i ∈ I : f_{2}(i) = g_{2}(i)}, …, {i ∈ I : f_{n}(i) = g_{n}(i)} u F, a {i ∈ I : f_{1}(i) = g_{1}(i)} ∩ {i ∈ I : f_{2}(i) = g_{2}(i)} ∩ … ∩ {i ∈ I : f_{n}(i) = g_{n}(i)} ⊆ {i ∈ I : f(i) = g(i)} sledi da je i {i ∈ I : f(i) = g(i)} ∈ F, tj. f^{F} = g^{F}. □

Prethodna lema pokazuje da su relacije i funkcije modela ∏_{F} A_{i} dobro

definisane, odnosno da njihova definicija ne zavisi od izbora predstavnika klasa f_{1}^{F} , f_{2}^{F} , …, f_{n}^{F}.

Lema 2.1.3 Neka je jezik L′ ekspanzija jezika L i za i ∈ I A_{i} model jezika L a B_{i} ekstenzija modela A_{i} na jezik L′. Tada je ∏_{F} B_{i} ekspanzija modela

∏_{F} A_{i} za svaki filter F na I.

Dokaz. Kako za svako i ∈ I modeli A_{i} i B_{i} imaju isti domen, i ∏_{F} A_{i} i ∏_{F} B_{i}

imaju isti domen. Kako interpretacija svakog znaka jezika L na modelima ∏_{F} A_{i} i ∏_{F} B_{i} zavisi samo od interpretacije tog znaka na modelima A_{i} i B_{i}

koje su iste, i interpretacije u ta dva modela su iste. □

2.2 Fundamentalna teorema

U ovom odeljku prikazana je fundamentalna teorema o ultraproizvodima i neke njene primene. Ako je t(x_{1}, x_{2}, …, x_{n}) neki term jezika L, B model tog jezika a b_{1}, b_{2}, …, b_{n} ∈ B, sa t^{B}[b_{1}, b_{2}, …, b_{n}] označićemo vrednost izraza koji se dobija kada se u t svaki znak jezika L zameni njegovom interpretacijom u modelu B, a svaka pojava promenljive x_{i} elementom b_{i}. Slično, ako je φ(x_{1}, x_{2}, …, x_{n}) formula jezika L, sa φ^{B}[b_{1}, b_{2}, …, b_{n}] označićemo vrednost izraza (⊤ ili ⊥) koji se dobija kada se u φ svaki znak jezika L zameni njegovom interpretacijom u modelu B, a svaka pojava promenljive x_{i} elementom b_{i}.

Teorema 2.1 (Łoš) Neka je A = ∏_{i∈I} A_{i}/F ultraproizvod. Tada:

(a) za svaki term t(x_{1}, x_{2}, …, x_{n}) jezika L i elemente f_{1}^{F} , f_{2}^{F} , …, f_{n}^{F} ∈ A važi

t^{A}[f_{1}^{F} , f_{2}^{F} , …, f_{n}^{F}] = ⟨t^{A_{i}}[f_{1}(i), f_{2}(i), …, f_{n}(i)] : i ∈ I⟩^{F};

(b) za svaku formulu φ(x_{1}, x_{2}, …, x_{n}) jezika L i elemente f_{1}^{F} , f_{2}^{F} , …, f_{n}^{F} ∈ A važi

A ⊧ φ[f_{1}^{F} , f_{2}^{F} , …, f_{n}^{F}] akko {i ∈ I : A_{i} ⊧ φ[f_{1}(i), f_{2}(i), …, f_{n}(i)]} ∈ F;

(c) za svaku rečenicu φ jezika L važi

A ⊧ φ akko {i ∈ I : A_{i} ⊧ φ} ∈ F.

Dokaz.

(a) Dokaz sprovodimo indukcijom po složenosti terma t. Ako je t ≡ x_{i} za neku promenljivu x_{i}, tvrd¯ enje sledi iz činjenice f^{F} = ⟨f(i) : i ∈ I⟩^{F} za sve f^{F} ∈ A. Ako je t ≡ c_{i} za neki znak konstante c_{i}, tvrd¯ enje sledi iz načina na koji je definisano cA_{i} u definiciji 2.1.1. Konačno, neka je

t ≡ G(t_{1}(x_{1}, x_{2}, …, x_{n}), t_{2}(x_{1}, x_{2}, …, x_{n}), …, t_{m}(x_{1}, x_{2}, …, x_{n})),

a t_{1}, t_{2}, …, t_{m} termi za koje važi tvrd¯ enje. Tada t^{A}[f_{1}^{F} , f_{2}^{F} , …, f_{n}^{F}] =

G^{A}(tA_{1}[f_{1}^{F} , f_{2}^{F} , …, f_{n}^{F}], tA_{2}[f_{1}^{F} , f_{2}^{F} , …, f_{n}^{F}], …, tA_{m}[f_{1}^{F} , f_{2}^{F} , …, f_{n}^{F}]), pa,

ako obeležimo g_{i}^{F} = tA_{i}[f_{1}^{F} , f_{2}^{F} , …, f_{n}^{F}] po definiciji 2.1.1

G^{A}(g_{1}^{F} , g_{2}^{F} , …, g_{m}^{F}) = ⟨G^{A_{i}}(g_{1}(i), g_{2}(i), …, g_{n}(i)) : i ∈ I⟩^{F}

= ⟨t^{A_{i}}[f_{1}(i), f_{2}(i), …, f_{n}(i)] : i ∈ I⟩^{F} ,

što je i trebalo dokazati.

(b) Dokaz ponovo sprovodimo indukcijom po složenosti formule φ. Prvo, ako je

φ ≡ R(t_{1}(x_{1}, x_{2}, …, x_{n}), t_{2}(x_{1}, x_{2}, …, x_{n}), …, t_{m}(x_{1}, x_{2}, …, x_{n}))

atomska formula, gde su t_{1}, t_{2}, …, t_{m} termi, onda A ⊧ φ[f_{1}^{F} , f_{2}^{F} , …, f_{n}^{F}]

akko R^{A}(tA_{1}[f_{1}^{F} , f_{2}^{F} , …, f_{n}^{F}], tA_{2}[f_{1}^{F} , f_{2}^{F} , …, f_{n}^{F}], …, tA_{m}[f_{1}^{F} , f_{2}^{F} , …, f_{n}^{F}]).

Obeležimo opet g_{i}^{F} = tA_{i}[f_{1}^{F} , f_{2}^{F} , …, f_{n}^{F}]. Po definiciji 2.1.1 je

R^{A}(g_{1}^{F} , g_{2}^{F} , …, g_{m}^{F})
akko {i ∈ I : R^{A_{i}}(g_{1}(i), g_{2}(i), …, g_{m}(i))} ∈ F
akko {i ∈ I : A_{i} ⊧ φ[f_{1}(i), f_{2}(i), …, f_{n}(i)]} ∈ F.

Dalje, neka je φ ≡ ¬ψ(x_{1}, x_{2}, …, x_{n}). Tada

A ⊧ φ[f_{1}^{F} , f_{2}^{F} , …, f_{n}^{F}]
akko ne važi A ⊧ ψ[f_{1}^{F} , f_{2}^{F} , …, f_{n}^{F}]
akko {i ∈ I : A_{i} ⊧ ψ[f_{1}(i), f_{2}(i), …, f_{n}(i)]} ∉ F
akko {i ∈ I : nije A_{i} ⊧ ψ[f_{1}(i), f_{2}(i), …, f_{n}(i)]} ∈ F
akko {i ∈ I : A_{i} ⊧ φ[f_{1}(i), f_{2}(i), …, f_{n}(i)]} ∈ F.

Ekvivalencija trećeg i četvrtog reda sledi iz činjenice da je F ultrafilter (videti teoremu 1.1). Neka je, zatim, φ ≡ ψ(x_{1}, x_{2}, …, x_{n}) ∧ θ(x_{1}, x_{2}, …, x_{n}). Tada

A ⊧ φ[f_{1}^{F} , f_{2}^{F} , …, f_{n}^{F}]
akko A ⊧ ψ[f_{1}^{F} , f_{2}^{F} , …, f_{n}^{F}] i A ⊧ θ[f_{1}^{F} , f_{2}^{F} , …, f_{n}^{F}]
akko {i ∈ I : A_{i} ⊧ ψ[f_{1}(i), f_{2}(i), …, f_{n}(i)]} ∈ F
i {i ∈ I : A_{i} ⊧ θ[f_{1}(i), f_{2}(i), …, f_{n}(i)]} ∈ F
akko {i ∈ I : A_{i} ⊧ ψ[f_{1}(i), f_{2}(i), …, f_{n}(i)]}
∩{i ∈ I : A_{i} ⊧ θ[f_{1}(i), f_{2}(i), …, f_{n}(i)]} ∈ F
akko {i ∈ I : A_{i} ⊧ ψ[f_{1}(i), f_{2}(i), …, f_{n}(i)]
i A_{i} ⊧ θ[f_{1}(i), f_{2}(i), …, f_{n}(i)]} ∈ F
akko {i ∈ I : A_{i} ⊧ φ[f_{1}(i), f_{2}(i), …, f_{n}(i)]} ∈ F

Konačno, neka φ ≡ (∃x_{0})ψ(x_{0}, x_{1}, …, x_{n}). Tada A ⊧ φ[f_{1}^{F} , f_{2}^{F} , …, f_{n}^{F}] akko postoji f_{0}^{F} takvo da A ⊧ ψ[f_{0}^{F} , f_{1}^{F} , …, f_{n}^{F}] akko postoji f_{0}^{F} takvo da

{i ∈ I : A_{i} ⊧ ψ[f_{0}(i), f_{1}(i), …, f_{n}(i)]} ∈ F.  (1)

Sada iz A_{i} ⊧ ψ[f_{0}(i), f_{1}(i), …, f_{n}(i)] sledi A_{i} ⊧ φ[f_{1}(i), …, f_{n}(i)], pa iz (1) sledi

{i ∈ I : A_{i} ⊧ φ[f_{1}(i), f_{2}(i) …, f_{n}(i)]} ∈ F.

Obratno, neka X = {i ∈ I : A_{i} ⊧ φ[f_{1}(i), f_{2}(i) …, f_{n}(i)]} ∈ F. Za sve i ∈ X definišimo f_{0}(i) kao proizvoljan element skupa A_{i} za kojeg važi A_{i} ⊧ ψ[f_{0}(i), f_{1}(i), …, f_{n}(i)], a za i ∈ I \ X neka je f_{0}(i) proizvoljan element modela A_{i}. Tako smo našli f_{0}^{F} takvo da važi (1).

(c) Ovo je samo specijalan slučaj tvrd¯ enja (b). □

Teorema 2.2 (Teorema kompaktnosti) Neka je Σ neka teorija jezika L, I = [Σ]^{<ℵ_{0}}, i za svako i ∈ I A_{i} model za i. Tada postoji ultrafilter F nad I takav da je ∏_{F} A_{i} model za Σ.

Dokaz. Za svako σ ∈ Σ obeležimo σ̂ = {i ∈ I : σ ∈ i}. Skup E = {σ̂ : σ ∈ Σ} ima s.k.p. jer za sve σ̂_{1}, σ̂_{2}, …, σ̂_{n} ∈ E važi {σ_{1}, σ_{2}, …, σ_{n}} ∈ σ̂_{1} ∩ σ̂_{2} ∩ … ∩ σ̂_{n}. Stoga E možemo proširiti do ultrafiltera F nad I. Iz i ∈ σ̂ sledi σ ∈ i odakle A_{i} ⊧ σ. Znači, σ̂ ⊆ {i ∈ I : A_{i} ⊧ σ}, pa pošto σ̂ ∈ F, zaključujemo {i ∈ I : A_{i} ⊧ σ} ∈ F. Po Łošovoj teoremi ∏_{F} A_{i} je model za

svaku od formula σ ∈ Σ. □

Teorema 2.3 Ako skup rečenica Σ ima proizvoljno velike konačne modele, on ima i beskonačan model.

Dokaz. Neka je za svako n ∈ ω A_{n} model skupa Σ kardinalnosti bar n. Neka je F neglavni ultrafilter nad ω, i obeležimo A = ∏_{F} A_{n}. Iz Łošove teoreme

sledi da je A model za Σ, a za svako n ∈ ω rečenica

(∃x_{1})(∃x_{2}) … (∃x_{n})(x_{1} ≠ x_{2} ∧ x_{1} ≠ x_{3} ∧ … ∧ x_{n−1} ≠ x_{n})

koja kaže da model ima bar n elemenata važi u svim A_{n} osim eventualno konačno mnogo njih, pa važi i u A. Dakle, A je beskonačan model skupa Σ. □ Definicija 2.2.1 Preslikavanje d : A → ∏_{F} A dato sa d(a) = ⟨a : i ∈ I⟩^{F} za

sve a ∈ A naziva se prirodno utapanje.

Lema 2.2.1 Neka je A neki model i F ultrafilter nad skupom I. Tada je prirodno utapanje A u ultrastepen A^{I}/F elementarno utapanje.

Dokaz. Neka je φ(x_{1}, x_{2}, …, x_{n}) formula i a_{1}, a_{2}, …, a_{n} ∈ A. Prema teoremi Łoša imamo

A^{I}/F ⊧ φ[d(a_{1}), d(a_{2}), …, d(a_{n})]
akko {i ∈ I : A ⊧ φ[a_{1}, a_{2}, …, a_{n}]} ∈ F
akko Aφ[a_{1}, a_{2}, …, a_{n}]

što znači da je d elementarno utapanje. □

2.3 Jedna važna teorema

U ovom odeljku koristićemo oznaku F |_{G} = {X ∈ F : X ⊆ G}, gde je F ultrafilter na nekom skupu I i G ⊆ I. Očigledno je F |_{G} = {X ∩ G : X ∈ F } ako je G ∈ F.

Lema 2.3.1 Ako je F filter na I i G ∈ F, onda je F |_{G} filter na G i za X ⊆ I važi

X ∈ F akko X ∩ G ∈ F |_{G}.

Ako je F ultrafilter, onda je i F |_{G} ultrafilter.

Dokaz. Očigledno je F |_{G} ≠ ∅ jer G ∈ F |_{G}. Ako X_{1}, X_{2} ∈ F |_{G}, tada X_{1}, X_{2} ∈ F, pa i X_{1} ∩ X_{2} ∈ F, a jasno je i da važi X_{1} ∩ X_{2} ⊆ G. Ako X_{1} ⊆ X_{2} ⊆ G i X_{1} ∈ F |_{G}, tada iz X_{1} ∈ F sledi X_{2} ∈ F, pa i X_{2} ∈ F |_{G}. Dakle, F |_{G} je filter nad G. Ako važi X ∈ F, onda X ∩ G ∈ F, pa i X ∩ G ∈ F |_{G}. Obratno, ako X ∩ G ∈ F |_{G}, tada iz X ⊇ X ∩ G sledi X ∈ F. Konačno, ako je F ultrafilter i Y ⊆ G, onda ili Y ∈ F ili I \ Y ∈ F. U prvom slučaju je i Y ∈ F |_{G}, a u drugom G \ Y = (I \ Y) ∩ G ∈ F |_{G}. □

Teorema 2.4 Ako je F ultrafilter nad I i G ∈ F, tada za svaku familiju {A_{i} : i ∈ I} modela važi

∏_{F} A_{i} ≅ ∏_{F |_{G}} A_{i}.

Dokaz. Ako je f ∈ ∏_{i∈I} A_{i}, sa f|_{G} obeležavamo restrikciju te funkcije na skup G i definišemo h : ∏_{F} A_{i} → ∏_{F |_{G}} A_{i} na sledeći način: h(f^{F}) = (f|_{G})^{F |_{G}}. Obeležimo A = ∏_{F} A_{i} i B = ∏_{F |_{G}} A_{i} i pokažimo da je h izomorfizam:

• Neka je R neko relacijsko slovo. Tada za sve f_{1}^{F} , f_{2}^{F} , …, f_{n}^{F} ∈ ∏_{F} A_{i}

važi

A ⊧ R[f_{1}^{F} , f_{2}^{F} , …, f_{n}^{F}]
akko {i ∈ I : A_{i} ⊧ R[f_{1}(i), f_{2}(i), …, f_{n}(i)]} ∈ F
akko {i ∈ I : A_{i} ⊧ R[f_{1}(i), f_{2}(i), …, f_{n}(i)]} ∩ G ∈ F |_{G}
akko {i ∈ G : A_{i} ⊧ R[f_{1}(i), f_{2}(i), …, f_{n}(i)]} ∈ F |_{G}
akko B ⊧ R[(f_{1}|_{G})^{F |_{G}}, (f_{2}|_{G})^{F |_{G}}, …, (f_{n}|_{G})^{F |_{G}}]
akko B ⊧ R[h(f_{1}^{F}), h(f_{2}^{F}), …, h(f_{n}^{F})].

• Neka je dalje G neko funkcijsko slovo. Za sve f_{1}^{F} , f_{2}^{F} , …, f_{n}^{F} ∈ ∏_{F} A_{i}

važi

h(G^{A}[f_{1}^{F} , f_{2}^{F} , …, f_{n}^{F}])
= h(⟨G^{A_{i}}[f_{1}(i), f_{2}(i), …, f_{n}(i)] : i ∈ I⟩^{F})
= ⟨G^{A_{i}}[f_{1}|_{G}(i), f_{2}|_{G}(i), …, f_{n}|_{G}(i)] : i ∈ G⟩^{F |_{G}}
= G^{B}[(f_{1}|_{G})^{F |_{G}}, (f_{2}|_{G})^{F |_{G}}, …, (f_{n}|_{G})^{F |_{G}}]
= G^{B}[h(f_{1}^{F}), h(f_{2}^{F}), …, h(f_{n}^{F})].

• Slično, ako je c znak konstante, imamo

h(c^{A})

= h(⟨c^{A_{i}} : i ∈ I⟩^{F})
= ⟨c^{A_{i}} : i ∈ G⟩^{F |_{G}}
= c^{B}.

• Razmatranjem analognim onom iz prve tačke, za R kao relaciju jednakosti, dobijamo f_{1}^{F} = f_{2}^{F} akko h(f_{1}^{F}) = h(f_{2}^{F}), pa je h 1-1 funkcija.

• Ostaje da dokažemo da je h na. Neka je g^{F |_{G}} ∈ B. Definišimo f ∈ ∏_{i∈I} A_{i} na sledeći način: ako i ∈ G, neka f(i) = g(i), a inače neka je f(i) ∈ A_{i} proizvoljno. Očigledno h(f^{F}) = g^{F |_{G}}. □

Prethodna teorema je od izuzetne važnosti, jer nam omogućuje da, pri radu sa ultraproizvodima, ako skup indeksa za koje neko svojstvo važi pripada ultrafilteru, onda možemo bez umanjenja opštosti pretpostaviti da to svojstvo važi za sve indekse.

Posledica 2.3.1 Ako je F glavni ultrafilter na skupu I, onda za neko k ∈ I

važi ∏_{F} A_{i} ≅ A_{k}.

Dokaz. Kao što znamo, svaki glavni ultrafilter sadrži jednoelementni skup, npr. {k} ∈ F. Po prethodnoj teoremi je

∏_{F} A_{i} ≅ ∏_{i∈{k}} A_{i}/F ≅ A_{k},

što je i trebalo dokazati. □

Dakle, kada je konstrukcija ultraproizvoda u pitanju, glavni ultrafilteri nam ne daju ništa novo. Sledeća posledica nam pokazuje da je čak dovoljno razmatranje ograničiti na uniformne ultrafiltere.

Posledica 2.3.2 Neka je F neglavni ultrafilter na skupu I. Tada postoji J ⊆ I i uniforman ultrafilter G na J takav da za svaku familiju {A_{i} : i ∈ I} modela nekog jezika važi

∏_{F} A_{i} ≅ ∏_{G} A_{i}.  (1)

Dokaz. Neka je κ = min{|X| : X ∈ F } i J bilo koji skup iz F kardinalnosti κ. Ako stavimo G = F |_{J}, teorema 2.4 kaže da važi (1). G je ustvari skup svih X ∩ J za X ∈ F, pa kako X ∩ J ∈ F, |X ∩ J| ≥ κ, a iz X ∩ J ⊆ J sledi |X ∩ J| ≤ κ. Dakle, svi skupovi u G su kardinalnosti κ. □

Lema 2.3.2 Ako je A model kardinalnosti ne veće od κ i F κ^{+}-kompletan ultrafilter nad I, onda je A^{I}/F ≅ A.

Dokaz. Dovoljno je dokazati da je prirodno utapanje d iz definicije 2.2.1 na, jer lema 2.2.1 kaže da je d zaista (elementarno) utapanje. U tu svrhu uzmimo f^{F} ∈ A^{I}/F. Za sve a ∈ A definišimo X_{a} = {i ∈ I : f(i) = a}. {X_{a} : a ∈ A ∧ X_{a} ≠ ∅} je particija skupa I na ne više od κ skupova, pa na osnovu leme 1.2.7 postoji a_{0} ∈ A za koje je X_{a_{0}} ∈ F. Zato je d(a_{0}) = f^{F}, pa je d na. □

2.4 Σ_{1}^{1} formule

Predikatski račun ima mnogo dobrih osobina, ali postoje veome bitne matematičke teorije čije se aksiome ne mogu izraziti kao formule predikatskog računa. Stoga postoje razni pokušaji njegovog proširenja, pri kojima se uvek gube neke od dobrih osobina, ali se dobija na izražajnosti. Mi ćemo dati nekoliko takvih proširenja, i za svako od njih odgovarajući oblik teoreme Łoša. Prvo takvo proširenje biće Σ_{1}^{1} formule.

Definicija 2.4.1 Σ_{1}^{1} formula nad jezikom L je formula oblika

ψ ≡ (∃R_{1}R_{2} … R_{m}G_{1}G_{2} … G_{n})φ,

gde su R_{i} relacijska slova za i = 1, 2, …, m, i G_{i} funkcijska slova za i = 1, 2, …, n, (koja se ne pojavljuju u L), φ formula nad jezikom L′ = L ∪ {R_{1}, R_{2}, …, R_{m}, G_{1}, G_{2}, …, G_{n}}.

Uopšte, formule u kojima pored promenljivih mogu biti kvantifikovane i relacije i funkcije nazivaju se formulama drugog reda. Ako je ψ(x_{1}, x_{2}, …, x_{n}) formula iz gornje definicije, kažemo da je elementi a_{1}, a_{2}, …, a_{n} nekog modela A jezika L zadovoljavaju (A ⊧ ψ[a_{1}, a_{2}, …, a_{n}]) akko postoji ekspanzija

A′ = (A, R̄_{1}, R̄_{2}, …, R̄_{m}, Ḡ_{1}, Ḡ_{2}, …, Ḡ_{n})

modela A na L′ u kojoj važi φ[a_{1}, a_{2}, …, a_{n}].

Teorema 2.5 Neka je A = ∏_{F} A_{i}, f_{1}^{F} , f_{2}^{F} , …, f_{r}^{F} ∈ A i ψ(x_{1}, x_{2}, …, x_{r})

Σ_{1}^{1} formula. Ako {i ∈ I : A_{i} ⊧ ψ[f_{1}(i), f_{2}(i), …, f_{r}(i)]} ∈ F, onda A ⊧ ψ[f_{1}^{F} , f_{2}^{F} , …, f_{r}^{F}].

Dokaz. Neka je ψ ≡ (∃R_{1}R_{2} … R_{m}G_{1}G_{2} … G_{n})φ i X = {i ∈ I : A_{i} ⊧ ψ[f_{1}(i), f_{2}(i), …, f_{r}(i)]}. Za sve i ∈ X neka je B_{i} ekspanzija modela A_{i} na L′ takva da B_{i} ⊧ φ[f_{1}(i), f_{2}(i), …, f_{r}(i)]. Na osnovu teoreme Łoša je ∏_{F} B_{i} ⊧ φ[f_{1}^{F} , f_{2}^{F} , …, f_{r}^{F}]. Prema lemi 2.1.3, ∏_{F} B_{i} je ekspanzija modela A

na L′, pa A ⊧ ψ[f_{1}^{F} , f_{2}^{F} , …, f_{r}^{F}]. □

2.5. JEZIK L_{κλ} 37

2.5 Jezik L_{κλ}

Pretpostavimo da, umesto prebrojivo mnogo, imamo na raspolaganju κ promenljivih. Formule jezika L_{κλ} formiraju se na isti način kao formule predikatskog računa, ali su dodata još dva pravila:

• ako je ϕ skup formula jezika L_{κλ} kardinalnosti manje od κ, onda je i ⋀ ϕ formula tog jezika;

• ako je φ formula jezika L_{κλ} i V skup promenljivih kardinalnosti manje od λ, i (∀V)φ je formula tog jezika.

Modeli jezika L_{κλ} su modeli jezika L. Tačnost formule na nekom modelu definiše se na prirodan način: ⋀ ϕ je tačno akko je svaka od formula iz ϕ tačna, a (∀V)φ (npr. za V = {x_{i} : i < β}) je tačno akko je za svaki niz ⟨a_{i} : i < β⟩ elemenata tog modela tačna formula φ za sve valuacije pri kojima promenljive x_{i} iz V redom dobijaju vrednosti a_{i}. Na prirodan način se zatim uvode i oznake ⋁ i (∃V) za skup promenljivih V kardinalnosti manje od λ. (Ustvari, ova definicija tačnosti nije sasvim precizna; ova materija je formalno izložena u [1], str. 286). Neke veoma interesantne osobine mogu se izraziti već u L_{ω_{1}ω_{1}} (ovaj jezik je detaljno opisan u [16]):

Primer. Rečenica

(∀x_{0}x_{1} …)¬ ⋀_{n<ω} R(x_{n+1}x_{n})

kaže da je R dobro zasnovana relacija. Ona omogućava da se, u kombinaciji sa aksiomama linearnog ured¯ enja, izrazi dobro ured¯ enje.

Primer. Rečenica

¬(∃x) ⋀{σ(x) : σ ∈ Σ}

izražava činjenicu da je tip Σ(x) ispušten (videti [2]).

Teorema 2.6 Neka je A = ∏_{F} A_{i}, gde je F κ-kompletan ultrafilter nad

skupom I. Tada (a) za svaku formulu φ(x_{1}, x_{2}, …) jezika L_{κλ} i elemente f_{1}^{F} , f_{2}^{F} , … ∈ A

važi

A ⊧ φ[f_{1}^{F} , f_{2}^{F} , …] akko {i ∈ I : A_{i} ⊧ φ[f_{1}(i), f_{2}(i), …]} ∈ F;

(b) za svaku rečenicu φ jezika L_{κλ} važi

A ⊧ φ akko {i ∈ I : A_{i} ⊧ φ} ∈ F.

Dokaz.

(a) Dokaz se izvodi indukcijom po složenosti formule φ. Iz dokaza Łošove teoreme sledi da tvrd¯ enje važi za atomske formule i da indukcija prolazi za negaciju. Ostaju dva slučaja. Neka je φ = ⋀ ϕ, gde je ϕ skup formula jezika L_{κλ} kardinalnosti manje od κ i neka tvrd¯ enje važi za svaku ψ ∈ ϕ. Tada

A ⊧ φ[f_{1}^{F} , f_{2}^{F} , …]
akko za sve ψ ∈ ϕ važi A ⊧ ψ[f_{1}^{F} , f_{2}^{F} , …]
akko za sve ψ ∈ ϕ važi {i ∈ I : A_{i} ⊧ ψ[f_{1}(i), f_{2}(i), …]} ∈ F
akko {i ∈ I : za sve ψ ∈ ϕ važi A_{i} ⊧ ψ[f_{1}(i), f_{2}(i), …]} ∈ F
akko {i ∈ I : A_{i} ⊧ φ[f_{1}(i), f_{2}(i), …]} ∈ F

pri čemu su treći i četvrti red ekvivalentni zbog κ-kompletnosti F. Konačno, neka je φ = (∃y_{1}y_{2} …)ψ(x_{1}, x_{2}, …, y_{1}, y_{2}, …) gde ψ zadovoljava tvrd¯ enje zadatka. Imamo

A ⊧ φ[f_{1}^{F} , f_{2}^{F} , …]
akko postoje g_{1}^{F} , g_{2}^{F} , … ∈ A takvi da A ⊧ ψ[f_{1}^{F} , f_{2}^{F} , …, g_{1}^{F} , g_{2}^{F} , …]
akko postoje g_{1}^{F} , g_{2}^{F} , … ∈ A takvi da
{i ∈ I : A_{i} ⊧ ψ[f_{1}(i), f_{2}(i), …, g_{1}(i), g_{2}(i), …]} ∈ F
akko {i ∈ I : A_{i} ⊧ φ[f_{1}(i), f_{2}(i), …]} ∈ F,

pri čemu se poslednja ekvivalencija pokazuje kao u dokazu Łošove teoreme. Kako se univerzalni kvantifikator može izraziti preko negacije i egzistencijalnog kvantifikatora, dobijamo da tvrd¯ enje važi za sve formule jezika L_{κλ}.

(b) Ovo je direktna posledica tvrd¯ enja (a). □

2.6. KVANTIFIKATORI Q_{α} 39

2.6 Kvantifikatori Q_{α}

Sledeće proširenje predikatskog računa biće jezik L_{Q_{α}} dobijen dodavanjem kvantifikatora Q_{α} jeziku L i pravila

• ako je φ formula jezika L_{Q_{α}}, i (Q_{α}x_{0})φ je formula jezika L_{Q_{α}}

uobičajenoj definiciji za formiranje formula u L. Modeli jezika L_{Q_{α}} su modeli jezika L, a u modelu je (Q_{α}x_{0})φ tačno akko on sadrži bar ℵ_{α} elemenata x_{0} koji zadovoljavaju φ. Da bismo izbegli nepotrebne komplikacije, pretpostavljaćemo da svi razmatrani modeli kardinalnosti bar ℵ_{α}. Pre nego što pred¯ emo na verziju Łošove teoreme za L_{Q_{α}} potrebno je da uvedemo jedan skup-teoretski pojam.

Definicija 2.6.1 Ako je κ beskonačan kardinal, kažemo da je κ malo za ℵ_{α} ako za svaku kolekciju {λ_{i} : i ∈ I} kardinala manjih od ℵ_{α} takvu da |I| < κ

važi ∏_{i∈I} λ_{i} < ℵ_{α}.

Teorema 2.7 Neka je F ultrafilter nad I, |I| malo za ℵ_{α}, i A = ∏_{F} A_{i}. Tada

za svaku formulu φ jezika L_{Q_{α}} i elemente f_{1}^{F} , f_{2}^{F} , … ∈ A važi

A ⊧ φ[f_{1}^{F} , f_{2}^{F} , …] akko {i ∈ I : A_{i} ⊧ φ[f_{1}(i), f_{2}(i), …]} ∈ F.

Dokaz. Obeležimo prvo X = {i ∈ I : A_{i} ⊧ φ[f_{1}(i), f_{2}(i), …]}. Dokaz opet sprovodimo indukcijom po složenosti formule φ. Svi koraci dokaza prikazani su u dokazu Łošove teoreme osim jednog: neka je φ ≡ (Q_{α}x_{0})ψ(x_{0}, …), i ψ(x_{0}, …) formula za koju tvrd¯ enje važi. Neka je B_{i} = {a ∈ A_{i} : A_{i} ⊧ ψ[a, f_{1}(i), f_{2}(i), …]} za i ∈ X i B_{i} ⊆ A_{i} proizvoljno inače. Definišimo preslikavanje P : ∏_{F} B_{i} → ∏_{F} A_{i} ovako: P (fB^{F}) = fA^{F} (pri

čemu je fB^{F} klasa ekvivalencije funkcije f u ∏_{F} B_{i}, a fA^{F} klasa te funkcije u

∏_{F} A_{i}, a one nisu jednake!) i primetimo da je to očigledno utapanje. Rang te

funkcije je {a ∈ ∏_{F} A_{i} : A ⊧ ψ[a, f_{1}^{F} , f_{2}^{F} , …]}.

(⇐) Ako je X ∈ F, po teoremi 2.4 je

| ∏_{i∈I} B_{i}/F | = | ∏_{i∈X} B_{i}/(F |_{X})|.

Za i ∈ X je |B_{i}| ≥ ℵ_{α}, odakle | ∏_{i∈X} B_{i}/(F |_{X})| ≥ ℵ_{α}, pa i | ∏_{i∈I} B_{i}/F | ≥

ℵ_{α}. Odatle sledi A ⊧ ϕ[f_{1}^{F} , f_{2}^{F} , …].

(⇒) Obratno, ako X ∉ F, onda Y = I \ X ∈ F, pa

| ∏_{i∈I} B_{i}/F | = | ∏_{i∈Y} B_{i}/(F |_{Y})|.

Za i ∈ Y je |B_{i}| < ℵ_{α} odakle

| ∏_{i∈Y} B_{i}/(F |_{Y})| ≤ ∏_{i∈Y} |B_{i}| < ℵ_{α}

jer je |Y | malo za ℵ_{α}. Dakle, ne važi A ⊧ φ[f_{1}^{F} , f_{2}^{F} , …]. □

2.7 Changov kvantifikator

Poslednje proširenje predikatskog računa u ovom izlaganju biće jezik L_{Q} dobijen dodavanjem tzv. Changovog kvantifikatora Q jeziku L i pravila

• ako je φ formula jezika L_{Q}, i (Qx_{0})φ je formula jezika L_{Q}

uobičajenoj definiciji za formiranje formula u L. Model jezika L_{Q} je svaki model A jezika L, a u njemu je (Qx_{0})φ tačno akko on sadrži bar |A| elemenata x_{0} koji zadovoljavaju φ. Pre nego što pred¯ emo na verziju Łošove teoreme za L_{Q} uvešćemo još jedan skup-teoretski pojam.

Definicija 2.7.1 Kardinal λ je κ-normalan ako za svaku kolekciju {λ_{ξ} : ξ < κ} kardinala manjih od λ važi ∏_{ξ<κ} λ_{ξ} < λ^{κ}.

Teorema 2.8 Neka je F regularan ultrafilter nad I, λ |I|-normalan, i A = ∏_{F} A_{i}, gde je svaki od skupova A_{i} kardinalnosti λ. Tada za svaku formulu φ

jezika L_{Q} i elemente f_{1}^{F} , f_{2}^{F} , … ∈ A važi

A ⊧ φ[f_{1}^{F} , f_{2}^{F} , …] akko {i ∈ I : A_{i} ⊧ φ[f_{1}(i), f_{2}(i), …]} ∈ F.

Dokaz. Neka je ponovo X = {i ∈ I : A_{i} ⊧ φ[f_{1}(i), f_{2}(i), …]}. Kao i za teoremu 2.7, dokaz sprovodimo indukcijom po složenosti formule φ. I ovde nam preostaje samo da razmotrimo još samo jedan slučaj: neka je φ ≡ (Qx_{0})ψ(x_{0}, …), i ψ(x_{0}, …) formula za koju tvrd¯ enje važi. Obeležimo B_{i} = {a ∈ A_{i} : A_{i} ⊧ ψ[a, f_{1}(i), f_{2}(i), …]}. Kao i u dokazu teoreme 2.7

imamo bijekciju izmed¯ u ∏_{F} B_{i} i {a ∈ ∏_{F} A_{i} : A ⊧ ψ[a, f_{1}^{F} , f_{2}^{F} , …]}.

(⇐) Ako je X ∈ F, po teoremi 2.4 je

| ∏_{i∈I} B_{i}/F | = | ∏_{i∈X} B_{i}/(F |_{X})|.

Za i ∈ X je |B_{i}| = λ, a kako je svaki regularan ultrafilter i uniforman, |X| = |I| te po teoremi 3.3 imamo | ∏_{i∈X} B_{i}/(F |_{X})| = λ^{|I|},

pa i | ∏_{i∈I} B_{i}/F | = λ^{|I|}. Pošto je po istoj teoremi i |A| = λ^{|I|}, sledi

A ⊧ ϕ[f_{1}^{F} , f_{2}^{F} , …].

(⇒) Obratno, ako X ∉ F, onda Y = I \ X ∈ F, pa

| ∏_{i∈I} B_{i}/F | = | ∏_{i∈Y} B_{i}/(F |_{Y})|.

Za i ∈ Y je |B_{i}| = λ odakle opet

| ∏_{i∈Y} B_{i}/(F |_{Y})| ≤ ∏_{i∈Y} |B_{i}| < λ^{|I|}

jer je λ |Y |-normalan. Dakle, ne važi A ⊧ φ[f_{1}^{F} , f_{2}^{F} , …]. □

Kardinalnost i zasićenost ultraproizvoda

3.1 Kardinalnost ultraproizvoda

Najpre dajemo nekoliko trivijalnih činjenica vezanih za kardinalnost ultraproizvoda. U svakoj od njih podrazumevamo da je F ultrafilter nad skupom I. Takod¯ e, kako kardinalnost ultraproizvoda ne zavisi od skupa na kojem je model definisan, već samo od njegove kardinalnosti, uzećemo da je taj skup neki od kardinala κ, λ, …

Lema 3.1.1 min{κ_{i} : i ∈ I} ≤ | ∏_{F} κ_{i}| ≤ | ∏_{i∈I} κ_{i}|.

Posledica 3.1.1 κ ≤ |κ^{I}/F | ≤ κ^{|I|}.

Posledica 3.1.2 Ako je κ^{|I|} = κ, onda |κ^{I}/F | = κ.

Lema 3.1.2 Ako su κ_{i} i λ_{i} (za i ∈ I) kardinali, i {i ∈ I : λ_{i} ≤ κ_{i}} ∈ F,

onda | ∏_{F} λ_{i}| ≤ | ∏_{F} κ_{i}|.

Teorema koja sledi je veoma opšteg karaktera, i iz nje ćemo izvesti nekoliko značajnih tvrd¯ enja.

Teorema 3.1 (Keisler) Neka su κ, μ nenula kardinali, {λ_{ξ} : ξ < κ} familija kardinala i F ultrafilter nad κ. Dalje, neka je {X_{η} : η < μ} ⊆ F, A_{ξ} = {η < μ : ξ ∈ X_{η}} i ν_{ξ} = |A_{ξ}| za ξ < κ. Tada je

| ∏_{F} λ_{ξ}|^{μ} ≤ | ∏_{F} λ_{ξ}^{ν_{ξ}}|.

Dokaz. Neka je P : ^{μ}( ∏_{ξ<κ} λ_{ξ}) → ^{μ}(∏_{F} λ_{ξ}) prirodno preslikavanje dato sa

P (⟨f(η) : η < μ⟩) = ⟨f(η)^{F} : η < μ⟩.

P je očigledno ”na”. Neka je e_{ξ} : ν_{ξ} → A_{ξ} proizvoljna bijekcija i π_{ξ} : ∏_{η<κ} λ_{η} →

λ_{ξ} uobičajena projekcija: π_{ξ}(f) = f(ξ), za ξ < κ. Za proizvoljno f ∈ ^{μ}( ∏_{ξ<κ} λ_{ξ})

je π_{ξ} ∘ f ∘ e_{ξ} ∈ ^{ν_{ξ}}λ_{ξ}, za sve ξ < κ. Definišimo funkciju Q : ^{μ}( ∏_{ξ<κ} λ_{ξ}) → ∏_{F}^{ν_{ξ}}λ_{ξ}

na sledeći način: Q(f) = ⟨π_{ξ} ∘ f ∘ e_{ξ} : ξ < κ⟩^{F}. Dokažimo: ako su f, g ∈ ^{μ}( ∏_{ξ<κ} λ_{ξ}) takve da P (f) ≠ P (g), onda Q(f) ≠ Q(g).

Zaista, neka P (f) = ⟨f(η)^{F} : η < μ⟩, P (g) = ⟨g(η)^{F} : η < μ⟩ i P (f) ≠ P (g). To znači da postoji η < μ za koje f(η)^{F} ≠ g(η)^{F}, odnosno da A = {ξ < κ : π_{ξ} ∘ f(η) ≠ π_{ξ} ∘ g(η)} ∈ F. Stoga A ∩ X_{η} ∈ F, a ako ξ ∈ A ∩ X_{η} tada postoji ζ < ν_{ξ} takvo da η = e_{ξ}(ζ), tako da π_{ξ} ∘ f ∘ e_{ξ}(ζ) ≠ π_{ξ} ∘ g ∘ e_{ξ}(ζ). Ako obeležimo B = {ξ < κ : π_{ξ} ∘ f ∘ e_{ξ} ≠ π_{ξ} ∘ g ∘ e_{ξ}}, zbog B ⊇ A ∩ X_{η} dobijamo B ∈ F. Odatle Q(f) ≠ Q(g). Iz upravo dokazanog sledi da svakom elementu x ∈ ^{μ}(∏_{F} λ_{ξ}) odgovara neprazan

podskup Q[P^{−1}[{x}]] skupa ∏_{F}^{ν_{ξ}}λ_{ξ} i da su podskupovi koji odgovaraju ra-

zličitim elementima disjunktni, odakle sledi tražena nejednakost. □

Posledica 3.1.3 Neka su κ, μ nenula kardinali, {λ_{ξ} : ξ < κ} familija kardinala i F ultrafilter nad κ. Tada je

| ∏_{F} λ_{ξ}|^{μ} ≤ | ∏_{F} λ_{ξ}^{μ}|.

Dokaz. Sledi direktno iz prethodne teoreme, ako za {X_{η} : η < μ} uzmemo ceo F, uz napomenu da je F sam sebi ustvari (μ^{+}, μ)-regularna familija. □

44 GLAVA 3. KARDINALNOST I ZASIĆENOST ULTRAPROIZVODA

3.1.1 Kardinalnost ultraproizvoda po regularnim ultrafilterima

Teorema 3.2 Ako je svaki od kardinala λ_{ξ} (ξ < κ) beskonačan, i F je ωregularan ultrafilter nad κ, onda | ∏_{F} λ_{ξ}|^{ω} = | ∏_{F} λ_{ξ}|. Posebno, ako je λ ≥ ω

onda |λ^{κ}/F |^{ω} = |λ^{κ}/F |.

Dokaz. Jedna od nejednakosti je ponovo direktna posledica Keislerove teoreme 3.1, gde za {X_{η} : η < μ} uzimamo ω-regularnu familiju za F. Svi ν_{ξ} su tada konačni, te je λ_{ξ}^{ν_{ξ}} = λ_{ξ}. Druga nejednakost je očigledna. □

Lema 3.1.3 Ako je F (κ, κ)-regularan ultrafilter nad κ i κ jako nedostižan kardinal, onda je |κ^{κ}/F | = 2^{κ}.

Dokaz. Primenićemo Keislerovu teoremu na (κ, κ)-regularnu familiju za F, recimo {X_{ξ} : ξ < κ}. Ako je ν_{ξ} = |{η < κ : ξ ∈ X_{η}}|, iz ν_{ξ} < κ i jake nedostižnosti κ sledi 2^{ν_{ξ}} < κ, pa

|κ^{κ}/F | ≥ | ∏_{F} 2^{ν_{ξ}}| ≥ | ∏_{F} 2|^{κ} ≥ 2^{κ}.

Druga nejednakost je očigledna. □

Definicija 3.1.1 Neka je {λ_{ξ} : ξ < κ} familija kardinala i F ultrafilter na κ. Esencijalni supremum familije {λ_{ξ} : ξ < κ} u odnosu na F je ess.sup_{F} {λ_{ξ}} = min{sup{λ_{ξ} : ξ ∈ X} : X ∈ F }.

Teorema 3.3 (Keisler, Prikry) Neka je κ beskonačan, {λ_{ξ} : ξ < κ} familija beskonačnih kardinala, F regularan ultrafilter na κ i μ = ess.sup_{F} {λ_{ξ}}. Tada je

| ∏_{F} λ_{ξ}| = μ^{κ}.

Posebno, ako je λ beskonačan kardinal, tada |λ^{κ}/F | = λ^{κ}.

Dokaz. Neka je {X_{η} : η < κ} κ-regularna familija za F. Keislerova teorema daje nam | ∏_{F} λ_{ξ}|^{κ} = | ∏_{F} λ_{ξ}|. Dovoljno je još dokazati μ ≤ | ∏_{F} λ_{ξ}| ≤ μ^{κ}.

Da bismo pokazali levu nejednakost, posmatraćemo dva slučaja:

1^{∘} μ je nasledni kardinal, npr. μ = ν^{+}. Tada skup X = {ξ < κ : λ_{ξ} = μ} mora biti u F (u suprotnom bismo imali {ξ < κ : λ_{ξ} ≤ ν} ∈ F, odakle ess.sup_{F} {λ_{ξ}} ≤ ν), pa po teoremi 2.4

| ∏_{F} λ_{ξ}| = | ∏_{F |_{X}} λ_{ξ}| = |μ^{|X|}/(F |_{X})| ≥ μ;

2^{∘} μ je granični kardinal. Tada za svako ν < μ skup X_{ν} = {ξ < κ : ν < λ_{ξ}} mora biti u F. Kao i gore

| ∏_{F} λ_{ξ}| = | ∏_{F |_{Xν}} λ_{ξ}| ≥ |ν^{|X_{ν}|}/(F |_{X_{ν}})| ≥ ν

za sve ν < μ.

Dokažimo sada drugu nejednakost. Neka je X ∈ F takvo da μ = sup{λ_{ξ} : ξ ∈ X}. Tada

| ∏_{F} λ_{ξ}| = | ∏_{F |_{X}} λ_{ξ}| ≤ | ∏_{F |_{X}} μ| ≤ |μ^{|X|}| = μ^{κ},

(Poslednja jednakost sledi iz činjenice da je svaki regularan ultrafilter i uniforman). □

Slede dve leme preuzete iz [28] koje u nekim slučajevima omogućavaju efikasniju primenu prethodne teoreme.

Lema 3.1.4 Neka je λ neprebrojiv granični kardinal, I skup kardinalnosti bar cf(λ) i F cf(λ)-opadajuće nekompletan ultrafilter nad I. Tada postoji niz ⟨κ_{i} : i ∈ I⟩ beskonačnih kardinala takav da κ_{i} < λ za sve i ∈ I i ess.sup_{F} {κ_{i}} = λ.

Lema 3.1.5 Ako je ⟨λ_{i} : i ∈ I⟩ niz beskonačnih kardinala, λ = ess.sup_{F} λ_{i}, |I| ≥ cf(λ), ω < λ_{i} < λ za i ∈ I i F regularan ultrafilter nad I, onda postoji niz ⟨κ_{i} : i ∈ I⟩ beskonačnih kardinala takav da κ_{i} < λ_{i} za sve i ∈ I i ess.sup_{F} {κ_{i}} = λ.

3.1.2 Kardinalnost ultraproizvoda po uniformnim ultrafilterima

Definicija 3.1.2 X ⊆ ^{I}κ je skoro disjunktna familija ako

iz f, g ∈ X i f ≠ g sledi |{α ∈ κ : f(α) = g(α)}| < κ.  (2)

Lema 3.1.6 Ako je |I| = κ beskonačan, onda postoji skoro disjunktna familija X ⊆ ^{κ}κ kardinalnosti veće od κ.

Dokaz. Neka je Y familija svih podskupova skupa ^{κ}κ koji zadovoljavaju (2). Jednostavno se dokazuje da svaki lanac u Y u odnosu na relaciju ⊆ ima gornje ograničenje, pa po Zornovoj lemi Y ima maksimalan element X. Dokažimo da je |X| > κ. Jasno je da važi |X| ≥ κ, jer bismo u suprotnom, ako bi za neko λ < κ ⟨f_{ξ} : ξ < λ⟩ bila numeracija elemenata iz X, lako našli g takvo da je X ∪ {g} skoro disjunktna familija: dovoljno bi bilo izabrati g_{η} različito od svih f_{ξ}(η) za ξ < κ i sve η < κ. Pretpostavimo zato da je ⟨f_{ξ} : ξ < κ⟩ jedna numeracija elemenata skupa X. Definišimo funkciju g ∈ ^{κ}κ ovako: neka je g(0) = 0. Ako je definisano g(η) za η < ξ, pošto je skup {f_{η}(ξ) : η < ξ} kardinalnosti manje od κ, možemo definisati g(ξ) kao najmanji element iz κ koji nije u tom skupu. Iz definicije sledi da je g(ξ) ≠ f_{η}(ξ) za sve η < ξ < κ. Neka je f proizvoljan element skupa X, npr. f = f_{ξ}. Videli smo da je skup {α < κ : f_{ξ}(α) = g(α)} sadržan u ξ + 1, pa je kardinalnosti manje od κ. Stoga X ∪ {g} zadovoljava uslov (2). Ovo je u suprotnosti sa izborom X kao maksimalnog elementa skupa Y odakle sledi |X| > κ. □

Lema 3.1.7 Ako je F uniforman ultrafilter na κ i κ ≥ ℵ_{0}, onda je |κ^{κ}/F | > κ.

Dokaz. Ako je X familija iz prethodne leme, neka je A = {f^{F} : f ∈ X}. Ako f, g ∈ X i f ≠ g, pošto |{α < κ : f(α) = g(α)}| < κ i F je uniforman, {α < κ : f(α) = g(α)} ∉ F. Dakle, f^{F} ≠ g^{F}, pa |κ^{κ}/F | ≥ |X| > κ. □

Evo i jedne primene prethodne leme: dokazaćemo da formiranje ultrastepena nije ”komutativna” operacija.

Primer. Neka je |I| = ℵ_{0}, |J| = 2^{ℵ_{0}}, a F uniforman ultrafilter nad J. Prethodna teorema kaže da je |(2^{I})^{J}/F | > 2^{ℵ_{0}}. Med¯ utim, |2^{J}/F | = 2 odakle |(2^{J}/F)^{I}| = 2^{ℵ_{0}} i stoga ne može biti (2^{I})^{J}/F ≅ (2^{J}/F)^{I}.

3.1.3 Kardinalnost ultraproizvoda konačnih skupova

Lema 3.1.8 Ako je κ konačan, a F ultrafilter na I, onda |κ^{I}/F | = κ.

Dokaz. Kako je κ konačan, F je κ^{+}-kompletan, pa tvrd¯ enje sledi iz 2.3.2. □

Lema 3.1.9 Neka su ν_{ξ} za ξ < κ konačni kardinali i F ultrafilter na κ. Ako

za neko n < ω važi {ξ < κ : ν_{ξ} = n} ∈ F  (∗)

onda | ∏_{F} ν_{ξ}| = n.

Dokaz. Obeležimo X_{m} = {ξ < κ : ν_{ξ} = m} za m < ω. Pretpostavka je da za neko n < ω važi X_{n} ∈ F, pa prema teoremi 2.4

∏_{F} ν_{ξ} ≅ ∏_{F |_{Xn}} ν_{ξ}.

Med¯ utim, po prethodnoj lemi | ∏_{F |_{Xn}} ν_{ξ}| = n. □

Posledica 3.1.4 Ako je {ν_{ξ} : ξ < κ} ograničen skup konačnih kardinala (tj. postoji n < ω takvo da za sve ξ < κ ν_{ξ} ≤ n), onda je | ∏_{F} ν_{ξ}| konačan.

Dokaz. Uz notaciju iz prethodnog dokaza imamo κ = X_{0} ∪ X_{1} ∪ … ∪ X_{n}, pa jedan od skupova X_{n} mora biti u F. Ostaje da se pozovemo na tvrd¯ enje leme 3.1.9. □

Posledica 3.1.5 Ako je {ν_{ξ} : ξ < κ} skup konačnih kardinala i F ω^{+}- kompletan ultrafilter na κ, onda je | ∏_{F} ν_{ξ}| konačan.

Uslov (∗) iz leme 3.1.9 ustvari tvrdi da važi ess.sup_{F} {n_{ξ} : ξ < κ} < ω. Sada ćemo se pozabaviti drugim slučajem, tj. ess.sup_{F} {n_{ξ} : ξ < κ} = ω.

Teorema 3.4 Ako je ⟨n_{ξ} : ξ < κ⟩ niz prirodnih brojeva, F λ^{+}-dobar ultrafilter na κ i ess.sup_{F} {n_{ξ} : ξ < κ} = ω, tada | ∏_{F} n_{ξ}| ≥ 2^{λ}.

Dokaz. Definišimo ϕ : [λ]^{<ℵ_{0}} → F ovako: ϕ(X) = {ξ < κ : n_{ξ} ≥ 2^{|X|}}. Zbog uslova ess.sup_{F} {n_{ξ}} = ω mora biti ϕ(X) ∈ F za sve X ∈ [λ]^{<ℵ_{0}} (u suprotnom, iz {ξ < κ : n_{ξ} < 2^{|X|}} ∈ F bi sledilo ess.sup_{F} {n_{ξ}} < 2^{|X|}). Takod¯ e, ϕ je očigledno monotona, pa kako je F λ^{+}-dobar postoji multiplikativna funkcija ψ : [λ]^{<ℵ_{0}} → F takva da ψ ≤ ϕ. Dalje, stavimo X_{ξ} = {η < λ : ξ ∈ ψ({η})} i pokažimo da važi |X_{ξ}| < ℵ_{0} za ξ < κ. Primetimo da je ⋂_{n<ω} ϕ(n) = ∅, tako da za svako ξ < κ postoji

minimalno n ∈ ω (označimo ga sa n(ξ)) takvo da ξ ∉ ϕ(n). Dokažimo da |X_{ξ}| < n(ξ); u suprotnom postoji X′ ⊆ X_{ξ} takav da |X′| = n(ξ). Pošto je ψ multiplikativna, imamo

ξ ∈ ⋂_{η∈X′} ψ({η}) = ψ(X′) ⊆ ϕ(X′) = ϕ(|X′|) = ϕ(n(ξ)),

što je u suprotnosti sa definicijom n(ξ). Dakle, svaki X_{ξ} je konačan. Med¯ utim važi i 2^{|X_{ξ}|} ≤ n_{ξ}. Zaista, za X_{ξ} = ∅ ovo je očigledno, a za X_{ξ} = {η_{i} : i < n} opet iz multiplikativnosti ψ

ξ ∈ ⋂_{i<n} ψ({η_{i}}) = ψ(X_{ξ}) ⊆ ϕ(X_{ξ})

pa tvrdnja sledi iz definicije preslikavanja ϕ. Ona daje | ∏_{ξ<κ}^{X_{ξ}}2| ≤ | ∏_{ξ<κ} n_{ξ}|,

pa treba još dokazati 2^{λ} ≤ | ∏_{F}^{X_{ξ}}2|.

Definišimo Q : ^{λ}2 → ∏_{F}^{X_{ξ}}2 ovako: Q(f) = ⟨f|_{X_{ξ}} : ξ < κ⟩^{F} i pokažimo da je

1-1. Neka su f, g ∈ ^{λ}2 i f ≠ g. Tada postoji η < λ za koje f(η) ≠ g(η), pa {ξ < κ : f|_{X_{ξ}} ≠ g|_{X_{ξ}}} ⊇ ψ({η}), pa pošto ψ({η}) ∈ F sledi Q(f) ≠ Q(g). □

Posledica 3.1.6 Ako je ⟨n_{ξ} : ξ < κ⟩ niz prirodnih brojeva, F κ^{+}-dobar ultrafilter na κ i ess.sup_{F} {n_{ξ} : ξ < κ} = ω, tada | ∏_{F} n_{ξ}| = 2^{κ}.

Dokaz. Jedna nejednakost sledi iz prethodne teoreme, a druga je trivijalna (videti leme 3.1.1 i 3.1.2). □

Teorema 3.5 Neka je ⟨n_{ξ} : ξ < κ⟩ niz prirodnih brojeva, i F ultrafilter na κ. Tada, ako za neko m ∈ ω {ξ < κ : n_{ξ} = m} ∈ F onda | ∏_{F} n_{ξ}| = m, a

inače | ∏_{F} n_{ξ}| ≥ 2^{ℵ_{0}}.

Dokaz. Prva polovina tvrd¯ enja je ustvari lema 3.1.9. Druga polovina sledi iz teoreme 3.4 i činjenice da je svaki ultrafilter ω_{1}-dobar. □

Lema 3.1.10 Ako je F regularan ultrafilter nad κ (κ ≥ ω), onda postoji niz ⟨n_{ξ} : ξ < κ⟩ prirodnih brojeva takav da | ∏_{F} n_{ξ}| = 2^{κ}.

Dokaz. Ako je {X_{ξ} : ξ < κ} κ-regularna familija za F, definišimo b_{ξ} = |{η < κ : ξ ∈ X_{η}}| i n_{ξ} = 2^{b_{ξ}}. Keislerova teorema 3.1 daje nam | ∏_{F} n_{ξ}| ≥ | ∏_{F} 2|^{κ} ≥

2^{κ}, a obratna nejednakost je očigledna. □

3.1.4 Kardinalnost ultraproizvoda beskonačnih skupova

Ako je A = ∏_{F} κ_{i}, tačno jedan od skupova {i ∈ I : κ_{i} < ℵ_{0}} i {i ∈ I : κ_{i} ≥ ℵ_{0}}

je u F, pa po teoremi 2.4 A je izomorfno ultraproizvodu kolekcije konačnih ili ultraproizvodu kolekcije beskonačnih skupova. Prvu od ove dve mogućnosti već smo razmotrili pa ćemo reći nešto i o drugoj.

Teorema 3.6 Ako je F ω^{+}-kompletan ultrafilter, onda |ω^{I}/F | = ℵ_{0}, a ako je ω^{+}-nekompletan onda |ω^{I}/F | ≥ 2^{ℵ_{0}}. Posebno, ako je |I| = ℵ_{0} onda |ω^{I}/F | = 2^{ℵ_{0}}.

Dokaz. Ako je F ω^{+}-kompletan, tvrd¯ enje direktno sledi iz leme 2.3.2. Neka je zato F ω^{+}-nekompletan. Tada po lemi 1.2.7 postoji particija {X_{n} : n ∈ ω} skupa I čiji nijedan element nije u F. Za sve i ∈ I, ako i ∈ X_{n}, stavimo κ_{i} = n. Iz teoreme 3.5 imamo 2^{ℵ_{0}} ≤ | ∏_{F} κ_{i}|, a iz leme 3.1.2 | ∏_{F} κ_{i}| ≤ |ω^{I}/F |.

Konačno, ako je i |I| = ℵ_{0}, iz posledice leme 3.1.1 sledi |ω^{I}/F | ≤ ℵ_{0}^{ℵ_{0}} = 2^{ℵ_{0}}. □

Posledica 3.1.7 Ako je {κ_{i} : i ∈ I} kolekcija beskonačnih kardinala i F ω_{1}-nekompletan ultrafilter nad I, onda | ∏_{F} κ_{i}| ≥ 2^{ℵ_{0}}.

3.2 Zasićenost ultraproizvoda

Ako je A neki model i X ⊆ A, sa (A, a)_{a∈X} označavamo njegovu ekspanziju dobijenu dodavanjem jeziku modela A po jednog konstantnog simbola za svaki element a ∈ X, i njegovom interpretacijom tim elementom. Teorijom nekog modela zovemo skup svih rečenica koje su tačne u tom modelu.

Neka je Φ skup formula sa najviše jednom slobodnom promenljivom x. Kažemo da je Φ zadovoljiv u modelu A ako postoji a ∈ A takvo da za sve φ(x) ∈ Φ važi A ⊧ φ[a]. Kažemo da je Φ konačno zadovoljiv u A ako za svaki konačan Φ_{1} ⊆ Φ postoji a ∈ A takav da za sve φ ∈ Φ_{1} važi A ⊧ φ[a] (ovo je ekvivalentno sa uslovom da je Φ konsistentno sa teorijom modela A).

Definicija 3.2.1 Model A je κ-zasićen ako za svaki podskup X ⊆ A takav da |X| < κ važi da je svaki skup formula Φ sa najviše jednom promenljivom koji je konačno zadovoljiv u (A, a)_{a∈X} zadovoljiv i u (A, a)_{a∈X}.

Ultraproizvodi igraju veoma važnu ulogu u delu teorije modela koji se bavi zasićenim modelima, jer su oni najprirodniji način za konstruisanje takvih modela.

3.2.1 Zasićenost ultraproizvoda po regularnim ultrafilterima

Definicija 3.2.2 Kažemo da je model A κ-univerzalan ako se svaki model kardinalnosti manje od κ elementarno ekvivalentan sa A (tj. koji zadovoljava iste rečenice kao A) može elementarno utopiti u A.

Pojam κ-univerzalnosti je tesno povezan sa κ-zasićenošću, videti [2], glava 5.1.

Lema 3.2.1 Neka je A model na jeziku kardinalnosti najviše κ i F κ-regu-laran ultrafilter na I. Tada je A^{I}/F κ^{+}-univerzalan.

Dokaz. Neka je E (ω, κ)-regularna familija za F, i B model elementarno ekvivalentan sa A^{I}/F, dakle i sa A, |B| ≤ κ. Dalje, neka je Φ teorija modela (B, b)_{b∈B}, i P : Φ → E proizvoljna injekcija.

Neka je i ∈ I proizvoljan. Postoji samo konačno mnogo e ∈ E takvih da i ∈ E, pa samim tim i konačno mnogo φ ∈ Φ takvih da i ∈ P (φ); neka su to φ_{1}, φ_{2}, …, φ_{n}. Rečenica φ_{1} ∧ φ_{2} ∧ … ∧ φ_{n} je tačna u (B, b)_{b∈B}. To znači da, ako su b_{1}, b_{2}, …, b_{k} konstante iz B koje se javljaju u φ_{1} ∧ φ_{2} ∧ … ∧ φ_{n}, i ψ_{1}, ψ_{2}, …, ψ_{n} formule dobijene od φ_{1}, φ_{2}, …, φ_{n} zamenom b_{1}, b_{2}, …, b_{k} promenljivim x_{1}, x_{2}, …, x_{k} kopje se ne javljaju u φ_{1} ∧ φ_{2} ∧ … ∧ φ_{n}, onda je rečenica (∃x_{1}, x_{2}, …, x_{k})(φ_{1} ∧ φ_{2} ∧ … ∧ φ_{n}) tačna u A, pa i u B. Sledi da postoji ekspanzija (A, a_{b}^{i})_{b∈B} modela A u kojoj je φ_{1} ∧ φ_{2} ∧ … ∧ φ_{n} tačna. Definišimo za b ∈ B funkcije f_{b} : I → A ovako: f_{b}(i) = a_{b}^{i} za i ∈ I. Kako iz i ∈ P (φ) sledi (A, f_{b}(i))_{b∈B} ⊧ φ, i P (φ) ∈ F, dobijamo

{i ∈ I : (A, f_{b}(i))_{b∈B} ⊧ φ} ∈ F, dakle ∏_{F}(A, f_{b}(i))_{b∈B} ⊧ φ. Med¯ utim,

∏_{F}(A, f_{b}(i))_{b∈B} = (A^{I}/F, f_{b}^{F})_{b∈B}, a Q : B → A^{I}/F dato sa Q(b) = f_{b}^{F} je

traženo utapanje. □

Napomena. Važi i obrat prethodnog tvrd¯ enja u sledećem smislu: ako je svaki ultrastepen A^{I}/F po F κ^{+}-univerzalan, onda je F κ-regularan (videti [14]).

Metod konstrukcije elementarnog utapanja opisan u prethodnom dokazu (pomoću tzv. elementarnog dijagrama, tj. teorije modela (B, b)_{b∈B}) često se koristi u teoriji modela.

U sledećoj lemi ćemo A^{I}/F posmatrati kao elementarnu ekstenziju modela A (preciznije, A se elementarno utapa u A^{I}/F, videti 2.2.1).

Lema 3.2.2 Neka je A model na jeziku kardinalnosti najviše κ, i F κ-re-gularan ultrafilter na I. Tada za svaki X ⊆ A takav da je |X| < κ, svaki skup Φ formula tog jezika sa najviše jednom slobodnom promenljivom koji je konačno zadovoljiv u (A, a)_{a∈X} je zadovoljiv u (A^{I}/F, a)_{a∈X}.

Dokaz. Kako je Φ skup formula konzistentan sa teorijom modela (A, a)_{a∈X}, postoji model (B, b_{a})_{a∈X} elementarno ekvivalentan sa (A, a)_{a∈X} takav da je Φ zadovoljen u njemu. Med¯ utim, prema prethodnoj lemi (B, b_{a})_{a∈X} se može elementarno utopiti u (A^{I}/F, a)_{a∈X}, jer je (A^{I}/F, a)_{a∈X} ≅ ∏_{F}(A, a)_{a∈X}, pa

je Φ i u njemu zadovoljiv. □

Pre nego što pred¯ emo na glavno tvrd¯ enje ovog odeljka, treba nam jedno važno tvrd¯ enje teorije modela. Za početak, ⟨A_{ξ} : ξ < α⟩ je elementarni lanac ako za sve ξ_{1} < ξ_{2} < α važi A_{ξ_{1}} ≺ A_{ξ_{2}} (A_{ξ_{1}} je elementarni podmodel modela A_{ξ_{2}}). Ako je ⟨A_{ξ} : ξ < α⟩ elementarni lanac, na prirodan način se definiše

model ⋃_{ξ<α} A_{ξ}.

Teorema 3.7 (Teorema o elementarnom lancu) Ako je ⟨A_{ξ} : ξ < α⟩ elementarni lanac, onda A_{η} ≺ ⋃_{ξ<α} A_{ξ} za sve η < α.

Dokaz. Ako je A = ⋃_{ξ<α} A_{ξ}, dokažimo da za sve formule φ(x_{1}, x_{2}, …, x_{n}),

sve ξ < α i sve a_{1}, a_{2}, …, a_{n} ∈ A_{ξ} važi

A_{ξ} ⊧ φ[a_{1}, a_{2}, …, a_{n}] akko A ⊧ φ[a_{1}, a_{2}, …, a_{n}]

indukcijom po složenosti formule φ. Za atomske formule tvrd¯ enje očigledno važi, a prelazak sa φ i ψ na ¬φ i φ ∧ ψ takod¯ e je jednostavan. Zato neka je ψ ≡ (∃x_{0})φ(x_{0}, x_{1}, …, x_{n}), ξ < α i a_{1}, …, a_{n} ∈ A_{ξ}. Ako A_{ξ} ⊧ ψ[a_{1}, …, a_{n}], onda postoji a_{0} ∈ A_{ξ} takav da A_{ξ} ⊧ φ[a_{0}, a_{1}, …, a_{n}], pa kako i a_{0} ∈ A, prema indukcijskoj hipotezi sledi A ⊧ φ[a_{0}, a_{1}, …, a_{n}], dakle i A ⊧ ψ[a_{1}, …, a_{n}]. Obratno, neka A ⊧ ψ[a_{1}, …, a_{n}]. To znači da postoji a_{0} ∈ A takav da A ⊧ φ[a_{0}, a_{1}, …, a_{n}]. Za neko η < α je a_{0} ∈ A_{η}. Ako η ≤ ξ, tada a_{0} ∈ A_{ξ}, i tvrd¯ enje je očigledno, a inače imamo A_{η} ⊧ ψ[a_{1}, …, a_{n}], pa kako je A_{ξ} ≺ A_{η} i A_{ξ} ⊧ ψ[a_{1}, …, a_{n}]. □

Teorema 3.8 Neka je A model na jeziku kardinalnosti najviše κ takav da ℵ_{0} ≤ |A| ≤ 2^{κ}. Tada on ima κ^{+}-zasićenu elementarnu ekstenziju kardinalnosti 2^{κ}.

Dokaz. Neka je F regularan ultrafilter na I, (|I| = κ). Konstruisaćemo elementarni lanac ⟨B_{ξ} : ξ < 2^{κ}⟩ modela na sledeći način: neka je B_{0} = A, za ξ < 2^{κ} B_{ξ+1} neka je ekstenzija B_{ξ} izomorfna sa B_{ξ}^{I}/F i za granični ordinal ξ < 2^{κ} neka je B_{ξ} = ⋃_{η<ξ} B_{η}. Konačno, neka je B = ⋃_{ξ<2^{κ}} B_{ξ}. Indukcijom

se, uz upotrebu Keisler-Prikryjeve teoreme, lako pokazuje da važi |B_{ξ}| = 2^{κ} za sve ξ < 2^{κ} i |B| = 2^{κ}, a prema teoremi o elementarnom lancu B je elementarna ekstenzija svakog od modela B_{ξ}, pa i modela A. Dokažimo još da je κ^{+}-zasićen. Neka je X ⊆ B kardinalnosti najviše κ, i Φ skup formula sa najviše jednom slobodnom promenljivom x konsistentan sa teorijom modela (B, b)_{b∈X}. Pošto je cf(2^{κ}) > κ, postoji ξ < 2^{κ} takav da X ⊆ B_{ξ}. Kako je Φ tada skup formula konsistentan sa teorijom modela (B_{ξ}, b)_{b∈X}, prema lemi 3.2.2 postoji c ∈ B_{ξ+1} takav da (B_{ξ+1}, b)_{b∈X} ⊧ Φ[c]. Kako je B_{ξ+1} ≺ B, sledi (B, b)_{b∈X} ⊧ Φ[c]. □

Model B dobijen kao u prethodnom dokazu, je tzv. granični ultrastepen. Za kraj ovog odeljka, evo dva važna rezultata, od kojih se prvi direktno nastavlja na prethodna tvrd¯ enja, a drugi je karakterizacija elementarne ekvivalencije modela preko ultrastepena, iz koje direktno sledi da su dva modela elementarno ekvivalentna akko imaju izomorfne ultrastepene. Dokaz ovih rezultata može se naći u [31] ili [2] (teorema 13.19).

Teorema 3.9 (Shelah) Neka je λ = λ^{<κ} i κ ≥ ω. Tada postoji regularan ultrafilter F nad λ takav da:

(a) ako je A model takav da |A| < κ, tada je A^{λ}/F λ^{+}-zasićen;

(b) ako je A ≡ B, |A| < κ i |B| < κ, onda A^{λ}/F ≅ B^{λ}/F.

3.2.2 Zasićenost ultraproizvoda po dobrim ured¯ enjima

U ovom odeljku videćemo kako se tvrd¯ enje teoreme 3.8 može dobiti direktno preko ultraproizvoda, ako koristimo ω_{1}-nekompletne λ-dobre ultrafiltere (taj zahtev je jači od regularnosti, videti lemu 1.2.22).

Teorema 3.10 Neka je κ beskonačan, a λ neprebrojiv kardinal, i F ω_{1}-ne-kompletan λ-dobar ultrafilter na κ. Ako je {A_{ξ} : ξ < κ} familija modela na jeziku kardinalnosti manje od λ, tada je ∏_{F} A_{ξ} λ-zasićen.

Dokaz. Obeležimo A = ∏_{F} A_{ξ}, i neka je X ⊆ A takav da |X| < λ, a Φ

skup formula sa najviše jednom slobodnom promenljivom konačno zadovoljiv u (A, a)_{a∈X}. Naravno, svako a ∈ X je oblika f_{a}^{F} za neko f_{a} ∈ ∏_{ξ<κ} A_{ξ}.

Definišimo g : [Φ]^{<ℵ_{0}} → F ovako: za ψ ⊆ Φ, |ψ| < ℵ_{0},

g(ψ) = {ξ < κ : ψ je zadovoljivo u (A_{ξ}, f_{a}(ξ))_{a∈X}}.

g je dobro definisano jer, ako obeležimo φ_{ψ} = (∃x) ⋀_{φ∈ψ} φ(x), iz (A, a)_{a∈X} ⊧ φ_{ψ} sledi {ξ < κ : (A_{ξ}, f_{a}(ξ))_{a∈X} ⊧ φ_{ψ}} ∈ F, dakle i g(ψ) ∈ F. Očigledno, g je i monotona. Neka je ⟨X_{n} : n < ω⟩ opadajući niz elemenata iz F sa praznim presekom čiju egzistenciju daje uslov ω_{1}-nekompletnosti (dakle i ω-opadajuće nekompletnosti). Definišimo g′ : [Φ]^{<ℵ_{0}} → F ovako: g′(ψ) = g(ψ) ∩ X_{|ψ|}. Jasno, i g′ je monotona i g′ ≤ g. Kako je F λ-dobar i |Φ| < λ, postoji multiplikativna funkcija h : [Φ]^{<ℵ_{0}} → F takva da h ≤ g′. Definišimo za ξ < κ Φ(ξ) = {φ ∈ Φ : ξ ∈ h({φ})} i pokažimo da su svi skupovi Φ(ξ) konačni. Zaista, neka je n(ξ) najmanji prirodan broj takav da ξ ∉ X_{n}. Iz |Φ(ξ)| ≥ n(ξ) sledilo bi da postoji Φ′ ⊆ Φ(ξ), |Φ′| = n(ξ), pa bi iz multiplikativnosti h sledilo

ξ ∈ ⋂_{φ∈Φ′} h({φ}) = h(Φ′) ⊆ g′(Φ′) ⊆ A_{|Φ′|} = A_{n(ξ)},

kontradikcija (uporediti sa dokazom leme 1.2.22 i teoreme 3.4). Dakle, za sve ξ < κ Φ(ξ) je konačan, pa je zadovoljiv u (A_{ξ}, f_{a}(ξ))_{a∈X}, tj. postoji f ∈ ∏_{ξ<κ} A_{ξ} takvo da (A_{ξ}, f_{a}(ξ))_{a∈X} ⊧ Φ(ξ)[f(ξ)]. Med¯ utim, za svako φ ∈ Φ

imamo

{ξ < κ : (A_{ξ}, f_{a}(ξ))_{a∈X} ⊧ φ[f(ξ)]} ⊇ {ξ < κ : φ ∈ Φ(ξ)} = h({φ}) ∈ F.

Iz Łošove teoreme sada direktno sledi (A, a)_{a∈X} ⊧ Φ[f^{F}]. □

Napomena. Ponovo imamo i neku vrstu obrata, jer važi: ako je svaki ultraproizvod po F λ-zasićen, onda F mora biti λ-dobar (videti [11]).

Kako su zasićeni modeli jedinstveni (do na izomorfizam), videti [2] ili [1], zaključujemo da se svaki zasićen model može predstaviti u obliku ultraproizvoda.

Ultraproizvodi parcijalnih ured¯ enja

4.1 Uopšteno o parcijalnim ured¯ enjima

Lema 4.1.1 Ako je F proizvoljan filter nad I, a A_{i} = (A_{i}, R^{A_{i}}) modeli takvi da X = {i ∈ I : A_{i} je parcijalno ured̄enje} ∈ F, onda je i A = ∏_{F} A_{i}

parcijalno ured̄enje.

Dokaz. Dokaz ćemo izvesti i za stroga parcijalna ured¯ enja, kada je relacija poretka irefleksivna, i kada je ona refleksivna. Dovoljno je pokazati da se sledeće četiri formule očuvavaju formiranjem redukovanih proizvoda:

(1a) (∀x)R(x, x): neka je f^{F} ∈ A; tada za sve i ∈ X važi R^{A_{i}}[f(i), f(i)], pa X ⊆ {i ∈ I : A_{i} ⊧ R[f(i), f(i)]}, odakle {i ∈ I : A_{i} ⊧ R[f(i), f(i)]} ∈

F, i A ⊧ R[f^{F} , f^{F}];

(1b) (∀x)¬R(x, x): potpuno analogno dobijamo A ⊧ ¬R[f^{F} , f^{F}];

(2) (∀x, y)(R(x, y) ∧ R(y, x) ⇒ x = y): neka f^{F} , g^{F} ∈ A, A ⊧ R[f^{F} , g^{F}] i A ⊧ R[g^{F} , f^{F}]. Tada Y_{1} = {i ∈ I : A_{i} ⊧ R[f(i), g(i)]} ∈ F i Y_{2} = {i ∈ I : A_{i} ⊧ R[g(i), f(i)]} ∈ F, pa i Y = Y_{1} ∩ Y_{2} ∩ X ∈ F. Za sve i ∈ Y važi f(i) = g(i). Dakle, Y ⊆ {i ∈ I : f(i) = g(i)}, odakle {i ∈ I : f(i) = g(i)} ∈ F, tj. f^{F} = g^{F}; (3) (∀x, y, z)(R(x, y) ∧ R(y, z) ⇒ R(x, z)): neka su f^{F} , g^{F} , h^{F} ∈ A i važi

A ⊧ R[f^{F} , g^{F}] i A ⊧ R[g^{F} , h^{F}]. Tada, ako obeležimo Y_{1} = {i ∈ I : A_{i} ⊧ R[f(i), g(i)]} i Y_{2} = {i ∈ I : A_{i} ⊧ R[g(i), h(i)]}, imamo Y_{1}, Y_{2} ∈ F, pa i Y = Y_{1} ∩Y_{2} ∩X ∈ F. Y ⊆ {i ∈ I : A_{i} ⊧ R[f(i), h(i)]}, odakle {i ∈ I : A_{i} ⊧ [f(i), h(i)]} ∈ F, tj. A ⊧ R[f^{F} , h^{F}]. □

Sledeće tvrd¯ enje je direktna posledica Łošove teoreme. Dovoljno je samo primetiti da su sve aksiome parcijalnog ured¯ enja, kao i

(∀x, y)(x ≠ y ⇒ R(x, y) ∨ R(y, x)),  (1)

rečenice prvog reda.

Lema 4.1.2 Ako je F ultrafilter nad I, a A_{i} = (A_{i}, R^{A_{i}}) modeli takvi da X = {i ∈ I : A_{i} je linearno ured̄enje} ∈ F, onda je i A = ∏_{F} A_{i} linearno

ured̄enje.

Prethodnu teoremu nije moguće poboljšati u smislu uzimanja proizvoljnog filtera. To pokazuje sledeći primer.

Primer. Neka su A_{i} za i ∈ I linearna ured¯ enja, |A_{i}| ≥ 2, i F filter koji nije ultrafilter. Tada ne važi (1). Zaista, neka su X i Y podskupovi skupa I takvi da X ∪ Y = I i nijedan od njih nije u F (videti teoremu 1.1). Neka su, za sve i ∈ I, a_{i}, b_{i} ∈ A_{i} različiti elementi takvi da A_{i} ⊧ R[a_{i}, b_{i}]. Tada definišimo a, b ∈ A ovako:

a(i) = \{ \begin{matrix}a_{i}, & i ∈ X \\ b_{i}, & i ∈ Y \end{matrix} i b(i) = \{ \begin{matrix}b_{i}, & i ∈ X \\ a_{i}, & i ∈ Y. \end{matrix}

Nije ispunjeno ni A ⊧ R[a, b] ni A ⊧ R[b, a], pa A nije linearno ured¯ enje.

4.2 Dobra ured¯ enja

4.2.1 Osnovno tvrd¯ enje

U ovom odeljku bavićemo se dobrim ured¯ enjem. Podsetimo se, linearno ured¯ enje (B, R) zovemo dobrim ako ne postoji beskonačan opadajući niz, tj. niz ⟨b_{n} : n ∈ ω⟩ takav da za sve n ∈ ω važi R(b_{n+1}, b_{n}). Pošto pretpostavljamo da je svaki od modela A_{ξ} dobro ured¯ enje za sve ξ < κ, svaki od njih je izomorfan sa nekim ordinalom, pa možemo pretpostaviti bez umanjenja opštosti da su u pitanju neki ordinali, npr. {α_{ξ} : ξ < κ}. Konačno, neka je F ultrafilter nad κ. Za početak, zanima nas kada je A = ∏_{F} α_{ξ} dobro

ured¯ enje. Prvo ćemo dokazati da osobina dobre ured¯ enosti ne može da se iskaže skupom rečenica prvog reda što znači da ne možemo koristiti teoremu Łoša.

Lema 4.2.1 Osobina ”biti dobro ured̄enje” ne može se izraziti skupom rečenica prvog reda.

Dokaz. Neka je φ_{1} rečenica koja kaže da je R relacija strogog linearnog ured¯ enja:

(∀x)¬R(x, x) ∧ (∀x)(∀y)(R(x, y) ⇒ ¬R(y, x))
∧(∀x)(∀y)(∀z)(R(x, y) ∧ R(y, z) ⇒ R(x, z))
∧(∀x)(∀y)(R(x, y) ∨ R(y, x)).

Obeležimo sa φ rečenicu

φ_{1} ∧ (∃x)(∀y)(R(y, x) ∨ x = y)∧
(∀x)((∃y)R(y, x) ⇒ (∃z)(R(z, x) ∧ (∀t)(R(t, x) ⇒ ¬R(z, t)))).

Ona govori da je R strogo linearno ured¯ enje sa najvećim elementom u kojem svaki element (osim eventualno najmanjeg) ima neposrednog prethodnika. Jasno je da postoje proizvoljno veliki konačni dobro ured¯ eni modeli ove rečenice, ali ona nema dobro ured¯ en beskonačan model. Ako bi dobra ured¯ enost mogla biti izražena rečenicom ψ prvog reda, i φ∧ψ bi bila rečenica prvog reda, i ovo bi se kosilo sa teoremom 2.3. □

Napomena. Osobina ”biti dobro ured¯ enje” ne može se izraziti ni u jeziku L_{ω_{1},ω}, videti [16].

Teorema 4.1 Neka je α_{ξ} > 0 za ξ < κ.

(a) Ako postoji n ∈ ω takvo da {ξ < κ : α_{ξ} < n} ∈ F, tada je A dobro ured̄enje, štaviše konačno je.

(b) Ako takvo n ne postoji, tada je A dobro ured̄enje akko je F ω_{1}-kompletan.

Dokaz.

(a) Bez umanjenja opštosti možemo pretpostaviti da je za neko n ∈ ω {ξ < κ : α_{ξ} < n} = I, pa treba samo primeniti posledicu leme 3.1.9.

(b) (⇒) Obeležimo X_{n} = {ξ < κ : α_{ξ} ≥ n}. Po pretpostavci je X_{n} ∈ F za sve n ∈ ω. Ako je F ω_{1}-nekompletan, prema lemi 1.2.9 postoji opadajući niz ⟨Y_{n} : n ∈ ω⟩ skupova iz F takav da ⋂_{n∈ω} Y_{n} = ∅;

možemo pretpostaviti i da je Y_{0} = Y_{1} = κ. Tada, ako obeležimo Z_{n} = X_{n} ∩Y_{n}, i ⟨Z_{n} : n ∈ ω⟩ je opadajući niz takav da ⋂_{n∈ω} Z_{n} = ∅.

Dalje, α_{ξ} ima lanac dužine bar n ako ξ ∈ Z_{n}; neka je to ⟨x_{k}^{ξ} : k < n⟩ u opadajućem poretku: x_{k}^{ξ} > x_{l}^{ξ} za k < l < n. Definišimo sada niz ⟨x_{k}^{F} : k < ω⟩ elemenata iz A ovako: x_{k}(ξ) = x_{m}^{ξ}, gde je m = min{k, max{n ∈ ω : ξ ∈ Z_{n}} − 1}. Kako je {ξ ∈ κ : x_{k}(ξ) > x_{k+1}(ξ)} = Z_{k+1} ∈ F, to je beskonačan opadajući niz u A, koje zato ne može biti dobro ured¯ enje.

(⇐) Neka je F ω_{1}-kompletan. Ponovo iz Łošove teoreme sledi da je A linearno ured¯ en. Stoga pretpostavimo da u A postoji beskonačan opadajući niz x_{0}^{F} > x_{1}^{F} > … Obeležimo X_{n} = {ξ ∈ κ : x_{n}(ξ) > x_{n+1}(ξ)} za n ∈ ω. Kako je svaki X_{n} u F, a F ω_{1}-kompletan, sledi da je i W = ⋂_{n∈ω} X_{n} ∈ F, pa za proizvoljno ξ ∈ W imamo

beskonačan opadajući niz x_{0}(ξ) > x_{1}(ξ) > …, kontradikcija sa činjenicom da je α_{ξ} dobro ured¯ en. □

4.2.2 Fiksne tačke višeg reda normalnih funkcija

U ovom odeljku ćemo bliže proučiti strukturu fiksnih tačaka višeg reda za normalne funkcije, uvedenu u [36].

Definicija 4.2.1 Ako je γ neki ordinal, funkcija p : γ → Ord je normalna ako za sve α, β ∈ dom(p) važi:

• monotonost: iz α < β sledi p(α) < p(β);

• neprekidnost: ako je α granični ordinal, onda p(α) = sup_{β<α} p(β).

Primetimo da, ako je p normalna funkcija, α ∈ dom(p) granični ordinal i ⟨α_{ξ} : ξ < β⟩ rastući niz kofinalan u α, onda je p(α) = sup_{ξ<β} p(α_{ξ}).

Sada ćemo definisati niz funkcija {p_{ξ} : ξ < κ^{+}}, zatim pokazati opravdanost te definicije, i tu oznaku koristiti u ovom i sledećem odeljku.

Definicija 4.2.2 Neka je p : κ^{+} → κ^{+} normalna funkcija. Definišimo niz funkcija ⟨p_{ξ} : ξ < κ^{+}⟩ na sledeći način:

• p_{0} = p;

• p_{ξ+1}(α) je α-ta fiksna tačka funkcije p_{ξ};

• ako je ξ granični ordinal, p_{ξ}(α) je α-ti ordinal koji je fiksan za p_{η} za sve η < ξ.

(Naravno, ”brojanje” fiksnih tačaka u prethodnoj definiciji počinjemo od nule.)

Lema 4.2.2 Neka je p : κ^{+} → κ^{+} normalna funkcija takva da je p(0) > 0, i definišimo niz ⟨e_{ξ} : ξ < κ^{+}⟩ na sledeći način:

• e_{0} = sup_{n<ω} θ_{n}, gde je θ_{0} = 1 i θ_{n+1} = p(θ_{n}) za n < ω;

• e_{ξ+1} = sup_{n<ω} θ_{n}, gde je θ_{0} = e_{ξ} + 1 i θ_{n+1} = p(θ_{n}) za n < ω;

• ako je ξ granični ordinal, onda e_{ξ} = sup_{η<ξ} e_{η}.

Tada je ⟨e_{ξ} : ξ < κ^{+}⟩ niz svih fiksnih tačaka funkcije p. Takod̄e, funkcija p_{1} : κ^{+} → κ^{+} koja slika ξ u ξ-tu fiksnu tačku funkcije p je normalna.

Dokaz. Dokažimo prvo da je e_{0} fiksna:

p(e_{0}) = p(sup_{n<ω} θ_{n}) = sup_{n<ω} p(θ_{n}) = sup_{n<ω} θ_{n+1} = e_{0}.

Dalje pokazujemo da je e_{0} prva fiksna tačka: pretpostavimo da postoji α < e_{0} takvo da p(α) = α. Tada θ_{n} ≤ α < θ_{n+1} za neko n ∈ ω, odakle p(θ_{n}) ≤ p(α) < p(θ_{n+1}), tj. θ_{n+1} ≤ α < θ_{n+2}, kontradikcija. Analogno dokazujemo da je svako e_{ξ} fiksno i da izmed¯ u e_{ξ} i e_{ξ+1} nema drugih fiksnih tačaka. Za granični ordinal ξ e_{ξ} je fiksno jer

p(e_{ξ}) = p(sup_{η<ξ} e_{η}) = sup_{η<ξ} p(e_{η}) = sup_{η<ξ} e_{η} = e_{ξ}.

Svi elementi našeg niza su manji od κ^{+} jer je kofinalnost svakog od njih manja od κ^{+}. Konačno, činjenica da je p_{1} normalna funkcija sledi iz definicije niza. □

Dakle, ako je p_{η} normalna, i p_{η+1} je normalna.

Lema 4.2.3 Neka je p : κ^{+} → κ^{+} normalna funkcija takva da je p(0) > 0 i ⟨p_{ξ} : ξ < δ⟩ inicijalni segment niza iz definicije 4.2.2 takav da su sve funkcije p_{ξ} : κ^{+} → κ^{+} normalne za ξ < δ, gde je δ granični ordinal. Definišimo niz ⟨e_{η} : η < κ^{+}⟩ na sledeći način:

• e_{0} = sup_{ξ<δ} θ_{ξ}, gde je θ_{0} = 1, za ξ < δ θ_{ξ+1} = p_{ξ}(θ_{ξ}), i za granične ordinale ξ < δ θ_{ξ} = sup_{ζ<ξ} θ_{ζ};

• e_{η+1} = sup_{ξ<δ} θ_{ξ}, gde je θ_{0} = e_{η} + 1, za ξ < δ θ_{ξ+1} = p_{ξ}(θ_{ξ}), i za granične ordinale ξ < δ θ_{ξ} = sup_{ζ<ξ} θ_{ζ};

• za granični ordinal η e_{η} = sup_{ζ<η} e_{ζ}.

Tada je ⟨e_{η} : η < κ^{+}⟩ upravo skup svih ordinala koji su fiksni za sve funkcije p_{ξ} za ξ < δ. Takod̄e, funkcija p_{δ} : κ^{+} → κ^{+} data sa p_{δ}(η) = e_{η} je normalna funkcija.

Dokaz. Dokažimo prvo da je e_{0} fiksna za sve p_{ξ}. Uzmimo ξ < δ. Kako je e_{0} = sup_{ξ<ζ<δ} θ_{ζ}, i svako θ_{ζ} za ζ > ξ je fiksno za p_{ξ}, sledi da je i e_{0} fiksno za p_{ξ}. Pretpostavimo da postoji α < e_{0} fiksno za sve p_{ξ} (ξ < δ). Tada θ_{ζ} ≤ α < θ_{ζ+1} za neko ζ < δ. Stoga p_{ζ}(θ_{ζ}) ≤ p_{ζ}(α) < p_{ζ}(θ_{ζ+1}), i zato θ_{ζ+1} ≤ α < θ_{ζ+2} = p_{ζ+1}(θ_{ζ+1}), kontradikcija. Analogno dokazujemo da su e_{η+1} fiksne i da izmed¯ u e_{η} i e_{η+1} nema drugih ordinala koji su fiksni za sve p_{ξ} za ξ < δ. Konačno, za granični ordinal η e_{η} je fiksno za sve p_{ξ} kao supremum niza ordinala fiksnih za sve p_{ξ} (ξ < δ), a normalnost funkcije p_{δ} je ponovo direktna posledica definicije. □

Posledica 4.2.1 Sve funkcije p_{ξ} (za ξ < κ^{+}) iz definicije 4.2.2 su normalne i preslikavaju κ^{+} u κ^{+}.

Primetimo još da, ako je p(0) > 0 tada za svaku fiksnu tačku ζ < κ^{+} funkcije p postoji najveći ordinal ξ < κ^{+} takav da je ζ fiksno za p_{ξ}. To je posledica činjenice da p_{ξ+1}(0) > p_{ξ}(0) za sve ξ < κ^{+} (što se jednostavno pokazuje indukcijom), tako da je niz ⟨p_{ξ}(0) : ξ < κ^{+}⟩ kofinalan u κ^{+}, pa ako p_{ξ+1}(0) > ζ, onda ζ nije fiksno za p_{ξ}. Znajući to, nazovimo ζ < κ^{+} fiksnom tačkom reda δ ako ζ ∈ ran(p_{δ}) \ ran(p_{δ+1}).

Napomenimo još jednu važnu činjenicu: ako je ξ_{1} < ξ_{2} < κ^{+}, svaka tačka fiksna za p_{ξ_{2}} fiksna je i za p_{ξ_{1}}.

U narednom odeljku radićemo sa funkcijom p : κ^{+} → κ^{+} datom sa p(μ) = κ^{μ}. Ona je očigledno normalna i p(0) > 0, tako da se gornji rezultati mogu na nju primeniti. Koristićemo i praktičniju oznaku za fiksne tačke: e_{ξ,α} umesto p_{ξ}(α).

4.2.3 Najmanji zanimljiv dobro ured¯ en ultrastepen ordinala

Lema 4.2.4 Neka je F ultrafilter nad I, β > 0 i f ∈ ^{I}(β \ {0}). Tada je

∏_{i∈I}(f(i), <)/F ≅ ({g^{F} ∈ β^{I}/F : g^{F} < f^{F} }, <).

Dokaz. Definišimo funkciju φ : ∏_{i∈I} f(i)/F → {g^{F} ∈ β^{I}/F : g^{F} < f^{F} } ovako:

φ(g_{A}^{F}) = g_{B}^{F}, gde je g_{A}^{F} klasa neke funkcije iz ∏_{i∈I} f(i) u tom proizvodu u

odnosu na F, a g_{B}^{F} klasa te iste funkcije u β^{I} u odnosu na F. Očigledno, φ je utapanje; ostaje da dokažemo da je φ[ ∏_{i∈I} f(i)/F] = {g^{F} ∈ β^{I}/F : g^{F} < f^{F} }.

Jasno je da je leva strana podskup desne. Obratno, ako je g^{F} ∈ β^{I}/F takvo da g^{F} < f^{F}, tada X = {i ∈ I : g(i) < f(i)} ∈ F, pa možemo definisati h^{F} ∈ β^{I}/F ovako: h(i) = g(i) za i ∈ X, i h(i) < f(i) proizvoljno za i ∉ X. Tada je φ(h^{F}) = g^{F}, dakle g^{F} ∈ φ[ ∏_{i∈I} f(i)/F]. □

Lema 4.2.5 Ako je F ω_{1}-kompletan ultrafilter na I i 0 < α < β, onda je α^{I}/F izomorfno sa nekim početnim segmentom β^{I}/F.

Dokaz. Ovo je direktna posledica prethodne leme, ako se uzme u obzir da je β^{I}/F dobro ured¯ eno, pošto je F ω_{1}-kompletan. □

Fiksirajmo sada indeksni skup I i ω_{1}-kompletan ultrafilter F na I. Zahvaljujući prethodnoj lemi, možemo identifikovati α^{I}/F sa nekim početnim segmentom β^{I}/F. Definišimo A_{0} = ∅ i za α ∈ Ord

A_{α} = (α^{I}/F) \ ( ⋃_{β<α} A_{β}).

A_{α+1} je jednoelementan za α ∈ Ord; njegov jedini element je f_{α}^{F}, gde f_{α}(i) = α za i ∈ I. Zaista, ako g^{F} ∈ (α + 1)^{I}/F, onda ili {i ∈ I : g(i) < α} ∈ F ili {i ∈ I : g(i) = α} ∈ F; u prvom slučaju g^{F} ∈ α^{I}/F, a u drugom g^{F} = f^{F}. (Primetimo da je opisani element f_{α}^{F} ustvari slika elementa α pri elementarnom utapanju d : α + 1 → (α + 1)^{I}/F –videti definiciju 2.2.1).

Lema 4.2.6 Za sve granične ordinale α je |A_{cf(α)}| ≤ |A_{α}|.

Dokaz. Neka je ⟨α_{ξ} : ξ < cf(α)⟩ rastući niz kofinalan u α. Definišimo φ : A_{cf(α)} → A_{α} ovako: φ(f^{F}) = g_{f}^{F}, gde g_{f}(i) = α_{f(i)} za i ∈ I. Pokažimo da g_{f}^{F} ∈ A_{α}: očigledno g_{f}^{F} ∈ α^{I}/F; ako bi važilo g_{f}^{F} ∈ β^{I}/F za neko β < α, imali bismo X = {i ∈ I : g_{f}(i) < β} ∈ F. Med¯ utim, postoji ξ_{0} < cf(α) takvo da α_{ξ} > β za ξ > ξ_{0}. Ali to znači da za sve i ∈ X g_{f}(i) = α_{ξ_{i}} za neke ξ_{i} < ξ_{0}, dakle i f(i) < ξ_{0}, što znači da {i ∈ I : f(i) < ξ_{0}} ∈ F, dakle f ∈ ξ_{0}^{I}/F, kontradikcija. φ je očigledno 1-1. □

Lema 4.2.7 Za granični ordinal α važi: A_{α} = ∅ akko je F cf(α)-opadajuće kompletan.

Dokaz.

(⇐) Pretpostavimo da je F cf(α)-opadajuće kompletan, i f^{F} ∈ α^{I}/F takav da f^{F} > f_{β}^{F} (definisano gore) za β < α. Neka je ⟨α_{ξ} : ξ < cf(α)⟩ niz kofinalan u α. Definišimo X_{ξ} = {i ∈ I : f(i) ≥ α_{ξ}}. Jasno je da je ⋂_{ξ<cf(α)} X_{ξ} = ∅, pa iz cf(α)-opadajuće kompletnosti sledi da postoji

ξ < cf(α) za koje X_{μ} ∉ F. Med¯ utim to bi značilo da je f^{F} < f_{α_{ξ}}^{F}, kontradikcija.

(⇒) Neka je F cf(α)-opadajuće nekompletan. Tada postoji opadajući niz ⟨X_{ξ} : ξ < cf(α)⟩ elemenata iz F takav da X_{0} = I i ⋂_{ξ<cf(α)} X_{ξ} = ∅. Neka

je ponovo ⟨α_{ξ} : ξ < cf(α)⟩ niz kofinalan u α. Definišimo za sve i ∈ I f(i) = α_{ξ}, gde je ξ najmanji takav da i ∉ X_{ξ}. Tada je f^{F} > f_{β}^{F} za sve β < α jer, ako α_{ξ} > β, onda {i ∈ I : f(i) > β} ⊇ {i ∈ I : f(i) > α_{ξ}} = X_{ξ}. Sledi da f^{F} ∉ (β + 1)^{I}/F za sve β < α, odakle f^{F} ∈ A_{α}. □

Lema 4.2.8 Ako je α granični ordinal i F cf(α)-opadajuće nekompletan, onda A_{α} ima bar cf(α) elemenata.

Dokaz. U prethodnoj lemi pokazano je da postoji bar jedan takav element g_{0}^{F}. Definišimo za η < cf(α) g_{η+1}(i) = g_{η}(i) + 1, a za granični ordinal η < cf(α) neka je g_{η}(i) = sup_{ξ<η} g_{ξ}(i). ⟨g_{η}^{F} : η < cf(α)⟩ je strogo rastući niz elemenata iz A_{α}. □

S obzirom na lemu 4.2.7, teoremu 1.10, lemu 1.2.9 i našu pretpostavku o ω_{1}-kompletnosti ultrafiltera F, A_{α} može biti neprazno tek za α merljiv kardinal. Stoga će do kraja ovog odeljka κ označavati najmanji kardinal za koji je F κ^{+}-nekompletan (nama će ustvari trebati samo činjenica da je on regularan). Ocenićemo koliko elemenata ima A_{κ}. Za početak, lema koja sledi je analogon poznate Kantorove teoreme o normalnoj formi:

Lema 4.2.9 Ako je κ proizvoljan beskonačan kardinal, svaki nenula ordinal manji od κ^{+} može se na jedinstven način predstaviti u obliku

κ^{α_{1}}β_{1} + κ^{α_{2}}β_{2} + … + κ^{α_{n}}β_{n},

gde je κ^{+} > α_{0} > α_{1} > … > α_{n} i β_{k} < κ za 1 ≤ k ≤ n (operacije u gornjem izrazu su ordinalno sabiranje, množenje i stepenovanje).

Dokaz. Indukcijom po α < κ^{+} dokažimo mogućnost takvog predstavljanja, a na sličan način se dokazuje i jedinstvenost. Neka ono važi za sve β < α, i neka je μ najmanji ordinal takav da κ^{μ} > α. On mora biti nasledni (ako bi bio granični, iz κ^{ξ} ≤ α za sve ξ < μ sledilo bi i κ^{μ} = sup_{ξ<μ} κ^{ξ} ≤ α), npr. μ = α_{1} + 1. Dalje, neka je δ najmanji ordinal takav da je κ^{α_{1}}δ > α. I δ je nasledni, npr. δ = β_{1} + 1. Ako je α = κ^{α_{1}}β_{1} + α′, tada α′ < κ^{α_{1}} ≤ α, pa po indukcijskoj hipotezi α′ = κ^{α_{2}}β_{2} + … + κ^{α_{n}}β_{n}, čime je tvrd¯ enje dokazano. □

Imajući u vidu prethodnu lemu, možemo definisati nivoe ordinala: jedan nivo sastoji se od svih ordinala oblika ξ = κ^{α_{1}}β_{1} + κ^{α_{2}}β_{2} + … + κ^{α_{n−1}}β_{n−1} + κ^{α_{n}}μ, gde su α_{1}, α_{2}, …, α_{n}, β_{1}, β_{2}, …, β_{n−1} fiksirani i μ prolazi kroz κ. Radi lakšeg baratanja ovim oblikom ordinala, označićemo sa ξ̄izraz κ^{α_{1}}β_{1}+κ^{α_{2}}β_{2}+ … + κ^{α_{n−1}}β_{n−1}.

U sledećoj teoremi koristićemo oznake p_{ξ} i e_{ξ,η} iz prethodnog odeljka.

Teorema 4.2 Ako je κ najmanji kardinal za koji je ultrafilter F nad I κ^{+}- nekompletan, onda |A_{κ}| ≥ κ^{+}.

Dokaz. Konstruisaćemo rastući niz ⟨g_{ξ}^{F} : ξ < κ^{+}⟩ elemenata skupa A_{κ} rekurzijom po ξ, tako što ćemo ustvari konstruisati niz funkcija ⟨g_{ξ} : ξ < κ^{+}⟩. Pritom stalno imamo u vidu rezultate lema 4.2.2 i 4.2.3. Za početak neka je g_{0} takva da je g_{0}^{F} najmanji element skupa A_{κ}. Za

ξ = κ^{α_{1}}β_{1} + κ^{α_{2}}β_{2} + … + κ^{α_{n}}β_{n} = ξ̄+ κ^{α_{n}}β_{n}

definisaćemo g_{ξ} tako da zadovoljava sledeće uslove:

(a) ako je η < ξ, tada {i ∈ I : g_{η}(i) < g_{ξ}(i)} ∈ F;

(b) ako je η < ξ i oni su na istom nivou, onda g_{η}(i) < g_{ξ}(i) za sve i ∈ I (ako je to ispunjeno, pišemo g_{η} < g_{ξ});

(c) ako je η < ξ i η̄ = ξ̄, η = η̄ + η_{1}, ξ = ξ̄ + ξ_{1}, tada g_{η} i g_{ξ} moraju zadovoljavati iste uslove koje smo postavili za g_{η_{1}} i g_{ξ_{1}};

(d) ako su η = e_{δ,α} i ξ = e_{δ,β} elementi skupa ran(p_{δ}, tada g_{η} i g_{ξ} moraju zadovoljavati iste uslove koje smo postavili za g_{α} i g_{β} (kao specijalan slučaj za δ = 0 imamo da g_{κ^{α}} i g_{κ^{β}} moraju zadovoljavati iste uslove koje smo postavili za g_{α} i g_{β}).

Pritom, u klauzulama (c) i (d) pod ”uslovima koje smo postavili za g_{α} i g_{β}” podrazumevamo uslove tipa (a)-(d). Imajući u vidu gornja ograničenja, definišemo g_{ξ}.

1^{∘} Ako je ξ = η + 1, stavimo g_{ξ}(i) = g_{η}(i) + 1.

2^{∘} Ako je ξ = ξ̄ + κ^{α}β, α i β su nasledni ordinali, npr. α = α_{1} + 1 i β = β_{1} + 1, stavimo η_{μ} = ξ̄ + κ^{α}β_{1} + κ^{α_{1}}μ za μ < κ. Kako je F κopadajuće nekompletan, postoji niz ⟨X_{ζ} : ζ < κ⟩ elemenata iz F takav

da X_{0} = I, X_{ζ_{1}} ⊇ X_{ζ_{2}} za ζ_{1} < ζ_{2} < κ i ⋂_{ζ<κ} X_{ζ} = ∅. Definišimo sada

g_{ξ}(i) = g_{η_{μ}}(i), gde μ = min{ζ < κ : i ∉ X_{ζ}}.

3^{∘} Ako je ξ = ξ̄+ κ^{α}β i β granični ordinal, onda definišimo η_{μ} = ξ̄+ κ^{α}μ za μ < β i g_{ξ}(i) = sup_{μ<β} g_{η_{μ}}(i). Pošto je β < κ, a κ regularan, imamo g_{ξ}(i) < κ.

4^{∘} Ako je ξ = ξ̄+κ^{α}β, α granični ordinal koji nije fiksan za p_{0} i β nasledni ordinal, npr. β = β_{1} + 1, tada postavimo η_{μ} = ξ̄ + κ^{α}β_{1} + κ^{μ} za μ < α, i definišemo g_{ξ} preko niza ⟨g_{η_{μ}} : μ < α⟩ na isti način kao što je g_{α} definisano preko ⟨g_{μ} : μ < α⟩ (ovo ćemo kasnije nešto detaljnije obrazložiti).

5^{∘} Ako je ξ = ξ̄+e_{δ,μ}β (gde je, podsetimo se, e_{δ,μ} = p_{δ}(μ)), δ = δ_{1} +1 i β i μ su nasledni ordinali, npr. β = β_{1} + 1 i μ = μ_{1} + 1, tada g_{ξ} definišemo na sledeći način: postavimo η_{n} = ξ̄ + e_{δ,μ}β_{1} + θ_{n}, gde θ_{0} = e_{δ,μ_{1}} + 1 i θ_{n+1} = p_{δ_{1}}(θ_{n}) za n < ω; konačno, neka je g_{ξ}(i) = sup_{n<ω} g_{η_{n}}(i).

6^{∘} Ako je ξ = ξ̄ + e_{δ,μ}β, gde je δ granični ordinal, a β i μ su nasledni ordinali, npr. β = β_{1} + 1 i μ = μ_{1} + 1, g_{ξ} se definiše ovako: postavimo η_{ν} = ξ̄+ e_{δ,μ}β_{1} + θ_{ν}, gde θ_{0} = e_{δ,μ_{1}} + 1, θ_{ν+1} = p_{ν}(θ_{ν}) za ν < δ i, ako je ν < δ granični ordinal, tada θ_{ν} = sup_{ζ<ν} θ_{ζ}. Konačno, definišemo g_{ξ} preko ⟨g_{η_{ν}} : ν < δ⟩ na isti način kao što je g_{δ} definisano preko ⟨g_{ν} : ν < δ⟩.

7^{∘} Ako je ξ = ξ̄ + e_{δ,μ}β gde su δ i μ granični ordinali i β je nasledni ordinal, recimo β = β_{1} + 1, neka je η_{ν} = ξ̄ + e_{δ,μ}β_{1} + e_{δ,ν} za ν < μ, i definišimo g_{ξ} preko ⟨g_{η_{ν}} : ν < μ⟩ na isti način kao što je g_{μ} definisano preko ⟨g_{ν} : ν < μ⟩.

Objasnimo bliže šta u nekim od koraka konstrukcije znači ”definišemo g_{ξ} preko niza ⟨g_{η_{μ}} : μ < α⟩ na isti način kao što je g_{α} definisano preko ⟨g_{μ} : μ < α⟩”. U nekom od prethodnih koraka konstrukcije smo definisali g_{α} koristeći neke od (ranije definisanih) g_{μ} (μ < α) pomoću nekog od pravila 1^{∘}−7^{∘}. Sada to isto pravilo upotrebimo za konstrukciju g_{ξ} koristeći naznačene prethodne članove niza. Ovo nam omogućava uslov (d). Pokažimo indukcijom po ξ > 0 simultano da važe uslovi (a)-(d) i

ako smo definisali g_{ξ} preko ⟨g_{η_{μ}} : μ < α⟩, onda g_{ξ} > g_{η_{0}} ≥ g_{0}. (∗)

(Pritom u 1^{∘}, 2^{∘}, 3^{∘} i 5^{∘} smatramo da je g_{ξ} definisan preko ⟨g_{μ} : μ < ξ⟩.) Obeležimo u ostatku dokaza Y_{ηξ} = {i ∈ I : g_{η}(i) < g_{ξ}(i)}. Neka važi (a)-(d) i (∗) za sve η < ξ.

(∗) U slučaju 1^{∘} je g_{ξ} > g_{η} > g_{0} (druga nejednakost važi prema indukcijskoj hipotezi). U slučaju 2^{∘} Y_{η_{0}ξ} = I, pa g_{ξ} > g_{η_{0}} > g_{0}. U slučajevima 3^{∘} i 5^{∘} za svako i ∈ I g_{ξ}(i) je supremum rastućeg niza čiji je prvi član g_{η_{0}}(i) pa, ponovo koristeći indukcijsku hipotezu, imamo g_{ξ} > g_{η_{0}} > g_{0} (za slučaj 5^{∘} g_{ξ} > g_{η_{0}} sledi iz (a)). Konačno, za slučajeve 4^{∘}, 6^{∘} i 7^{∘} (∗) sledi direktno iz definicije g_{ξ}.

(a) Razmotrićemo ovaj uslov za svaki od slučajeva 1^{∘} − 7^{∘} zasebno:

1^{∘} Uslov Y_{ηξ} ∈ F je trivijalno zadovoljen.

2^{∘} Jasno je da je, za μ < κ, skup Y_{η_{μ}ξ} jednak X_{μ} (jer g_{η_{ν}} > g_{η_{μ}} za ν > μ), dakle Y_{η_{μ}ξ} ∈ F. Ali ξ = sup_{μ<κ} η_{μ}, pa za svako η < ξ postoji η_{μ} > η, a po indukcijskoj hipotezi Y_{ηη_{μ}} ∈ F, pa, kako Y_{ηξ} ⊇ Y_{ηη_{μ}} ∩ Y_{η_{μ}ξ}, i Y_{ηξ} ∈ F.

3^{∘} Slično kao gore za zadato η < ξ nalazimo η_{μ} takvo da Y_{ηη_{μ}} ∈ F, ali i Y_{η_{μ}ξ} = I jer je za svako i ∈ I niz ⟨g_{η_{μ}}(i) : μ < κ⟩ strogo rastući (uslov (b)).

4^{∘} Da je Y_{ηξ} ∈ F i u ovom slučaju za η < ξ dokazuje se na isti način kao u dokazu Y_{ηα} ∈ F za η < α, u zavisnosti od toga koja od tačaka konstrukcije je upotrebljena u definiciji g_{α} preko g_{μ} za μ < α. To je moguće zahvaljujući uslovima (c) i (d), koji kažu da g_{ξ} i niz ⟨g_{η_{μ}} : μ < α⟩ zadovoljavaju iste uslove kao g_{κ^{α}} i ⟨g_{κ^{μ}} : μ < α⟩ a zatim i kao g_{α} i ⟨g_{μ} : μ < α⟩.

5^{∘} Dokaz je analogan onom za 3^{∘}, ako pokažemo da je g_{η_{m}} < g_{η_{n}} za sve m < n. Za početak, dokažimo g_{θ_{1}} > g_{θ_{0}}. g_{θ_{1}}(i) je definisano ili (u 5^{∘}) kao supremum rastućeg niza ordinala čiji je prvi član g_{θ_{0}}(i), ili (u slučaju 6^{∘}) preko niza čiji je prvi član g_{θ_{0}}(i) (razlog je to što je, podsetimo se, e_{δ,μ_{1}} fiksno za funkciju p_{δ_{1}}). U prvom slučaju g_{θ_{1}} > g_{θ_{0}} sledi direktno, a u drugom iz (∗). Dalje, g_{θ_{n+1}} = g_{p_{δ_{1}}(θ_{n})} > g_{p_{δ_{1}}(θ_{n−1})} = g_{θ_{n}}. Sada g_{η_{n+1}} > g_{η_{n}} sledi iz uslova (d).

6^{∘} Ovaj slučaj, kao i prethodni, svodimo na 3^{∘} ako pokažemo da niz ⟨g_{η_{ν}} : ν < δ⟩ zadovoljava iste uslove koje smo postavili za niz ⟨g_{ν} : ν < δ⟩ (tj. da za ν_{1} < ν_{2} < δ g_{η_{ν_{1}}} i g_{η_{ν_{1}}} zadovoljavaju iste uslove (a)-(d) kao g_{ν_{1}} i g_{ν_{2}}). Ali, izuzev uslova g_{η_{ν+1}} > g_{η_{ν}}, svi oni su jednostavna posledica definicije, pošto su članovi niza ⟨g_{η_{ν}} : ν < δ⟩ definisani preko prethodnih na isti način kao odgovarajući članovi niza ⟨g_{ν} : ν < δ⟩. Dokažimo taj preostali uslov indukcijom: g_{η_{1}} > g_{η_{0}} dokazujemo kao u slučaju 5^{∘}. Kada je ν < δ granični ordinal, g_{θ_{ν+1}} = g_{p_{ν}(θ_{ν})} > g_{p_{ν}(θ_{0})} = g_{θ_{ν}} (jer je p_{ν}(θ_{0}) upravo θ_{ν} - videti tačku 6^{∘} definicije). Ako imamo g_{η_{n}} > g_{η_{n−1}} jer g_{θ_{n+1}} = g_{p_{n}(θ_{n})} > g_{p_{n}(θ_{n−1})} > g_{p_{n−1}(θ_{n−1})} = g_{θ_{n}} (poslednja nejednakost sledi iz činjenice da je g_{p_{n}(θ_{n−1})}(i) definisano kao supremum niza čiji je prvi član g_{p_{n−1}(θ_{n−1})}(i)). Ostali slučajevi tvrd¯ enja g_{η_{ν+1}} > g_{η_{ν}} za nasledni ordinal ν pokazuju se analogno.

7^{∘} Ovo je potpuno analogno slučaju 4^{∘}.

(b) U slučajevima 1^{∘} i 3^{∘} tvrd¯ enje je opet očigledno, jer je g_{ξ} na svakoj koordinati veći od neposrednog prethodnika na svom nivou. Isti argument može se primeniti i za 2^{∘}, ako primetimo da je u ovom slučaju neposredni prethodnik za ξ baš η_{0}. Sličnu situaciju imamo i u 4^{∘}, jer je g_{ξ} > g_{η_{0}} > g_{ξ̄+κ^{α}β_{1}}, (prva nejednakost važi zbog (∗)) a ξ̄ + κ^{α}β_{1} je neposredni prethodnik ordinala ξ na odgovarajućem nivou. Što se tiče slučajeva 5^{∘} i 6^{∘}, imamo g_{ξ} > g_{η_{0}} > g_{ξ̄+e_{δ,μ}β_{1}+e_{δ,μ_{1}}} > g_{ξ̄+e_{δ,μ}β_{1}+1} > g_{ξ̄+e_{δ,μ}β_{1}}, a ξ̄+ e_{δ,μ}β_{1} je neposredni prethodnik ordinala ξ na njegovom nivou. Konačno, pokažimo (b) za ξ iz 7^{∘}. Imamo g_{ξ} > g_{η_{0}} > g_{ξ̄+e_{δ,μ}β_{1}+1} > g_{ξ̄+e_{δ,μ}β_{1}}.

(c) Ova osobina sledi direktno iz konstrukcije: g_{ξ̄+ξ_{1}} je u svakom koraku definisano preko elemenata niza ⟨g_{ξ̄+η} : η < ξ_{1}⟩ na isti način kao što je g_{ξ_{1}} definisano preko elemenata niza ⟨g_{η} : η < ξ_{1}⟩.

(d) Ovde nas interesuju slučajevi 4^{∘} − 7^{∘} za ξ̄ = 0 i β = 1. Med¯ utim, za sve njih tvrd¯ enje traženi uslov važi po definiciji g_{ξ}, osim u slučaju 5^{∘}. Ali u tom slučaju je g_{e_{δ,μ}} > g_{e_{δμ_{1}}+1} > g_{e_{μ_{1}}}, a e_{μ_{1}} je upravo prethodna fiksna tačka reda δ. Dakle, za niz fiksnih tačaka reda δ zadovoljen je uslov (b), a iz konstrukcije se vidi da su zadovoljeni i ostali.

Konačno, iz uslova (a) vidimo da je ⟨g_{ξ}^{F} : ξ < κ^{+}⟩ strogo rastući niz elemenata skupa A_{κ}. □

Jednostavno je uvideti da se analogna konstrukcija može sprovesti za bilo koje A_{β} za β takvo da cf(β) = κ. Odatle ili primenom leme 4.2.6 dobijamo

Posledica 4.2.2 Ako je κ najmanji kardinal za koji je ultrafilter F nad I κ^{+}-nekompletan i cf(β) = κ, tada |A_{β}| ≥ κ^{+}.

Kao posledicu gornje teoreme dobijamo i jedno tvrd¯ enje o kardinalnosti ultraproizvoda, koje nije posebno jako, ali za razliku od većine takvih tvrd¯ enja važi u slučaju kada je ultrafilter ω_{1}-kompletan.

Posledica 4.2.3 Ako je κ najmanji kardinal za koji je ultrafilter F nad I κ^{+}-nekompletan, onda je |κ^{I}/F | ≥ κ^{+}.

4.2.4 Još neka tvrd¯ enja

Lema 4.2.10 Ako je F regularan ultrafilter i |I| = κ, onda u ω^{I}/F postoji dobro ured̄en niz dužine κ^{+}.

Dokaz. Neka je E κ-regularna familija za F, i G : E → κ bijekcija. Definišimo niz funkcija ⟨g_{ξ} : ξ < κ^{+}⟩ u ω^{I} takav da g_{ξ_{1}}^{F} < g_{ξ_{2}}^{F} za ξ_{1} < ξ_{2} < κ^{+}. Neka je α < κ^{+}, g_{ξ} definisano za ξ < α i i ∈ I. Dalje, neka su e_{1}, e_{2}, …, e_{m} svi skupovi u E koji sadrže i. Konačno, neka je g_{α}(i) ∈ ω veći od svih g_{G(e_{1})}(i), g_{G(e_{2})}(i), …, g_{G(e_{m})}(i). Tada je za svako ξ < α i svako i ∈ G^{−1}(ξ) g_{ξ}(i) < g_{α}(i), odakle sledi, pošto G^{−1}(ξ) ∈ F, da g_{ξ}^{F} < g_{α}^{F}. □

Primetimo da smo samu činjenicu da je |ω^{I}/F | ≥ κ^{+} mogli izvesti iz leme 3.1.7 i činjenice da je svaki regularan ultrafilter i uniforman, ali prethodna lema daje nam više informacija.

Lema 4.2.11 Ako je |I| = κ ≥ ℵ_{0}, onda postoji pravi filter G na I koji sadrži sve komplemente konačnih podskupova I takav da za sve ultrafiltere F ⊇ G ω^{I}/F sadrži dobro ured̄en niz dužine 2^{κ}, i dakle važi |ω^{I}/F | = 2^{κ}.

Dokaz. Neka je S = {f_{ξ} : ξ < 2^{κ}} ⊆ ^{κ}ω familija velike oscilacije (i f_{ξ} ≠ f_{η} za ξ < η < 2^{κ})–videti teoremu 1.5 i njenu posledicu. Takod¯ e, za ξ < η < 2^{κ} definišimo X_{ξη} = {μ < κ : f_{ξ}(μ) < f_{η}(μ)}. Presek svaka dva skupa X_{ξ_{1}η_{1}} i X_{ξ_{2}η_{2}} je beskonačan (npr. za svako n ∈ ω možemo naći μ_{n} < κ takvo da f_{ξ_{1}}(μ_{n}) = f_{ξ_{2}}(μ_{n}) = n i f_{η_{1}}(μ_{n}) = f_{η_{2}}(μ_{n}) = n + 1, odakle {μ_{n} : n < ω} ⊆ X_{ξ_{1}η_{1}} ∩ X_{ξ_{2}η_{2}}) pa

{X_{ξη} : ξ < η < 2^{κ}} ∪ {Y ⊆ κ : |κ \ Y | < ℵ_{0}}

generiše pravi filter G koji zadovoljava tražene uslove (jer je za svaki ultrafilter F ⊇ G {f_{ξ}^{F} : ξ < 2^{κ}} familija različitih elemenata iz ω^{I}/F). □

Definicija 4.2.3 Ako je κ merljiv kardinal, ultrafilter F nad κ je normalan ako je neglavni, κ-kompletan, i u ultrastepenu κ^{κ}/F klasa ekvivalencije id^{F}, gde je id : κ → κ identička funkcija, je κ-ti element.

Uzimajući u obzir rezultate prethodnog odeljka, prvih κ elemenata u κ^{κ}/F za F κ-kompletan ultrafilter moraju biti klase konstantnih funkcija. Dakle, F je normalan ako je prvi element u A_{κ} baš id^{F}.

Da bismo formulisali sledeće tvrd¯ enje potreban nam je sledeći niz kardinala:

Definicija 4.2.4 • β_{0} = 0;

• β_{α+1} = 2^{β_{α}};

• za granični ordinal α β_{α} = sup_{β<α} β_{β}.

Sledeća lema je posledica teoreme 4.2.21. iz [2]:

Lema 4.2.12 Ako je κ neprebrojiv merljiv kardinal i F normalan ultrafilter

nad κ. Tada je | ∏_{ξ<κ} β_{ξ+1}/F | = β_{κ+1}.

Teorema 4.3 Neka je F normalan ultrafilter nad neprebrojivim merljivim kardinalom κ. Tada je κ^{κ}/F izomorfno nekom ordinalu većem od 2^{κ} a manjem od (2^{κ})^{+}.

Dokaz. κ^{κ}/F je izomorfno nekom ordinalu prema teoremi 4.1. Prema lemi 3.1.3, kako je merljiv kardinal i jako nedostižan, a κ-kompletan ultrafilter uvek uniforman, dakle i (κ, κ)-regularan (videti leme 1.2.6, 1.2.19 i 1.2.16), imamo |κ^{κ}/F | = 2^{κ}. Treba još dokazati da κ^{κ}/F nije izomorfno baš sa 2^{κ}, tj. da ima niz dužine bar 2^{κ} + 1. Definišimo funkciju b : κ → κ ovako: b(α) = β_{α+1} (b(α) < κ jer je κ jako nedostižan). Prema lemi 4.2.4 i prethodnoj lemi je

|{f^{F} ∈ κ^{κ}/F : f^{F} < b^{F} }| = | ∏_{α<κ} b(α)/F | = β_{κ+1} = 2^{κ}.

Dakle, ⟨f^{F} ∈ κ^{κ}/F : f^{F} ≤ b^{F} ⟩ je traženi niz tipa 2^{κ} + 1.

4.3 Drveta

4.3.1 Definicije i osnovna teorema

Rezultati prikazani u ovom odeljku su iz [37]. O drvetima se više informacija može naći u [38] i [39], kao i [20].

Definicija 4.3.1 Parcijalno ured̄en skup (T, ≤) je drvo ako je za svaki element t ∈ T skup (·, t)_{T} = {s ∈ T : s < t} dobro ured̄en.

Definicija 4.3.2 Visina elementa t u drvetu T, u oznaci ht_{T} (t), je ordinal izomorfan sa (·, t)_{T}. α-ti nivo drveta T je skup R_{α}T = {t ∈ T : ht_{T} (t) = α}. Visina drveta T je ht(T) = min{α : R_{α}T = ∅}.

Kada je jasno o kojem drvetu se radi, u (·, t)_{T} ćemo često izostavljati indeks T.

Teorema 4.4 Neka su T_{i} za i ∈ I neprazna drveta i F ultrafilter nad I.

(a) Ako postoji n ∈ ω takvo da {i ∈ I : ht(T_{i}) < n} ∈ F, tada je T = ∏_{F} T_{i}

drvo, i to konačne visine.

(b) ako takvo n ne postoji, tada je T drvo akko je F ω_{1}-kompletan.

Dokaz.

(a) Pretpostavimo da ∏_{F} T_{i} nije drvo. To bi značilo da skup (·, t^{F}) nije dobro

ured¯ en za neki čvor t^{F}. Med¯ utim, on mora biti linearno ured¯ en, zbog leme 4.1.2. Dalje, osobina “svaki linearno ured¯ en skup je kardinalnosti manje od n” može se izraziti rečenicom prvog reda:

¬(∃x_{0}, x_{1}, …, x_{n−1})(x_{0} < x_{1} ∧ x_{1} < x_{2} ∧ … ∧ x_{n−2} < x_{n−1}).

Kako svako od drveta T_{i} ima tu osobinu, po teoremi Łoša imaće je i ∏_{F} T_{i}, pa on ne može imati beskonačan opadajući niz. Stoga je (·, t^{F}) i

dobro ured¯ enje za sve t^{F} ∈ ∏_{F} T_{i}.

(b) (⇒) Obeležimo X_{n} = {i ∈ I : ht(T_{i}) ≥ n}. Po pretpostavci je X_{n} ∈ F za sve n ∈ ω. Ako je F ω_{1}-nekompletan, prema lemi 1.2.9 postoji opadajući niz ⟨Y_{n} : n ∈ ω⟩ skupova iz F takav da ⋂_{n∈ω} Y_{n} = ∅;

možemo pretpostaviti i da je Y_{0} = Y_{1} = I. Tada, ako obeležimo Z_{n} = X_{n} ∩Y_{n}, i ⟨Z_{n} : n ∈ ω⟩ je opadajući niz takav da ⋂_{n∈ω} Z_{n} = ∅.

Dalje, drvo T_{i} ima lanac dužine bar n ako i ∈ Z_{n}; neka je to {t_{k}^{i} : k < n} u opadajućem poretku: t_{k}^{i} > t_{l}^{i} za k < l < n. Definišimo sada niz {t_{k}^{F} : k < ω} elemenata iz ∏_{F} T_{i} ovako: t_{k}(i) =

t_{m}^{i}, gde je m = min{k, max{n ∈ ω : i ∈ Z_{n}} − 1}. Kako je {i ∈ I : t_{k}(i) > t_{k+1}(i)} = Z_{k+1} ∈ F, to je beskonačan opadajući niz u ∏_{F} T_{i}, koje zato ne može biti drvo.

(⇐) Neka je F ω_{1}-kompletan. Kao u dokazu tačke (a) najpre zaključujemo da je (·, t^{F}) linearno ured¯ en za svako t^{F}. Stoga pretpostavimo da u (·, t) postoji beskonačan opadajući niz t^{F} = t_{0}^{F} > t_{1}^{F} > … Obeležimo X_{n} = {i ∈ I : t_{n}(i) > t_{n+1}(i)} za n ∈ ω. Kako je svaki X_{n} u F, a F ω_{1}-kompletan, i W = ⋂_{n∈ω} X_{n} ∈ F,

pa za proizvoljno i ∈ W imamo beskonačan opadajući niz t_{0}(i) > t_{1}(i) > … što je kontradikcija sa uslovom da je T_{i} drvo. □

Već iz prethodnog dokaza možemo uvideti da rad sa drvetima ima mnogo sličnosti sa radom sa dobrim ured¯ enjima.

Imajući u vidu upravo dokazanu teoremu, u ostatku ovog odeljka pretpostavljamo da je F ω_{1}-kompletan.

4.3.2 Grane ultrastepena drveta

Bilo koji podskup skupa T zovemo poddrvo drveta T. Očigledno je da je preslikavanje d : T → T^{I}/F dato sa d(t) = s_{t}^{F}, gde s_{t}(i) = t za i ∈ I, utapanje T u T^{I}/F (videti teoremu 2.2.1). Dakle, svaki ultrastepen drveta T sadrži T kao poddrvo. Elemente s_{t}^{F} za t ∈ T obeležavaćemo nadalje samo sa t^{F}.

Definicija 4.3.3 Grana drveta T je svaki maksimalan lanac u T.

U ovom delu teksta zanimaće nas kako izgledaju grane drveta T^{I}/F. Za početak, jasno je da susedni elementi iz T ostaju susedni i u T^{I}/F, pošto je x < y ∧ ¬(∃z)(x < z ∧ z < y) formula prvog reda. Slično, elementi jedne grane iz T ostaju na istoj grani (tj. uporedivi) i u T^{I}/F. Takod¯ e, pošto su “x je minimalan element” i “x je maksimalan element” osobine prvog reda (izražavaju se formulama ¬(∃y)y < x i ¬(∃y)x < y), svaka grana drveta T može u T^{I}/F dobiti nove elemente samo na graničnim nivoima (tj. ako je B = {t_{ξ} : ξ < β} grana drveta T i za neko α ≤ β element t^{F} ∈ T^{I}/F iznad svih t_{ξ} za ξ < α i ispod svih t_{ξ} za ξ ≥ α, onda α mora biti granični ordinal).

Takod¯ e važi i

Lema 4.3.1 Ako je B = {t_{ξ} : ξ < β} grana drveta T, i s^{F} ∈ T^{I}/F element uporediv sa svim elementima iz B, ali ne veći od svih elemenata iz B, onda {i ∈ I : (∃ξ < β)s(i) = t_{ξ}} ∈ F.

Dokaz. Prema uslovu leme postoji ξ_{0} < β takvo da s^{F} < t_{ξ_{0}}^{F}, odnosno X = {i ∈ I : s(i) < t_{ξ_{0}}} ∈ F. Med¯ utim, svaki element ispod nekog elementa grane mora takod¯ e biti na grani, tj. {i ∈ I : (∃ξ < β)s(i) = t_{ξ}} ⊇ X, pa i taj skup mora biti u F. □

Sledeći primer objašnjava zašto je u prethodnoj lemi neophodan uslov da s^{F} nije veći od svih elemenata grane B.

Primer. Neka je T = {t_{ξ} : ξ < α} ∪ {s_{ξ} : ξ < α} sa poretkom definisanim ovako: t_{ξ_{1}} < t_{ξ_{2}} za ξ_{1} < ξ_{2} < α, a s_{ξ} > t_{ξ} i s_{ξ} i t_{ξ+1} su neuporedivi za ξ < α. Dalje, neka je F α-opadajuće nekompletan nad I, tj. postoji opadajući niz ⟨X_{ξ} : ξ < α⟩ elemenata iz F čiji je presek prazan. Definišimo s^{F} ∈ T^{I}/F ovako: neka s(i) = s_{ξ}, gde je ξ = min{ξ < α : i ∉ X_{ξ}}. Tada je za svako ξ < α {i ∈ I : s(i) > t_{ξ}} = X_{ξ} ∈ F, tj. s^{F} je iznad svih elemenata grane {t_{ξ}^{F} : ξ < α}, ali {i ∈ I : (∃ξ < α)s(i) = t_{ξ}(i)} = ∅.

Ali B ne mora dobiti nove elemente ni na svakom graničnom nivou (dokaz je sličan dokazu leme 4.2.7):

Lema 4.3.2 Neka je B = {t_{ξ} : ξ < β} grana drveta T, i α ≤ β granični ordinal. Tada postoji element u T^{I}/F iznad svih t_{ξ} za ξ < α i ispod svih t_{ξ} za α ≤ ξ < β akko je F cf(α)-opadajuće nekompletan.

Dokaz.

(⇒) Pretpostavimo da je F cf(α)-opadajuće kompletan, i s^{F} ∈ T^{I}/F takav da s^{F} > t_{ξ}^{F} za ξ < α i s^{F} < t_{ξ}^{F} za α ≤ ξ < β. Zahvaljujući poslednjem uslovu i teoremi 2.4 možemo bez umanjenja opštosti pretpostaviti da je s(i) < t_{α} za sve i ∈ I. Neka je {α_{η} : η < cf(α)} niz kofinalan u α. Definišimo X_{η} = {i ∈ I : t_{α_{η}} ≤ s(i)}. Jasno je da je ⋂_{η<cf(α)} X_{η} = {i ∈

I : (∀η < cf(α))t_{α_{η}} ≤ s(i)} = ∅, pa iz cf(α)-opadajuće kompletnosti sledi da postoji η < cf(α) za koje X_{η} ∉ F. Med¯ utim to bi značilo da je s^{F} < t_{α_{η}}^{F}, kontradikcija.

(⇐) Neka je F cf(α)-opadajuće nekompletan. Tada postoji opadajući niz {X_{η} : η < cf(α)} elemenata iz F takav da X_{0} = I i ⋂_{η<cf(α)} X_{η} = ∅.

Neka je ponovo {α_{η} : η < cf(α)} niz kofinalan u α. Definišimo za sve i ∈ I s(i) = t_{α_{η}}, gde je η = min{η < cf(α) : i ∉ X_{η}}. Tada za za sve η < cf(α) imamo {i ∈ I : s(i) > t_{ξ}} = X_{η} ∈ F, pa s^{F} > t_{ξ}^{F} za ξ < α, a očigledno i s^{F} < t_{ξ}^{F} za α ≤ ξ < β. □

Med¯ utim, nije poznat odgovor na pitanje: koliko novih elemenata dobija grana na raznim nivoima? Sledi jedna (prilično gruba) procena:

Lema 4.3.3 Neka je B = {t_{ξ} : ξ < β} grana drveta T, α ≤ β granični ordinal i F cf(α)-opadajuće nekompletan. Tada postoji bar cf(α) elemenata u T^{I}/F većih od svih t_{ξ} za ξ < α i manjih od t_{ξ} za α ≤ ξ < β.

Dokaz. U prethodnoj lemi pokazano je da postoji bar jedan takav element s_{0}^{F}. Definišimo za η < cf(α) s_{η+1}(i) = s_{η}(i) + 1, a za granični ordinal η < cf(α) neka je s_{η}(i) = sup_{ξ<η} s_{ξ}. ⟨s_{η}^{F} : η < cf(α)⟩ je strogo rastući niz elemenata iz T^{I}/F koji su veći od svih t_{ξ} za ξ < α, a manji od t_{α}. □

U jednom specijalnom slučaju imamo i bolji rezultat, koji sledi iz teoreme 4.2:

Lema 4.3.4 Ako je κ ≤ β najmanji kardinal takav da je F κ^{+}-nekompletan, i B = {t_{ξ} : ξ < β} grana drveta T. Tada postoji bar cf(κ)^{+} elemenata u T^{I}/F većih od svih t_{ξ} za ξ < κ i (ako κ < β) manjih od t_{α}.

4.3.3 Nivoi ultraproizvoda drveta

Lema 4.3.5 Neka je F κ^{+}-kompletan i |α| ≤ κ. Svaki element t ∈ R_{α}T je i na nivou α u drvetu T^{I}/F.

Dokaz. Osobina “tip dobro ured¯ enog skupa (·, t) je α” se za |α| ≤ κ može izraziti formulom jezika L_{κ^{+},κ^{+}}: ako su V_{α} = {x_{ξ} : ξ < α} i V_{α+1} = {x_{ξ} : ξ ≤ α} skupovi promenljivih, t ima pomenutu osobinu akko

(∃V_{α})(⋀{x_{ξ_{1}} < x_{ξ_{2}} : ξ_{1} < ξ_{2} < α} ∧ ⋀{x_{ξ} < t : ξ < α})∧
¬(∃V_{α+1})(⋀{x_{ξ_{1}} < x_{ξ_{2}} : ξ_{1} < ξ_{2} ≤ α} ∧ ⋀{x_{ξ} < t : ξ ≤ α}).

Na osnovu teoreme 2.6 ta osobina se prenosi na ultrastepen po κ^{+}-kompletnom ultrafilteru. □

Lema 4.3.6 Za elemente s^{F} , t^{F} ∈ ∏_{F} T_{i} = T važi {i ∈ I : ht_{T_{i}}(s(i)) =

ht_{T_{i}}(t(i))} ∈ F akko je ht_{T} (s^{F}) = ht_{T} (t^{F}).

Dokaz.

(⇒) Neka su s^{F} , t^{F} ∈ T, i (·, s^{F})_{T} = {s_{ξ}^{F} : ξ < α}, gde s_{ξ_{1}}^{F} < s_{ξ_{2}}^{F} za ξ_{1} < ξ_{2} < α. Za svako ξ < α je X_{ξ} = {i ∈ I : s_{ξ}(i) < s(i)} ∈ F. Zahvaljujući teoremi 2.4 možemo pretpostaviti da je β_{i} = ht_{T_{i}}(s(i)) = ht_{T_{i}}(t(i)) za sve i ∈ I. Neka su analogno (·, s(i))_{T_{i}} = {x_{ξ}^{i} : ξ < β_{i}} i (·, t(i))_{T_{i}} = {y_{ξ}^{i} : ξ < β_{i}}. Definišimo za i ∈ I preslikavanje f_{i} : (·, s(i))_{T_{i}} → (·, t(i))_{T_{i}} ovako: f_{i}(x_{ξ}^{i}) = y_{ξ}^{i}. Konačno, definišimo t_{ξ}^{F} ∈ T za ξ < α na sledeći način: t_{ξ}(i) = f_{i}(s_{ξ}(i)) za sve i ∈ X_{ξ}, i t_{ξ}(i) ∈ T_{i} proizvoljno za i ∉ X_{ξ}. ⟨t_{ξ}^{F} : ξ < α⟩ je niz dužine α različitih prethodnika elementa t^{F} u T, što znači da u T postoji monotona injekcija izmed¯ u (·, s^{F})_{T} i (·, t^{F})_{T}. Analogno pokazujemo i obratno, pa su ured¯ enja (·, s^{F})_{T} i (·, t^{F})_{T} istog tipa, što znači ht_{T} (s^{F}) = ht_{T} (t^{F}).

(⇐) Obeležimo: X_{0} = {i ∈ I : ht_{T_{i}}(s(i)) = ht_{T_{i}}(t(i))}, X_{1} = {i ∈ I : ht_{T_{i}}(s(i)) < ht_{T_{i}}(t(i))} i X_{2} = {i ∈ I : ht_{T_{i}}(s(i)) > ht_{T_{i}}(t(i))}. Kako je X_{0} ∪ X_{1} ∪ X_{2} = I i ako pretpostavimo X_{0} ∉ F, sledi da X_{1} ∈ F ili X_{2} ∈ F. Neka npr. X_{1} ∈ F. Definišimo x^{F} ∈ T ovako: za i ∈ X_{1} neka je x(i) element na nivou ht_{T_{i}}(s(i)) manji od t(i), a za i ∉ X_{1} neka je x(i) proizvoljno. Prema prvoj implikaciji ove leme je ht_{T} (s^{F}) = ht_{T} (x^{F}). Med¯ utim, važi x^{F} < t^{F}, kontradikcija. □

Posledica 4.3.1 Svaka dva elementa koji su na istom nivou u drvetu T moraju biti na istom nivou i u T^{I}/F.

Posledica 4.3.2 Za svaki element t^{F} ∈ T^{I}/F važi: postoji α takvo da {i ∈ I : ht_{T} (t(i)) = α} ∈ F akko je t^{F} na istom nivou u drvetu T^{I}/F kao elementi s^{F} za s ∈ R_{α}T.

4.3.4 Neke važne vrste drveta

Definicija 4.3.4 Drvo T je normalno ako važe sledeći uslovi:

N(i) |R_{0}T | = 1;

N(ii) ako s, t ∈ T, ht_{T} (s) = ht_{T} (t) je granični ordinal i (·, s)_{T} = (·, t)_{T}, onda s = t;

N(iii) ako α < β < ht(T) i t ∈ R_{α}T, tada postoje bar dva elementa s_{1}, s_{2} ∈ R_{β}T takva da t < s_{1} i t < s_{2}.

Teorema 4.5 Ako su T_{i} normalna drveta za i ∈ I, i drvo T = ∏_{F} T_{i} je

normalno.

Dokaz.

N(i) Kako svako od drveta T_{i} ima najmanji element, i T ima najmanji element, jer je postojanje najmanjeg elementa osobina prvog reda.

N(ii) Pretpostavimo da s^{F} , t^{F} ∈ T, da je ht_{T} (s^{F}) = ht_{T} (t^{F}) neki granični ordinal i (·, s^{F})_{T} = (·, t^{F})_{T}. Prema lemi 4.3.6 je X = {i ∈ I : ht_{T_{i}}(s(i)) = ht_{T_{i}}(t(i))} ∈ F, pa zbog teoreme 2.4 možemo pretpostaviti X = I. Obeležimo dalje Y = {i ∈ I : ht_{T_{i}}(t(i)) je granični ordinal}. Ako bi važilo I \ Y ∈ F, mogli bismo definisati x^{F} ovako: za i ∈ I \ Y neka je x(i) neposredni prethodnik elementa t(i) u T_{i}, a za i ∈ Y neka je x(i) proizvoljno. Tada je x^{F} neposredni prethodnik elementa t^{F} u T, što je nemoguće. Dakle, Y ∈ F. Obeležimo sada Z = {i ∈ I : (·, s(i))_{T_{i}} = (·, t(i))_{T_{i}}}. Za i ∈ Z, pošto je T_{i} normalno, imamo s(i) = t(i). Ako dokažemo Z ∈ F, to će značiti s^{F} = t^{F}, i dokaz će biti završen. Pretpostavimo stoga da Z ∉ F. Za i ∈ I \Z postoji x(i) < s(i) takvo da ne važi x(i) < t(i). Ako još definišemo x(i) proizvoljno za i ∈ Z, dobićemo element x^{F} ∈ T koji je u (·, s^{F})_{T}, ali nije u (·, t^{F})_{T}, kontradikcija.

N(iii) Neka je α < β < htT i ht_{T} (t^{F}) = α. Neka je x^{F} proizvoljan element β-tog nivoa u T i za i ∈ I neka je α_{i} = ht_{T_{i}}(x(i)). Jasno je da zbog ht_{T} (x^{F}) > ht_{T} (t^{F}) mora biti X = {i ∈ I : α_{i} > ht_{T_{i}}(t(i))} ∈ F. Kako je svako T_{i} normalno, za i ∈ X postoje bar dva elementa, s_{1}^{i} i s_{2}^{i}, na α_{i}-tom nivou veći od t(i). Definišimo za i ∈ X s_{1}(i) = s_{1}^{i} i s_{2}(i) = s_{2}^{i}, a za i ∈ I \ X neka su s_{1}(i) i s_{2}(i) proizvoljni. Jasno je da ht_{T} (s_{1}^{F}) = ht_{T} (s_{2}^{F}) = ht_{T} (x^{F}) = β, s_{1}^{F} > t^{F}, s_{2}^{F} > t^{F} i s_{1}^{F} ≠ s_{2}^{F}. □

Definicija 4.3.5 κ-drvo je drvo za koje važi ht(T) = κ i za sve α < κ |R_{α}T | < κ.

Teorema 4.6 (a) Ako je F κ^{+}-kompletan, ultraproizvod T = ∏_{F} T_{i} κ-drveta

je κ-drvo;

(b) ako je F κ-opadajuće nekompletan, T nije κ-drvo.

Dokaz.

(a) Pretpostavimo da je F κ^{+}-kompletan. Prvo dokazujemo da je ht(T) = κ. Neka je t^{F} ∈ T. Definišimo X_{ξ} = {i ∈ I : ht_{T_{i}}(t(i)) = α}. Pošto je F κ^{+}-kompletan, jedan od skupova X_{ξ} je u F, te iz posledice 4.3.2 sledi ht_{T} (t^{F}) = α. Dakle, ht(T) = κ. Dokažimo sada da svaki nivo drveta T ima manje od κ elemenata. Pretpostavimo da postoji α < κ takvo da R_{α}T ima bar κ elemenata. Posledica 4.3.2 tvrdi da je za svaki element t^{F} ∈ R_{α}T skup X = {i ∈ I : ht_{T_{i}}(t(i)) = α} u F. Neka je λ_{i} kardinalnost nivoa R_{α}T_{i} i {x_{ξ}^{i} : ξ < λ_{i}} jedno dobro ured¯ enje elemenata tog nivoa. Za ξ < κ definišimo X_{ξ} = {i ∈ I : t(i) = x_{ξ}^{i}}. Pošto je X = ⋃_{ξ<κ} X_{ξ} i F κ^{+}-kompletan, jedan

od skupova X_{ξ} mora biti u F. To znači da je svaki t^{F} ∈ R_{α}T jednak x_{ξ}^{F} = ⟨x_{ξ}^{i} : i ∈ I⟩^{F} za neko ξ < κ. Ali za neko λ < κ skup Y_{λ} = {i ∈ I : λ_{i} ≥ λ} nije u F (inače bi {Y_{λ} : λ < κ} bila familija skupova iz F čiji je presek prazan, dakle nije u F). To znači da elemenata x_{ξ} ima manje od κ.

(b) Pretpostavimo da je F κ-opadajuće nekompletan. To znači da postoji niz {X_{α} : α < κ} elemenata iz F takav da X_{α} ⊇ X_{β} za α < β < κ i ⋂_{α<κ} X_{α} = ∅ (možemo pretpostaviti i X_{0} = I). Takod¯ e, pošto je svako

T_{i} κ-drvo, za i ∈ X_{α} možemo izabrati lanac dužine α + 1 u T_{i}, npr. {x_{η}^{i} : η ≤ α} (x_{η_{1}}^{i} < x_{η_{2}}^{i} za η_{1} < η_{2} ≤ α). Definišimo sada t_{ξ} ∈ T: za i ∈ I, ako je α = min{η < κ : i ∉ X_{α}}, neka je

t_{ξ}(i) = \{ \begin{matrix}x_{ξ}^{i}, & ξ < α \\ x_{α}^{i}, & ξ ≥ α \end{matrix}

i t_{κ}(i) = x_{α}^{i}. Tada je {x_{ξ} : ξ ≤ κ} lanac dužine κ + 1 u T, i zato T nije κ-drvo. □

Za ultrastepene imamo jače tvrd¯ enje, koje je direktna posledica leme 2.3.2:

Lema 4.3.7 Ako je F κ^{+}-kompletan i T je κ-drvo, tada T^{I}/F ≅ T.

Kažemo da je grana drveta T kofinalna ako seče svaki nivo drveta T.

Definicija 4.3.6 κ-Aronszajnovo drvo je κ-drvo bez kofinalnih grana, tj. drvo koje nema lanac dužine κ.

Antilanac u drvetu T je njegov podskup takav da su svaka dva elementa s, t tog podskupa neuporediva, tj. niti je s ≤ t niti t ≤ s. (Uopšte, kod parcijalnih ured¯ enja antilanac je skup elemenata takvih da su svaka dva od njih x i y nekompatibilni, odnosno ne postoji z takvo da z ≤ x i z ≤ y; definicija za drveta slaže se sa opštom definicijom za parcijalno ured¯ enje (T, ≥)).

Definicija 4.3.7 κ-Suslinovo drvo je drvo kardinalnosti κ koje ne sadrži ni lanac ni antilanac dužine κ.

Napomenimo ovde da egzistencija κ-Aronszajnovih (a samim tim i κ-Suslinovih) drveta ne može biti dokazana u ZFC, ali je konzistentna sa ZFC. Pretpostavke o njihovoj egzistenciji povlače razne zanimljive posledice, a posebno su interesantni neki njihovi ekvivalenti (postojanje tzv. Aronszajnove, odnosno Suslinove linije). Za više informacija videti [38],[39],[20] ili [7].

Teorema 4.7 (a) Ako je ultrafilter F κ^{+}-kompletan, ultraproizvod T = ∏_{F} T_{i} κ-Aronszajnovih drveta je κ-Aronszajnovo drvo;

(b) ako je F κ-opadajuće nekompletan, T nije κ-Aronszajnovo drvo.

Dokaz.

(a) Pretpostavimo da je ultrafilter F κ^{+}-kompletan i da drvo T = ∏_{F} T_{i} nije

κ-Aronszajnovo. Kako je, prema teoremi 4.6, T κ-drvo, ono mora imati kofinalnu granu; neka je to {t_{α}^{F} : α < κ}. Za sve parove α < β < κ skup X_{α,β} = {i ∈ I : t_{α}(i) < t_{β}(i)} je u F. Pošto takvih skupova ima samo |[κ]^{2}| = κ njihov presek X je u F, dakle X ≠ ∅. Za svako i ∈ X imamo lanac dužine κ u T_{i} {t_{α}(i) : α < κ} što implicira da T_{i} nije Aronszajnovo, kontradikcija.

(b) Ako je F κ-opadajuće nekompletan, T nije čak ni κ-drvo (teorema 4.6) te ne može biti κ-Aronszajnovo. □

Teorema 4.8 (a) Ako je ultrafilter F κ^{+}-kompletan, ultraproizvod T = ∏_{F} T_{i} κ-Suslinovih drveta je κ-Suslinovo drvo;

(b) ako je F κ-opadajuće nekompletan, T nije κ-Suslinovo drvo.

Dokaz. Jedina razlika u odnosu na dokaz prethodne teoreme je što treba pokazati, u slučaju kada je F κ^{+}-kompletan, da T nema antilanac dužine κ. Pretpostavimo suprotno, da je {t_{ξ}^{F} : ξ < κ} taj antilanac. Za sve parove ξ < η < κ skup X_{ξ,η} = {i ∈ I : ¬(t_{ξ}(i) ≤ t_{η}(i) ∨ t_{ξ}(i) ≥ t_{η}(i))} je u F. Kao i prethodnom dokazu imamo da iz κ^{+}-kompletnosti sledi, ako obeležimo X = ⋂_{ξ<η<κ} X_{ξ,η}, da X ∈ F, dakle X ≠ ∅, pa za i ∈ X dobijamo antilanac

{t_{ξ}(i) : ξ < κ}, kontradikcija. □

4.4 Boolove algebre

U knjizi [27] ispitivano je kako formiranje ultraproizvoda utiče na vrednosti raznih kardinalnih funkcija Boolovih algebri. U njoj se nalazi mnogo rezultata, ali i neki problemi koji su rešeni u nedavno objavljenim radovima. Mi ćemo ovde razmotriti one kardinalne funkcije κ koje se tiču poretka na Boolovoj algebri. Značajan doprinos u njihovom proučavanju dao je Peterson u radu [28], tako što ih je svrstao ih u nekoliko klasa sa sličnim osobinama, i dobio opštije rezultate, za sve funkcije iste klase. Značajni rezultati o konsistentnosti dobijeni su iz radova Shelaha i saradnika. U toku celog odeljka pretpostavljaćemo da je {B_{i} : i ∈ I} familija Boolovih algebri, F neki ultrafilter i B = ∏_{F} B_{i} (jasno je, na osnovu Łošove teoreme,

da je B Boolova algebra).

4.4.1 Celularnost

Definicija 4.4.1 Ako je A Boolova algebra, X ⊆ A \ {0} je antilanac ako za sve a, b ∈ X važi a ∧ b = 0. Celularnost Boolove algebre A, u oznaci cA, je

sup{|X| : X je antilanac u A}.

Kažemo da A zadovoljava uslov κ-lanaca ako je svaki antilanac u A kardinalnosti manje od κ. Specijalno, ako je svaki antilanac u A prebrojiv, kažemo da A zadovoljava uslov ccc.

Primetimo da se definicija antilanca u Boolovoj algebri ne slaže sa definicijom koju smo dali za parcijalna ured¯ enja uopšte u odeljku o drvetima, ali to je upravo lanac u parcijalnom ured¯ enju (B \ {0}, ≤) prema toj definiciji.

Lema 4.4.1 Ako je F ω_{1}-kompletan i sve algebre B_{i} zadovoljavaju ccc, onda i B zadovoljava ccc.

Dokaz. Pretpostavimo suprotno: neka je {b_{ξ}^{F} : ξ < ω_{1}} antilanac u B. To znači da za α, β ∈ ω_{1}, α ≠ β, skup J_{α,β} = {i ∈ I : b_{α}(i) ∧ b_{β}(i) = 0} pripada F. Takod¯ e, za α ∈ ω_{1} skupovi K_{α} = {i ∈ I : b_{α}(i) ≠ 0} su u F. Med¯ utim, prema posledici teoreme 1.10 F je i ω_{2}-kompletan, pa ⋂_{α<β<ω_{1}} J_{α,β} ∩ ⋂_{α<ω_{1}} K_{α} ≠ ∅, što je očigledno nemoguće (ako bi za neko i ∈ I

važilo i ∈ ⋂_{α<β<ω_{1}} J_{α,β} ∩ ⋂_{α<ω_{1}} K_{α}, u B_{i} bismo imali antilanac {b_{ξ}(i) : ξ < ω_{1}}). □

Lema 4.4.2 Ako je F ω_{1}-nekompletan, B ne zadovoljava ccc.

Dokaz. Prema lemi 1.2.21 F je i ω_{1}-dobar, pa po teoremi 3.10, B je ω_{1}- zasićena. Neka je {b_{ξ} : ξ < κ} maksimalan antilanac u B, i za svako ξ < κ obeležimo sa φ_{ξ}(x) formulu x∧b_{ξ} = 0. Skup {φ_{ξ}(x) : ξ < κ} je konačno zadovoljiv u (B, b_{ξ})_{ξ<κ}, pa je i zadovoljiv, što znači da postoji b ∈ B \ {0} takav da b∧b_{ξ} = 0 za sve ξ < κ, što je u suprotnosti sa maksimalnošću antilanca. □

Sledećih nekoliko rezultata se pokazuju analogno za celularnost i još neke kardinalne funkcije (nama su zanimljive dužina i neuporedivost), pa ćemo, kao u [28], sprovesti dokaze u opštem slučaju.

Definicija 4.4.2 Neka je P funkcija koja svakoj Boolovoj algebri A pridružuje skup P (A) ⊆ P(A). Kardinalna funkcija inv je ultra-sup funkcija u odnosu na P ako važi

1) invA = sup{|X| : X ∈ P (A)},

2) ako je {A_{i} : i ∈ I} familija beskonačnih Boolovih algebri, F ultrafilter nad I i X_{i} ∈ P (A_{i}) za sve i ∈ I, onda

{f^{F} : f ∈ ∏_{i∈I} X_{i}} ∈ P (∏_{F} A_{i}).

Ako je inv ultra-sup funkcija u odnosu na P, definišimo

inv′A = min{κ : |X| < κ za sve X ∈ P (A)}.

Primetimo da je inv′A = invA ako je invA granični kardinal, a inv′A = (invA)^{+} ako je invA nasledni.

Lema 4.4.3 Ako je inv ultra-sup funkcija, sve algebre B_{i} su beskonačne i λ_{i} < inv′B_{i} za sve i ∈ I, tada

inv′B > | ∏_{F} λ_{i}|

i stoga

invB ≥ | ∏_{F} λ_{i}|.

Dokaz. Za svako i ∈ I postoji X_{i} ∈ P (B_{i}) takvo da |X_{i}| = λ_{i}. Iz definicije ultra-sup funkcija vidimo da

X = {f^{F} : f ∈ ∏_{i∈I} X_{i}} ∈ P (∏_{F} A_{i}).

Ostaje još da primetimo |X| = | ∏_{F} λ_{i}| □.

Lema 4.4.4 Ako je inv ultra-sup funkcija, sve algebre B_{i} su beskonačne i λ = ess.sup_{F} {invB_{i}}, onda je

invB ≥ λ.

Dokaz. Ako je λ nasledni kardinal, onda je {i ∈ I : invB_{i} = λ} ∈ F, pa kako za sve i ∈ I iz invB_{i} = λ sledi inv′B_{i} = λ^{+} > λ, iz prethodne leme dobijamo inv(∏_{F} B_{i}) ≥ |λ^{I}/F | ≥ λ. Ako je λ granični kardinal, za svako

μ < λ imamo {i ∈ I : invB_{i} > μ} ∈ F i stoga inv(∏_{F} B_{i}) ≥ |μ^{I}/F | ≥ μ, dakle

i inv(∏_{F} B_{i}) ≥ λ. □

Da bismo dokazali sledeću lemu o ultra-sup funkcijama treba nam sledeće tvrd¯ enje:

Lema 4.4.5 Ako je λ granični kardinal, λ = sup_{ξ<μ} λ_{ξ} i κ < cf(λ), onda je λ^{κ} = sup_{ξ<μ} λ_{ξ}^{κ}.

Dokaz. Očigledno je λ^{κ} ≥ sup_{ξ<μ} λ_{ξ}^{κ}. Zato uzmimo f ∈ ^{κ}λ i pokažimo da f ∈ ⋃_{ξ<μ}^{κ}λ_{ξ}. Za sve η < κ iz f(η) < λ sledi da postoji ξ_{η} < μ takav da

f(η) < λ_{ξ_{η}}. Ako obeležimo ξ′ = sup_{η<κ} ξ_{η}, iz κ < cf(λ) sledi da je ξ′ < μ, pa f ∈ ^{κ}λ_{ξ′}, što je i trebalo dokazati. □

Lema 4.4.6 Ako je inv ultra-sup funkcija, F regularan, sve algebre B_{i} su beskonačne, P (B_{i}) sadrži proizvoljno velike konačne skupove za svako i ∈ I, i λ = ess.sup_{F} {invB_{i}}, onda

invB ≥ | ∏_{F} invB_{i}| = λ^{|I|}.

Dokaz. Jednakost sledi iz teoreme 3.3. Da bismo dokazali nejednakost, posmatraćemo četiri slučaja:

1^{∘} λ = ω. Tada je λ^{|I|} = 2^{|I|} i, prema lemi 3.1.10, inv(∏_{F} B_{i}) ≥ 2^{|I|}.

2^{∘} ω < λ ≤ |I|. Opet je λ^{|I|} = 2^{|I|}, a iz posledice teoreme 3.6 sledi

inv(∏_{F} B_{i}) ≥ |ω^{I}/F | ≥ 2^{|I|}.

3^{∘} cf(λ) ≤ |I| < λ. Ako je {i ∈ I : invB_{i} = λ} ∈ F (bez umanjenja opštosti možemo pretpostaviti invB_{i} = λ za sve i ∈ I), prema lemi 3.1.4 postoji niz ⟨κ_{i} : i ∈ I⟩ takav da je ess.sup_{F} {κ_{i}} = λ i κ_{i} < λ za sve i ∈ I, pa prema lemi 4.4.3 inv(∏_{F} B_{i}) ≥ | ∏_{F} κ_{i}| = λ^{|I|}. S druge

strane, ako je {i ∈ I : invB_{i} < λ} ∈ F, egzistenciju takvog niza daje lema 3.1.5.

4^{∘} |I| < cf(λ). Tada je, prema lemi 4.4.5, λ^{|I|} = sup{κ^{|I|} : κ < λ}, i za sve beskonačne κ < λ važi

inv(∏_{F} B_{i}) ≥ |κ^{I}/F | = κ^{|I|}.

Stoga je po lemi 4.4.3 i Keisler-Prikryjevoj teoremi inv(∏_{F} B_{i}) ≥ λ^{|I|}. □

Lema 4.4.7 Ako je inv ultra-sup funkcija i sve algebre B_{i} su beskonačne, onda

inv′B ≥ | ∏_{F} inv′B_{i}|.

Dokaz. Neka je za i ∈ I λ_{i} = inv′B_{i}, i pretpostavimo da je λ < ∏_{F} λ_{i}. Kako

je ∏_{F} λ_{i} linearno ured¯ en skup kardinalnosti veće od λ, možemo naći f ∈ ∏_{i∈I} λ_{i}

takvo da |{g^{F} ∈ ∏_{F} λ_{i} : g^{F} < f^{F} }| ≥ λ, tj. | ∏_{F} f(i)| ≥ λ. Med¯ utim, prema

lemi 4.4.3 je inv′B > | ∏_{F} f(i)|. □

Lema 4.4.8 Celularnost je ultra-sup funkcija.

Dokaz. Neka je P (A) = {X ⊆ A : X je antilanac}. Očigledno je cA = sup{|X| : X ∈ P (A)}. Neka je {A_{i} : i ∈ I} familija beskonačnih Boolovih algebri, F ultrafilter nad I, X_{i} ∈ P (A_{i}) za sve i ∈ I, i X = {f^{F} : f ∈ ∏_{i∈I} X_{i}}.

Ako bi za neke f^{F} , g^{F} ∈ X važilo f^{F} ∧g^{F} = h^{F} ≠ 0^{F} (gde 0^{F} = ⟨0 : i ∈ I⟩^{F}), imali bismo Y = {i ∈ I : f(i) ∧ g(i) ≠ 0} ∈ F, i za sve i ∈ Y f(i) ∧ g(i) ≠ 0, što je kontradikcija sa činjenicom da f(i), g(i) ∈ X_{i} a X_{i} je antilanac. Dakle,

X ∈ P (∏_{F} A_{i}). □

Ovako izgledaju gore dokazane leme u slučaju funkcije c:

Posledica 4.4.1 Ako su sve algebre B_{i} beskonačne i λ_{i} < c′B_{i} za sve i ∈ I, tada

c′B > | ∏_{F} λ_{i}|

i stoga

cB ≥ | ∏_{F} λ_{i}|.

Posledica 4.4.2 Ako su sve algebre B_{i} beskonačne i λ = ess.sup_{F} {cB_{i}}, onda je

cB ≥ λ.

Posledica 4.4.3 Ako je F regularan i sve algebre B_{i} su beskonačne, onda

cB ≥ | ∏_{F} cB_{i}| = λ^{|I|}.

Posledica 4.4.4 Ako su sve algebre B_{i} beskonačne, onda

c′B ≥ | ∏_{F} c′B_{i}|.

4.4.2 Neuporedivost

Definicija 4.4.3 Elementi x, y ∈ A su neuporedivi ako ne važi ni x ≤ y ni y ≤ x. Neuporedivost Boolove algebre A je

IncA = sup{|X| : X je podskup skupa A takav da su

svaka dva elementa iz X neuporedivi}.

Lema 4.4.9 Neuporedivost je ultra-sup funkcija.

Dokaz. Neka je

P (A) = {X ⊆ A : X je podskup skupa A takav da su

svaka dva elementa iz X neuporedivi}.

Očigledno je IncA = sup{|X| : X ∈ P (A)}. Neka je {A_{i} : i ∈ I} familija beskonačnih Boolovih algebri, F ultrafilter nad I, X_{i} ∈ P (A_{i}) za sve i ∈ I, i X = {f^{F} : f ∈ ∏_{i∈I} X_{i}}. Ako bi neki f^{F} , g^{F} ∈ X bili uporedivi, npr. f^{F} ≤ g^{F},

imali bismo Y = {i ∈ I : f(i) ≤ g(i)} ∈ F, i za sve i ∈ Y f(i) ≤ g(i), što je kontradikcija sa činjenicom da f(i), g(i) ∈ X_{i} a X_{i} je skup neuporedivih elemenata. Sledi da je X ∈ P (∏_{F} A_{i}). □

Prema prethodnoj i lemama prošlog odeljka odmah imamo

Posledica 4.4.5 Ako su sve algebre B_{i} beskonačne i λ_{i} < Inc′B_{i} za sve i ∈ I, tada

Inc′B > | ∏_{F} λ_{i}|

i stoga

IncB ≥ | ∏_{F} λ_{i}|.

Posledica 4.4.6 Ako su sve algebre B_{i} beskonačne i λ = ess.sup_{F} {IncB_{i}}, onda je

IncB ≥ λ.

Posledica 4.4.7 Ako je F regularan i sve algebre B_{i} su beskonačne, onda

IncB ≥ | ∏_{F} IncB_{i}| = λ^{|I|}.

Posledica 4.4.8 Ako su sve algebre B_{i} beskonačne, onda

Inc′B ≥ | ∏_{F} Inc′B_{i}|.

U [34] dokazano je

Teorema 4.9 Konsistentno je da postoji niz Boolovih algebri ⟨B_{i} : i ∈ I⟩ i ultrafilter F nad I takav da za neki kardinal λ IncB ≤ λ i ∏_{F} IncB_{i} = λ^{+}.

4.4.3 Dužina

Definicija 4.4.4 Dužina Boolove algebre A je

LengthA = sup{|X| : X je linearno ured̄en podskup skupa A}.

Lema 4.4.10 Dužina je ultra-sup funkcija.

Dokaz. Neka je P (A) = {X ⊆ A : X je linearno ured¯ en podskup skupa A}. Opet je očigledno LengthA = sup{|X| : X ∈ P (A)}. Neka je, kao i u dokazima analognih tvrd¯ enja za celularnost i neuporedivost, {A_{i} : i ∈ I} familija beskonačnih Boolovih algebri, F ultrafilter nad I, X_{i} ∈ P (A_{i}) za sve i ∈ I, i X = {f^{F} : f ∈ ∏_{i∈I} X_{i}}. Pretpostavimo da su neki f^{F} , g^{F} ∈ X neuporedivi.

Med¯ utim, ako obeležimo Y_{1} = {i ∈ I : f(i) ≤ g(i)} i Y_{2} = {i ∈ I : f(i) > g(i)}, iz Y_{1} ∪ Y_{2} = I sledi Y_{1} ∈ F ili Y_{2} ∈ F, odnosno ili f^{F} ≤ g^{F} ili f^{F} > g^{F}, kontradikcija. Dakle, X ∈ P (∏_{F} A_{i}). □

Kao i kod prethodne dve funkcije, kao posledice imamo

Posledica 4.4.9 Ako su sve algebre B_{i} beskonačne i λ_{i} < Length′B_{i} za sve i ∈ I, tada

Length′B > | ∏_{F} λ_{i}|

i stoga

LengthB ≥ | ∏_{F} λ_{i}|.

Posledica 4.4.10 Ako su sve algebre B_{i} beskonačne, onda je

LengthB ≥ ess.sup_{F} {LengthB_{i}}.

Posledica 4.4.11 Ako je F regularan i sve algebre B_{i} su beskonačne, onda

LengthB ≥ | ∏_{F} LengthB_{i}| = λ^{|I|}.

Posledica 4.4.12 Ako su sve algebre B_{i} beskonačne, onda

Length′B ≥ | ∏_{F} Length′B_{i}|.

U [25] dokazan je sledeći rezultat:

Teorema 4.10 Neka je postojanje κ^{+}-hipermerljivog kardinala μ za neki strogo nedostižan kardinal κ > μ konsistentno sa ZFC. Tada je konsistentno da postoji niz ⟨B_{i} : i ∈ I⟩ Boolovih algebri i ultrafilter F nad I takav da LengthB = λ i ∏_{F} LengthB_{i} = λ^{+}.

4.4.4 Dubina

Definicija 4.4.5 Dubina Boolove algebre A je

DepthA = sup{|X| : X je dobro ured̄en podskup A}.

Lema 4.4.11 Ako je F ω_{1}-kompletan i za sve algebre B_{i} važi DepthB_{i} = ω_{0}, onda je i DepthB = ω_{0}.

Dokaz. Pretpostavimo suprotno: neka je {b_{ξ}^{F} : ξ < ω_{1}} dobro ured¯ en lanac u B (β_{ξ_{1}}^{F} < β_{ξ_{2}}^{F} za ξ_{1} < ξ_{2} < ω_{1}). To znači da za α, β ∈ ω_{1}, α ≠ β, skup J_{α,β} = {i ∈ I : b_{α}(i) < b_{β}(i)} pripada F. Med¯ utim, prema posledici teoreme 1.10 F je i ω_{2}-kompletan, pa ⋂_{α<β<ω_{1}} J_{α,β} ≠ ∅, što je očigledno nemoguće (ako

bi za neko i ∈ I važilo i ∈ ⋂_{α<β<ω_{1}} J_{α,β}, u B_{i} bismo imali dobro ured¯ en lanac

{b_{ξ}(i) : ξ < ω_{1}}). □

Lema 4.4.12 Ako je F ω_{1}-nekompletan, tada DepthB > ℵ_{0}.

Dokaz. Prema lemi 1.2.21 F je i ω_{1}-dobar, pa po teoremi 3.10, B je ω_{1}- zasićena. Neka je {b_{ξ} : ξ < α} maksimalan dobro ured¯ en lanac u B, i za svako ξ < α obeležimo sa φ_{ξ}(x) formulu x > b_{ξ}. Skup {φ_{ξ}(x) : ξ < α} je konačno zadovoljiv u (B, b_{ξ})_{ξ<α}, pa je i zadovoljiv, što znači da postoji b ∈ B takav da b > b_{ξ} za sve ξ < α, što je u suprotnosti sa maksimalnošću dobro ured¯ enog lanca. □

Primetimo da Depth nije ultra-sup funkcija (da bi bio zadovoljen uslov iz definicije potrebno je da F bude ω_{1}-kompletan, videti odeljak o ultraproizvodima dobrih ured¯ enja). Stoga o njoj imamo slabije rezultate, koji slede iz odgovarajućih rezultata o ultraproizvodima dobrih ured¯ enja (leme 4.2.10, 4.2.11 i teoreme 4.2).

Posledica 4.4.13 Ako je F regularan, |I| = κ i sve algebre B_{i} su beskonačne, onda je DepthB ≥ κ^{+}.

Posledica 4.4.14 Ako je |I| = κ ≥ ℵ_{0} i sve algebre B_{i} su beskonačne, onda postoji pravi filter G na I koji sadrži sve komplemente konačnih podskupova I takav da za sve ultrafiltere F ⊇ G važi Depth ∏_{F} B_{i} ≥ 2^{κ}.

Posledica 4.4.15 Ako je κ najmanji merljiv kardinal, F ω_{1}-kompletan i DepthB_{i} ≥ κ, onda je DepthB ≥ κ^{+}.

4.4.5 Topološka gustina

Definicija 4.4.6 Topološka gustina Boolove algebre A, u oznaci dA, je najmanji kardinal κ takav da postoji gust podskup skupa Ult(A) kardinalnosti κ.

Kao što vidimo, topološka gustina nije direktno povezana sa poretkom na algebri, ali smo je ipak uvrstili u ovaj izbor radi pored¯ enja sa algebarskom gustinom, i zbog sledeće leme:

Lema 4.4.13 Za svaku beskonačnu Boolovu algebru A kardinal dA jednak je svakom od sledećih:

(a) min{κ : A je izomorfno nekoj podalgebri algebre P(κ)}; (b) min{κ : A je κ-centrirana} (Boolova algebra A je κ-centrirana ako

je A \ {0} unija κ centriranih podskupova, tj. takvih da je infimum konačno mnogo elemenata svakog od njih različit od nule);

(c) min{κ : A \ {0} je unija κ pravih filtera};

(d) min{κ : A \ {0} je unija κ ultrafiltera}.

Lema 4.4.14 Ako su sve algebre B_{i} beskonačne, onda je

dB ≤ | ∏_{F} dB_{i}|.

Dokaz. Koristićemo prethodnu lemu pod (a). Neka je f_{i} : B_{i} → P(dB_{i}) utapanje za i ∈ I. Definišimo g : B → P(∏_{F} dB_{i}) ovako: za x ∈ ∏_{i∈I} B_{i} neka

g(x^{F}) = {y^{F} : y ∈ ∏_{i∈I} dB_{i} i {i ∈ I : y(i) ∈ f_{i}(x(i))} ∈ F }. g je očigledno

utapanje. □

Naravno, postavlja se pitanje: da li u prethodnoj lemi mora uvek važiti jednakost? U [29] je pokazano da je odgovor negativan:

Teorema 4.11 Neka je λ jak granični kardinal i κ < cf(λ) < λ, |I| = κ i F ω_{1}-nekompletan ultrafilter. Tada postoji familija Boolovih algebri {B_{i} : i ∈ I} takva da dB ≤ λ i ∏_{F} dB_{i} = 2^{λ}.

4.4.6 Algebarska gustina

Definicija 4.4.7 Podskup D Boolove algebre A je gust ako za svako b ∈ A \ {0} postoji d ∈ D \ {0} takvo da d ≤ b. Algebarska gustina Boolove algebre A, u oznaci πA, je najmanji kardinal κ takav da postoji gust podskup algebre A kardinalnosti κ.

Algebarska gustina može se, slično postupku sa ultra-sup funkcijama, proučavati paralelno sa još nekim funkcijama. To je učinjeno u [28], gde se one zovu sup-min funkcije. Mi to nećemo raditi, jer ostale sup-min funkcije nisu povezane sa ured¯ enjem na Boolovoj algebri.

Lema 4.4.15 Ako su sve algebre B_{i} beskonačne, onda je

πB ≤ | ∏_{F} πB_{i}|.

Dokaz. Za svako i ∈ I izaberimo gust podskup D_{i} algebre B_{i} kardinalnosti πB_{i}. Dokažimo da je skup ∏_{F} D_{i} (preciznije skup klasa ekvivalencije svih

elemenata iz ∏_{F} D_{i}) gust u B, što će značiti da je gustina algebre B najvi-

še | ∏_{F} D_{i}|. Neka je f^{F} ∈ B. Za svako i ∈ I neka je g(i) ∈ B_{i} takav da

g(i) ≤ f(i). Tada g^{F} ∈ ∏_{F} D_{i} i g^{F} ≤ f^{F}. □

Ponovo se postavlja pitanje: da li mora uvek da važi jednakost? U nekim slučajevima odgovor je potvrdan. Da bismo to uvideli, treba nam sledeća veza izmed¯ u algebarske gustine i celularnosti:

Lema 4.4.16 Za svaku Boolovu algebru A važi cA ≤ πA.

Dokaz. Neka je {a_{ξ} : ξ < κ} antilanac u A i D skup gust u A. Za svako ξ < κ postoji b_{ξ} ∈ D takav da b_{ξ} ≤ a_{ξ}. Takod¯ e, svi elementi b_{ξ} su različiti, jer bi iz b_{ξ} = b_{η} sledilo a_{ξ} ∧ a_{η} ≥ b_{ξ} ≠ 0, što je nemoguće. Dakle, {b_{ξ} : ξ < κ} je podskup kardinalnosti κ u D. □

Lema 4.4.17 Ako su sve algebre B_{i} beskonačne, |I| = κ, F regularan ultrafilter nad I, i πB_{i} ≤ 2^{κ}, onda je

π(B) = | ∏_{F} πB_{i}|.

Dokaz. Kako je B_{i} beskonačna, ona sadrži beskonačan antilanac, pa cB_{i} ≥ ℵ_{0}. Med¯ utim, iz prethodne leme dobijamo πB_{i} ≥ ℵ_{0}, a na osnovu teoreme 3.3 | ∏_{F} πB_{i}| ≤ 2^{κ}. Sve u svemu,

2^{κ} ≤ πB ≤ | ∏_{F} πB_{i}| ≤ 2^{κ},

što je i trebalo dokazati. □

Med¯ utim, ako je πB_{i} > 2^{|I|} za i ∈ I, odgovor zavisi od tzv. hipoteze singularnih kardinala (SCH), koja je konsistentna, ali i nezavisna od ZFC. Ona glasi ovako:

(SCH) Za sve kardinale λ, ako je 2^{cf(λ)} < λ, onda λ^{cf(λ)} = λ^{+}.

Par napomena: iz pretpostavke 2^{cf(λ)} < λ sledi da je λ singularan (odatle i ime); takod¯ e, uvek važi λ^{cf(λ)} ≥ λ^{+}, tako da SCH kaže da λ^{cf(λ)} ima najmanju moguću vrednost.

U [19] su dokazana sledeća dva tvrd¯ enja:

Teorema 4.12 Ako važi SCH, a sve B_{i} su beskonačne, onda je

πB = | ∏_{F} πB_{i}|.

Teorema 4.13 Ako ne važi SCH, onda postoji familija {B_{i} : i ∈ I} beskonačnih Boolovih algebri i ultrafilter F nad I tako da

πB < | ∏_{F} πB_{i}|.

Literatura

[1] J. L. Bell, A. B. Slomson, Models and Ultraproducts: an introduction, North-Holland, 1969.

[2] C. C. Chang, H. J. Keisler, Model Theory, North-Holland, 1973.

[3] W. W. Comfort, S. Negrepontis, The Theory of Ultrafilters, Springer, 1974.

[4] F. Drake, Set Theory: an Introduction to Large Cardinals, North-Holland, 1974.

[5] R. Engelking, General Topology, Monografie matematyczne, tom 60, Państwowe Wydavnictwo Naukowe, 1977.

[6] T. E. Frayne, A. C. Morel, D. S. Scott, Reduced direct products, Fund. Math. 51 (1962), 195-28.

[7] T. Jech, Set Theory, 2^{nd} ed, Springer, 1997.

[8] P. Jipsen, H. Rose, Ultraproducts of atomic Boolean algebras, Bull. Korean Math. Soc. 27 (1990), 19-26.

[9] A. Jovanović, Ultraproducts of well orders, Publicationes de l’Institute Matématique, nouvelle série, 27 (1980), 99-102.

[10] A. Jovanović, Prilog teoriji ultraproizvoda, doktorska disertacija, Matematički Fakultet u Beogradu, 1982.

[11] H. J. Keisler, Ultraproducts and saturated models, Indag. Math. 26 (1964), 178-186.

[12] H. J. Keisler, On cardinalities of ultraproducts, Bull. Amer. Math. Soc. 70 (1964), 644-647.

[13] H. J. Keisler, Limit ultraproducts, Journal of Symbolic Logic 30 (1965), 212-233.

[14] H. J. Keisler, Ultraproducts which are not saturated, Journal of Symbolic Logic 32 (1967), 23-46.

[15] H. J. Keisler, Ultraproducts of finite sets, Journal of Symbolic Logic 32 (1967), 47-57.

[16] H. J. Keisler, Model Theory for Infinitary Logic, North-Holland, 1971.

[17] H. J. Keisler, K. Prikry, A result concerning cardinalities of ultraproducts, Journal of Symbolic Logic 39 (1974), 43-48.

[18] S. Koppelberg, Cardinalities of ultraproducts of finite sets, Journal of Symbolic Logic 45 (1980), 574-584.

[19] S. Koppelberg, S. Shelah, Densities of ultraproducts of Boolean algebras, Canadian Journal of Math. 47 (1995), 132-145.

[20] K. Kunen, Set Theory: an Introduction to Independence Proofs, North-Holland, 1980.

[21] Kunen K, Prikry K, On descendingly incomplete ultrafilters, Journal of Symbolic Logic 36 (1971), 650-652.

[22] M. Kurilić, Osnovi opšte topologije, Univerzitet u Novom Sadu, 1998.

[23] P. Lipparini, Every (λ^{+}, κ^{+})-regular ultrafilter is (λ, κ)-regular, Proc. Amer. Math. Soc. 128 (1999), 605-609.

[24] M. Magidor, On the existence of nonregular ultrafilters and the cardinality of ultrapowers, Trans. Amer. Math. Soc. 249 (1979) 97-111.

[25] M. Magidor, S. Shelah, Length of Boolean algebras and ultraproducts, Mathematica Japonica 48 (1998), 301-307.

[26] Ž. Mijajlović, An Introduction to Model Theory, Univerzitet u Novom Sadu, 1987.

[27] D. Monk, Cardinal Functions on Boolean Algebras, Birkhauser, 1990.

[28] D. Peterson, Cardinal functions on ultraproducts of Boolean algebras, Journal of Symbolic Logic 62 (1997), 43-59.

[29] A. Roslanowski, S. Shelah, Cardinal invariants of ultraproducts of Boolean algebras, Fund. Math. 155 (1998) 101-151.

[30] A. Roslanowski, S. Shelah, More on cardinal invariants of Boolean algebras, Annals of Pure and Applied Logic.

[31] S. Shelah, Every two elementarily equivalent models have isomorphic ultrapowers, Israel J. of Math. 10 (1971), 224-233.

[32] S. Shelah, On Monk’s questions, Fund. Math. 151 (1996), 1-19.

[33] S. Shelah, σ-entangled linear orders and narrowness of products of Boolean algebras, Fund. Math. 153 (1997), 199-275.

[34] S. Shelah, O. Spinas, On incomparability and related cardinal functions on ultraproducts of Boolean algebras, Mathematica Japonica 52 (2000), 345-358.

[35] R. Sikorski, Boolean Algebras, Springer, 1964.

[36] B. Šobot, Higher order fixed points of normal functions and an application to well-ordered ultrapowers of ordinals, preprint.

[37] B. Šobot, Ultraproducts of trees, u Extended abstracts of 4^{th} Panhellenic Logic Symposium, 2003.

[38] S. Todorčević, Trees, subtrees and order types, Ann. Math Logic 20, (1981), 233-268.

[39] S. Todorčević, Trees and linear orderings, u Handbook of Set-Theoretic Topology, North-Holland, 1988.

Biografija

Šobot Boris je rod¯ en 14. juna 1977. godine u Novom Sadu. Završio je gimnaziju ”J. J. Zmaj” u Novom Sadu. Diplomirao je matematiku na smeru Profesor matematike Prirodno-matematičkog fakulteta u Novom Sadu 2000. godine sa prosekom 10.00, a potom i informatiku na smeru Diplomirani informatičar istog fakulteta 2002. godine. 2000. godine upisao je magistarske studije iz matematike, smer Algebra i matematička logika.

Novi Sad, 24. 5. 2004. Boris Šobot

UNIVERZITET U NOVOM SADU PRIRODNO-MATEMATIČKI FAKULTET KLJUČNA DOKUMENTACIJASKA INFORMACIJA

Redni broj: RBR

Identifikacioni broj: IBR

Tip dokumentacije: monografska dokumentacija TD

Tip zapisa: tekstualni štampani materijal TZ

Vrsta rada: magistarska teza VR

Autor: Boris Šobot AU

Mentor: dr Milan Grulović MN

Naslov rada: Ultrafiltri i ultraproizvodi MR

Jezik publikacije: srpski (latinica) JP

Jezik izvoda: srpski i engleski JI

Zemlja publikovanja: Srbija i Crna Gora ZP Uže geografsko područje: Vojvodina UGP

Godina: 2004 GO

Izdavač: autorski reprint IZ

Mesto i adresa: Novi Sad, Trg Dositeja Obradovića 4 MA

Fizički opis rada: 4 poglavlja, 93 strane, 39 literarnih citata, 0 slika, 0 grafika, 0 priloga FO

Naučna oblast: matematika NO

Naučna disciplina: matematička logika ND

Ključne reči: ultrafiltri, ultraproizvodi, parcijalna ured¯ enja PO

UDK:

Čuva se: ČU

Važna napomena: VN

Izvod: ova teza opisuje najvažnije vrste i osobine ultrafiltera, a zatim konstrukciju ultraproizvoda, sa posebnim naglaskom na osobine koje se očuvavaju pri konstrukciji ultraproizvoda, i primenom na ultraproizvode parcijalnih ured¯ enja.

IZ

Datum prihvatanja teme od strane NN veća: DP

Datum odbrane: DO

Članovi komisije: KO

Predsednik: dr Gradimir Vojvodić, redovni profesor Prirodno matematičkog fakulteta u Novom Sadu

Mentor: dr Milan Grulović, redovni profesor Prirodno matematičkog fakulteta u Novom Sadu

Član: dr Miloš Kurilić, vanredni profesor Prirodno matematičkog fakulteta u Novom Sadu

Član: dr Žarko Mijajlović, redovni profesor Matematičkog fakulteta u Beogradu

Član: dr Aleksandar Jovanović, vanredni profesor Matematičkog fakulteta u Beogradu UNIVERSITY OF NOVI SAD FACULTY OF SCIENCE KEY WORDS DOCUMENTATION

Accession number: ANO

Identification number: INO

Document type: Monograph type DT

Type of record: Printed text TR

Contents code: Master thesis CC

Author: Boris Šobot AU

Mentor: dr Milan Grulović MN

Title: Ultrafilters and ultraproducts XI

Language of text: Serbian (latin) LT

Language of abstract: serbian and english LA

Country of publication: Serbia and Montenegro CP Locality of publication: Vojvodina LP

Publication year: 2004 PY

Publisher: Author’s reprint PU

Publication place: Novi Sad, Trg Dositeja Obradovića 4 PP

Physical description: 4 chapters, 93 pages, 39 citations, 0 pictures, 0 graphs, 0 appendices PD

Scientific field: Mathematics SF

Scientific discipline: Matematical logic SD

Key words: ultrafilters, ultraproducts, partial orders UC

Holding data:

HD note:

Abstract: the thesis describes the most important types and properties of ultrafilters, as well as the construction of ultraproducts, with particular accent to properties preserved by construction of ultraproducts, and applications to ultraproducts of partial orders. AB

Accepted by the Scientific Board on:

Defended on:

Thesis defend board: President: dr Gradimir Vojvodić, professor at Faculty of Science, Novi Sad

Mentor: dr Milan Grulović, professor at Faculty of Science, Novi Sad Member: dr Miloš Kurilić, associate professor at Faculty of Science, Novi Sad Member: dr Žarko Mijajlović, professor at Faculty of Mathematics, Belgrade Member: dr Aleksandar Jovanović, associate professor at Faculty of Mathemat-

ics, Belgrade