Przez n oznaczę ilość podzbiorów zbioru Zauważmy, że dla twierdzenie jest prawdziwe, bowiem można wybrać jeden dowolny element z Niech Zakładamy, że twierdzenie jest prawdziwe dla
Jeżeli dla danego n mnogościowa suma zbiorów ma więcej niż n elementów, to twierdzenie jest prawdziwe, wystarczy bowiem wybrać dowolny element k zbioru utworzyć transwersalę dla -elementowej rodziny zbiorów (co jest możliwe na mocy założenia indukcyjnego) oraz dołączyć do niej element k.
W przeciwnym wypadku istnieje pewien podzbiór J (właściwy) zbioru taki, że suma mnogościowa wszystkich elementów zbiorów jest równa ilości elementów zbioru J. Wybierzmy teraz transwersalę dla rodziny oraz rodziny gdzie zaś Dla obu rodzin na mocy założenia indukcyjnego istnieją transwersale, i są one rozłączne, co wynika z powyższych warunków. Poszukiwaną transwersalą jest więc zbiór, będący sumą tych transwersalHalmos Paul R., Vaughan Herbert E., The marriage problem, „American Journal of Mathematics” 72, (1950), s. 214–215..
Przypisy
Linki zewnętrzne
Kategoria:Twierdzenia kombinatoryki Kategoria:Twierdzenia teorii grafów