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

Teorijska pitanja iz prvog kolokvija iz UM

1. Napišite definiciju jednakosti skupova.
   
2. Karakterizirajte jednakost skupova pomoću inkluzije.
   
3. Napišite definiciju relacije ekvivalencije, s detaljnim opisom svojstava, te dajte jedan primjer.
   
4. Iskažite teorem o odnosu među klasama ekvivalencije.
   
5. Iskažite osnovni teorem aritmetike (o kanonskom rastavu prirodnog broja), te dajte jedan primjer.
   

1. Napišite definiciju uređenog para.
   
2. Karakterizirajte jednakost uređenih parova.
   
3. Napišite definiciju parcijalnog uređaja, s detaljnim opisom svojstava, te dajte jedan primjer.
   
4. Napišite definiciju klase ekvivalencije, te dajte jedan primjer.
   
5. Iskažite teorem o dijeljenju s ostatkom.
   

1. Napišite definiciju particije skupa, te dajte jedan primjer.
   
2. Napišite definiciju Kartezijevog produkta skupova.
   
3. Napišite definiciju kogruencije.
   
4. Iskažite teorem o odnosu među klasama ekvivalencije.
   
5. Iskažite teorem o dijeljenju s ostatkom.
   

Zornova lema i (a)tipični uređaji

From: Veky <vedgar@gmail.com>
Date: Feb 8, 2006 1:43 PM
Subject: Re: ts,kolokvij
To: Kristina

On 2/8/06, Kristina wrote:

...me zanima na cemu sam izgubila bod:) u zadatku sa Zornovom lemom. Jeli nesto bas vezano za Z. lemu ili nesto s vektorskim potprostorima. Dakle, nije da se zalim, nego me cisto zbog usmenog zanima ako nesto krivo radim s Z. lemom.

Hm... ima jedna trivijalna stvar, a to je da ne možete reći "BSOMP V₁<V₂" ako situacija nije simetrična. Kod Vas nažalost nije, jer ste za opću linearnu kombinaciju uzeli x+λ∙y, dakle x i y nisu ravnopravni (preciznije, ako je V₂<V₁, onda trebate još jedan korak da zaključite da je λ∙x u istom prostoru kao i x). No čovjek bi trebao biti puno veća cjepidlaka čak i od mene da bi Vam za to skinuo bod. :-)

Stvar zbog koje ste izgubili bod je ova: ako imamo standardni parcijalni uređaj "⊂" na familiji skupova ℱ, onda znamo da je ⋃ℒ gornja međa lanca ℒ. Štoviše, znamo da je to najmanja gornja međa, i prirodno je za nju provjeravati je li u ℱ. No ako imamo neki drugi uređaj (na primjer "<", "biti potprostor", u Vašem slučaju), to ne možemo znati. Tada imate dvije mogućnosti:

1. Dokazati da je za Vašu familiju ℱ "biti podskup" ekvivalentno s "biti potprostor" (što je ok, jer se u ℱ nalaze samo potprostori od V), slično kao što smo napravili za podgrupe na vježbama: jedan smjer očito vrijedi (potprostor je podskup), a za drugi: ako je V₁⊂V₂, te su V₁ i V₂ potprostori od V, to znači da je V₁ vektorski prostor s obzirom na restringirane operacije, dakle V₁<V₂.
2. Uzeti pravu "najmanju gornju među" s obzirom na relaciju "biti potprostor", a to je, kao što možda znate iz LA, suma potprostora (ne unija). Tada, naravno, ima malo posla na drugom kraju: dokazati da se u toj sumi ne može kojim slučajem naći vektor x.

Ja sam zamislio da se zadatak riješi na prvi način (jer smo tako riješili analogni zadatak s grupama na vježbama), ali nemam ništa protiv (dapače, drago mi je:) ako netko riješi na ovaj drugi način (npr. kolega G.R. — tako da za detalje te metode možete njega pitati:).

HTH,
--
~Veky

Rješenja kolokvija iz Uvoda u matematiku 2006-02-06

2. Dokazujemo matematičkom indukcijom.
   

   Baza

   1³=1>(1-1)⋅(2⋅1-1)=0⋅1=0
   

   Pretpostavka

   Pretpostavimo da je za neki k∈ℕ, k³>(k-1)⋅(2k-1)=2k²-3k+1.
   

   Korak

   Trebamo dokazati da je (k+1)³>(k+1-1)(2(k+1)-1)=k(2k-1)=2k²-k.
   
   Koristeći pretpostavku, možemo dobiti (k+1)³=k³+3k²+3k+1>2k²-3k+1+3k²+3k+1=5k²+2.
   
   Dakle, sve što još trebamo dokazati je 5k²+2>2k²-k za sve prirodne k. No to je ekvivalentno s 3k²-k+2>0, što vrijedi čak za sve realne k (jer je diskriminanta=-23 negativna, a vodeći_član=3 pozitivan).

   
   
   
