Zornova lema i aritmetika ordinalâ - detaljnije nego obično

---------- Forwarded message ----------
From: Veky <vedgar@gmail.com>
Date: Oct 3, 2006 11:32 PM
Subject: Re: Pitanje
To: Mario

On 10/3/06, Mario wrote:

Zamolio bih vas da mi ipak raspisete 5.zadatak sa
zadnjeg roka

Neka je (A,<) proizvoljni TUS. Označimo sa S skup svih u sebi gustih podskupova od A. Kako je A TUS, u njemu nema neusporedivih elemenata, pa ni u jednom njegovom podskupu nema neusporedivih elemenata: dakle, svaki element G od S je također TUS. Za takve TUSove "gust u sebi" znači da za svaka dva elementa x i y iz G, takve da je x<y, postoji element z iz G takav da je x<z<y.

Prvo, za sve elemente praznog skupa vrijedi bilo što, pa je prazan skup svakako gust u sebi. Kako je prazan skup uvijek također i podskup od A, vrijedi da je prazan skup element od S, pa je S neprazan. S je očito parcijalno uređen relacijom "biti podskup" (ta relacija je uvijek refleksivna, antisimetrična i tranzitivna). Dakle, imamo neprazan, parcijalno uređen skup.

Uzmimo proizvoljni lanac L u S. Primijetimo da, kako su u S svi elementi bili podskupovi od A, tako će i svi elementi od L biti podskupovi od A. Unija tog lanca (svih skupova u tom lancu) UL je očito gornja međa za L (nadskup od svakog elementa od L). Također, svaki element od UL nalazi se u nekom elementu G od L, pa se nalazi i u A (jer je G kao element od L podskup od A). To znači da je UL podskup od A.

Neka su x i y proizvoljni elementi od UL takvi da je x<y. Kako je x u UL, postoji element X lanca L u kojem se nalazi x. Također, y je element nekog (možda drugog) elementa od L, kojeg označimo s Y. Sada, kako je L lanac, a X i Y njegovi elementi, X i Y su usporedivi (s obzirom na relaciju koja uređuje L, dakle "biti podskup"). To znači da je X podskup od Y, ili Y podskup od X.

Ako je X podskup od Y, tada x, kao element od X, mora biti i u Y. Tada imamo x i y elemente od Y, a na početku smo uzeli da je x<y. Kako je Y u lancu L, a L je podskup od S, gdje se nalaze u sebi gusti podskupovi od A, i Y je takav: Y je u sebi gust podskup od A. To znači da su x i y elementi od A, te da postoji element z u Y takav da je x<z<y. z se nalazi u Y, a Y se nalazi u L, dakle z je element od UL.

Ako je pak bio Y podskup od X, također možemo ponoviti prethodni odlomak, samo zamijenimo X i Y. Zaključujemo da se između svaka dva različita elementa iz UL nalazi element iz UL, pa je UL u sebi gust. Gore smo vidjeli da je podskup od A, dakle UL je element od S. Odnosno, UL je gornja međa za L u S, pa kako je L bio proizvoljan, zaključujemo da svaki lanac u S ima gornju među u S.

To, zajedno s ovim što smo vidjeli gore -- S je neprazan parcijalno uređen skup -- znači da su ispunjeni uvjeti Zornove leme za S, pa u S postoji (bar jedan) maksimalni element. Ako pogledamo koji su elementi u S, vidimo da je taj maksimalni element upravo maksimalni podskup od A koji je u sebi gust, čije postojanje smo trebali dokazati. QED

i jos imam pitanje iz ordinalnih brojeva
da mi pojasnite zasto je (w+alfa)*w=w^2

Well... nije za sve alfa. Ali za alfa<omega^2, jest. Naime, tada je alfa oblika omega*i+j, za neke prirodne i i j -- pa je omega+alfa=omega+(omega*i+j)=[asocijativnost zbrajanja](omega+omega*i)+j=[lijeva distributivnost * prema +]omega*(1+i)+j. Taj ordinal je očito veći od omega*(i+1) (i+1=1+i jer su i i 1 prirodni brojevi, a za njih vrijedi komutativnost zbrajanja), a manji je (jer je j<omega) od omega*(1+i)+omega=[lijeva distributivnost]omega*(1+i+1)=[i je prirodni broj]omega*(i+2).

