Ten fragment wykładu przypomina poznany już wcześniej materiał. Służy jedynie ustaleniu terminologii i notacji.
Funkcja o dziedzinie \( X \) i przeciwdziedzinie \( Y \) to dowolna relacja \( f \subseteq X \times Y \) taka, że:
Pierwszy warunek mówi, że każdy element dziedziny ma jakąś wartość przypisaną funkcją \( f \). Drugi, że taka wartość jest co najwyżej jedna (dowolne dwie są bowiem równe). W skrócie oba warunki możemy zapisać łącznie jako
\( \forall x\in X \ \exists! y \in Y \ \ \langle x,y \rangle\in f, \)
gdzie kwantyfikator \( \exists! \) oznacza istnieje dokładnie jeden.
Najczęściej będziemy się zajmowali funkcjami, które działają na liczbach (dziedziną i przeciwdziedziną będą zbiory liczbowe, np. \( \mathbb{N}, \mathbb{R} \)), ale można mówić o funkcjach na różnych zbiorach.
Wielomian to funkcja:
\( x \mapsto a_nx^n + a_{n-1}x^{n-1} + \ldots + a_2x^2 + a_1 x + a_0 \)
gdzie
Surjekcja to funkcja \( f : X \longrightarrow Y \) spełniająca warunek
Przykład
Funkcja \( \mathbb{R} \ni x \mapsto x^3 \in \mathbb{R} \) jest surjekcją.
Funkcja \( \mathbb{Q} \ni x \mapsto x^3 \in \mathbb{Q} \) nie jest surjekcją.
Funkcja \( \mathbb{N} \ni x \mapsto 2x \in \mathbb{N} \) nie jest surjekcją.
Funkcja \( \mathbb{Q} \ni x \mapsto 2x \in \mathbb{Q} \) jest surjekcją.
Funkcja \( \mathbb{Z} \ni x \mapsto \lfloor x\rfloor \in \mathbb{Z} \) jest surjekcją.
Funkcja \( \mathbb{R} \ni x \mapsto \lfloor x\rfloor \in \mathbb{Z} \) jest surjekcją.
Funkcja \( \mathbb{Z} \ni x \mapsto \lfloor x\rfloor \in \mathbb{Q} \) nie jest suriekcją.
Funkcja \( \mathbb{R} \ni x \mapsto \sin{x} \in \mathbb{R} \) nie jest surjekcją.
Funkcja \( {\{ {0,1} \}\ }^* \ni w \mapsto w1 \in {\{ {0,1} \}\ }^* \) nie jest suriekcją.
Funkcja \( {\{ {0,1} \}\ }^* \ni w \mapsto d(w) \in \mathbb{N} \) jest suriekcją.
Injekcja to funkcja \( f : X \longrightarrow Y \) spełniająca warunek:
Przykład
Funkcja \( \mathbb{R} \ni x \mapsto x^3 \in \mathbb{R} \) jest injekcją.
Funkcja \( \mathbb{R} \ni x \mapsto x^2 \in \mathbb{R} \) nie jest injekcją.
Funkcja \( \mathbb{Z} \ni x \mapsto \lfloor x\rfloor \in \mathbb{Z} \) jest injekcją.
Funkcja \( \mathbb{R} \ni x \mapsto \lfloor x\rfloor \in \mathbb{Z} \) nie jest injekcją.
Funkcja \( \mathbb{N} \ni x \mapsto 2x \in \mathbb{N} \) jest injekcją.
Funkcja \( \mathbb{Q} \ni x \mapsto 2x \in \mathbb{Q} \) jest injekcją.
Funkcja \( \mathbb{R} \ni x \mapsto \sin{x} \in \mathbb{R} \) nie jest injekcją.
Funkcja \( {\{ {0,1} \}\ }^* \ni w \mapsto w1 \in {\{ {0,1} \}\ }^* \) jest injekcją.
Funkcja \( {\{ {0,1} \}\ }^* \ni w \mapsto d(w) \in \mathbb{N} \) nie jest injekcją.
Bijekcja to funkcja, która jest jednocześnie surjekcją i injekcją.
Przykład
Funkcja \( \mathbb{R} \ni x \mapsto x^3 \in \mathbb{R} \) jest bijekcją.
Funkcja \( \mathbb{Q} \ni x \mapsto x^3 \in \mathbb{Q} \) nie jest bijekcją.
Funkcja \( \mathbb{N} \ni x \mapsto 2x \in \mathbb{N} \) nie jest bijekcją.
Funkcja \( \mathbb{Q} \ni x \mapsto 2x \in \mathbb{Q} \) jest bijekcją.
Funkcja \( \mathbb{Z} \ni x \mapsto \lfloor x\rfloor \in \mathbb{Z} \) jest bijekcją.
Funkcja \( \mathbb{R} \ni x \mapsto \lfloor x\rfloor \in \mathbb{Z} \) nie jest bijekcją.
Funkcja \( \mathbb{Z} \ni x \mapsto \lfloor x\rfloor \in \mathbb{Q} \) nie jest bijekcją.
Funkcja \( {\{ {0,1} \}\ }^* \ni w \mapsto w1 \in {\{ {0,1} \}\ }^* \) nie jest bijekcją.
Funkcja \( {\{ {0,1} \}\ }^* \ni w \mapsto d(w) \in \mathbb{N} \) nie jest bijekcją.
Traktując funkcję \( f : X \longrightarrow Y \) jako relację \( f \subseteq X \times Y \) (zbiór par), możemy rozważać relację \( f^{-1} \) odwrotną do \( f \).
Kiedy ta relacja jest funkcją?
A zatem: funkcja posiada funkcję odwrotną, wtedy i tylko wtedy, gdy jest bijekcją.
Przykład
\( f : \mathbb{R} \ni x \mapsto x^2 \in [0, +\infty). \)
Wciąż jednak brakowałoby injektywności. Ograniczając jednak, tę funkcję do liczb nieujemnych, tzn. traktując ją jako:
\( f|_{[0, +\infty)}: [0, +\infty) \ni x \mapsto x^2 \in [0, +\infty), \)
staje się już bijekcją, więc posiada funkcję odwrotną, którą jest
\( [0, +\infty) \ni x \mapsto \sqrt{x} \in [0, +\infty). \)
Złożenie funkcji \( f : X \longrightarrow Y \) i funkcji \( g : Y \longrightarrow Z \) to funkcja
\( gf: X \longrightarrow Z \)
określona dla wszystkich argumentów \( x \in X \) jako \( (gf)(x) = g(f(x)) \).
\( X \longrightarrow Y \longrightarrow Z \)
Przykład
Morał: złożenia \( fg \) i \( gf \) to (na ogół) różne funkcje.
\( (fg)(x) = f(g(x)) = f((x + \pi)^2) = \sin(3(x + \pi)^2). \)
Morał: Nie zawsze da się łatwo wyliczyć przepis na funkcję złożoną.
\( (f^{-1} f)(x) = f^{-1}(f(x)) = x. \)
Taka funkcja zwana jest identycznością na zbiorze \( X \) i oznaczana \( id_X \). Podobnie - składając \( f f^{-1} : Y \longrightarrow Y \), otrzymamy identyczność na zbiorze \( Y \).
Widzieliśmy, że nie zawsze \( fg = gf \).
Obserwacja 3.1
Dla funkcji \( X \stackrel{h}{\longrightarrow} Y \stackrel{g}{\longrightarrow} Z \stackrel{f}{\longrightarrow} W \) zachodzi \( f(gh) = (fg)h \). <
Obserwacja 3.2
Nadto dla \( X \stackrel{f}{\longrightarrow} Y \stackrel{g}{\longrightarrow} Z \) mamy:
Przykład
Zbadaj czy dla funkcji \( X \stackrel{f}{\longrightarrow} Y \stackrel{g}{\longrightarrow} Z \) zachodzi:
Przykład
Przykładem funkcji dwóch zmiennych są działania arytmetyczne:
a także konkatenacja (sklejenie) słó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:
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 \rightarrow 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 \rightarrow \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} \rightarrow \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} \rightarrow \mathbb{Z}_{m-1} \) zadana przez
\( g(x)= \{ \begin{array} {cl} f(x), & \textrm{dla} \quad x\neq a \\ b, & \textrm{dla} \quad x=a \end{array} . \)
jest injekcją, bo dla \( x_1,x_2\in\mathbb{Z}_{n_0-1}-{\{ {a} \}\ } \) zachodzi \( g(x_1)=g(x_2) \rightarrow 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)= \{ \begin{array} {cl} \frac{x}{2}, & \textrm{dla parzystych } x, \\ \frac{-1-x}{2}, & \textrm{dla nieparzystych } x, \end{array} . \)
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:
Bardzo często w tym kursie będziemy stać przed problemem zliczenia pewnego skończonego zbioru obiektów. Skrajnie niewygodne i nieefektywne byłoby, gdybyśmy za każdym razem konstruowali bijekcję z \( \mathbb{Z}_n \) w nasz zbiór dla pewnego naturalnego \( n \). Na szczęście istnieje wiele reguł pozwalających szybciej zliczać obiekty kombinatoryczne. Poniżej przedstawiamy te podstawowe. Pierwsza z nich jest bardzo prosta i w sposób intuicyjny stosowana od początków cywilizacji.
Dla skończonych i rozłącznych zbiorów \( A \) i \( B \) mamy:
Niech liczności zbiorów \( \vert A\vert=m \), \( \vert B\vert=n \) będą poświadczone bijekcjami \( f:\mathbb{Z}_m \rightarrow A \) i \( g:\mathbb{Z}_n \rightarrow B \). Wtedy funkcja \( h:\mathbb{Z}_{m+n} \rightarrow A\cup B \) zadana przez:
\( h(x)= \left\{ \begin{array} {ll} f(x), & \textrm{dla }x\in{\{ {0,\ldots,m-1} \}\ } \\ g(x-m), & \textrm{dla } x\in{\{ {m,\ldots,m+n-1} \}\ } \end{array} \right. \)
jest bijekcją. Istotnie, skoro zbiory \( A \) i \( B \) są rozłączne, to dla dowolnych \( x_1\in{\{ {0,\ldots,m-1} \}\ } \), \( x_2\in{\{ {m,\ldots,m+n-1} \}\ } \) zachodzi \( h(x_1)\neq h(x_2) \). Ponadto restrykcje \( h \) do zbiorów zbiorów \( {\{ {0,\ldots,m-1} \}\ } \) i \( {\{ {m,\ldots,m+n-1} \}\ } \) są injekcjami. A zatem \( h \) jest injekcją.
Dla dowodu surjektywności \( h \) weźmy dowolny element \( y\in A\cup B \). Załóżmy, że \( y\in A \) (w drugim przypadku dowód przebiega analogicznie). Wtedy z surjektywności \( f \) wiemy, że istnieje \( x\in\mathbb{Z}_m \) takie, że \( f(x)=y \). Ale \( h(x)=f(x)=y \). Zatem \( h \) jest surjekcją.
Łatwy dowód indukcyjny pozwala uogólnić zasadę dodawania na dowolnie wiele skończonych zbiorów.
Wniosek 3.7
Dla zbiorów \( A_1,\ldots,A_n \) skończonych i parami rozłącznych:
\( \vert A_1\cup\ldots\cup A_n\vert=\vert A_1\vert+\ldots+\vert A_n\vert. \)
Więcej pracy wymaga analiza sytuacji, gdy zbiory \( A,B \) nie są rozłączne.
Dla zbiorów skończonych \( {\{ {A_1,A_2,\ldots,A_n} \}\ } \) zachodzi
\( \begin{align*} & & \vert A_1\cup A_2\cup\ldots\cup A_n\vert\ =\ \sum_{I\subseteq{\{ {1,\ldots,n} \}\ }}(-1)^{\vert I\vert+1}\vert\bigcap_{i\in I}A_i\vert \\ & & \begin{array} {lr} = \vert A_1\vert+\vert A_2\vert+\vert A_3\vert+\ldots & +\vert A_{n-2}\vert+\vert A_{n-1}\vert+\vert A_n\vert \\ -\vert A_1\cap A_2\vert-\vert A_1\cap A_3\vert-\ldots & -\vert A_{n-2}\cap A_n\vert-\vert A_{n-1}\cap A_n\vert \\ +\vert A_1\cap A_2 \cap A_3\vert+\ldots & +\vert A_{n-2}\cap A_{n-1} \cap A_n\vert \\ -\vert A_1\cap A_2 \cap A_3\cap A_4\vert-\ldots & -\vert A_{n-3}\cap A_{n-2}\cap A_{n-1} \cap A_n\vert \\ +\ldots & \\ (-1)^{n+1}\vert A_1\cap A_2\cap\ldots\cap A_n\vert & \end{array} \end{align*} \)
W szczególności, \( \vert A\cup B\vert=\vert A\vert+\vert B\vert-\vert A\cap B\vert \), o ile tylko \( A,B \) są skończone.
Dowód
Zaczniemy od dowodu drugiego zdania. Ponieważ trzy zbiory \( A - B, A\cap B \) i \( B- A \) są parami rozłączne i sumują się do \( (A - B) \cup (A\cap B) \cup (B- A) = A \cup B \), na mocy Wniosku 3.7 mamy:
\( |A \cup B| = |(A - B) \cup (A\cap B) \cup (B- A)| = |A - B| + |A\cap B| + |B- A| \)
skąd
\( \begin{align*} |A \cup B| + |A \cap B| & =|A - B| + |A\cap B| + |B- A| + |A\cap B| \\ & =(|A - B| + |A\cap B|) + (|B- A| + |A\cap B|) \\ & =|(A - B) \cup (A\cap B)| + |(B- A) \cup (A\cap B)| \\ & =|A| + |B| \end{align*} \)
skąd już natychmiast dostajemy:
\( \begin{align*} \vert\bigcup_{k=1}^nA_k\vert\ =\ \vert\bigcup_{k=1}^{n-1}A_k\vert+\vert A_n\vert-\vert\bigcup_{k=1}^{n-1}A_k\cap A_n\vert. \end{align*} \)
Wykorzystując założenie indukcyjne dla wartości \( n-1 \) zachodzi
\( \begin{align*} \vert\bigcup_{k=1}^nA_k\vert & =\sum_{I\subseteq{\{ {1,\ldots,n-1} \}\ }}(-1)^{\vert I\vert+1}\vert\bigcap_{i\in I}A_i\vert+\vert A_n\vert-\sum_{I\subseteq{\{ {1,\ldots,n-1} \}\ }}(-1)^{\vert I\vert+1}\vert\bigcap_{i\in I}A_i\cap A_n\vert \\ & =\sum_{I\subseteq{\{ {1,\ldots,n-1} \}\ }}(-1)^{\vert I\vert+1}\vert\bigcap_{i\in I}A_i\vert+\sum_{I\subseteq{\{ {1,\ldots,n-1} \}\ }}(-1)^{\vert I\cup{\{ {n} \}\ }\vert+1}\vert\bigcap_{i\in I\cup{\{ {n} \}\ }}A_i\vert. \end{align*} \)
Rodzina wszystkich podzbiorów \( I \) zbioru liczb \( {\{ {1,\ldots,n} \}\ } \) można podzielić na dwie rozłączne rodziny:
W rezultacie otrzymujemy, że
\( \begin{align*}\vert\bigcup_{k=1}^nA_k\vert\ =\ \sum_{I\subseteq{\{ {1,\ldots,n} \}\ }}(-1)^{\vert I\vert+1}\vert\bigcap_{i\in I}A_i\vert,\end{align*} \)
co kończy dowód.
Wniosek 3.7 pozwala uogólnić Zasadę Szufladkową. Załóżmy, że pewna ilość obiektów jest rozmieszczona w \( n \) szufladach. Niech \( A_i \) będzie zbiorem obiektów w \( i \)-tej szufladce. Ponieważ zbiory obiektów w różnych szufladach są rozłączne, to ilość obiektów we wszystkich szufladach wynosi \( \vert A_1\cup\ldots\cup A_n\vert=\vert A_1\vert\cup\ldots\cup\vert A_n\vert \). Zatem jeśli każda szufladka ma co najwyżej \( r \) obiektów, to w sumie jest co najwyżej \( nr \) obiektów.
Jeśli \( m \) obiektów rozmieszczonych jest w \( n \) szufladach i \( m>nr \), dla pewnego naturalnego \( r \), to istnieje szufladka z co najmniej \( r+1 \) obiektami.
Przypomnijmy, że iloczyn kartezjański (produkt) zbiorów \( X \) i \( Y \) to zbiór
\( X\times Y={\{ {(x,y): x\in X, y\in Y} \}\ }. \)
Dla skończonych zbiorów \( X,Y \):
\( \vert X\times Y\vert=\vert X\vert\cdot\vert Y\vert. \)
Dowód
Najpierw pokażemy, że \( \vert\mathbb{Z}_m\times\mathbb{Z}_n\vert=m \cdot n \). W tym celu pokażemy, że funkcja
\( f:\mathbb{Z}_m\times\mathbb{Z}_n \ni (i,j) \mapsto in+j \in \mathbb{Z}_{mn} \)
jest bijekcją.
Dla dowodu injektywności załóżmy, że \( f(i,j)=f(i',j') \), czyli \( in+j=i'n+j' \). Bez straty ogólności możemy założyć, że \( i\leq i' \), wtedy \( (i'-i)n=j-j' \). Lewa strona równości jest wielokrotnością \( n \), zaś prawa leży w zbiorze \( {\{ {-n+1,\ldots,n-1} \}\ } \), gdyż \( j,j'\in\mathbb{Z}_n \). Ponieważ \( 0 \) jest jedyną wielokrotnością liczby \( n \) w tym zbiorze, to \( i'-i=0 \) i \( j-j'=0 \), co dowodzi injektywności \( f \).
Dla dowodu surjektywności rozważmy \( y\in\mathbb{Z}_{mn} \). Niech \( i \) będzie największą liczbą taką, że \( in\leq y \). Wtedy \( y < (i+1)n \) zatem istnieje \( j\in{\{ {0,\ldots,n-1} \}\ } \) takie, że \( y=in+j=f(i,j) \), co było do udowodnienia.
Załóżmy teraz, że \( \vert X\vert=m \) i \( \vert Y\vert=n \). Wtedy, z poczynionej wyżej obserwacji, dowód Zasady Mnożenia jest natychmiastowy, gdyż
\( \vert X\times Y\vert=\vert\mathbb{Z}_m\times \mathbb{Z}_n\vert=m\cdot n=\vert X\vert\cdot\vert Y\vert. \)
Przykład
Rozważ turniej rycerski między bractwem czerwonych a bractwem niebieskich. Bractwo czerwonych ma \( 12 \) rycerzy, bractwo niebieskich \( 15 \). Ile różnych indywidualnych pojedynków może być stoczonych, jeśli rycerze z tego samego bractwa nigdy ze sobą nie walczą?
Zbiór potegowy, lub inaczej zbiór podzbiorów, zbioru \( X \) oznaczamy przez \( \mathcal{P}(X) \).
Przykład
Przykład
Ile podzbiorów ma skończony zbiór \( n \)-elementowy? Łatwo jest odpowiedzieć na to pytanie dla małych liczb \( n \). Np. zbiór \( {\{ {a,b} \}\ } \) ma następujące cztery podzbiory:
\( \emptyset,{\{ {a} \}\ }, {\{ {b} \}\ }, {\{ {a,b} \}\ } \)
a zbiór trzyelementowy \( {\{ {a,b,c} \}\ } \) ma osiem podzbiorów:
\( \emptyset, {\{ {a} \}\ }, {\{ {b} \}\ }, {\{ {c} \}\ }, {\{ {a,b} \}\ }, {\{ {a,c} \}\ }, {\{ {b,c} \}\ }, {\{ {a,b,c} \}\ } \)
Spróbujmy odpowiedzieć na to pytanie w ogólnej sytuacji i w sposób rekurencyjny. Niech \( p_n \) oznacza liczbę podzbiorów zbioru \( n \)-elementowego. Na podstawie dotychczasowych przykładów mamy:
\( \begin{array} {|c||c|c|c|c|c} \hline n & 0 & 1 & 2 & 3 & \ldots \\ \hline p_n & 1 & 2 & 4 & 8 & \ldots \\ \hline \end{array} \)
i można wysunąć hipotezę, że w ogólności \( p_n = 2^n \). Ale jak ją uzasadnić?
Załóżmy, że znamy liczbę \( p_n \) i chcemy policzyć \( p_{n+1} \). Niech więc zbiór \( Z \) ma \( n+1 \) elementów, czyli po usunięciu ze zbioru \( Z \) elementu \( a\in Z \) dostajemy \( n \)-elementowy zbiór \( Z' \). Podobnie jak w dowodzie Zasady Włączania-Wyłączania, podzbiory zbioru \( Z \) można podzielić na dwa typy:
W drugim przypadku są to podzbiory zbioru \( Z' \). Jest więc ich dokładnie \( p_n \).
Każdy zaś podzbiór pierwszego typu, czyli \( A \subseteq Z \) takie, że \( a\in A \) jest jednoznacznie wyznaczony przez swoje pozostałe elementy, tzn. elementy różne od \( a \). A zatem każdy taki zbiór \( A \), że \( a \in A \subseteq Z \), jest postaci \( A'\cup {\{ {a} \}\ } \) dla pewnego \( A'\subseteq Z' \). A zatem podzbiorów zbioru \( Z \), w których jest element \( a \) jest też tyle ile podzbiorów zbioru \( Z' \), tzn. \( p_n \).
Łącznie więc zbiór \( Z \) ma \( p_n + p_n \) podzbiorów, czyli \( p_{n+1} = 2\cdot p_n \) Teraz już bez trudu stwierdzamy, że to wraz z warunkiem \( p_0 = 1 \) jest spełnione przez
\( p_n = 2^n \)
co można łatwo uzasadnić przez indukcję. 0
Obserwacja 3.8
Dla dowolnego, skończonego zbioru \( X \)
\( \vert\mathcal{P}(X)\vert=2^{\vert X\vert}. \)
Zbiór funkcji postaci \( X \longrightarrow Y \) oznaczamy przez \( Y^X \).
Obserwacja 3.9
Dla skończonych zbiorów \( X,Y \) mamy:
\( \vert Y^X\vert=\vert Y\vert^{\vert X\vert}. \)
Dowód
Niech \( X={\{ {x_0,\ldots,x_{m-1}} \}\ } \) oraz \( Y={\{ {y_0,\ldots, y_{n-1}} \}\ } \). Każda funkcja \( f: X \longrightarrow Y \) to krotka wartości dla kolejnych \( x_i \):
\( (f(x_0),f(x_1),\ldots,f(x_{m-1}))\in \underbrace{Y\times\ldots\times Y}_{m\ razy}. \)
A więc zbiór funkcji z \( X \) w \( Y \) jest równoliczny z \( Y^m \). Z Zasady Mnożenia otrzymujemy więc:
\( \vert\underbrace{Y\times\ldots\times Y}_{m\ razy}\vert =\underbrace{\vert Y\vert\times\ldots\times\vert Y\vert}_{m\ razy} =n^m= \vert Y\vert^{\vert X\vert}. \)
Przykład
Trzech kolegów: Bartek, Paweł i Piotrek spotkali się w pubie tuż po zdanym egzaminie z matematyki dyskretnej. Okazało się, że jest pięć marek piwa do wyboru. Na ile sposobów mogą oni wypić pierwszą kolejkę?
Każdy wybór marki piwa przez wszystkie \( 3 \) osoby możemy interpretować jako funkcję ze zbioru \( {\{ {\textrm{Bartek},\textrm{Paweł},\textrm{Piotrek}} \}\ } \) w pięcioelementowy zbiór marek piwa. A więc istnieje \( 5^3=125 \) sposobów spożycia pierwszej kolejki. I tyleż sposobów dla każdej nastepnej......
Przykład
Kod PIN jest kodem autoryzującym właściciela karty bankomatowej. Składa się on z \( 4 \) cyfr dziesiętnych. Ile jest różnych kodów PIN?
Każdy kod PIN to funkcja z czteroelementowego zbioru pozycji \( {\{ {0,1,2,3} \}\ } \) w dziesięcioelementowy zbiór cyfr \( {\{ {0,1,\ldots,9} \}\ } \). Z Obserwacji 3.9 wynika że kodów PIN jest dokładnie \( 10^4=10000. \)
Posługując się Obserwacją 3.8 udowodnimy jeszcze raz wzór na ilość podzbiorów skończonego zbioru. Zatem Obserwację 3.9 możemy traktować jako uogólnienie Obserwacji 3.8.
Dowód
Alternatywny dowód Obserwacji 3.8
Zauważmy, że dowolny podzbiór \( A\subseteq X \) wyznacza jednoznacznie funkcję \( \chi_A:X \rightarrow \mathbb{Z}_2 \) w następujący sposób:
\( \chi_Y(x)= \left \{ \begin{array}{ll} {cl} 0, & \textrm{dla }x\in X- A \\ 1, & \textrm{dla }x\in A \end{array} \right. \)
Również każda funkcja \( f :X \longrightarrow \mathbb{Z}_2 \) wyznacza jednoznacznie podzbiór \( A_f{\{ {x\in X:f(x)=1} \}\ } \) zbioru \( X \). Nadto, odpowiedniość
\( \mathcal{P}(X) \ni A \mapsto \chi_A \in \mathbb{Z}_2^X \)
jest bijektywna. Zatem \( \vert\mathcal{P}(X)\vert=\vert\mathbb{Z}_2^X\vert =2^{\vert X\vert} \).
Obserwacja 3.10
Liczba injekcji ze zbioru skończonego \( X \) w zbiór skończony \( Y \) wynosi:
\( \vert Y\vert(\vert Y\vert-1)\cdot\ldots\cdot(\vert Y\vert-\vert X\vert+1)= \frac{\vert Y\vert!}{(\vert Y\vert-\vert X\vert)!}. \)
Dowód
Niech \( X={\{ {x_0,\ldots,x_{m-1}} \}\ } \) i \( Y={\{ {y_0,\ldots,y_{n-1}} \}\ } \). Każdą injekcję z \( X \) w \( Y \) możemy utożsamić z uporządkowanym wyborem \( m \) różnych elementów ze zbioru \( Y \):
\( f(x_0),f(x_1),\ldots,f(x_{m-1}). \)
Pierwszy element możemy wybrać na \( n \) sposobów, drugi na \( n-1 \), bo musi być różny od poprzednio wybranego, trzeci już tylko na \( n-2 \) sposoby, itd., aż wreszcie \( m \)-ty na \( n-m+1 \) sposobów. Zatem liczba injekcji równa jest \( n(n-1)\cdot\ldots\cdot(n-m+1) \).
Przykład
Ile jest PIN-ów, czyli cztero-elementowych słów złożonych z cyfr dziesiętnych, takich że żadna cyfra się nie powtarza?
Każdy PIN z niepowtarzającymi się cyframi to injekcja z cztero-elementowego zbioru pozycji \( {\{ {0,1,2,3} \}\ } \) w \( 10 \)-elementowy zbiór cyfr \( {\{ {0,1,\ldots,9} \}\ } \). Zatem jest ich dokładnie \( 10\cdot9\cdot8\cdot7=5040 \).
Obserwacja 3.11
Liczba bijekcji pomiędzy skończonymi zbiorami \( X \) i \( Y \), gdzie \( \vert X\vert=\vert Y\vert \) wynosi \( \vert X\vert!. \)
Dowód
Pokażemy najpierw, że każda injekcja \( f: X \longrightarrow Y \) jest bijekcją. Istotnie, gdyby \( f \) nie było surjekcją, to \( f(X) \) byłoby właściwym podzbiorem zbioru \( Y \). A zatem \( \vert f(X)\vert < \vert Y\vert \) i funkcja \( f : X \longrightarrow f(X) \) ustalałaby injekcję ze zbioru o większej liczbie elementów w zbiór o mniej liczny. A to nie jest możliwe na mocy Obserwacji 3.3. Udowodniliśmy, że liczba bijekcji z \( X \) w \( Y \) równa jest liczbie injekcji z \( X \) w \( Y \), czyli, z Obserwacji 3.10), wynosi ona:
\( n(n-1)\cdot\ldots\cdot(n-n+2)(n-n+1)=n!. \)
Zauważmy jeszcze, że \( \emptyset \subseteq \emptyset \times \emptyset \) jest nie tylko funkcją \( \emptyset : \emptyset \longrightarrow \emptyset \), ale i bijekcją i jest to jedyna bijekcja \( \emptyset \longrightarrow \emptyset \).
Przykład
Na kurs tańca uczęszcza pięciu chłopaków i pięć dziewcząt. Większość kroków tanecznych ćwiczy się parami. Dla urozmaicenia pary często się zmieniają. Na ile sposobów może być wykonany jeden taniec?
Niech \( C \) będzie zbiorem chłopaków, a \( D \) zbiorem dziewcząt. Matematycznym modelem doboru par do tańca jest bijekcja \( f:C \rightarrow D \). Zatem możliwych wyborów jest tyle samo co bijekcji pomiędzy \( 5 \)-elementowymi zbiorami, czyli \( 5!=5\cdot4\cdot3\cdot2\cdot1=120 \).
Permutacja zbioru skończonego \( X \) to bijekcja z \( X \) w \( X \).
Zbiór permutacji zbioru \( \mathbb{Z}_n \) oznaczamy przez \( S_n \), a permutacje bedziemy w tym kursie oznaczać małymi literami greckimi.
Przykład
Rozważ funkcję \( \alpha:\mathbb{Z}_7 \rightarrow \mathbb{Z}_7 \) zadaną przez poniższą tabelę:
\( \begin{array} {|c||c|c|c|c|c|c|c|} \hline n & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline \alpha(n) & 2 & 3 & 6 & 0 & 4 & 1 & 5 \\ \hline \end{array} \)
Funkcja \( \alpha \) jest bijekcją z \( \mathbb{Z}_7 \) w \( \mathbb{Z}_7 \), zatem jest permutacją i \( \alpha\in S_7 \).
Przykład
Dla permutacji \( \alpha,\beta\in S_5 \) zadanych przez poniższą tabelę:
\( \begin{array} {|c||c|c|c|c|c|} \hline n & 0 & 1 & 2 & 3 & 4 \\ \hline \alpha(n) & 4 & 2 & 3 & 0 & 1 \\ \hline \beta(n) & 2 & 3 & 1 & 4 & 0 \\ \hline \end{array} \)
ich złożenia podane są poniżej:
\( \begin{array} {|c||c|c|c|c|c|} \hline n & 0 & 1 & 2 & 3 & 4 \\ \hline \beta\alpha(n) & 0 & 1 & 4 & 2 & 3 \\ \hline \alpha\beta(n) & 3 & 0 & 2 & 1 & 4 \\ \hline \end{array} \)
Zauważ, że oba złożenia także są permutacjami \( \mathbb{Z}_5 \).
Ponieważ permutacje są bijekcjami, to natychmiast z Obserwacji 3.2 dostajemy:
Obserwacja 3.12
Dla dowolnych permutacji \( \alpha,\beta \) skończonego zbioru \( X \):
Następne spostrzeżenie jest natychmiastowym wnioskiem z Obserwacji 3.11.
Wniosek 3.13
Zbiór \( n \)-elementowy ma dokładnie \( n! \) permutacji, \( \vert S_n\vert=n! \).
Przykład
Oto wszystkie (\( 3!=6 \)) permutacje zbioru \( S_3 \):
\( \begin{array} {ccccccccccc} 0 & 1 & 2 & \qquad & 0 & 1 & 2 & \qquad & 0 & 1 & 2 \\ \downarrow & \downarrow & \downarrow & & \downarrow & \downarrow & \downarrow & & \downarrow & \downarrow & \downarrow \\ 0 & 1 & 2 & \qquad & 0 & 2 & 1 & \qquad & 1 & 0 & 2 \\ \\ 0 & 1 & 2 & \qquad & 0 & 1 & 2 & \qquad & 0 & 1 & 2 \\ \downarrow & \downarrow & \downarrow & & \downarrow & \downarrow & \downarrow & & \downarrow & \downarrow & \downarrow \\ 1 & 0 & 2 & \qquad & 2 & 0 & 1 & \qquad & 2 & 1 & 0 \end{array} \)
Permutację \( \alpha \) zbioru \( X={\{ {x_0,\ldots,x_{n-1}} \}\ } \) wygodnie jest identyfikować z krotką \( (\alpha(x_0),\ldots,\alpha(x_{n-1}))\in X^n \). Często też permutację interpretuje się jako uporządkowanie zbioru \( X \).
Przykład
Na ile sposobów można poukładać koło siebie na półce \( 7 \) książek?
Na dokładnie tyle, ile jest permutacji zbioru siedmio-elementowego, a więc \( 7!=5040 \).
Cykl zbioru \( n \)-elementowego \( X \) to taka permutacja zbioru \( X \), dla której \( {\{ {x,\alpha(x),\alpha^2(x),\ldots,\alpha^{n-1}(x)} \}\ }=X \), przy dowolnym \( x\in X \). Łatwo zauważyć, że jeśli dla pewnego \( x_0\in X \) mamy \( {\{ {x,\alpha(x),\alpha^2(x),\ldots,\alpha^{n-1}(x)} \}\ }=X \), to jest tak dla wszystkich \( x\in X \), czyli \( \alpha \) jest cyklem na \( X \). Cykl \( \alpha \) zbioru \( X \) zapisujemy jako \( (x,\alpha(x),\ldots,\alpha^{n-1}(x)) \) dla dowolnie wybranego \( x\in X \).
Przykład
Rozważmy \( \alpha\in S_6 \) daną przez
Dowolną permutację \( \alpha \) zbioru \( X \) można rozłożyć na rozłączne cykle w sposób następujący:
Dowód
Dla dowodu poprawności algorytmu rozkładu pokażemy najpierw, że iteracja w drugim punkcie zawsze osiąga element wyjściowy \( x \). Ponieważ zbiór \( X \) jest skończony iteracja \( x,\alpha(x),\alpha^2(x)\ldots \) w pewnym kroku musi wrócić do elementu już rozważanego, zatem \( \alpha^i(x)=\alpha^j(x) \) dla pewnych \( i < j \). Weźmy najmniejsze takie \( j \), że \( \alpha^i(x)=\alpha^j(x) \) dla pewnego \( 0\leq i < j \). Gdyby \( i\neq 0 \) to z faktu, że \( \alpha \) jest permutacją mamy \( \alpha^{i-1}(x)=\alpha^{j-1}(x) \), co stoi w sprzeczności z minimalnością \( j \). A zatem \( \alpha^j(x)=x \).
Pozostaje jeszcze pokazać, że otrzymane cykle są rozłączne. Załóżmy, że nie są i weźmy pierwszy napotkany element \( y=\alpha^i(x) \), który był już w którymś z poprzednich cykli. Zauważmy, że \( i>0 \) gdyż \( x \) był wybrany jako element nie pokryty przez żaden cykl (patrz punkt pierwszy). Wiemy, że istnieje element \( z \) w tym samym cyklu co \( y \) taki, że \( \alpha(z)=y \), ale także \( \alpha(\alpha^{i-1}(x))=y \). Ponieważ \( \alpha \) jest permutacją, otrzymujemy \( \alpha^{i-1}(x)=z \), co stoi w sprzeczności z faktem, że \( y \) jest jedynym elementem z poprzedniego cyklu.
Jeśli permutacja \( \alpha \) złożona jest z \( k \) rozłącznych cykli, to zapisujemy \( \alpha=(x_0,\ldots)(x_1,\ldots)\ldots(x_{k-1},\ldots) \), gdzie w kolejnych nawiasach są elementy kolejnych cykli startujące od odpowiednio: \( x_0,\ldots,x_{k-1} \).
Przykład
Rozważmy jeszcze raz permutację \( \alpha\in S_7 \):
\( \begin{array} {|c||c|c|c|c|c|c|c|} \hline n & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline \alpha(n) & 2 & 3 & 6 & 0 & 4 & 1 & 5 \\ \hline \end{array} \)
Rozkład \( \alpha \) na cykle: