28 novembra 2008

Zapadajúce množiny (súťažná úloha č.2)

Druhý príspevok do súťaže o najkrajšiu úlohu poslal Ondrej Budáč, študent 3. ročníka FMFI UK, odbor matematika.

Majme množinu M, ktorá obsahuje podmnožiny prirodzených čísel. Pre každé dva prvky A, B množiny M platí, že A je podmožina B, alebo naopak B je podmožina A. (Formálne povedané, M je úplne usporiadaná vzhľadom na inklúziu.) Môže sa stať, že množina M bude nespočitateľná?

Úloha je prevzatá; riešenie nájdete tu (pdf).

8 komentárov:

Ruziklan povedal(a)...

Riesenie je tak kontraintuitivne, ze sa stale zdraham mu uverit a hladam v nom chybu. Hm. Pekna ulozka.

katka povedal(a)...

Mne sa zase to riesenie vobec nezdalo neuveritelne, kedze poznam Dedekindovu konstrukciu realnych cisel. Ale priznam sa, to riesenie by mi asi len tak nenapadlo.

Na druhej strane mi to pripomenulo jeden priklad o hromadnych hodnotach postupnosti, ktory sme mali na cviku z komplexnej analyzy, a ten mal naozaj necakane a kontraintuitivne riesenie.

Radoslav Harman povedal(a)...

Katka: Aký príklad o hromadných hodnotách? Napíš, nech sa zabavíme... :-)

katka povedal(a)...

Islo o takyto priklad:

"Existuje postupnost komplexnych (stacilo by aj realnych) cisel, ktora ma nespocitatelne vela hromadnych hodnot?"

Najprv sme si vsetci mysleli, ze taka postupnost nemoze existovat, lebo to by sa muselo nekonecne vela clenov postupnosti nachadzat v roznych okoliach hromadnych hodnot, ktorych je nespocitatelne vela, a ta postupnost ma predsa len spocitatelne vela clenov. No ale takato uvaha mala nejaku drobnu chybicku... :)

Radoslav Harman povedal(a)...

Katka: OK. Ale riešenie tej Ondrovej úlohy sa mi predsa len javí trochu kontraintuitívnejšie. Ale úplný mindbender využívajúci naše nedokonalé intutívne chápanie nekonečna je tá úloha o súčasnom odpovedaní nekonečne veľa zbojníkov, ktorú Ondro napísal v komentári k problému o Ali Babovi.

katka povedal(a)...

tak s tym suhlasim :)

Peter Richtárik povedal(a)...

Veľmi pekné!

Povedal som to tu chalanom z roboty a samozrejme ich to hneď zaujalo. Dúfam, že som im "nepokazil" (práve začínajúci) víkend!

Pre mňa osobne to je naozaj nesmierne kontraintuitívne! Sila.

Peter Richtárik povedal(a)...

Ešte som chcel napísať svoje riešenie. Pozerám, že je podobné vašim, ale je predsa len dostatočne odlišné aby som ho spomenul.

Uvažujme nad množinou M všetkých postupností núl a jednotiek. Nech K je množina všetkých postupností s konečným počtom jednotiek. Štandardne sa dá ukázať, že M je nespočítateľná a K je spočítateľná. Pre a = {a_i} z M položme a' = sum a_i*2^{-i}. Teraz uvažujme množinu C(a) = {b z K : b' < a'} nech C je kolekcia množín C(a) pre všetky a z M.

C je nespočítateľná, úplne usporiadaná a prvky množín C sú všetky zo spočítateľnej množiny.