Kako je množenje ordinalâ rastuće, (nestroge) nejednakosti omega*(i+1)<=omega+alfa<=omega*(i+2) se čuvaju množenjem zdesna s omega, pa imamo (omega*(i+1))*omega <= (omega+alfa)*omega <= (omega*(i+2))*omega. Lijeva strana je po asocijativnosti množenja omega*((i+1)*omega). Kako su i i 1 prirodni brojevi, i njihov zbroj i+1 je prirodan, a svaki prirodan broj pomnožen s omega daje omega (napravljeno na vježbama). Dakle, lijeva strana je omega*omega=omega^2. Analogno se dobije i za desnu stranu, zamjenom 1 s 2 svuda.

Zaključujemo da je omega^2<=(omega+alfa)*omega<=omega^2, pa mora biti (omega+alfa)*omega=omega^2.

i sup(w^2*n +w*n + n)= w^3.

(Pretpostavljam da je supremum po n iz omega.) Svaki član niza na lijevoj strani ima n<omega, pa je omega*n+n<=omega*n+omega=omega*(n+1), a kako je i n+1 onda prirodan, to je manje ili jednako omega*omega=omega^2. Jednako tako, onda je omega^2*n+omega*n+n< =omega^2*n+omega^2=omega^2*(n+1), što je manje ili jednako od omega^2*omega=omega^(2+1)=omega^3. Dakle, omega^3 je gornja međa niza koji se pojavljuje na lijevoj strani.

Pokažimo da je to i najmanja gornja međa -- dakle, supremum. Pretpostavimo da postoji neka strogo manja, i označimo je s beta. Po definiciji, omega^3=omega^(2+1)=omega^2*omega= omega^2*sup{n<omega}n=sup{n<omega}omega^2*n. To znači da za svaki ordinal strogo manji od omega^3 (pa tako i za beta) postoji neki član niza omega^2*n koji se nalazi između njih. Dakle, postoji prirodni n takav da je beta<omega^2*n, a to je pak manje ili jednako od omega^2*n+omega*n+n.

Dobili smo da za svaki beta<omega^3 postoji član našeg niza na lijevoj strani koji je strogo veći od beta, pa beta nikad nije gornja međa tog niza. Kako smo vidjeli da omega^3 jest gornja međa tog niza, proizlazi da je to najmanja gornja međa, dakle supremum.

--
~Veky

Rješenja pismenog ispita iz Teorije skupova 06-09-15

