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