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:
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
\( 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} \).
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:
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.
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?
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:
\( 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.
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: