Zliczanie zbiorów

Gdy chcemy policzyć liczbę samochodów na parkingu zazwyczaj wskazujemy na kolejne samochody odliczając: jeden, dwa, trzy, itd., aż do momentu gdy każdy samochód zostanie wskazany. Wtedy ostatnia liczba, którą wypowiedzieliśmy jest uważana za liczbę samochodów na parkingu.

Aby wprowadzić matematyczny model procedury zliczania definiujemy początkowe odcinki liczb naturalnych:

\( \begin{align*} \mathbb{Z}_0 & =\emptyset, \\ \mathbb{Z}_1 & ={\{ {0} \}\ }, \\ \mathbb{Z}_2 & ={\{ {0,1} \}\ }, \\ & \vdots \\ \mathbb{Z}_k & ={\{ {0,\ldots,k-1} \}\ }. \end{align*} \)

Załóżmy, że na parkingu stoi \( n \) samochodów. Zliczając je wybieramy elementy \( \mathbb{Z}_n \) (zazwyczaj kolejne liczby) i przypisujemy je do samochodów na parkingu. Uwaga: wybierając liczby z \( \mathbb{Z}_n \) zaczynamy od \( 0 \) i kończymy na \( n-1 \) (na ogół nie-informatycy zliczają od \( 1 \) do \( n \)). Określamy zatem w trakcie tego zliczania bijekcję \( f:\mathbb{Z}_n \to S \), gdzie \( S \) jest zbiorem samochodów na parkingu. W istocie jest to bijekcja, bo dwa różne samochody mają różne numery (injektywność) i każdy samochód jest policzony (surjektywność).

Obserwacja 3.3

Gdy \( m < n \), to nie istnieje injekcja z \( \mathbb{Z}_n \) w \( \mathbb{Z}_m \).

Dowód

Niech \( S \) będzie zbiorem liczb naturalnych \( n \) takich, że istnieje injekcja postaci \( f:\mathbb{Z}_m \to \mathbb{Z}_n \), przy pewnym \( m < n \). Oczywiście \( 0\notin S \), bo nie istnieje liczba naturalna \( m \) taka, że \( 0\leq m < 0 \). Także \( 1\notin S \), bo nie istnieje funkcja z niepustego zbioru \( \mathbb{Z}_1 \) w pusty \( \mathbb{Z}_0 \). Dla dowodu niewprost załóżmy, że \( S \) jest niepusty. Wtedy, z Zasady Minimum, \( S \) ma element najmniejszy, powiedzmy math>n_0>1</math>. Istnieje zatem \( m < n_0 \) i injekcja \( f:\mathbb{Z}_{n_0} \to \mathbb{Z}_m \). Analogicznie jak wcześniej \( m\neq 0 \) oraz \( m\neq 1 \), bo inaczej wszystkie elementy \( N_{n_0} \) musiałyby mieć tę samą wartość, co stoi w sprzeczności z injektywnością \( f \). Zatem \( m-1 \) jest dodatnią liczbą naturalną.

Jeśli \( m-1\notin f({\{ {0,\ldots,n_0-2} \}\ }) \), to restrykcja \( f|_{\mathbb{Z}_{n_0-1}} \) jest injekcją z \( \mathbb{Z}_{n_0-1} \) w \( \mathbb{Z}_{m-1} \), czyli \( n_0-1\in S \) co stoi w sprzeczności z minimalnością \( n_0 \) w \( S \).

Jeśli \( m-1\in f({\{ {0,\ldots,n_0-2} \}\ }) \), to niech \( a \) i \( b \) będą takimi liczbami, że \( f(a)=m-1 \) i \( f(n_0-1)=b \).

Wtedy funkcja \( g:\ N_{n_0-1} \to \mathbb{Z}_{m-1} \) zadana przez