1. 1. Ako je S skup čiju kardinalnost tražimo, vrijedi S⊆ℂ, pa je cardS≤cardℂ=c. S druge strane, svakom realnom broju x∈[0,2π> možemo (injektivno) pridružiti kompleksan broj e^ix modula 1∈ℚ. To znači i cardS≥card[0,2π>=c, pa je cardS=c.
      
   2. Očito ih ima najviše koliko i svih funkcijâ s ℝ u ℝ, dakle ≤c^c=2^c. S druge strane, svakoj funkciji f s ℝ₀⁻ u ℝ možemo pridružiti f∪(rd|_ℝ⁺), gdje je rd funkcija "razlomljeni dio", rd(x):=x-⌊x⌋. Tako dobivena funkcija očito poprima svaku vrijednost y∈<0,1> beskonačno mnogo puta (bar u svim točkama skupa ℕ+y), i pridruživanje je injekcija jer ako se dvije funkcije razlikuju na ℝ₀⁻, tada se razlikuju i na ℝ. Dakle, naših funkcija nema manje nego svih funkcijâ s ℝ₀⁻ u ℝ, a to je opet 2^c. Zaključak: ima ih točno 2^c.
      
   
   
2. Tražimo sumu S:=∑_i∈ω+1α_i, gdje je α_i:=∏_j∈ω+1(ω²+ω⋅i+j)= ∏_j∈ω(ω²+ω⋅i+j)⋅(ω²+ω⋅i+ω). Svi faktori se nalaze između ω² i ω³, pa se ovaj početni produkt (po j∈ω) nalazi između (ω²)^ω=ω^2⋅ω=ω^ω i (ω³)^ω=ω^3⋅ω=ω^ω — dakle, jednak je ω^ω. Tada je α_i=ω^ω⋅(ω²+ω⋅i+ω)= ω^ω+1⋅(ω+i+1) (možemo izlučivati slijeva), pa je S=∑_i∈ω+1(ω^ω+1⋅(ω+i+1))= ω^ω+1⋅∑_i∈ω+1(ω+i+1). Ova posljednja suma je ∑_i∈ω(ω+i+1)+(ω+ω+1), čiji je prvi dio ω², pa je S=ω^ω+1⋅(ω²+ω⋅2+1).
   
3. Nijedna inkluzija ne vrijedi općenito (iako za svaki takav A vrijedi bar jedna od njih — pokušajte to dokazati!), kao što pokazuju sljedeći kontraprimjeri:
   
   • Za A={0,{1}}, imamo ⋂A=0∩{1}=0, pa je i ⋃⋂A=⋃0=0. S druge strane je ⋃A=0∪{1}={1}, pa je ⋂⋃A=⋂{1}=1⊈0.
     
   • Za A=(1,0)={{1},2} imamo po definiciji uređenog para ⋃⋂A=1, dok je ⋃A={1}∪{0,1}={0,1}, te ⋂⋃A=0∩1=0⊉1.
     
   
   
4. Primjeri skupova uređenih standardno (antileksikografski) s danim uređajnim tipovima su S₁:=ℤ⁻×{0}∪ℤ×ℕ×{1} i S₂:=ℤ×ℤ⁻×{0}∪ℕ×{1}. Ako pokažemo da S₁≄S₂, znat ćemo da su ta dva tipa različiti.
   Svaki element od S₁ je par — uređene trojke shvaćamo ovdje kao (a,b,c):=((a,b),c) — i ako je to (x,y), razlikujemo dva slučaja, ovisno o y.
   Ako je y=0, mora biti x<0, pa je (x-1,0)∈S₁ neposredni prethodnik od (x,0)=(x,y). Ako je pak y=1, mora x biti par, x=(u,v), i tada je ((u-1,v),1) opet neposredni prethodnik od ((u,v),1)=(x,y). Dakle, u S₁ svaki element ima neposrednog prethodnika.
   S druge strane, (0,1)∈S₂, ali svaki njegov prethodnik u S₂ mora biti oblika ((u,v),0), pa je ((u+1,v),0) u S₂ između ((u,v),0) i (0,1) — dakle, (0,1) nema neposrednog prethodnika u S₂. Kako je "svaki element ima neposrednog prethodnika" invarijanta sličnosti, S₁ i S₂ nisu slični, pa su ω^*+π⋅ω i π⋅ω^*+ω različiti uređajni tipovi.
   
5. Standardno, primjenom Zornove leme. Skup svih konveksnih podskupova od S je neprazan (∅⊆S je konveksan), uređen standardno relacijom ⊆, i u njemu svaki lanac ℒ ima gornju među ⋃ℒ koja je trivijalno ⊆S, treba još pokazati da je konveksna. Ako su sad X i Y dvije proizvoljne točke iz ⋃ℒ, postoje A i B iz ℒ takvi da je X∈A∧Y∈B, pa su zbog usporedivosti od A i B oba u jednom, recimo A. Sada, kako je A konveksan, čitava dužina XY je podskup od A, pa tako i od njegovog nadskupa ⋃ℒ.
   Po Zornovoj lemi, postoji maksimalni konveksni podskup od S, odnosno konveksna skela.
   Primjer za nejedinstvenost: za S:={(0,0),(1,0)}⊆ℝ², svaki njegov jednočlan podskup je očito konveksna skela od S: jednočlan skup je uvijek konveksan, a i maksimalan je jer jedini njegov pravi nadskup, S, nije konveksan.
   

Je li nula paran broj?

From: Veky <vedgar@gmail.com>
Date: Sep 14, 2006 9:47 AM
Subject: Re: Nula
To: demi lucy

On 9/14/06, demi lucy  wrote:

Je li nula paran ili neparan broj?

Da vidimo prvo što znači "paran".

Što je zajedničko brojevima 2,4,18,42,...., a da to svojstvo s njima ne dijele brojevi 1,3,13,257,....? Možemo se izvući na zadnju znamenku, no znamo da zadnja znamenka ionako ovisi o brojevnom sustavu u kojem računamo. To što znamenaka ima onoliko koliko imamo prstiju na obje ruke zajedno, očito nije matematička, već biološko-psihološka činjenica. Htjeli bismo da definicija parnosti ipak bude malo univerzalnija.

Naravno, definicija koja ne ovisi o brojevnom sustavu je "broj je djeljiv s 2". Time smo definirali što mislimo pod "broj je paran", samo što sada moramo definirati što znači "biti djeljiv s". (Za "dva" pretpostavljamo da znamo što znači.:)

Broj je djeljiv s nekim drugim brojem ako se njime može podijeliti bez ostatka. Teorem o dijeljenju (u cijelim brojevima) kaže da za svaki broj a ( djeljenik) i svaki broj različit od nule b (djelitelj -- znamo da nulom ne možemo dijeliti) postoje jedinstveni brojevi q ( količnik) i r (ostatak) takvi da vrijedi q*b+r=a. Ako je dijeljenje bez ostatka, znači da je r=0, pa mora biti q*b=a za neki q. To sada može poslužiti kao definicija djeljivosti i u slučaju b=0, no to nas ovdje neće zanimati -- nama treba slučaj a=0.

Došli smo do definicije (u cijelim brojevima) "a je djeljiv s b ako i samo ako postoji q takav da je a=b*q". Specijalno, nula je djeljiva s dva ako i samo ako postoji q takav da je 0=2*q. Postoji li takav q? Naravno da da: 0=2*0, pa cijeli broj q=0 zadovoljava tu jednakost -- odnosno, nula je djeljiva s dva, pa je paran broj.

Inače, više o djeljivosti možeš naći na http://web.math.hr/~veky/em/vjezbe/djeljivost.html.
HTH,
--

~Veky

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.
   

Rješenja pismenog ispita iz Teorije skupova 06-07-07

1. 1. Očito ih ima manje nego svih prirodnih brojeva, dakle ≤ℵ₀. S druge strane, preslikavanje n↦100ⁿ je očito injekcija (koja svakom prirodnom broju n pridružuje prirodni broj s 2n+1 znamenaka), koja pokazuje da ih ima i ≥ℵ₀. Dakle, ima ih prebrojivo mnogo.
      
   2. Po tranzitivnosti je i A⊆ℝ, pa ih nema više nego svih parova podskupova od ℝ; dakle ≤card(℘(ℝ))²=(2^c)²=2^c⋅2=2^c. S druge strane, svakom podskupu C⊆[0,1] možemo pridružiti par (C,ℝ) koji zadovoljava uvjet, i to je injekcija (po definicijskom svojstvu uređenog para) sa ℘([0,1]) u naš skup, koja govori da je njegov kardinalitet ≥2^card[0,1]=2^c. Zaključujemo da ih ima 2^c.
   
   
2. Budući da je indeks sumacije sigurno manji od ω⋅3, prvi faktor u sumandu je između ω i ω⋅4, pa je sam sumand između ω⋅ω=ω² i ω⋅4⋅ω=ω⋅(4⋅ω)=ω⋅ω=ω². Drugim riječima, svi sumandi su jednaki ω², pa ω² možemo izlučiti (lijevo) izvan sume, koja onda postaje trivijalno jednaka ω⋅2+3. Rezultat je time ω²⋅(ω⋅2+3)=ω³⋅2+ω²⋅3.
   
3. Unija od ℘(A) je najveći element od ℘(A), a to je naravno A. Također, ako je x∈A, svaki element od x je i element od ∪A, pa je x⊆∪A — odnosno, x∈℘(∪A). Dakle, A⊆℘(∪A). Obrnuta inkluzija ne vrijedi općenito, npr. ℘(∪{{1}})=℘({1})={∅,{1}}⊈{{1}}.
   
4. Nisu slični: u skupu ℝ×ℚ između svaka dva različita elementa ima neprebrojivo mnogo elemenata. Ako je b<d, između (a,b) i (c,d) se nalaze npr. svi (e,b), gdje je e∈<a,+∞>. Ako je pak b=d∧a<c, između se nalaze svi (e,b) za koje je e∈<a,c>. Dok u skupu ℚ×ℝ, to ne vrijedi: na primjer, (0,0)<(1,0), ali između njih se nalaze samo parovi oblika (r,0), gdje je r racionalan broj između 0 i 1 — dakle, samo prebrojivo mnogo njih.
   Budući da sličnosti čuvaju krajeve intervalâ, kao i (ne)prebrojivost, svojstvo "između svaka dva različita elementa postoji neprebrojivo mnogo elemenata" je invarijanta sličnosti po kojoj se ℝ×ℚ i ℚ×ℝ razlikuju.
   
5. Da za svaki a∈A postoji maksimalni lanac koji ga sadrži, dokazuje se standardno, Zornovom lemom (jedan lanac koji je dobar je {a}, a unija lanca dobrih lanaca je ponovo dobar lanac: sadrži a, i svaka dva elementa su usporediva). Sada, budući da ≺ nije totalni uređaj, sigurno postoje bar dva neusporediva elementa: fiksirajmo takva dva, i označimo ih s b i c. Za svakog od njih po upravo dokazanom postoji maksimalni lanac koji ga sadrži, označimo ih s B∋b i C∋c. To su zaista različiti lanci, jer npr. b∈B∧b∉C (pretpostavka b∈C bi, jer je C lanac, značila da su b i c usporedivi).

Sve žene su plavuše

to: Nesi (koja nikako nije plavuša:)



Dokažimo da za svaki prirodni n, za svaku skupinu od n ženâ, vrijedi sljedeće svojstvo (PFP): ako je bar jedna žena u toj skupini plavuša, onda su sve žene u toj skupini plavuše. Dokaz ide (naravno:) matematičkom indukcijom po n. Za n=1 tvrdnja se svodi na "za svaku skupinu koja se sastoji od jedne žene, ako je jedna žena u toj skupini plavuša, onda su sve žene u toj skupini plavuše", sto je očito točno, pa je baza indukcije ispunjena. Sad pretpostavimo da sve skupine od n ženâ zadovoljavaju [PFP], i uzmimo bilo koju skupinu od n+1 ženâ, od kojih je jedna plavuša. Označimo tu plavušu sa z0, a ostalih n ženâ u toj novoj skupini sa z1..n . Ako sad gledamo skupinu ženâ z0..(n-1), vidimo da ona ima n članova, pa zadovoljava [PFP] po pretpostavci indukcije. Budući da ta skupina ima bar jednu plavušu (namely z0), slijedi da su i sve žene z1..(n-1) plavuše. Specijalno, z1 je plavuša. Sad pogledamo skupinu ženâ z1..n . Ona takoder ima n članova (članicâ:-?), pa zadovoljava [PFP]. Budući da i ta skupina ima bar jednu plavušu (namely z1), slijedi i da su sve žene z1..n plavuše. Budući da za z0 znamo već otprije da je plavuša, imamo da su sve z0..n plavuše, što daje [PFP] za sve skupine od n+1 ženâ. Budući da [PFP] vrijedi za sve 1-skupine, i iz pretpostavke da vrijedi za sve n-skupine slijedi da vrijedi za sve (n+1)-skupine, po principu matematičke indukcije slijedi da, za svaki n, [PFP] vrijedi za sve n-skupine, odnosno, [PFP] vrijedi za sve (konačne:) skupine žena. Specijalno, vrijedi i za Z0, skupinu svih žena na Zemlji. Budući da Z0 očito ima bar jednu plavušu (dokaži za vježbu:), slijedi da su sve žene u Z0, dakle, sve žene na Zemlji, plavuše." Budući da si ti (bar trenutno:) _žena_ _na Zemlji_, dakle element od Z0, slijedi da si plavuša. Priznaj!:-)

Rješenja pismenog ispita iz Teorije skupova 06-06-23

1. 1. Ako skup svih takvih skupova označimo sa S, tada je funkcija sort (koja svakom n-članom skupu pridruži n-torku njegovih elemenata uređenih po velični) injekcija sa S u ℂ^*, pa je card S≤card ℂ^*, što je c (napravljeno na vježbama). S druge strane, preslikavanje z↦{z,z+1} je injekcija sa ℂ u S, pa je c≤card S. Dakle, S je kardinaliteta kontinuum.
   
   
   2. Preslikavanje f↦f(1) je bijekcija između našeg skupa i ℤ (inverzno preslikavanje cijelom broju k pridruži množenje brojem k), budući da su sve aditivne funkcije na ℤ oblika n↦k⋅n. Dakle, traženi kardinalitet je card ℤ=ℵ₀.



2. Traženi produkt je jednak sup_n∈ω(0⁰⋅1¹⋅2²⋅…⋅(n-1)^n-1) ⋅ω^ω⋅(ω+1)^ω+1⋅(ω+2)^ω+2. Prvi faktor je očito supremum neograničenog niza prirodnih brojeva, dakle ω. Umnožak prvog i drugog faktora je onda ω⋅ω^ω=ω^1+ω=ω^ω. Nakon toga je (ω+1)^ω+1=(ω+1)^ω⋅(ω+1), te još (ω+2)^ω+2=(ω+2)^ω⋅(ω+2)². Za i=1 ili i=2, imamo ω<ω+i<ω², pa je ω^ω≤(ω+i)^ω≤(ω²)^ω=ω^2⋅ω=ω^ω, iz čega slijedi (ω+1)^ω=(ω+2)^ω=ω^ω.
   Traženi produkt sada postaje ω^ω⋅ω^ω⋅(ω+1)⋅ω^ω⋅(ω+2)². Još ponešto možemo pojednostaviti: (ω+1)⋅ω^ω se nalazi između 1⋅ω^ω i ω²⋅ω^ω=ω^2+ω=ω^ω, dakle jednak je ω^ω. Pored toga, (ω+2)²=(ω+2)(ω+2)=(ω+2)ω+(ω+2)⋅2=ω²+ω+2+ω+2=ω²+ω⋅2+2.
   Dakle, rezultat je ω^ω⋅ω^ω⋅ω^ω⋅(ω²+ω⋅2+2)=ω^ω⋅3⋅(ω²+ω⋅2+2)= ω^ω⋅3+2+ω^ω⋅3+1⋅2+ω^ω⋅3⋅2.



3. Postoji. Da bismo to dokazali, prvo primijetimo da je s B_x:={q∈ℚ:q<x} zadana analogna familija podskupova od ℚ (budući da između svaka dva realna broja postoji racionalni, x<y zaista povlači B_x⊂B_y). Sada, ako je q:ℚ→ℕ neka bijekcija (koja postoji jer su ℚ i ℕ ekvipotentni), sa A_x označimo sliku od B_x po funkciji q. Kako je q bijekcija, gornje svojstvo se čuva.



4. Ako je A neprazan, po aksiomu utemeljenosti postoji a∈A koji je disjunktan s A. Kad bi a imao neki element b, po tranzitivnosti bismo imali i b∈A, što je u kontradikciji s disjunktnošću. Dakle, a je prazan skup, element od A.



5. Zadatak se mogao riješiti kao i obično primjenom Zornove leme, ali se u ovom slučaju primjer traženog skupa mogao i direktno naći: na primjer, <-1,1>\{0}. Taj skup je očito neprazan, ne sadrži nijedan cijeli broj, i zatvoren je na množenje. Štoviše, kada bismo ubacili bilo koji necijeli broj x unutra, budući da je 1/x već u skupu, da bismo očuvali zatvorenost na množenje, morali bismo ubaciti i 1 u skup, a tada bismo izgubili svojstvo disjunktnosti sa ℤ. Dakle, <-1,1>\{0} je maksimalan skup s traženim svojstvima.

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

1. 
   
   1. Neka je S skup čiji broj elemenata tražimo. Preslikavanje f:S→ℤ²;(a₀,a₁,a₂,…)↦(a₀,a₁-a₀) je bijekcija (inverzno preslikavanje je f⁻¹:ℤ²→S;(a,d)↦(a,a+d,a+2d,a+3d,…)), dakle card S=card ℤ²=ℵ₀²=ℵ₀.
   
   
   
   2. Budući da je prebrojivi skup ℂ_ℚ (kompleksni brojevi s racionalnim koordinatama) gust u ℂ, svaka neprekidna funkcija s ℂ u ℂ je jednoznačno zadana svojim djelovanjem na ℂ_ℚ. Odnosno, preslikavanje g↦g|_ℂℚ je injekcija sa skupa C(ℂ→ℂ) u skup ℂ^ℂ_ℚ, pa je card C(ℂ→ℂ)≤card ℂ^ℂ_ℚ= c^ℵ₀²=c^ℵ₀=c. S druge strane, svaka konstatna funkcija je neprekidna, a njih ima koliko i kompleksnih brojeva - kontinuum. Dakle, card C(ℂ→ℂ)=c.
      



2. Ako opći faktor u produktu označimo s α_j, vidimo da je traženi produkt jednak sup_n∈ω(α₀⋅α₁⋅…⋅α_n-1)⋅α_ω.
   Za konačne j je α_j=sup_m∈ω(ω^j+ω^j+1+…+ω^j+m-1). Zbog apsorpcije je suma pod supremumom jednaka zadnjem članu ω^j+m-1, pa je taj supremum α_j=ω^ω (neprekidnost potenciranja, a j+m-1 je neograničeni niz prirodnih brojeva po m).
   Zadnji faktor je α_ω, suma od ω članova, koji su svi jednaki ω^i+ω=ω^ω. Dakle, sama suma je jednaka ω^ω⋅ω, odnosno α_ω=ω^ω+1.
   Sve u svemu, traženi produkt je
   sup_n∈ω(α₀⋅α₁⋅…⋅α_n-1)⋅α_ω=
   =sup_n∈ω(ω^ω)ⁿ⋅ω^ω+1=
   =(ω^ω)^ω⋅ω^ω+1=ω^ω⋅ω⋅ω^ω+1= ω^ω²+ω+1.



3. Budući da je ℱ familija disjunktnih nepraznih podskupova, za nju postoji funkcija izbora f:ℱ→∪ℱ. Kako su elementi familije disjunktni, f je injekcija, pa je card ℱ≤card ∪ℱ=ℵ₀. No kada bi ℱ bila konačna, njena unija - unija konačno mnogo konačnih skupova - bi također bila konačna. Dakle, ℱ mora biti prebrojiva.



4. U skupu ℕ×ℚ, antileksikografski uređenom, vrijedi (1,5)<(2,5), no ne postoji nijedan element iz ℕ×ℚ strogo između njih: morao bi biti oblika (x,5), gdje je x prirodan broj strogo između 1 i 2. Dakle, ℕ×ℚ nije gust, pa nije ni tipa η (gustoća je invarijanta sličnosti, a η je gust).
   Skup ℚ×ℤ je prebrojiv (ℵ₀⋅ℵ₀=ℵ₀), nema najmanjeg ni najvećeg elementa (od svakog (a,b) uvijek postoji strogo veći (a+1,b) i strogo manji (a-1,b)), i gust je: neka je (a,b)<(c,d) u ℚ×ℤ. Ako je b<d, tada se (a+1,b) nalazi strogo između njih; ako je pak b=d∧a<c, tada se ((a+c)/2,b) nalazi strogo između njih. Dakle, ℚ×ℤ ispunjava uvjete uređajne karakterizacije od ℚ, pa je sličan s ℚ - odnosno, tipa je η.
   Skup ℝ×ℚ je neprebrojiv (c⋅ℵ₀=c), dakle ne postoji bijekcija između njega i ℚ, pa pogotovo ne može postojati sličnost.
   Zaključak: od gornja tri skupa sa standardnim (antileksikografskim) uređajem, samo ℚ×ℤ ima uređajni tip η.



5. Označimo s ℬ skup svih balansiranih podskupova od ℝ disjunktnih s ℚ, i uredimo ga standardno relacijom ⊆. Skup {√2} je balansiran i disjunktan s ℚ, pa je ℬ neprazan. Ako je ℒ⊆ℬ lanac, svi njegovi elementi su disjunktni s ℚ, pa je i njihova unija disjunktna s ℚ (distributivnost presjeka prema uniji). Dokažimo da je ∪ℒ također balansiran skup (to je tada gornja međa za ℒ u ℬ).
   Neka su x i y proizvoljni elementi skupa ∪ℒ. To znači da postoje skupovi B i C iz ℒ, takvi da je x∈B∧y∈C. No ℒ je lanac, pa su B i C usporedivi: vrijedi B⊆C ili C⊆B. BSOMP da vrijedi B⊆C. Tada je i x∈C, pa kako je C balansiran, aritmetička sredina x i y se nalazi u C. C je element lanca, pa je podskup njegove unije - odnosno, (x+y)/2∈∪ℒ. Dakle, ∪ℒ je balansiran podskup od ℝ, disjunktan s ℚ - drugim riječima, lanac ℒ ima gornju među ∪ℒ u ℬ. To skupa s gornjim daje da su ispunjeni svi uvjeti Zornove leme, pa ℬ ima maksimalni element: maksimalni balansirani podskup od ℝ, disjunktan s ℚ.

Neke očitosti o integralima

imam zadatak
odredite površinu (duljinu) domene funkcije
i kada rjesim domenu kako odredim njenu duljinu???

Ako pričamo o funkciji jedne realne varijable (što bi se dalo zaključiti na osnovu tvog poistovjećivanja površine i duljine):

domena je u većini slučajeva (disjunktna) unija (konačno mnogo) nekih intervala (bilo otvorenih, zatvorenih, poluotvorenih...), i pojedinih točaka (singletonova). Jednostavno zbroji duljine svih tih intervala. Duljina od intervala a,b (bilo [a,b], bilo [a,b>,...) je b-a .
Na primjer, duljina od [1,2>U<3,7>U{-2,0} je (2-1)+(7-3)=1+4=5 . Duljina od <-oo,-4>U[0,5] je, naravno, beskonačna.
Teoretski, možeš tako izračunati i ako imaš prebrojivo mnogo takvih intervala, samo što tada ovo "zbroji duljine" postaje izračunavanje sume reda. Npr. duljina od <-1,-1/2>U<-1/4,-1/8>U<-1/16,-1/32>U.... je 1/2+1/8+1/32+....=(1/2)/(1-1/4)=2/3 .
**
Ako se radi o funkciji više varijabli, stvari su kompliciranije. No jednom kad imaš neku razumnu karakterizaciju domene (npr. jednadžbama ili nejednadžbama), to je standardni problem "odredi površinu/volumen/.... nekog skupa", koji se onda najčešće rješava geometrijski (crtanjem i uočavanjem geometrijskih likova/tijelâ), ili u kompliciranijim slučajevima, integriranjem.

i kako odretiti povrsinu i duljinu slike neke fnkcije?

Jednakim postupkom. :-) Samo prvo sliku prikažeš kao uniju intervalâ... ili, za funkcije s višedimenzionalnom kodomenom, karakteriziraš je (ne)jednadžbama i onda to integriraš (preciznije, integriraš konstantu 1 po tom području, odnosno karakterističnu funkciju tog područja po nekom pravokutniku koji ga sadrži).

i broj siljaka?

Broj čega? [:-)]
Vjerojatno se misli na (izolirane) točke u kojima je funkcija neprekidna, ali nije derivabilna. Dobri kandidati za to su točke na kojima se susreću razna pravila definicije, za funkcije definirane po slučajevima. U svakoj takvoj točki treba provjeriti neprekidnost i derivabilnost, i na kraju prebrojiti.

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

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].