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. Jelöljük az -elemű halmazt -sel, elemei legyenek , , . Könnyen ellenőrizhető, hogy megfelelő az a két felbontás, amikor az összes részhalmaz -ba, illetve -be kerül, azaz és valamelyike üres. Nevezzük ezeket triviális felbontásoknak. A továbbiakban pontosan leírjuk, mik azok a nemtriviális felbontások, amelyekben sem , sem nem üres. Először megmutatjuk, hogy egy nem triviális felbontásban és . Legyen ugyanis és két tetszőleges halmaz; ekkor és az a), b) és c) tulajdonságok miatt. Tegyük fel, hogy , és tekintsük most az , , egyelemű részhalmazokat. Azt állítjuk, hogy ezek közül pontosan egy tartozik -be. Ha mindegyik egyelemű halmaz -ba tartozna, akkor a c) tulajdonság miatt az halmaz is -ban lenne, ami ellentmondás. Az egyelemű részhalmazok között tehát van olyan, ami -be tartozik. Ha az egyelemű halmazok közül legalább kettő tartozna -be, akkor az a) tulajdonság miatt ezek metszete, is -beli lenne, ami szintén ellentmondás. Legyen az az egyelemű halmaz, amely -be tartozik. Az a) és b) tulajdonságok alapján megállapíthatjuk, hogy minden olyan részhalmaz, amelynek eleme, -be tartozik; ugyanis . Megfordítva, ha egy részhalmaznak nem eleme, akkor nem lehetséges, ugyanis esetén az a) tulajdonság alapján is -beli lenne. Azt kaptuk tehát, hogy egy halmaz akkor és csak akkor tartozik -be, ha . A nemtriviális felbontások száma tehát a lehetséges -k száma, azaz . Az , azaz esetben a két triviális felbontás ugyanaz: és más felbontás nincs; az összes felbontások száma tehát 1. Ha , akkor a két triviális felbontás különböző, és más felbontás nincs, így a felbontások száma 2. Ha , akkor a két triviális felbontás különböző, az összes felbontások száma . |