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!:-)