3. Tri uvjeta zadana u zadatku nam znače p(1)=2, p(-1)=0, te p(0)=2. Ako p(x) podijelimo s x³-x (stupnja 3), dobit ćemo ostatak stupnja strogo manjeg od 3 (ili nulpolinom), dakle nešto oblika r(x)=ax²+bx+c. Sve u svemu, imamo p(x)=(x³-x)q(x)+ax²+bx+c. Uvrštavajući u to za x brojeve -1, 0 i 1, dobijemo 0=a-b+c, 2=c, te 2=a+b+c, iz čega se lako dobije b=-1 i a=1. Dakle ostatak je r(x)=x²-x+2.
   
   
4. Budući da je zadani polinom jednak f(x)=2x³+7x²+4x-4, cjelobrojna nultočka mora biti djelitelj slobodnog člana 4, dakle iz skupa {1,-1,2,-2,4,-4}. Uvrštavanjem (npr. pomoću Hornerove sheme) se dobije da je -2 nultočka. Uvrštavajući -2 redom u derivacije od f(x) (ili u kvocijente koji se dobiju iz Hornerove sheme), dobije se da je f'(-2)=0, te f''(-2)=-10≠0. Dakle, kratnost nultočke -2 jednaka je 2.
   
   
5. Prebacivši 1 na lijevu stranu nejednadžbe, faktoriziranjem nazivnika i svođenjem na zajednički nazivnik, dobije se ekvivalentna nejednadžba 2(5x+4)/(x-2)(x-1)≥0. To se može riješiti pomoću tablice, gledanjem predznaka pojedinih faktorâ na intervalima određenim točkama -4/5, 1 i 2. Nakon toga još treba izbaciti 1 i 2 kao nultočke nazivnika. Konačno rješenje je x∈〈-∞,-4/5]∪〈1,2〉.
   

2. Dokazujemo matematičkom indukcijom po n. Primijetimo da na lijevoj strani eksponenti broja 3 idu od 0 do 6n-2 s korakom 2, dakle suma na lijevoj strani ima 3n članova.
   

   Baza

   Za n=1, imamo tri člana na lijevoj strani: 1+3²+3⁴=1+9+81=91=13⋅7, što je djeljivo s 13. (Zadnji član u sumi je 3^6⋅1-2=3⁴.)
   

   Pretpostavka

   Pretpostavimo da je za neki prirodni k, 1+3²+3⁴+...+3^6k-2 djeljivo s 13, odnosno jednako 13q za neki cjelobrojni q. Suma na lijevoj strani ima 3k članova.
   

   Korak

   Za n=k+1, na lijevoj strani imamo 3n=3(k+1)=3k+3 člana: to su 3k iz pretpostavke indukcije, i još 3 sljedeća (nakon 3^6k-2 s korakom 2 u eksponentu): 3^6k, 3^6k+2 i 3^6k+4. Primijetimo da je posljednji jednak 3^6(k+1)-2, kao što i treba biti. Naša suma je sada jednaka (1+3²+3⁴+...+3^6k-2)+(3^6k+3^6k+2+3^6k+4) =
   13q+3^6k(1+3²+3⁴) = 13q+91⋅3^6k = 13(q+7⋅3^6k), što je djeljivo s 13.

   
   
   
3. Prvo provjerimo je li nulpolinom rješenje. Za p(x)=0, dobivamo istinitu jednakost 0=0, dakle nulpolinom je jedno rješenje. Ako pak p nije nulpolinom, tada ima stupanj: označimo n:=st(p). Stupanj kompozicije je produkt stupnjeva, a stupanj produkta je zbroj stupnjeva faktorâ, dakle stupanj lijeve strane je 2n, a desne 2+n (primijetimo da sada nijedna od njih nije nulpolinom). Ako su one jednake, moraju imati i jednake stupnjeve, odnosno 2n=2+n, iz čega dobijemo n=2. Dakle p(x) koji nije nulpolinom mora biti stupnja 2, odnosno imati oblik ax²+bx+c (gdje a kao vodeći koeficijent nije 0). Uvrstivši to u zadanu jednadžbu, dobijemo a(1+x²)²+b(1+x²)+c=(1+x+x²)(ax²+bx+c). Kad to raspišemo po potencijama od x, dobijemo:
   
   
   • uz x⁴: a=a
     
   • uz x³: 0=a+b
     
   • uz x²: 2a+b=a+b+c
     
   • uz x: 0=b+c
     
   • slobodno: a+b+c=c
   
   
   Iz toga se dobije rješenje a=-b=c, odnosno p(x)=a(x²-x+1), gdje je a proizvoljan realan broj različit od 0. Ako je a=0, dobije se upravo nulpolinom (za koji smo gore vidjeli da je rješenje), pa je opće rješenje p(x)=a(x²-x+1) za proizvoljni a∈ℝ.
   
   
4. Imamo jednakost (x²+x+1)ⁿ=a_2nx²ⁿ+...+a₁x+a₀. Uvrštavanjem x=1 i x=-1 u nju, dobijemo
   3ⁿ=a_2n+a_2n-1+...+a₁x+a₀ i
   1=a_2n-a_2n-1+...-a₁x+a₀. Zbrajanjem te dvije jednakosti, i dijeljenjem s 2, dobijemo
   (3ⁿ+1)/2=a_2n+a_2n-2+...+a₂+a₀. Da bismo dobili ono što se od nas u zadatku traži, treba još oduzeti od toga slobodni član a₀, koji se može dobiti uvrštavanjem x=0: 1=a₀. Dakle traženi izraz je (3ⁿ+1)/2-1=(3ⁿ-1)/2.
   
   
5. Prebacivši 2 na lijevu stranu nejednadžbe, faktoriziranjem nazivnika i svođenjem na zajednički nazivnik, dobije se ekvivalentna nejednadžba -(5x-17)/(x-3)(x+2)≤0. To se može riješiti pomoću tablice, gledanjem predznaka pojedinih faktorâ na intervalima određenim točkama -2, 3 i 17/5. Nakon toga još treba izbaciti -2 i 3 kao nultočke nazivnika. Konačno rješenje je x∈〈-∞,-2〉∪〈3,17/5].