Rješenja pismenog ispita iz Teorije skupova 2006-02-24

1. 1. Označimo skup beskonačnih podskupova od ℚ sa S. Očito je S⊆℘(ℚ), pa vrijedi card S≤card ℘(ℤ)=2^ℵ₀=c. S druge strane, lako je konstruirati injekciju sa ℝ u S: svakom realnom x pridružimo {y∈ℚ:y≤x}. (To je injekcija jer između svaka dva realna broja postoji bar jedan racionalan broj.) Dakle, card S≤c, što skupa s ovim gore daje card S=c.
   2. Sigurno ih ima ne više nego svih segmenata u ℝ, dakle najviše kontinuum. S druge strane, svakom realnom x iz segmenta [1/4,1/3] možemo injektivno pridružiti segment [x,1/2] koji je disjunktan sa ℤ. To znači da ih ima barem koliko i realnih brojeva u segmentu [1/4,1/3], a to je kontinuum.
      Možemo i direktno: ako skup takvih segmenata označimo s T, funkcija f:ℤ×〈0,1〉×〈0,1〉→T;(m,y,z)↦[m+y⋅z,m+y] je bijekcija (dokažite).
      
2. ∑_{α∈ω⋅2+2}(2+α+2^α)= ∑_α∈ω(2+α+2^α)+ ∑_α∈ω(2+(ω+α)+2^ω+α)+ (2+ω⋅2+2^ω⋅2)+ (2+(ω⋅2+1)+2^ω⋅2+1)= sup_n∈ω∑_α=0..n-1(2+α+2^α)+ sup_m∈ω∑_α=0..m-1(ω+α+2^ω⋅2^α)+ (ω⋅2+(2^ω)²)+ (ω⋅2+1+(2^ω)²⋅2)= sup_n∈ω(2+0+2⁰+2+1+2¹+...+2+n-1+2^n-1)+ sup_m∈ω(ω⋅(1+2⁰+1+2¹+...+1+2^m-1))+ (ω⋅2+ω²+ω⋅2+ω²⋅2)= ω+ω⋅sup_m∈ω(1+2⁰+1+2¹+...+1+2^m-1)+ω⋅(2+ω+2+ω⋅2)= ω+ω⋅ω+ω⋅(ω+ω⋅2)= ω²+ω²⋅3=ω²⋅4.
3. Tvrdnja ne vrijedi, kontraprimjer je kanonski ne-dobro uređen skup ω^*. Za njega stvarno postoji jedinstvena auto-sličnost, što nije problem dokazati matematičkom indukcijom, ili na sljedeći način: uzmemo konkretni skup tipa ω^*, recimo ℤ⁻ uređen standardno, i neka je f:ℤ⁻→ℤ⁻ sličnost. Tada, budući da je s m(x):=-x zadana sličnost između ℤ⁻ i ℤ⁺, te je kompozicija sličnosti sličnost, vidimo da je m∘f∘m sličnost između ℤ⁺ i ℤ⁺. Budući da je ℤ⁺ dobro uređen, za njega postoji jedinstvena sličnost i to je identiteta. Dakle m∘f∘m je identiteta na ℤ⁺, a onda je f identiteta na ℤ⁻. Dakle, svaka auto-sličnost od ℤ⁻ je identiteta, odnosno postoji jedinstvena takva. No ℤ⁻, naravno, nije dobro uređen, jer sâm nema najmanji element.
   
4. Promotrimo skup T:={y∈S:y≼x}. T je parcijalno uređen restrikcijom uređaja ≽, obrnutog uređaju ≼, odnosno možemo pisati da je (T,≽) PUS. Budući da imamo refleksivan uređaj, vrijedi x≼x, dakle x∈T, pa T nije prazan. Svaki lanac u T je neprazan totalno ≽-uređen podskup u T, dakle i neprazan totalno ≼-uređen podskup u S, odnosno lanac u S, pa po pretpostavci zadatka ima ≼-donju među u S; označimo je s d. Budući da je lanac neprazan, u njemu postoji bar jedan element l. Budući da je lanac u T, vrijedi l∈T, odnosno l≼x. Budući da je d ≼-donja međa za taj lanac, specijalno vrijedi d≼l, pa po tranzitivnosti d≼x, odnosno d∈T. Sada primijetimo, budući da je T uređen obrnuto od S, da je d gornja međa za naš lanac u skupu T. Odnosno, svaki lanac u T ima gornju među u T. Vidimo da su ispunjeni svi uvjeti Zornove leme za skup T, pa postoji maksimalni element u T; nazovimo ga z. Budući da je z∈T, odmah imamo z≼x. Treba još vidjeti da je z minimalan element u S (Zornova lema nam daje da je maksimalan u T). Pretpostavimo da postoji w∈S takav da je w≺z. Po tranzitivnosti bi tada bilo i w≺x, odnosno w∈T, što je u kontradikciji s maksimalnošću od z u skupu T (sjetimo se, T je obrnuto uređen). Dakle, z je stvarno minimalan element u skupu S, i vrijedi z≼x.
5. Neka su x i y elementi od ℕ, takvi da x ne završava znamenkom 0 (nije djeljiv s 10). Ako zadnju znamenku od x označimo s a, a prvu znamenku od y označimo s b (b:=0 ako je y=0), vidimo da je x u relaciji R s 10a+b, te je 10a+b u relaciji R s y. Dakle, x je u relaciji R² s y, pa je pâr (x,y) u tranzitivnom zatvorenju od R (svaka tranzitivna relacija koja sadrži R mora sadržavati i parove (x,y) i (y,z), a time i (x,z)). S druge strane, ako je x djeljiv s 10, on je u relaciji jedino s 0. Budući da je 0 također djeljiva s 10, svaki "lanac" oblika xRyR...Rz mora završavati nulom, odnosno za tranzitivno zatvorenje možemo dodati samo još (x,0), gdje su x djeljivi s 10. Dakle R⁺=R²=((ℕ\10ℕ)×ℕ)∪(10ℕ×{0}).