2006-07-03

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

    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 ℤ=ℵ₀.


  1. Traženi produkt je jednak supn∈ω(00⋅11⋅22⋅…⋅(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.


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


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


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

Broj komentara: 5:

  1. Imala bih dva pitanja u vezi rjesenja roka 2006-2-10, pa bih molila Veky-ja da mi odgovori:
    1. u petom zadatku u trecoj recenici prije kraja, kaze "Pretpostavimo da psotoji w E S takav da je w>z." Nije mi jasno zato bi maksimalan element iz S uopce bio usporediv sa z (posto je maksimalan a ne najveci)?
    2.U trecem zadatku, ako pretpostavimo da su redovi odvojeni znakom jednakosti,pri prelasku iz cetvrtog reda u peti gdje nestaje (w+2), a pri prijelazu iz petog u zadnji red gdje nestaje pocetni w?

    Puno hvala

    OdgovoriIzbriši
  2. Hm... bilo bi bolje da je ovaj komentar stavljen na post koji se odnosi na taj rok, al dobro.

    Dakle, 5. zadatak. Jednom kad smo dokazali da je z maksimalan u T, trebamo još dokazati da je maksimalan u S. Odnosno, trebamo dokazati da ne postoji element w u S, veći od z. To je točno definicija maksimalnog elementa.

    To dokazujemo pretpostavivši suprotno, i došavši time do kontradikcije. "suprotno" ovdje onda zaista znači da postoji w iz S koji je veći od z. Tu pretpostavku smo doveli do kontradikcije, na način koji se nadam da je jasan. Dakle, ne postoji takav w, pa je z maksimalan.

    Ukratko, w ne mora biti maksimalan, niti maksimalnost od w ima ikakve veze s dokazom. w je samo (pretpostavljeni) kontraprimjer za maksimalnost od z u S.

    Što se tiče trećeg zadatka, pogledajte rješenje drugog zadatka u gornjem postu (rok 06-06-23). Tamo je, nadam se, detaljnije raspisano.

    OdgovoriIzbriši
  3. Jos jednom hvala na brzom odgovoru.Imala bih jos jedno pitanje vezano uz rok iz 23.lipnja 2006. vezano uz treci zadatak.
    Molila bi da me ispravite gdje sam pogrijesila (znam da jesam jer takva familija postoji): Pretpostavimo da takva familija postoji, to je zapravo funkcija f sa R u P(N).Posto vrijedi x manje od y povlaci Ax pravipodskup Ay ta je funkcija injekcija, posto je card(R)=c i card(P(N))=(2 na N0)=c to povlaci da je i bijekcija tj. i surjekcija.Uzmimo sada prazan skup 0 E P(N) i gledajmo original toga skupa u R,tj. x1 E R t.d. f(x1)=prazan skup.Posto R nema najmanjeg elementa tada postoji x2 manje od x1,i trebalo bi vrijediti Ax2 pravi podskup od Ax1=prazan skup.Znaci Ax2 bi trebao biti pravipodskup praznog skupa a to mi se cini kao kontradikcija tj. takva familija ne postoji.

    Puno hvala

    OdgovoriIzbriši
  4. "...ta je funkcija injekcija, posto je card(R)=c i card(P(N))=(2 na N0)=c to povlaci da je i bijekcija..."

    Tu je greška. Naime, to što su skupovi A i B ekvipotentni, znači da postoji bijekcija između njih. Nipošto to ne znači da svaka injekcija između njih mora biti i surjektivna (iako to vrijedi ako su skupovi konačni).

    Kontraprimjer: funkcija sljedbenik s ℕ u ℕ jest injekcija (x+1=y+1⇒x=y), i trivijalno je ℕ~ℕ, ali ipak sljedbenik nije surjekcija (ne poprima vrijednost 0).

    OdgovoriIzbriši
  5. Administrator je uklonio komentar.

    OdgovoriIzbriši