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