Rozważ dowolną rodzinę podzbiorów zbioru n-elementowego.... asdf: Rozważ dowolną rodzinę podzbiorów zbioru n−elementowego zawierającą więcej niż połowę wszystkich podzbiorów. Wykaż, że w tej rodzinie muszą być dwa zbiory takie, ze jeden zawiera sie w drugim. Mógłby ktoś mi to objaśnić? Wiem tyle, że można skorzystać z zasady szufladkowej Dirichleta... Serdecznie dziękuję.

asdf: podbijam

jc: Indukcja względem n. Dla n=1 twierdzenie jest prawdziwe (dlaczego?). Załóżmy, że twierdzenie jest prawdziwe dla n. Weźmy rodzinę złożoną z co najmniej 2ⁿ+1 podzbiorów zbioru n+1 elementowego. Podzielmy rodzinę na dwie rodziny: zbiory do których należy element n+1 i zbiory do których nie należy. Jedna z tych rodzin liczy co najmniej 2ⁿ⁻¹+1 elementów. Z założenia indukcyjnego wynika, że zawiera dwa podzbiory, z których jeden zawarty jest w drugim, n+1 element niczego nie psuje.