Rješenja pismenog ispita iz Teorije skupova 2006-09-04

1. 1. Skup svih takvih označimo sa S. S je podskup od ℘(ℝ), pa vrijedi cardS≤2^c. S druge strane, preslikavanje f:℘([0,1])→S;A↦A⋃[2,3] je injekcija (presjekom s [0,1] dobijemo original, a za svaki A je ℝ~[2,3]⊆A⋃[2,3]⊆ℝ, pa je po Cantor-Bernsteinovoj lemi ℝ~A⋃[2,3]), pa je i 2^c=card℘([0,1])≤cardS. Dakle, ima ih koliko i svih podskupova od ℝ, 2^c.
      
   2. Svaki konstantan niz je takav, pa ih ima ne manje nego konstantnih nizova u ℕ, dakle prebrojivo. S druge strane, jer je ℕ dobro uređen, svaki niz u ℕ poprima najmanji element (recimo da ga prvi put poprima u indeksu k — primijetimo da ovdje još jednom koristimo dobru uređenost od ℕ, ovaj put kao domene niza), a ako je padajući, nakon indeksa k mora biti stacionaran: i>k⇒a_i=a_k. Ako sad svakom takvom nizu (a_i)_i∈ω pridružimo konačni niz (a_i)_i≤k, dobit ćemo injekciju: iz slike je trivijalno reorganizirati original, samo posljednji element ponovimo još beskonačno mnogo puta. Dakle, gornja ograda za naš kardinalni broj je cardℕ^*=ℵ₀, pa zaključujemo da padajućih nizova u ℕ ima prebrojivo.
   
   
2. Sumand za konačne indekse iznosi i⋅ω+ω⋅i=ω+ω⋅i=ω⋅(i+1), pa tom dijelu sume odgovara ω⋅∑_i∈ω(i+1)=ω⋅ω=ω². Na to treba još nadodati ω⋅ω+ω⋅ω=ω²⋅2, zatim (ω+1)⋅ω+ω⋅(ω+1)=ω²+ω²+ω=ω²⋅2+ω, i još (ω+2)⋅ω+ω⋅(ω+2)=ω²+ω²+ω⋅2=ω²⋅2+ω⋅2, tako da je krajnji rezultat ω²+ω²⋅2+ω²⋅2+ω+ω²⋅2+ω⋅2=ω²⋅7+ω⋅2 (ω se apsorbira u ω²⋅2).
   
3. Ako je x∈⋃A², postoji neki element p∈A² takav da je x∈p. Svaki element od A² je uređen par elemenata od A, pa je tako i p=(a,b)={{a},{a,b}} za neke a i b iz A. Sada x∈p znači x={a}∨x={a,b}. U svakom slučaju x⊆A, dakle x∈℘(A). Zaključak: vrijedi ⋃A²⊆℘(A).
   Druga inkluzija nikada ne vrijedi, jer je uvijek ∅∈℘(A), ali ∅ nikada nije uređeni par (svaki uređen par ima 1 ili 2 elementa).
   

