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. Legyen a feladatban leírt tulajdonságú részhalmazok egy rendszere, és legyenek és a különböző tagjai. Tegyük fel, hogy az halmaz legkisebb eleme az halmazt alkotja. Tekintettel arra, hogy , az halmaz legnagyobb eleme nem tartozik -hoz. Ezért ez az elem -hez tartozik, ilyenformán a halmazcsalád tagjainak legnagyobb elemei páronként különbözők. A halmazcsaládhoz tehát legfeljebb annyi halmaz tartozhat, mint ahányféle az hamaz egy elemű részhalmazának a legnagyobb eleme lehet. Világos, hogy az számok egyike sem lehet egy ilyen elemű részhalmaz legnagyobb eleme, ezért a feladatban kérdezett részhalmazok száma legfeljebb a halmaz számossága, azaz legfeljebb lehet. Annak igazolására, hogy ez a felső korlát elérhető, elegendő azt észrevenni, hogy az halmazok rendelkeznek a feladatban leírt tulajdonsággal, ha . Ezzel pedig pontosan halmazt adtunk meg, a feladat kérdésére a válasz tehát .
Megjegyzés. Maximális méretű halmazcsaládra egy, a fentitől különböző példa esetén az halmazok rendszere.
|