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}).

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

1. 1. Označimo skup čiji broj elemenata tražimo sa S. Očito je S⊆℘(ℤ), pa vrijedi card S≤card ℘(ℤ)=2^ℵ₀=c. S druge strane, svaki podskup od ℕ je dobro uređen i podskup od ℤ. Dakle, ℘(ℕ)⊆S, odnosno card ℘(ℕ)=2^ℵ₀=c≤card S. Sve u svemu, card S=c.
   2. Ako je T skup takvih funkcijâ, preslikavanje g:T→C¹(ℝ⁻)×ℝ×C²(ℝ⁺);f↦(f|_ℝ⁻,f(0),f|_ℝ⁺) je bijekcija. (Injekcija je jer se dvije funkcije s ℝ u ℝ koje se razlikuju, razlikuju ili na ℝ⁻, ili u nuli, ili na ℝ⁺. Surjekcija je jer se svaka uređena trojka (f₁,a,f₂) u kodomeni može dobiti kao g(f), gdje je f po slučajevima definirana kao f₁, a, odnosno f₂.) Dakle, card T=card(C¹(ℝ⁻)×ℝ×C²(ℝ⁺))=(card C¹(ℝ⁻))⋅(card ℝ)⋅(card C²(ℝ⁺)). Prvi i treći kardinalni broj su jednaki c, argumentom koji je napravljen na vježbama. Odnosno, card T=c⋅c⋅c=c³=c.
2. Tvrdnja vrijedi. Da bismo je dokazali, dokazujemo dvije inkluzije.
   • (⊆) Neka je x∈⋃⋃A² proizvoljan. To znači, po definiciji unije, da postoji y∈⋃A² takav da je x∈y. Opet po definiciji unije, imamo da postoji z∈A² takav da je y∈z. Budući da je z∈A², z je uređen par elemenata iz A, recimo z=(a,b)={{a},{a,b}}, gdje su a i b elementi iz A. Sada, po definiciji para y∈z znači y={a} ili y={a,b}, a u svakom od tih slučajeva opet po definiciji para x∈y povlači x=a ili x=b. U svakom slučaju x∈A.
   • (⊇) Neka je s∈A proizvoljan. Tada je (s,s)={{s}}∈A², pa je {s}∈⋃A² (jer je {s}∈{{s}}∈A²), te je s∈⋃⋃A² (jer je s∈{s}∈⋃A²).
3. ∏_α∈ω+2(α+2)^α+1= (∏_α∈ω(α+2)^α+1)⋅(ω+2)^ω+1⋅(ω+3)^ω+2=
   (sup_n∈ω∏_α=0..n-1(α+2)^α+1)⋅(ω+2)^ω⋅(ω+2)⋅(ω+3)^ω⋅(ω+3)⋅(ω+3)=
   sup_n∈ω(2¹⋅3²⋅...⋅(n+1)ⁿ)⋅ω^ω⋅(ω+2)⋅ω^ω⋅((ω+3)⋅ω+ω+3+ω+3+ω+3)=
   ω⋅ω^ω⋅ω^ω⋅(ω²+ω⋅3+3)= ω^ω⋅2+2+ω^ω⋅2+1⋅3+ω^ω⋅2⋅3
4. 2≤ℵ₀≤2^c, pa je 2^c≤ℵ₀^c≤(2^c)^c=2^c⋅c=2^c, odnosno ℵ₀^c=2^c.
   1≤ℵ₁≤c (ovo zadnje jer je ℵ₁ najmanji od svih kardinalnih brojeva većih od ℵ₀, a c je veći od ℵ₀ po Cantorovom teoremu), pa je c=1⋅c≤ℵ₁⋅c≤c⋅c=c, odnosno ℵ₁⋅c=c.
   Dakle, (ℵ₁⋅c)^ℵ₀=c^ℵ₀=(2^ℵ₀)^ℵ₀=2^{ℵ₀⋅ℵ₀}=2^ℵ₀=c.
   Sve u svemu, rezultat je 2^c+c, što je između 2^c+0=2^c i 2^c+2^c=2⋅2^c=2^c+1=2^c; dakle jednak je 2^c.
   
