Dla dowolnego zbioru \( X \) rodzina \( \mathscr{P}\!( X ) \) jego podzbiorów wraz z inkluzją tworzy zbiór częściowo uporządkowany \( ( \mathscr{P}\!( X ),\subseteq ) \).
Rodzina Sperner'a podzbiorów zbioru \( X \) to antyłańcuch w posecie \( ( \mathscr{P}\!( X ),\subseteq ) \).
Starano się oszacować liczność rodzin Spernera, czyli znaleźć szerokość posetu \( ( \mathscr{P}\!( X ),\subseteq ) \). Poniższe twierdzenie pomaga odpowiedzieć na to pytanie.
Twierdzenie 2.5 [K. Yamamoto 1954; L. D. Meshalkin 1963; D. Lubell 1966]
Niech \( \lbrace A_1,\ldots,A_m \rbrace \) będzie rodziną Spernera podzbiorów zbioru \( X \). Wówczas
\( \sum_{i=1}^{m}{\vert X \vert \choose \vert A_i \vert}^{-1}\leq 1. \)
Dowód [D. Lubell]
Niech \( n=\vert X \vert \). W posecie \( ( \mathscr{P}\!( X ),\subseteq ) \) każdy maksymalny łańcuch
\( \emptyset=C_0\subseteq C_1\subseteq\ldots\subseteq C_{n-1}\subseteq C_n=X \)
musi spełniać \( \vert C_j \vert=j \). Zbiór \( C_1 \) może być wybrany na \( n \) sposobów, z kolei \( C_2 \) na \( n-1 \) sposobów. W ogólności \( C_j \) może być wybrany na \( n-j+1 \) sposobów. Czyli łącznie jest \( n! \) różnych łańcuchów maksymalnych.
Z drugiej strony policzymy ile jest łańcuchów, w których występuje konkretny zbiór \( A_i \) z rodziny Spernera, tzn.
\( \emptyset=C_0\subseteq C_1\subseteq\ldots\subseteq C_{\vert A_i \vert}=A_i \subseteq\ldots\subseteq C_{n-1}\subseteq C_n=X \)
Ponieważ singleton \( C_1 \) musi zawierać się w \( A_i \), może być wybrany na \( \vert A_i \vert \) sposobów. Tak więc \( C_2 \) może być wybrane już jedynie na \( \vert A_i \vert-1 \) sposobów i tak dalej. A zatem różnych łańcuchów postaci
\( \emptyset=C_0\subseteq C_1\subseteq\ldots\subseteq C_{\vert A_i \vert}=A_i \)
jest \( \vert A_i \vert! \). W analogiczny sposób otrzymujemy, że różnych łańcuchów postaci
\( A_i=C_{\vert A_i \vert}\subseteq C_{\vert A_i \vert+1}\subseteq\ldots\subseteq C_n=X \)
jest \( ( n-\vert A_i \vert )! \). Podsumowując, liczba maksymalnych łańcuchów, w których występuje \( A_i \) wynosi \( \vert A_i \vert!( n-\vert A_i \vert )! \).
Ponieważ \( \lbrace A_1,\ldots,A_m \rbrace \) jest antyłańcuchem, to dla \( i\neq j \) w łańcuchu nie mogą wystąpić równocześnie \( A_i \) i \( A_j \). Zliczając teraz maksymalne łańcuchy przechodzące przez któreś \( A_i \), możemy pominąć jakiś łańcuch maksymalny. Nie mniej jednak mamy
\( \sum_{i=1}^m{\vert A_i \vert!( n-\vert A_i \vert )!}\leq n!. \)
To w konsekwencji daje
\( \sum_{i=1}^{m}{\frac{1}{{n\choose\vert A_i \vert}}} =\sum_{i=1}^m{\frac{\vert A_i \vert!( n-\vert A_i \vert )!}{n!}} \leq 1. \)
Przykład
Oczywiście, dla ustalonego \( k \) rodzina \( k \)-elementowych podzbiorów jest rodziną Spernera. Ponieważ wartość \( {n\choose k} \) jest maksymalna dla \( k=/n/2\rfloor \), to \( n \)-elementowy podzbiór ma rodzinę Spernera o mocy \( {n \choose /n/2\rfloor} \). Następne twierdzenie pokazuje, że jest to najliczniejsza rodzina Spernera.
Twierdzenie 2.6 [E. Sperner 1928]
Jeśli \( \mathscr{A} \) jest rodziną Spernera podzbiorów zbioru \( X \), to
\( \vert \mathscr{A} \vert\leq{\vert X \vert\choose\lfloor\vert X \vert/2\rfloor}. \)
Dowód
Niech \( n=\vert X \vert \) oraz \( \mathscr{A}=\lbrace A_1,\ldots,A_m \rbrace \). Wartość \( {n\choose k} \) jest maksymalna dla \( k=/2\rfloor \). Tak więc \( {n\choose\vert A_i \vert}\leq{n\choose{n/2}} \). Na mocy Twierdzenia 2.5 otrzymujemy:
\( m\frac{1}{{n \choose/2\rfloor }}\leq\sum_{i=1}^{m}{\frac{1}{{n\choose\vert A_i \vert}}}\leq 1, \)
skąd natychmiast
\( m\leq{n\choose/2\rfloor}. \)
Uwaga
W posecie \( ( \mathscr{P}\!( X ),\subseteq ) \) dowolne dwa jego elementy \( A,B\in\mathscr{P}\!( X ) \) spełniają:
W takim razie dowolne dwa elementy posetu \( ( \mathscr{P}\!( X ),\subseteq ) \) mają najmniejsze ograniczenie górne oraz największe ograniczenie dolne. Posety o tej własności nazywane są kratami.
Krata to częściowy porządek \( \mathbf{P}=( P,\leq ) \), w którym dla dowolnych \( a,b\in P \) istnieją
Kres dolny oznaczać bedziemy przez \( a \wedge b \).
Kres dolny oznaczać bedziemy przez \( a \vee b \).
Przykład
Rozważmy zbiór liczb naturalnych \( \mathbb{N} \) oraz relacje \( \sqsubseteq \) zdefiniowaną w następujący sposób
\( a \sqsubseteq b\quad\textrm{wtedy i tylko wtedy, gdy}\quad a\ \textrm{dzieli}\ b\quad\textrm{dla}\ a,b\in\mathbb{N}. \)
Relacja \( \sqsubseteq \) jest zwrotna, antysymetryczna, i przechodnia. Tak więc para \( ( \mathbb{N},\sqsubseteq ) \) tworzy częściowy porządek. Jako ćwiczenie 6 pozostawiamy do udowodnienia, że \( ( \mathbb{N},\sqsubseteq ) \) jest kratą, oraz że kres dolny dwu liczb naturalnych to ich największy wspólny dzielnik, a kres ich kres górny to najmniejsza wspólna wielokrotność.