4. irefleksivnost:

   Pretpostavimo da je A⊆ω takav da je A⊏A. To bi značilo da postoji n∈A\A=∅, a to je očito nemoguće.
   

   tranzitivnost:

   Neka je A⊏B i B⊏C. To znači da postoje m∈B\A takav da je A∩m=B∩m, i n∈C\B takav da je B∩n=C∩n. Kako je m∈B, a n∉B, zaključujemo m≠n, a kako su m i n prirodni brojevi, vrijedi m<n (dakle m⊂n, također i m∈n) ili m>n (dakle m⊃n, pa i m∋n). (Napomena: ovo nije trivijalno simetrična situacija, dakle ne možemo BSO pretpostaviti jednu od tih mogućnostî — trebamo dokazati A⊏C za svaku od njih.)
   U prvom slučaju je m=n∩m, pa je C∩m=C∩(n∩m)=(C∩n)∩m= (B∩n)∩m=B∩(n∩m)=B∩m=A∩m. Također vrijedi m∈B∩n=C∩n⊆C∧m∉A, dakle postoji m∈C\A takav da je C∩m=A∩m, odnosno vrijedi A⊏C.
   U drugom slučaju je n=m∩n, pa je C∩n=B∩n=B∩(m∩n)=(B∩m)∩n= (A∩m)∩n=A∩(m∩n)=A∩n. Sada za n vrijedi n∈C, i još samo treba dokazati n∉A. Kad bi bilo n∈A, zbog n∈m bi vrijedilo n∈A∩m=B∩m⊆B, što je nemoguće jer je n∈C\B. Dakle, postoji n∈C\A za koji je C∩n=A∩n, pa je opet A⊏C.
   

   totalnost:

   Za proizvoljne različite podskupove od ω, A≠B, pogledajmo simetričnu razliku A△B⊆ω. Ako su A i B različiti, tada je A△B neprazan (kontrapozicija toga je aksiom ekstenzionalnosti) podskup od ω, pa zbog dobre uređenosti od ω ima najmanji element — označimo ga s x. Dakle, x∈A△B=(A\B)∪(B\A), pa zbog simetrije BSOMP x∈B\A. Ako je sada y∈x proizvoljan, tada je y<x, pa y∉A△B (x je najmanji). To znači da je y∈A⇔y∈B (za y∈x), pa je A∩x=B∩x. Dakle, postoji x∈B\A takav da je A∩x=B∩x, pa je A⊏B, odnosno A i B su usporedivi.
   

   
   
5. Označimo sa ℬ skup svih algebrî skupova ℱ⊆℘(ℝ), takvih da je ℚ∉ℱ. Skup ℱ₀:={∅,ℝ} očito zadovoljava aksiome, pa je ℱ₀∈ℬ, odnosno ℬ≠∅. ℬ parcijalno uredimo standarno relacijom ⊆.
   Neka je ℒ⊆ℬ, ℒ≠∅ lanac u ℬ. Želimo dokazati postoji gornja međa za ℒ u ℬ. ⋃ℒ je uvijek gornja međa za ℒ ako je uređaj ⊆, no treba dokazati ⋃ℒ∈ℬ — odnosno, da je ⋃ℒ algebra skupova, i da ℚ∉⋃ℒ.
   
   • Kako je ℒ neprazan, postoji ℱ₁∈ℒ. ℱ₁ je algebra skupova, pa po prvom aksiomu imamo ∅∈ℱ₁, a time i ∅∈⋃ℒ.
     
   • Ako je A∈⋃ℒ proizvoljan, postoji ℱ∈ℒ takav da je A∈ℱ. Opet, kako je ℱ algebra skupova, mora biti i ℝ\A∈ℱ⊆⋃ℒ.
     
   • Ako su A₁,A₂,...,A_n proizvoljni skupovi iz ⋃ℒ, postoje elementi lanca ℱ₁,ℱ₂,...,ℱ_n takvi da je svaki A_i iz odgovarajuće algebre skupova ℱ_i. Kako su sve ℱ_i međusobno usporedive, a ima ih konačno mnogo, među njima postoji ⊆-najveća — označimo je s ℱ'∈ℬ. To znači da su svi A_i iz ℱ', pa kako je ℱ' algebra skupova, vrijedi i ⋃_i∈[1..n]A_i∈ℱ'⊆⋃ℒ.
     
   • I za kraj, pretpostavka ℚ∈⋃ℒ bi značila da postoji ℱ∈ℒ⊆ℬ takva da je ℚ∈ℱ, što je nemoguće jer je ℱ∈ℬ, a elementi od ℬ po definiciji ne sadrže ℚ kao element.
   
   Zaključujemo da je ⋃ℒ zaista algebra skupova koje ℚ nije element, pa je ⋃ℒ∈ℬ i kao takva je gornja međa za ℒ u ℬ.
   Dakle, svaki lanac u ℬ ima gornju među u ℬ, a gore smo vidjeli da je PUS ℬ neprazan, pa po Zornovoj lemi postoji maksimalni element u ℬ, što je upravo maksimalna algebra skupova nad ℝ koja ne sadrži ℚ kao element.