A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre. I. megoldás. A megoldás során az alábbi szóhasználattal élünk. Azt mondjuk, hogy a pozitív egész az pozitív egészet felülről dominálja, ha osztója -nek, és alulról dominálja, ha osztója -nek. (Minden pozitív egész tehát felülről és alulról is dominálja önmagát.) A egész akkor dominálja -t, ha felülről vagy alulról dominálja -t. Az halmaz pedig akkor dominálja az halmazt, ha minden eleméhez található olyan az -ből, amely dominálja -t. Végül, pozitív egészek egy halmazát akkor nevezzük függetlennek, ha egyetlen eleme sem dominálja egy másik elemét. Az imént bevezetett terminológia segítségével a feladat állítása úgy fogalmazható meg, hogy a pozitív egészek minden véges halmazának van olyan független részhalmaza, amely dominálja -t. Tekintsük az halmaz mindazon részhalmazait, melyekre
| ha valamely eleme alulról dominálja egy elemét, akkor felülről dominálja -et. |
Létezik a fenti tulajdonságokat teljesítő halmaz, hisz az üreshalmaz például ilyen. Válasszuk a halmazt ezen halmazok közül úgy, hogy a lehető legtöbb elemét dominálja felülről az halmazban. Azt állítjuk, hogy egy eképpen választott halmaz rendelkezik a feladatban előírt tulajdonságokkal. Mivel -t függetlennek választottuk, ezért csupán azt kell igazolni, hogy dominálja a teljes halmazt. Indirekt módon bizonyítunk, tegyük fel, hogy mégsem dominálja -t. Legyen tehát az halmaz legkisebb olyan eleme, amit nem dominál, és legyen , ahol az osztóinak halmazát jelöli. Megmutatjuk, hogy választásának ellentmondva a halmaz amellett, hogy több elemet dominál felülről, mint , teljesíti az és tulajdonságokat is. A konstrukcióból adódóan az halmaz minden olyan elemét felülről dominálja, amely elemeket felülről dominál, és ezen túl felülről dominálja -t is. Ezért több elemet dominál felülről, mint . A részhalmazaként független, továbbá az választásából adódóan nem dominálja -t. Sőt, sem dominálja egyetlen elemét sem: alulról a halmaz tulajdonsága miatt, felülről pedig definíciójából adódóan. Ezért a halmaz csakugyan független. Végül, a tulajdonság igazolásához indirekt módon tegyük fel, hogy alulról dominálja egy elemét. Ha mármost , akkor a tulajdonság miatt felülről dominálja -et, így is, tehát teljesül a tulajdonság. Ha pedig , akkor és az alulról történő dominálás miatt . Mivel az halmaz legkisebb olyan eleme, amit nem dominál, ezért dominálja -et. Ha felülről dominálja -et, akkor is felülről dominálja -et, a tulajdonság teljesül. Ha pedig egy eleme alulról dominálja -et, akkor mivel alulról dominálja -t, is alulról dominálja -t. Ez azt jelenti, hogy mégiscsak dominálja -t, ellentétben az választásával. A kapott ellentmondás pedig azt igazolja, hogy -re teljesül a tulajdonság, és ezzel a bizonyítást befejeztük.
II. megoldás. Az I. megoldásban bevezetett szóhasználatot tovább bővítjük. Pozitív egészek egy véges halmaza tetejének nevezzük azt a halmazt, melyet mindazon elemei alkotnak, amelyet nem dominál felülről a egyetlen -tól különböző eleme sem. Hasonlóan, a halmaz -val jelölt alja a azon elemeiből áll, amelyet a -nak -tól különböző eleme nem dominál alulról. Világos, hogy felülről, pedig alulról dominálja -t, továbbá, hogy tetejének egyik eleme sem dominálja tetejének egy másik elemét felülről, illetve aljának egyetlen eleme sem dominálja aljának egy másik elemét alulról. Szükségünk lesz még az alábbi megfigyelésre. Ha egy halmaz alulról dominálja az halmazt, továbbá az alulról dominálja -t, akkor is alulról dominálja -t. Legyen ugyanis tetszőleges. Az és viszonya folytán létezik olyan , amelyre osztója -nek. Mivel alulról dominálja -t, ezért -nek van olyan eleme, amelyre osztja -et. Ám ekkor osztója -nek is, azaz alulról dominálja minden elemét. A továbbiakban megadunk egy véges eljárást, amely tetszőleges halmazhoz talál egy, a feladatban megkívánt tulajdonságokkal rendelkező részhalmazt. Legyen | | Ha már meghatároztuk az , és halmazokat, akkor legyen | | Figyeljük meg, hogy az teteje lévén felülről dominálja -et és a alulról dominálja -t, így -t is. Ugyancsak a definícióból adódóan , ezért alulról dominálja -t, így a által alulról dominált -t is. Világos, hogy , így az halmaz végessége miatt teljesül valamely -ra. Ez azt jelenti, hogy , azaz . Mivel , ezért független. Megmutatjuk, hogy a halmaz megfelel a feladat feltételeinek. Láttuk, hogy független, így csupán azt kell bizonyítanunk, hogy -t is dominálja. Korábban láttuk, hogy az -t felülről dominálja. Elegendő tehát annyit bizonyítani, hogy alulról dominálja az halmazt. Láttuk azt is, hogy alulról dominálja az halmazt. Mivel , ezért a -et is alulról dominálja. Hasonlóan, alulról dominálja -t, így -t is, tehát is alulról dominálja -t. Ugyanez az érvelés mutatja, hogy alulról dominálja -t és -t minden -ra. Mindezt összevetve kapjuk, hogy alulról dominálja az halmazt. Ezzel pedig beláttuk, hogy a halmaz rendelkezik a feladatban leírt tulajdonsággal. |
|