\( g(x)= \left\{ \begin{array} {cl} f(x), & \textrm{dla} \quad x\neq a \\ b, & \textrm{dla} \quad x=a \end{array}. \right. \)

jest injekcją, bo dla \( x_1,x_2\in\mathbb{Z}_{n_0-1}-{\{ {a} \}\ } \) zachodzi \( g(x_1)=g(x_2) \to x_1=x_2 \) i dodatkowo \( b\notin g(\mathbb{Z}_{n_0}-{\{ {a} \}\ })=f(\mathbb{Z}_{n_0}-{\{ {a} \}\ }) \). Zatem znów \( n_0-1\in S \), co stoi w sprzeczności z minimalnością \( n_0 \) w \( S \).

Wniosek 3.4

Jeśli istnieje bijekcja ze zbioru \( \mathbb{Z}_m \) na \( \mathbb{Z}_n \), to \( m=n \).

Zbiór skończony to zbiór bijektywny z pewnym zbiorem postaci \( \mathbb{Z}_n \).

Zbiór nieskończony to zbiór, który nie jest skończony.

Jeśli \( X \) jest zbiorem skończonym, to Wniosek 3.4 gwarantuje nam, że \( X \) jest bijektywny z dokładnie jednym zbiorem postaci \( \mathbb{Z}_n \). Rozważając skończony zbiór \( n \)-elementowy \( X \), często używamy notacji \( X={\{ {x_0,x_1,\ldots,x_{n-1}} \}\ } \) ukrywającej w sobie bijekcję postaci \( \mathbb{Z}_n \longrightarrow X \).

Liczba elementów skończonego zbioru \( X \), to jedyna liczba naturalna \( n \) taka, że istnieje bijekcja z \( \mathbb{Z}_n \) w \( X \). Liczbę te oznaczamy
przez \( \vert X\vert \).

Przykład

Oczywiście \( \vert\mathbb{Z}_n\vert = n \). W szczególności zbiór pusty ma, zgodnie z intuicją, liczbę elementów równą \( 0 \).

Przykład

Zbiór liczb parzystych \( \mathbb{P} \) jest nieskończony.

Dla dowodu niewprost załóżmy, że \( \vert\mathbb{P}\vert=k \), tzn. \( \mathbb{P} = {\{ {p_0,\ldots,p_{k-1}} \}\ } \). Oczywiście \( \mathbb{P} \neq \emptyset \), bo \( 0\in \mathbb{P} \). Nadto suma wszystkich \( p_i \) jest ograniczeniem zbioru \( \mathbb{P} \), a więc, z Zasady Maksimum, \( \mathbb{P} \) posiada element największy, powiedzmy \( p_0 \). Ponieważ \( p_0 \) jest największą liczbą parzystą, \( p_0+2\notin \mathbb{P} \), co oczywiście daje sprzeczność.

Obserwacja 3.5

Zbiór \( X \) jest nieskończony wtedy i tylko wtedy, gdy istnieje injekcja z \( \mathbb{N} \) w \( X \).

Dowód

Załóżmy, że \( X \) jest nieskończony i zdefiniujmy indukcyjnie funkcję \( f:\mathbb{N}\longrightarrow X \), kładąc:

  1. niech \( f(0) \) będzie dowolnym, wybranym elementem \( X \),
  2. gdy \( f(0),\ldots,f(n) \) są już określone, wtedy niech \( f(n+1) \) będzie dowolnie wybranym elementem z \( X-{\{ {f(0),\ldots,f(n)} \}\ } \).

To, że wyboru opisanego w punkcie drugim możemy zawsze dokonać, wynika wprost z nieskończoności zbioru \( X \). Istotnie, gdyby zbiór \( X-{\{ {f(0),\ldots,f(n)} \}\ } \) był pusty, to \( f \) byłoby bijekcją \( \mathbb{Z}_{n+1} \longrightarrow X \) świadczącą o tym, że \( X \) jest skończony. Oczywiście, tak zdefiniowana funkcja \( f : \mathbb{N} \longrightarrow X \) jest injekcją.

Dla dowodu implikacji odwrotnej załóżmy, że istnieje injekcja \( f:\mathbb{N}\longrightarrow X \) oraz że \( X \) jest skończony tzn. że istnieje bijekcja \( g:\mathbb{Z}_n\longrightarrow X \) dla pewnego \( n \). Zauważmy, że restrykcja \( f|_{\mathbb{Z}_{n+1}} \) jest również injekcją. A zatem złożenie \( g^{-1} f|_{\mathbb{Z}_{n+1}} \) jest injekcją z \( \mathbb{Z}_{n+1} \) w \( \mathbb{Z}_n \), co stoi w sprzeczności z Obserwacją 3.3.

Zbiór przeliczalny to zbiór skończony lub bijektywny z \( \mathbb{N} \).

Przykład

  • zbiór pusty jest przeliczalny, bo jest skończony,
  • zbiór liczb parzystych jest przeliczalny, bo \( f(x)=2x \) jest bijekcją \( \mathbb{N}\longrightarrow\mathbb{P} \)
  • zbiór liczb całkowitych jest przeliczalny, bo

\( f(x)= \left\{ \begin{array} {cl} \frac{x}{2}, & \textrm{dla parzystych } x, \\ \frac{-1-x}{2}, & \textrm{dla nieparzystych } x, \end{array} .\right. \)

jest bijekcją z \( \mathbb{N} \) w \( \mathbb{Z} \).

Zasada Szufladkowa

Wróćmy jeszcze do Obserwacji 3.3 - formalnej podstawy zliczania skończonych zbiorów. Ma ona także bardziej praktyczną interpretację. Jest to formalne ujęcie faktu powszechnie znanego jako Zasada Szufladkowa Dirichleta (wierzy się, że jako pierwszy opisał ja Dirichlet w 1834).

Wniosek 3.6 [Zasada Szufladkowa Dirichleta]

Jeśli \( n \) obiektów jest rozmieszczonych w \( m \) szufladach i \( n>m \), to istnieje szuflada z przynajmniej dwoma obiektami.

Dowód

Zbiór obiektów jest bijektywny ze zbiorem \( \mathbb{Z}_n \), zaś zbiór szuflad z \( \mathbb{Z}_m \). Rozmieszczenie obiektów w szufladach to określenie funkcji z \( \mathbb{Z}_n \) w \( \mathbb{Z}_m \). Ponieważ \( n>m \) to Obserwacja 3.3 mówi nam, ze funkcja ta nie jest injekcją, a zatem lokuje co najmniej dwa obiekty w tej samej szufladzie.

Przykład

Proste przykłady:

  • Wśród mieszkańców Krakowa co najmniej dwie osoby mają tę samą liczbę włosów na głowie.

Dowód

Rzeczywiście, liczba włosów na głowie człowieka nie przekracza \( 500 000 \), natomiast liczba mieszkańców Krakowa przekracza \( 800 000 \). Weźmy \( 500 000 \) szufladek ponumerowanych kolejnymi liczbami naturalnymi od \( 0 \) do \( 499 999 \) i wkładajmy do szufladki o danym numerze osoby, które mają taką liczbę włosów na głowie, jak numer szufladki. Ponieważ osób jest \( 800 000 \), a szufladek \( 500 000 \), z Zasady Szufladkowej wynika, że w jednej szufladce muszą znaleźć się co najmniej dwie osoby.

  • W grupie \( 13 \) osób muszą być co najmniej dwie, które urodziły się w tym samym miesiącu.

Dowód

Weźmy \( 12 \) szufladek z nazwami miesięcy i wkładajmy do nich osoby, które urodziły się w danym miesiącu. Ponieważ osób jest \( 13 \), a szufladek \( 12 \), w jednej z nich muszą być co najmniej dwie osoby.

Czasem, umiejętnie dobierając "pudełka" można pokazać bardziej zaskakujące fakty...

Przykład

Pewna grupa osób wita się podając sobie ręce. Nikt nie wita się z samym sobą i żadna para osób nie wita się podwójnie. Czy muszą być dwie osoby, które witały taką samą liczbę osób?

  • Gdy jest \( n \) osób, to każda z nich przywita \( 0 \) lub \( 1 \) lub \( 2 \) lub ... \( n-1 \) osób.
  • Utwórzmy więc \( n \) szuflad z etykietami \( k=0,1,2,\ldots, n-1 \) i umieśćmy osobę w szufladzie o etykiecie \( k \), jeśli witała się z dokładnie \( k \) osobami.
  • Skoro jest \( n \) osób i \( n \) szuflad, to ...
    niewiele z tego wynika  :-(
  • Ale... niewiele wynika tylko jeśli wszystkie szuflady będą zajęte, a tak jest w przypadku, gdy również dwa konkretne pudełka o etykietach \( 0 \) i \( n-1 \) są zajęte. Tyle, że nie jest to możliwe - nie może być osoby, która przywitała wszystkie pozostałe i równocześnie takiej, która nie przywitała nikogo.
  • A zatem \( n \) osób zajęło co najwyżej \( n-1 \) szuflad, więc w jednej z nich są co najmniej dwie osoby - takie, które przywitały tę samą liczbę osób.

Przykład

Wybierając \( n+1 \) liczb spośród \( 1,2,3,\ldots, 2n \), wśród wybranych liczb zawsze znajdziemy dwie, z których jedna dzieli drugą.

Istotnie:

  • Określmy relacje \( xRy \) na liczbach naturalnych, tak by:

\( xRy \ \ \Leftrightarrow \) iloraz \( \frac{x}{y} \) jest potęgą (być może ujemną) liczby \( 2 \).

Oznacza to, że \( xRy \) jeśli liczby \( x, y \) mają ten sam największy czynnik nieparzysty.

  • Szufladami niech będą klasy równoważności relacji \( R \).
  • Ile jest klas-szuflad dla liczb ze zbioru \( {\{ {1,2,3,\ldots, 2n} \}\ } \)? Co najwyżej \( n \), gdyż tyle może być liczb nieparzystych w zbiorze \( {\{ {1, 2, ..., 2n} \}\ } \).
  • Skoro wybrano \( n + 1 \), to rozkładając je do naszych szuflad jakieś dwie, powiedzmy \( a,b \) muszą trafić do wspólnej szuflady.

Oznacza to, że któryś z ilorazów \( \frac{a}{b}, \frac{b}{a} \) jest dodatnią potęgą dwójki, a zatem \( a \) dzieli \( b \) lub \( b \) dzieli \( a \).

Przykład

Wybierzmy dowolnie \( 10 \) różnych liczb naturalnych \( a_1,a_2,\ldots,a_{10} \) spośród \( 1,2,3,\ldots,100 \). Pokażemy, że w zbiorze \( {\{ {a_1,a_2,\ldots,a_{10}} \}\ } \) można wybrać dwa rozłączne podzbiory, dające tę samą sumę.

Istotnie:

  • Szuflady poetykietujmy liczbami reprezentującymi możliwe sumy liczb w co najwyżej 10-cio elementowych podzbiorach zbioru \( {\{ {1,2,3,\ldots,100} \}\ } \). Ponieważ największa możliwa taka suma to \( 91+92+93+\cdots+99+100 = 955 \), to mamy \( 955 \) szuflad z etykietami: \( 0,1,2,3,\ldots, 955 \)
  • z drugiej strony \( 10 \)-cio elementowy zbiór \( {\{ {a_1,a_2,\ldots,a_{10}} \}\ } \) ma \( 2^{10}=1024 \) podzbiory, więc muszą być dwa podzbiory zbioru \( {\{ {a_1,a_2,\ldots,a_{10}} \}\ } \) o tej samej sumie.
  • Te dwa podzbiory nie muszą być rozłączne. Ale jeśli z obu z nich usuniemy wspólne liczby, to pozostałe dalej będą dawać takie same sumy, a powstałe zbiory będą już rozłączne.