5. Promotrimo skup T:={y∈S:y≻x}.
   T je parcijalno uređen restrikcijom uređaja ≺, možemo pisati da je (T,≺) PUS.
   Također, budući da x nije maksimalan, postoji bar jedan y∈S takav da je y≻x, odnosno 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 kao takav ima gornju među u S; označimo je s g. 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 g gornja međa za taj lanac, specijalno vrijedi g≽l, pa po tranzitivnosti g≻x, odnosno g∈T. Dakle, 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 maksimalan element u S (Zornova lema nam samo 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. Dakle, z je stvarno maksimalan element u skupu S, i vrijedi z≻x.
   

Aksiom izbora i (bes)konačni izbori

From: Veky <vedgar@gmail.com>
Date: Feb 17, 2006 12:49 PM
Subject: Re: Teorijsko pitanje iz teorije skupova...
To: Goran

On 2/16/06, Goran wrote:

Ima jedna stvar u koju nisam siguran pa bih trebao pomoć...
Radi se o aksiomu izbora. Koliko sam ja zaključio AC nam treba samo kada je familija iz koje "čupamo" elemente beskonačna?

Ukratko, da. Evo relativno jednostavnog heurističkog objašnjenja za to:
dokaz je slog od konačno mnogo izjavâ, koje slijede jedna iz drugih po strogo definiranim pravilima. Ako imamo konačno mnogo nepraznih disjunktnih skupova, možemo za svaki od njih reći "taj skup je neprazan, dakle po definiciji nepraznog skupa postoji element u njemu". To efektivno znači i da ga možemo izabrati, jer kad ne bismo mogli, skup bi bio prazan.

No kada imamo beskonačno mnogo skupova, ne možemo koristiti gornji argument, jer bismo na taj način imali beskonačno mnogo koraka u dokazu. Treba nam ili algoritamsko pravilo po kojem možemo u konačno mnogo izjavâ izabrati po jedan element iz beskonačno mnogo skupova (poznata je ona Russellova "Aksiom izbora nam treba za odabrati po jednu čarapu iz beskonačno mnogo parova čarapâ, ali za cipele nam ne treba: možemo iz svakog para odabrati lijevu cipelu.":), ili pak aksiom koji će nam reći da kao što nešto možemo u konačnosti (izabirati elemente), tako možemo i u beskonačnosti -- uvijek -- iako, naravno, ne kaže kako.

Mislim, jer kada smo dokazivali na predavanjima da je konačna unija prebrojivih skupava prebrojiva, onda nismo koristili AC, dok smo za prebrojivu familiju koristili AC...

Naravno. Jer da je skup prebrojiv, to samo znači da postoji bijekcija između njega i ℕ. Odnosno, jezikom TS, skup svih takvih bijekcijâ je neprazan. Ako imamo konačno mnogo prebrojivih skupova A_i, tada imamo i konačno mnogo nepraznih skupova bijekcijâ između A_i i ℕ. Da bismo iz svakog od tih skupova bijekcijâ odabrali po jednu (što nam treba za nastavak dokaza), nije nam potreban aksiom izbora.

No kada imamo prebrojivo mnogo prebrojivih skupova A_i, to znači da imamo, za svaki i, neprazan skup bijekcijâ između A_i i ℕ, te da bismo odabrali po jednu iz svakog skupa (što nam treba za nastavak dokaza), treba nam aksiom izbora (nekom algoritamskom pravilu se ne možemo nadati, ako su A_i proizvoljni skupovi).

Nadalje, nije mi jasno gdje se točno koristi AC kod dokaza
da beskonačan skup A ima prebrojiv podskup: Uzmemo element x0 iz A, pa je A\{x0} neprazan, pa uzmemo x1 iz A\{x0}, pa je A\{x0,x1} neprazan i tako dalje...

Nadam se da je sad jasnije. Ako je A beskonačan, on ima i beskonačno mnogo (čak i više:) nepraznih podskupova. U svakom od njih se može odabrati po jedan element, no da bismo to učinili u konačno mnogo koraka, treba nam aksiom izbora. Netko može reći da ne moramo izabrati po jedan element iz jako puno (neprebrojivo) nepraznih podskupova od A, kad nam treba samo prebrojivo mnogo akata izbora za dokaz. I to je točno, i postoje slabije varijante, poput aksioma zavisnih izborâ, koji nam može poslužiti ovdje. No treba reći da iako imamo puno manje akata izbora nego što na prvi pogled možemo pomisliti da nam treba (za svaki neprazni podskup od A), još uvijek nam ih treba beskonačno mnogo, i algoritamsko pravilo se (za proizvoljni A) ne može naći, pa moramo koristiti aksiom izbora.

Puno više o tome, i zanimljivo za čitanje, može se naći na http://www.math.vanderbilt.edu/~schectex/ccc/choice.html .

--
~Veky