Matematyka dyskretna 1/Wykład 3: Zliczanie zbiorów i funkcji

Funkcje

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:

• $\mathrm{\forall }x\in X\mathrm{\exists }y\in Y⟨x,y⟩\in f$
• $\mathrm{\forall }x\in X\mathrm{\forall }{y}_1,y_2\in Y(⟨x,y_1⟩\in f\wedge ⟨x,y_2⟩\in f)\to y_1=y_2$

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

$\mathrm{\forall }x\in X\mathrm{\exists }!y\in Y⟨x,y⟩\in f,$

gdzie kwantyfikator $\mathrm{\exists }!$ oznacza { istnieje dokładnie jeden}.

• Ważne jest
  • wykorzystanie wszystkich elementów dziedziny: { każdemu elementowi dziedziny ...}
  • i jednoznaczność: { jest przyporządkowany dokładnie jeden element przeciwdziedziny},
• nie wyklucza to sytuacji, gdy np. dwóm elementom dziedziny przyporządkowany jest ten sam element przeciwdziedziny,
• nie każdy element przeciwdziedziny musi być wykorzystany, tzn. mogą istnieć takie elementy przeciwdziedziny, które nie są przyporządkowane żadnemu elementowi dziedziny,
• dziedzina i przeciwdziedzina mogą być tym samym zbiorem.

Notacja:

• Piszemy $f:X⟶Y$ lub $X\stackrel{f}{⟶}Y$ na oznaczenie funkcji o nazwie $f$, której dziedziną jest zbiór $X$, a przeciwdziedziną zbiór $Y$.

  elementy dziedziny nazywamy argumentami funkcji

  elementy przeciwdziedziny im przyporządkowane nazywamy wartościami funkcji

  .

• Piszemy $f(x)=y$ lub $f:x\mapsto y$ na oznaczenie tego, że funkcja $f$ elementowi $x$ przyporządkowuje element $y$
  • mówimy wtedy, że $y$ jest wartością funkcji $f$ na argumencie $x$.
• Często podaje się { przepis} na funkcję, wykorzystując
  • operacje arytmetyczne: $f(x)=3x+7$
  • lub inne powszechnie znane funkcje $g(x)=2\sin (x)\cos (x)$.
• W powyższych przykładach dziedziny i przeciwdziedziny można się domyślić (zapewne liczby rzeczywiste), ale dla ścisłości powinno się je podać, np. $f:\mathbb{ℝ}⟶\mathbb{ℝ}$.

Przykłady funkcji

Najczęściej będziemy się zajmowali funkcjami, które działają na liczbach (dziedziną i przeciwdziedziną będą zbiory liczbowe, np. $\mathbb{\mathbb{N}},\mathbb{ℝ}$), ale można mówić o funkcjach na różnych zbiorach.

• $f:\mathbb{\mathbb{N}}\ni n\mapsto 2n\in \mathbb{\mathbb{N}}$,
  • jest zwartym zapisem, że $f$ jest funkcją postaci $f:\mathbb{\mathbb{N}}⟶\mathbb{\mathbb{N}}$
    daną przepisem $f(n)=2n$
  • jako przeciwdziedzinę określiliśmy zbiór liczb naturalnych,
    ale w istocie wartościami tej funkcji są tylko liczby parzyste
• $g:\mathbb{\mathbb{N}}⟶\mathbb{ℝ},g(n)=n/2$,
  • określenie $g:\mathbb{\mathbb{N}}⟶\mathbb{\mathbb{N}}$ nie byłoby tu prawidłowe, gdyż wartość $n/2$ nie zawsze jest liczbą naturalną
• $h:\mathbb{\mathbb{N}}⟶\left\{13\right\},h(n)=13$,
  • to też jest poprawnie określona funkcja, mimo że niezbyt frapująca (tzw. funkcja stała)
• $f:\mathbb{\mathbb{N}}⟶\mathbb{\mathbb{N}},f(n)=(1+3+5+...+(2n+1){)}^n$.
  • takie określenie też jest poprawne, choć nie od razu widać, ile to jest
• $g:\mathbb{ℝ}\ni x\mapsto \sin \frac{x}{\pi }\in \mathbb{ℝ}$ jest całkiem poprawną funkcją.
• $h:\mathbb{ℝ}\ni x\mapsto \sin \frac{\pi }{x}\in \mathbb{ℝ}$,
  • to określenie (mimo, że podobne do poprzedniego) jest błędne:
    nie da się policzyć wartości $h(0)$;
    należałoby więc napisać np. $h:\mathbb{ℝ}-\left\{0\right\}⟶\mathbb{ℝ}$
• ${\left\{0,1\right\}}^{*}\ni w\mapsto w1\in {\left\{0,1\right\}}^{*}$,
  • to funkcja określona na słowach nad alfabetem dwuelementowym $\left\{0,1\right\}$
  • każdemu słowu przypisuje to słowo rozszerzone na końcu o symbol $1$
• Parser nie mógł rozpoznać (błąd składni): {\displaystyle d: {\left\{ {0,1} \right\}\ }^* \longrightarrow \mathbb{N}, \ d(w) = \mbox{długość słowa } wParser nie mógł rozpoznać (błąd składni): {\displaystyle }}

Wielomian to funkcja:

$x\mapsto a_n{x}^n+a_{n-1}{x}^{n-1}+\dots +a_2{x}^2+a_{1}x+a_0$

gdzie

• liczby $a_n,a_{n-1},\dots ,a_1,a_0$ zwane są { współczynnikami} wielomianu
  • mówimy więc o wielomianach o współczynnikach
    • naturalnych -- jeśli $a_n,a_{n-1},\dots ,a_1,a_0\in \mathbb{\mathbb{N}}$
    • całkowitych -- jeśli $a_n,a_{n-1},\dots ,a_1,a_0\in \mathbb{\mathbb{Z}}$
    • wymiernych -- jeśli $a_n,a_{n-1},\dots ,a_1,a_0\in \mathbb{\mathbb{Q}}$
    • rzeczywistych -- jeśli $a_n,a_{n-1},\dots ,a_1,a_0\in \mathbb{ℝ}$
  • liczba $n$ zwana jest stopniem wielomianu, ale tylko o ile $a_n\ne 0$.

Surjekcje, injekcje i bijekcje

Suriekcja to funkcja $f:X⟶Y$ spełniająca warunek

$\mathrm{\forall }y\in Y\mathrm{\exists }x\in Xf(x)=y$

• Intuicyjnie, funkcja jest surjekcją, jeśli jej cała przeciwdziedzina jest wykorzystana, tzn. każdy jej element jest wartością funkcji dla jakiegoś elementu dziedziny,
• surjekcje często są nazywane funkcjami "na",
• piszemy też wtedy $f:X\twoheadrightarrow Y$.

Rysunek: Rys. 2.1 Szkic na kartce.

Przykład

Funkcja $\mathbb{ℝ}\ni x\mapsto x^3\in \mathbb{ℝ}$ jest surjekcją.
Funkcja $\mathbb{\mathbb{Q}}\ni x\mapsto x^3\in \mathbb{\mathbb{Q}}$ nie jest surjekcją.
Funkcja $\mathbb{\mathbb{N}}\ni x\mapsto 2x\in \mathbb{\mathbb{N}}$ nie jest surjekcją.
Funkcja $\mathbb{\mathbb{Q}}\ni x\mapsto 2x\in \mathbb{\mathbb{Q}}$ jest surjekcją.
Funkcja $\mathbb{\mathbb{Z}}\ni x\mapsto \lfloor x\rfloor \in \mathbb{\mathbb{Z}}$ jest surjekcją.
Funkcja $\mathbb{ℝ}\ni x\mapsto \lfloor x\rfloor \in \mathbb{\mathbb{Z}}$ jest surjekcją.
Funkcja $\mathbb{\mathbb{Z}}\ni x\mapsto \lfloor x\rfloor \in \mathbb{\mathbb{Q}}$ nie jest suriekcją.
Funkcja $\mathbb{ℝ}\ni x\mapsto \sin x\in \mathbb{ℝ}$ nie jest surjekcją.
Funkcja ${\left\{0,1\right\}}^{*}\ni w\mapsto w1\in {\left\{0,1\right\}}^{*}$ nie jest suriekcją.
Funkcja ${\left\{0,1\right\}}^{*}\ni w\mapsto d(w)\in \mathbb{\mathbb{N}}$ jest suriekcją.

Injekcja to funkcja $f:X⟶Y$ spełniająca warunek:

$\mathrm{\forall }{x}_1,x_2\in X{x}_1\ne x_2\to f(x_1)\ne f(x_2)$

• Intuicyjnie, funkcja jest injekcją, jeśli różnym elementom dziedziny funkcja przyporządkowuje różne elementy przeciwdziedziny,
• injekcje często są nazywane funkcjami różnowartościowymi,
• piszemy też wtedy $f:X\hookrightarrow Y$.

Rysunek: Rys. 2.2 Szkic na kartce.

Przykład

Funkcja $\mathbb{ℝ}\ni x\mapsto x^3\in \mathbb{ℝ}$ jest injekcją.
Funkcja $\mathbb{ℝ}\ni x\mapsto x^2\in \mathbb{ℝ}$ nie jest injekcją.
Funkcja $\mathbb{\mathbb{Z}}\ni x\mapsto \lfloor x\rfloor \in \mathbb{\mathbb{Z}}$ jest injekcją.
Funkcja $\mathbb{ℝ}\ni x\mapsto \lfloor x\rfloor \in \mathbb{\mathbb{Z}}$ nie jest injekcją.
Funkcja $\mathbb{\mathbb{N}}\ni x\mapsto 2x\in \mathbb{\mathbb{N}}$ jest injekcją.
Funkcja $\mathbb{\mathbb{Q}}\ni x\mapsto 2x\in \mathbb{\mathbb{Q}}$ jest injekcją.
Funkcja $\mathbb{ℝ}\ni x\mapsto \sin x\in \mathbb{ℝ}$ nie jest injekcją.
Funkcja ${\left\{0,1\right\}}^{*}\ni w\mapsto w1\in {\left\{0,1\right\}}^{*}$ jest injekcją.
Funkcja ${\left\{0,1\right\}}^{*}\ni w\mapsto d(w)\in \mathbb{\mathbb{N}}$ nie jest injekcją.

Bijekcja to funkcja, która jest jednocześnie surjekcją i injekcją.

Rysunek: Rys. 2.3 Szkic na kartce.

Przykład

Funkcja $\mathbb{ℝ}\ni x\mapsto x^3\in \mathbb{ℝ}$ jest bijekcją.
Funkcja $\mathbb{\mathbb{Q}}\ni x\mapsto x^3\in \mathbb{\mathbb{Q}}$ nie jest bijekcją.
Funkcja $\mathbb{\mathbb{N}}\ni x\mapsto 2x\in \mathbb{\mathbb{N}}$ nie jest bijekcją.
Funkcja $\mathbb{\mathbb{Q}}\ni x\mapsto 2x\in \mathbb{\mathbb{Q}}$ jest bijekcją.
Funkcja $\mathbb{\mathbb{Z}}\ni x\mapsto \lfloor x\rfloor \in \mathbb{\mathbb{Z}}$ jest bijekcją.
Funkcja $\mathbb{ℝ}\ni x\mapsto \lfloor x\rfloor \in \mathbb{\mathbb{Z}}$ nie jest bijekcją.
Funkcja $\mathbb{\mathbb{Z}}\ni x\mapsto \lfloor x\rfloor \in \mathbb{\mathbb{Q}}$ nie jest bijekcją.
Funkcja ${\left\{0,1\right\}}^{*}\ni w\mapsto w1\in {\left\{0,1\right\}}^{*}$ nie jest bijekcją.
Funkcja ${\left\{0,1\right\}}^{*}\ni w\mapsto d(w)\in \mathbb{\mathbb{N}}$ nie jest bijekcją.

Funkcje odwrotne

Traktując funkcję $f:X⟶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ą?

• ponieważ $f^{-1}$ ma spełniać warunek, że każdy element dziedziny $f^{-1}$ (tzn. zbioru $Y$) ma przypisaną jakąś wartość, oznacza to, że sama funkcja $f$ wyczerpuje wszystkie elementy przeciwdziedziny, a zatem, że $f$ jest surjekcją,
• nadto $f^{-1}$ ma przypisywać dokładnie jeden taki element, czyli że każdy element z $Y$ jest przypisany poprzez $f$ jednemu elementowi z $X$, a zatem $f$ musi być injekcją.

A zatem: funkcja posiada funkcję odwrotną, wtedy i tylko wtedy, gdy jest bijekcją.

• Nieformalnie tworzenie funkcji odwrotnej polega na odwracaniu strzałek.
• Gdyby $f$ nie była surjekcją, to przy próbie odwrócenia strzałek niektóre elementy zbioru $Y$

nie miałyby przyporządkowanego żadnego elementu z $X$.

• Gdyby zaś $f$ nie była injekcją, to przy próbie odwrócenia strzałek niektóre strzałki byłyby "rozdwojone".

Przykład

• Funkcja $f:\mathbb{ℝ}\ni x\mapsto 2x\in \mathbb{ℝ}$ jest bijekcją,

a zatem posiada funkcję odwrotną. Tę funkcję odwrotną można wyliczyć: skoro $y=f(x)=2x$, to $f^{-1}(y)=x=y/2$. Zatem $f^{-1}:\mathbb{ℝ}\ni x\mapsto x/2\in \mathbb{ℝ}$.

• Funkcja $\mathbb{ℝ}\ni x\mapsto \lfloor x\rfloor \in \mathbb{\mathbb{Z}}$ nie jest injekcją. Nie posiada więc funkcji odwrotnej.
• Funkcja $\mathbb{\mathbb{N}}\ni x\mapsto 2x\in \mathbb{\mathbb{N}}$ nie jest surjekcją. Nie posiada więc funkcji odwrotnej. Ale rozważając tę funkcję z przeciwdziedziną $\mathbb{\mathbb{P}}$ będącą zbiorem liczb parzystych, tzn. $\mathbb{\mathbb{N}}\ni x\mapsto 2x\in \mathbb{\mathbb{P}}$ staje się ona bijekcją i posiada funkcję odwrotną $\mathbb{\mathbb{P}}\ni x\mapsto x/2\in \mathbb{\mathbb{N}}$.
• Funkcja $\mathbb{ℝ}\ni x\mapsto x^2\in \mathbb{ℝ}$ nie jest ani injekcją ani surjekcją. Nie posiada więc funkcji odwrotnej. Surjektywność można by "uratować", rozważając $f:\mathbb{ℝ}\ni x\mapsto x^2\in [0,+\mathrm{\infty }).$ Wciąż jednak brakowałoby injektywności.

Ograniczając jednak, tę funkcję do liczb nieujemnych, tzn. traktując ją jako:

$f{|}_{[0,+\mathrm{\infty })}:[0,+\mathrm{\infty })\ni x\mapsto x^2\in [0,+\mathrm{\infty }),$

staje się już bijekcją, więc posiada funkcję odwrotną, którą jest

$[0,+\mathrm{\infty })\ni x\mapsto \sqrt{x}\in [0,+\mathrm{\infty }).$

Składanie funkcji

Złożenie funkcji $f:X⟶Y$ i funkcji $g:Y⟶Z$ to funkcja

$gf:X⟶Z$

określona dla wszystkich argumentów $x\in X$ jako $(gf)(x)=g(f(x))$.

• Nieformalnie -- najpierw obliczamy wartość funkcji $f$ dla elementu $x$,
  a następnie obliczamy wartość funkcji $g$ dla wyniku tego obliczenia;
  czyli "idziemy dalej wzdłuż następnej strzałki" $X⟶Y⟶Z$
• Piszemy $gf$ (a nie $fg$) na oznaczenie złożenia, w którym najpierw obliczana jest wartość funkcji $f$, a potem funkcji $g$.
• W praktyce, przy złożeniu $gf$, dziedzina funkcji $g$ nie musi być tym samym zbiorem, co przeciwdziedzina funkcji $f$ -- wystarczy, by była większa.

Przykład

• Niech $f:\mathbb{\mathbb{N}}\ni n\mapsto n+2\in \mathbb{\mathbb{N}}$ i $g:\mathbb{\mathbb{N}}\ni n\mapsto 3n\in \mathbb{\mathbb{N}}$.

Wówczas dla $gf:\mathbb{\mathbb{N}}⟶\mathbb{\mathbb{N}}$ mamy $(gf)(n)=g(f(n))=g(n+2)=3(n+2)=3n+6$ a dla $fg:\mathbb{\mathbb{N}}⟶\mathbb{\mathbb{N}}$ mamy $(fg)(n)=f(g(n))=f(3n)=3n+2$.
Morał: złożenia $fg$ i $gf$ to (na ogół) różne funkcje.

• Niech $f:\mathbb{ℝ}\ni x\mapsto \sin 3x\in \mathbb{ℝ}$

i $g:\mathbb{ℝ}\ni x\mapsto (x+\pi {)}^2\in \mathbb{ℝ}$. Wówczas złożenie $fg:\mathbb{ℝ}⟶\mathbb{ℝ}$ dane jest wzorem

$(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ą.

• Gdy $f:X⟶Y$ jest bijekcją,

to istnieje funkcja odwrotna $f^{-1}:Y⟶X$. Jeśli złożymy $f^{-1}f$, to uzyskamy funkcję $X⟶X$, która "nic nie robi":

$(f^{-1}f)(x)=f^{-1}(f(x))=x.$

Taka funkcja zwana jest identycznością na zbiorze $X$ i oznaczana $i{d}_X$.
Podobnie -- składając $f{f}^{-1}:Y⟶Y$, otrzymamy identyczność na zbiorze $Y$.

Widzieliśmy, że nie zawsze $fg=gf$.

Obserwacja

Dla funkcji $X\stackrel{h}{⟶}Y\stackrel{g}{⟶}Z\stackrel{f}{⟶}W$ zachodzi $f(gh)=(fg)h$.

Obserwacja

Nadto dla $X\stackrel{f}{⟶}Y\stackrel{g}{⟶}Z$ mamy:

• Jeśli $f,g$ są surjekcjami, to $gf$ jest surjekcją.
• Jeśli $f,g$ są injekcjami, to $gf$ jest injekcją.
• Jeśli $f,g$ są bijekcjami, to $gf$ jest bijekcją.

Pierwsza i trzecia z powyższych własności nie zachodzą, jeśli dziedzina funkcji $g$ jest większa niż przeciwdziedzina funkcji $f$.

Przykład

Zbadaj czy dla funkcji $X\stackrel{f}{⟶}Y\stackrel{g}{⟶}Z$ zachodzi:

• jeśli $gf$ jest surjekcją, to $f$ jest surjekcją
• jeśli $gf$ jest surjekcją, to $g$ jest surjekcją
• jeśli $gf$ jest injekcją, to $f$ jest injekcją
• jeśli $gf$ jest injekcją, to $g$ jest injekcją

Funkcje wielu zmiennych

• Funkcja dwóch zmiennych to funkcja, której dziedziną jest zbiór par (zamiast pojedynczych elementów).
• Piszemy np. $f:X\times Y⟶Z$.
• Zatem funkcja taka każdej parze $(x,y)\in X\times Y$ przyporządkowuje dokładnie jeden element $f(x,y)\in Z$.
• Podobnie można zdefiniować funkcje trzech i więcej zmiennych.

Przykład

Przykładem funkcji dwóch zmiennych są działania arytmetyczne:

• $\mathbb{ℝ}\times \mathbb{ℝ}\ni (x,y)\mapsto x+y\in \mathbb{ℝ}$
• $\mathbb{ℝ}\times \mathbb{ℝ}\ni (x,y)\mapsto x-y\in \mathbb{ℝ}$
• $\mathbb{ℝ}\times \mathbb{ℝ}\ni (x,y)\mapsto xy\in \mathbb{ℝ}$
• $\mathbb{ℝ}\times \mathbb{ℝ}-\left\{0\right\}\ni (x,y)\mapsto \frac{x}{y}\in \mathbb{ℝ}$
• $\mathbb{\mathbb{N}}\times \mathbb{\mathbb{N}}\ni (x,y)\mapsto x^y\in \mathbb{\mathbb{N}}$

a także konkatenacja (sklejenie) słów

• $X^{*}\times X^{*}\ni (v,w)\mapsto vw\in X^{*}$,

gdzie $vw$ oznacza słowo (krotkę) powstałe z doklejenia słowa $w$ na końcu słowa $v$.

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.

Rysunek: 2.4 Zdjęcie samochodów na parkingu. Samochody są ponumerowane liczbami tak jakby ktoś je zliczał.

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned \mathbb{Z}_0&=&\emptyset,\\ \mathbb{Z}_1&=&{\left\{ {0} \right\}\ },\\ \mathbb{Z}_2&=&{\left\{ {0,1} \right\}\ },\\ &\vdots&\\ \mathbb{Z}_k&=&{\left\{ {0,\ldots,k-1} \right\}\ }. \endaligned}

Załóżmy, że na parkingu stoi $n$ samochodów. Zliczając je wybieramy elementy ${\mathbb{\mathbb{Z}}}_n$ (zazwyczaj kolejne liczby) i przypisujemy je do samochodów na parkingu. Uwaga: wybierając liczby z ${\mathbb{\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{\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

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

Dowód

Niech $S$ będzie zbiorem liczb naturalnych $n$ takich, że istnieje injekcja postaci $f:{\mathbb{\mathbb{Z}}}_m\to {\mathbb{\mathbb{Z}}}_n$, przy pewnym $m<n$. Oczywiście $0\notin S$, bo nie istnieje liczba naturalna $m$ taka, że $0\le m<0$. Także $1\notin S$, bo nie istnieje funkcja z niepustego zbioru ${\mathbb{\mathbb{Z}}}_1$ w pusty ${\mathbb{\mathbb{Z}}}_0$. Dla dowodu niewprost załóżmy, że $S$ jest niepusty. Wtedy, z Zasady Minimum, $S$ ma element najmniejszy, powiedzmy $n_0>1$. Istnieje zatem $m<n_0$ i injekcja $f:{\mathbb{\mathbb{Z}}}_{n_0}\to {\mathbb{\mathbb{Z}}}_m$. Analogicznie jak wcześniej $m\ne 0$ oraz $m\ne 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(\left\{0,\dots ,n_0-2\right\})$, to restrykcja $f{|}_{{\mathbb{\mathbb{Z}}}_{n_0-1}}$ jest injekcją z ${\mathbb{\mathbb{Z}}}_{n_0-1}$ w ${\mathbb{\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(\left\{0,\dots ,n_0-2\right\})$, to niech $a$ i $b$ będą takimi liczbami, że $f(a)=m-1$ i $f(n_0-1)=b$.

Rysunek: Rys 2.5 Szkic na kartce.

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

Parser nie mógł rozpoznać (nieznana funkcja „\begin{array}”): {\displaystyle g(x)= \left\{ \begin{array} {cl} f(x),& \textrm{dla } x\neq a \\ b,& \textrm{dla } x=aParser nie mógł rozpoznać (błąd składni): {\displaystyle } \end{array} \right. }

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

Wniosek

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

Zbiór skończony to zbiór bijektywny z pewnym zbiorem postaci ${\mathbb{\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 Uzupelnic bijekcja Nm Nm| gwarantuje nam, że $X$ jest bijektywny z dokładnie jednym zbiorem postaci ${\mathbb{\mathbb{Z}}}_n$. Rozważając skończony zbiór $n$-elementowy $X$, często używamy notacji $X=\left\{x_0,x_1,\dots ,x_{n-1}\right\}$ ukrywającej w sobie bijekcję postaci ${\mathbb{\mathbb{Z}}}_n⟶X$.

Liczba elementów skończonego zbioru $X$, to jedyna liczba naturalna $n$ taka, że istnieje bijekcja z ${\mathbb{\mathbb{Z}}}_n$ w $X$. Liczbę te oznaczamy przez Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vertX\right\vert} .

Przykład

Oczywiście $\left|{\mathbb{\mathbb{Z}}}_n\right|=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{\mathbb{P}}$ jest nieskończony.

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

Obserwacja

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

Dowód

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

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

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

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

Zbiór przeliczalny to zbiór skończony lub bijektywny z $\mathbb{\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{\mathbb{N}}⟶\mathbb{\mathbb{P}}$
• zbiór liczb całkowitych jest przeliczalny, bo $f(x)=\{\begin{array}{cl}\frac{x}{2},& \text{<mrow data-mjx-texclass="ORD">dlaparzystych</mrow>}x,\\ \frac{-1-x}{2},& \text{<mrow data-mjx-texclass="ORD">dlanieparzystych</mrow>}x,\end{array}$

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

Zasada Szufladkowa

Wróćmy jeszcze do Obserwacji Uzupelnic obserwacja - nie ma injekcji z m do n| -- 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

[Zasada Szufladkowa Dirichleta] Jeśli $n$ obiektów jest rozmieszczonych w $m$ szufladach i $n>m$, to istnieje szuflada z przynajmniej dwoma obiektami.

Rysunek: Rys. 2.6 Szkic i omówienie na kartce.

Dowód

Zbiór obiektów jest bijektywny ze zbiorem ${\mathbb{\mathbb{Z}}}_n$, zaś zbiór szuflad z ${\mathbb{\mathbb{Z}}}_m$. Rozmieszczenie obiektów w szufladach to określenie funkcji z ${\mathbb{\mathbb{Z}}}_n$ w ${\mathbb{\mathbb{Z}}}_m$. Ponieważ $n>m$ to Obserwacja Uzupelnic obserwacja - nie ma injekcji z m do n| 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 $500000$, natomiast liczba mieszkańców Krakowa przekracza $800000$. Weźmy $500000$ szufladek ponumerowanych kolejnymi liczbami naturalnymi od $0$ do $499999$ 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 $800000$, a szufladek $500000$, 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,\dots ,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,\dots ,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:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle xRy \ \ \Leftrightarrow \ \ \mbox{iloraz } {x}{y}Parser nie mógł rozpoznać (błąd składni): {\displaystyle jest potęgą (być może ujemną) liczby } 2Parser nie mógł rozpoznać (błąd składni): {\displaystyle .} }

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 $\left\{1,2,3,\dots ,2n\right\}$?
  

Co najwyżej $n$, gdyż tyle może być liczb nieparzystych w zbiorze $\left\{1,2,...,2n\right\}$.

• 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,\dots ,a_{10}$ spośród $1,2,3,\dots ,100$. Pokażemy, że w zbiorze $\left\{a_1,a_2,\dots ,a_{10}\right\}$ 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 $\left\{1,2,3,\dots ,100\right\}$.
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,\dots ,955$

• z drugiej strony $10$-cio elementowy zbiór $\left\{a_1,a_2,\dots ,a_{10}\right\}$

ma $2^{10}=1024$ podzbiory, więc muszą być dwa podzbiory zbioru $\left\{a_1,a_2,\dots ,a_{10}\right\}$ 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.

Zasady zliczania

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{\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.

Zasada dodawania

Dla skończonych i rozłącznych zbiorów $A$ i $B$ mamy:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vertA\cup B\right\vert=\left\vertA\right\vert+\left\vertB\right\vert. }

Dowód

Niech liczności zbiorów Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vertA\right\vert=m} , Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vertB\right\vert=n} będą poświadczone bijekcjami $f:{\mathbb{\mathbb{Z}}}_m\to A$ i $g:{\mathbb{\mathbb{Z}}}_n\to B$. Wtedy funkcja $h:{\mathbb{\mathbb{Z}}}_{m+n}\to A\cup B$ zadana przez:

$h(x)=\{\begin{array}{ll}f(x),& \text{<mrow data-mjx-texclass="ORD">dla</mrow>}x\in \left\{0,\dots ,m-1\right\}\\ g(x-m),& \text{<mrow data-mjx-texclass="ORD">dla</mrow>}x\in \left\{m,\dots ,m+n-1\right\}\end{array}$

jest bijekcją. Istotnie, skoro zbiory $A$ i $B$ są rozłączne, to dla dowolnych $x_1\in \left\{0,\dots ,m-1\right\}$, $x_2\in \left\{m,\dots ,m+n-1\right\}$ zachodzi $h(x_1)\ne h(x_2)$. Ponadto restrykcje $h$ do zbiorów zbiorów $\left\{0,\dots ,m-1\right\}$ i $\left\{m,\dots ,m+n-1\right\}$ 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{\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

Dla zbiorów $A_1,\dots ,A_n$ skończonych i parami rozłącznych:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vertA_1\cup\ldots\cup A_n\right\vert=\left\vertA_1\right\vert+\ldots+\left\vertA_n\right\vert. }

Więcej pracy wymaga analiza sytuacji, gdy zbiory $A,B$ nie są rozłączne.

Zasada włączania i wyłączania

Dla zbiorów skończonych $\left\{A_1,A_2,\dots ,A_n\right\}$ zachodzi

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned &&\left\vertA_1\cup A_2\cup\ldots\cup A_n\right\vert\ =\ \sum_{I\subseteq{\left\{ {1,\ldots,n} \right\}\ }}\left(-1\right)^{\left\vertI\right\vert+1}\left\vert\bigcap_{i\in I}A_i\right\vert\\ &&\begin{array} {lr} = \left\vertA_1\right\vert+\left\vertA_2\right\vert+\left\vertA_3\right\vert+\ldots\quad&+\left\vertA_{n-2}\right\vert+\left\vertA_{n-1}\right\vert+\left\vertA_n\right\vert\\ -\left\vertA_1\cap A_2\right\vert-\left\vertA_1\cap A_3\right\vert-\ldots&-\left\vertA_{n-2}\cap A_n\right\vert-\left\vertA_{n-1}\cap A_n\right\vert\\ +\left\vertA_1\cap A_2 \cap A_3\right\vert+\ldots&+\left\vertA_{n-2}\cap A_{n-1} \cap A_n\right\vert\\ -\left\vertA_1\cap A_2 \cap A_3\cap A_4\right\vert-\ldots&-\left\vertA_{n-3}\cap A_{n-2}\cap A_{n-1} \cap A_n\right\vert\\ +\ldots&\\ \left(-1\right)^{n+1}\left\vertA_1\cap A_2\cap\ldots\cap A_n\right\vert& \end{array} \endaligned}

W szczególności, Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vertA\cup B\right\vert=\left\vertA\right\vert+\left\vertB\right\vert-\left\vertA\cap B\right\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 Uzupelnic wniosek - moc sumy wielu zbiorow| mamy:

$|A\cup B|=|(A-B)\cup (A\cap B)\cup (B-A)|=|A-B|+|A\cap B|+|B-A|$

skąd

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned |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| \endaligned}

skąd już natychmiast dostajemy:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vertA\cup B\right\vert=\left\vertA\right\vert+\left\vertB\right\vert-\left\vertA\cap B\right\vert. }

W sytuacji dowolnie wielu $n$ zbiorów użyjemy rozumowania indukcyjnego. Oczywiście $n=1,2$ twierdzenie jest prawdziwe. Załóżmy, że $n>2$. Na mocy równości (Uzupelnic suma-zb|) otrzymujemy:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vert\bigcup_{k=1}^nA_k\right\vert\ =\ \left\vert\bigcup_{k=1}^{n-1}A_k\right\vert+\left\vertA_n\right\vert-\left\vert\bigcup_{k=1}^{n-1}A_k\cap A_n\right\vert. }

Wykorzystując założenie indukcyjne dla wartości $n-1$ zachodzi

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \aligned \left\vert\bigcup_{k=1}^nA_k\right\vert&=&\sum_{I\subseteq{\left\{ {1,\ldots,n-1} \right\}\ }}\left(-1\right)^{\left\vertI\right\vert+1}\left\vert\bigcap_{i\in I}A_i\right\vert+\left\vertA_n\right\vert-\sum_{I\subseteq{\left\{ {1,\ldots,n-1} \right\}\ }}\left(-1\right)^{\left\vertI\right\vert+1}\left\vert\bigcap_{i\in I}A_i\cap A_n\right\vert\\ &=&\sum_{I\subseteq{\left\{ {1,\ldots,n-1} \right\}\ }}\left(-1\right)^{\left\vertI\right\vert+1}\left\vert\bigcap_{i\in I}A_i\right\vert+\sum_{I\subseteq{\left\{ {1,\ldots,n-1} \right\}\ }}\left(-1\right)^{\left\vertI\cup{\left\{ {n} \right\}\ }\right\vert+1}\left\vert\bigcap_{i\in I\cup{\left\{ {n} \right\}\ }}A_i\right\vert. \endaligned}

Rodzina wszystkich podzbiorów $I$ zbioru liczb $\left\{1,\dots ,n\right\}$ można podzielić na dwie rozłączne rodziny:

• pierwsza składa się z tych $I$, które nie zawierają $n$, czyli

$\left\{I:I\subseteq \left\{1,\dots ,n-1\right\}\right\},$

• druga jest rodziną tych $I$, które zawierają $n$, czyli

$\left\{I\cup \left\{n\right\}:I\subseteq \left\{1,\dots ,n-1\right\}\right\}$.

W rezultacie otrzymujemy, że

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vert\bigcup_{k=1}^nA_k\right\vert\ =\ \sum_{I\subseteq{\left\{ {1,\ldots,n} \right\}\ }}\left(-1\right)^{\left\vertI\right\vert+1}\left\vert\bigcap_{i\in I}A_i\right\vert, }

co kończy dowód.

Wniosek Uzupelnic wniosek - moc sumy wielu zbiorow| 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vertA_1\cup\ldots\cup A_n\right\vert=\left\vertA_1\right\vert\cup\ldots\cup\left\vertA_n\right\vert} . Zatem jeśli każda szufladka ma co najwyżej $r$ obiektów, to w sumie jest co najwyżej $nr$ obiektów.

Uogólniona Zasada Szufladkowa

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=\left\{(x,y):x\in X,y\in Y\right\}.$

Zasada Mnożenia

Dla skończonych zbiorów $X,Y$:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vertX\times Y\right\vert=\left\vertX\right\vert\cdot\left\vertY\right\vert. }

Dowód

Najpierw pokażemy, że $|{\mathbb{\mathbb{Z}}}_m\times {\mathbb{\mathbb{Z}}}_n|=m\cdot n$. W tym celu pokażemy, że funkcja

$f:{\mathbb{\mathbb{Z}}}_m\times {\mathbb{\mathbb{Z}}}_n\ni (i,j)\mapsto in+j\in {\mathbb{\mathbb{Z}}}_{mn}$

jest bijekcją.

Dla dowodu injektywności załóżmy, że $f(i,j)=f(i^{\prime },j^{\prime })$, czyli $in+j=i^{\prime }n+j^{\prime }$. Bez straty ogólności możemy założyć, że $i\le i^{\prime }$, wtedy $(i^{\prime }-i)n=j-j^{\prime }$. Lewa strona równości jest wielokrotnością $n$, zaś prawa leży w zbiorze $\left\{-n+1,\dots ,n-1\right\}$, gdyż $j,j^{\prime }\in {\mathbb{\mathbb{Z}}}_n$. Ponieważ $0$ jest jedyną wielokrotnością liczby $n$ w tym zbiorze, to $i^{\prime }-i=0$ i $j-j^{\prime }=0$, co dowodzi injektywności $f$.

Dla dowodu surjektywności rozważmy $y\in {\mathbb{\mathbb{Z}}}_{mn}$. Niech $i$ będzie największą liczbą taką, że $in\le y$. Wtedy $y<(i+1)n$ zatem istnieje $j\in \left\{0,\dots ,n-1\right\}$ takie, że $y=in+j=f(i,j)$, co było do udowodnienia.

Załóżmy teraz, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vertX\right\vert=m} i Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vertY\right\vert=n} . Wtedy, z poczynionej wyżej obserwacji, dowód Zasady Mnożenia jest natychmiastowy, gdyż

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vertX\times Y\right\vert=\left\vert\mathbb{Z}_m\times \mathbb{Z}_n\right\vert=m\cdot n=\left\vertX\right\vert\cdot\left\vertY\right\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ą?

• Niech $C$ i $N$ będą zbiorami rycerzy, odpowiednio

z bractwa czerwonych i z bractwa niebieskich,

• każdy pojedynek może być interpretowany jako uporządkowana para $(c,n)$,

gdzie $c\in C$, $n\in N$. Zatem liczba pojedynków to liczność zbioru $C\times N$.

• Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vertC\times N\right\vert=\left\vertC\right\vert\cdot\left\vertN\right\vert=12\cdot15=300} .

Zliczanie podzbiorów

Zbiór potegowy, lub inaczej zbiór podzbiorów, zbioru $X$ oznaczamy przez ${𝒫}(X)$.

Przykład

• ${𝒫}(\mathrm{\varnothing })=\left\{\mathrm{\varnothing }\right\}$ i $|{𝒫}(\mathrm{\varnothing })|=1$

• ${𝒫}(\left\{\mathrm{\varnothing }\right\})=\left\{\mathrm{\varnothing },\left\{\mathrm{\varnothing }\right\}\right\}$ i $|{𝒫}(\left\{\mathrm{\varnothing }\right\})|=2$

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 $\left\{a,b\right\}$ ma następujące cztery podzbiory:

$\mathrm{\varnothing },\left\{a\right\},\left\{b\right\},\left\{a,b\right\}$

a zbiór trzyelementowy $\left\{a,b,c\right\}$ ma osiem podzbiorów:

$\mathrm{\varnothing },\left\{a\right\},\left\{b\right\},\left\{c\right\},\left\{a,b\right\},\left\{a,c\right\},\left\{b,c\right\},\left\{a,b,c\right\}$

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:

{

Obserwacja

Dla dowolnego, skończonego zbioru $X$

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vert\mathcal{P}(X)\right\vert=2^{\left\vertX\right\vert}. }

Zliczanie funkcji

Zbiór funkcji postaci $X⟶Y$ oznaczamy przez $Y^X$.

Obserwacja

Dla skończonych zbiorów $X,Y$ mamy:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vertY^X\right\vert=\left\vertY\right\vert^{\left\vertX\right\vert}. }

Dowód

Niech $X=\left\{x_0,\dots ,x_{m-1}\right\}$ oraz $Y=\left\{y_0,\dots ,y_{n-1}\right\}$. Każda funkcja $f:X⟶Y$ to krotka wartości dla kolejnych $x_i$:

$(f(x_0),f(x_1),\dots ,f(x_{m-1}))\in \underset{mrazy}{\underbrace{Y\times \dots \times Y}}.$

A więc zbiór funkcji z $X$ w $Y$ jest równoliczny z $Y^m$. Z Zasady Mnożenia otrzymujemy więc:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \vert\underbrace{Y\times\ldots\times Y}_{m\ razy}\vert =\underbrace{\left\vertY\right\vert\times\ldots\times\left\vertY\right\vert}_{m\ razy} =n^m= \left\vertY\right\vert^{\left\vertX\right\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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle {\left\{ {\textrm{Bartek},\textrm{Paweł},\textrm{Piotrek}} \right\}\ }} 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 $\left\{0,1,2,3\right\}$ w dziesięcioelementowy zbiór cyfr $\left\{0,1,\dots ,9\right\}$. Z Obserwacji Uzupelnic obserwacja - zliczanie funkcji| wynika że kodów PIN jest dokładnie $10^4=10000.$

Posługując się Obserwacją Uzupelnic obserwacja - zliczanie funkcji| udowodnimy jeszcze raz wzór na ilość podzbiorów skończonego zbioru. Zatem Obserwację Uzupelnic obserwacja - zliczanie funkcji| możemy traktować jako uogólnienie Obserwacji Uzupelnic obserwacja - liczba podzbiorów|.

Dowód

{Alternatywny dowód Obserwacji Uzupelnic obserwacja - liczba podzbiorów|.}
Zauważmy, że dowolny podzbiór $A\subseteq X$ wyznacza jednoznacznie funkcję ${\chi }_A:X\to {\mathbb{\mathbb{Z}}}_2$ w następujący sposób:

${\chi }_Y(x)=\{\begin{array}{cl}0,& \text{<mrow data-mjx-texclass="ORD">dla</mrow>}x\in X-A\\ 1,& \text{<mrow data-mjx-texclass="ORD">dla</mrow>}x\in A\end{array}$

Również każda funkcja $f:X⟶{\mathbb{\mathbb{Z}}}_2$ wyznacza jednoznacznie podzbiór $A_f\left\{x\in X:f(x)=1\right\}$ zbioru $X$. Nadto, odpowiedniość

${𝒫}(X)\ni A\mapsto {\chi }_A\in {\mathbb{\mathbb{Z}}}_2^X$

jest bijektywna. Zatem Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vert\mathcal{P}(X)\right\vert=\left\vert\mathbb{Z}_2^X\right\vert =2^{\left\vertX\right\vert}} .

Obserwacja

Liczba injekcji ze zbioru skończonego $X$ w zbiór skończony $Y$ wynosi:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vertY\right\vert(\left\vertY\right\vert-1)\cdot\ldots\cdot(\left\vertY\right\vert-\left\vertX\right\vert+1)= \frac{\left\vertY\right\vert!}{(\left\vertY\right\vert-\left\vertX\right\vert)!}. }

Dowód

Niech $X=\left\{x_0,\dots ,x_{m-1}\right\}$ i $Y=\left\{y_0,\dots ,y_{n-1}\right\}$. 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),\dots ,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 \dots \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 $\left\{0,1,2,3\right\}$ w $10$-elementowy zbiór cyfr $\left\{0,1,\dots ,9\right\}$. Zatem jest ich dokładnie $10\cdot 9\cdot 8\cdot 7=5040$.

Obserwacja

Liczba bijekcji pomiędzy skończonymi zbiorami $X$ i $Y$, gdzie Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vertX\right\vert=\left\vertY\right\vert} wynosi Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vertX\right\vert!. }

Dowód

Pokażemy najpierw, że każda injekcja $f:X⟶Y$ jest bijekcją. Istotnie, gdyby $f$ nie było surjekcją, to $f(X)$ byłoby właściwym podzbiorem zbioru $Y$. A zatem Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vertf(X)\right\vert < \left\vertY\right\vert} i funkcja $f:X⟶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 Uzupelnic obserwacja - nie ma injekcji z m do n|. Udowodniliśmy, że liczba bijekcji z $X$ w $Y$ równa jest liczbie injekcji z $X$ w $Y$, czyli, z Obserwacji Uzupelnic obserwacja - zliczanie injekcji|), wynosi ona:

$n(n-1)\cdot \dots \cdot (n-n+2)(n-n+1)=n!.$

Zauważmy jeszcze, że $\mathrm{\varnothing }\subseteq \mathrm{\varnothing }\times \mathrm{\varnothing }$ jest nie tylko funkcją $\mathrm{\varnothing }:\mathrm{\varnothing }⟶\mathrm{\varnothing }$, ale i bijekcją i jest to jedyna bijekcja $\mathrm{\varnothing }⟶\mathrm{\varnothing }$.

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\to D$. Zatem możliwych wyborów jest tyle samo co bijekcji pomiędzy $5$-elementowymi zbiorami, czyli $5!=5\cdot 4\cdot 3\cdot 2\cdot 1=120$.

Permutacje

Permutacja zbioru skończonego $X$ to bijekcja z $X$ w $X$.

Zbiór permutacji zbioru ${\mathbb{\mathbb{Z}}}_n$ oznaczamy przez $S_n$, a permutacje bedziemy w tym kursie oznaczać małymi literami greckimi.

Przykład

Rozważ funkcję $\alpha :{\mathbb{\mathbb{Z}}}_7\to {\mathbb{\mathbb{Z}}}_7$ zadaną przez poniższą tabelę:

$\begin{array}{cccccccc}n& 0& 1& 2& 3& 4& 5& 6\\ \alpha (n)& 2& 3& 6& 0& 4& 1& 5\end{array}$

Funkcja $\alpha$ jest bijekcją z ${\mathbb{\mathbb{Z}}}_7$ w ${\mathbb{\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}{cccccc}n& 0& 1& 2& 3& 4\\ \alpha (n)& 4& 2& 3& 0& 1\\ \beta (n)& 2& 3& 1& 4& 0\end{array}$

ich złożenia podane są poniżej:

$\begin{array}{cccccc}n& 0& 1& 2& 3& 4\\ \beta \alpha (n)& 0& 1& 4& 2& 3\\ \alpha \beta (n)& 3& 0& 2& 1& 4\end{array}$

Zauważ, że oba złożenia także są permutacjami ${\mathbb{\mathbb{Z}}}_5$.

Ponieważ permutacje są bijekcjami, to natychmiast z Obserwacji Uzupelnic obs-zlozenia| dostajemy:

Obserwacja

Dla dowolnych permutacji $\alpha ,\beta$ skończonego zbioru $X$:

• $\alpha \beta ,\beta \alpha$ są permutacjami $X$,

• ${\alpha }^{-1}$ jest permutacją $X$ taką,

że $\alpha {\alpha }^{-1}=i{d}_X={\alpha }^{-1}\alpha =$.

Następne spostrzeżenie jest natychmiastowym wnioskiem z Obserwacji Uzupelnic obserwacja - zliczanie bijekcji|.

Wniosek

Zbiór $n$-elementowy ma dokładnie $n!$ permutacji, Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\vertS_n\right\vert=n!} .

Przykład

Oto wszystkie ($3!=6$) permutacje zbioru $S_3$:

$\begin{array}{ccccccccccc}0& 1& 2& & 0& 1& 2& & 0& 1& 2\\ \downarrow & \downarrow & \downarrow & & \downarrow & \downarrow & \downarrow & & \downarrow & \downarrow & \downarrow \\ 0& 1& 2& & 0& 2& 1& & 1& 0& 2\\ \\ 0& 1& 2& & 0& 1& 2& & 0& 1& 2\\ \downarrow & \downarrow & \downarrow & & \downarrow & \downarrow & \downarrow & & \downarrow & \downarrow & \downarrow \\ 1& 0& 2& & 2& 0& 1& & 2& 1& 0\end{array}$

Permutację $\alpha$ zbioru $X=\left\{x_0,\dots ,x_{n-1}\right\}$ wygodnie jest identyfikować z krotką $(\alpha (x_0),\dots ,\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?

Rysunek: 2.7 Rysunek bądź zdjęcie siedmiu książek na półce.

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 $\left\{x,\alpha (x),{\alpha }^2(x),\dots ,{\alpha }^{n-1}(x)\right\}=X$, przy dowolnym $x\in X$. Łatwo zauważyć, że jeśli dla pewnego $x_0\in X$ mamy $\left\{x,\alpha (x),{\alpha }^2(x),\dots ,{\alpha }^{n-1}(x)\right\}=X$, to jest tak dla wszystkich $x\in X$, czyli $\alpha$ jest cyklem na $X$. Cykl $\alpha$ zbioru $X$ zapisujemy jako $(x,\alpha (x),\dots ,{\alpha }^{n-1}(x))$ dla dowolnie wybranego $x\in X$.

Przykład

Rozważmy $\alpha \in S_6$ daną przez

$\begin{array}{ccccccc}n& 0& 1& 2& 3& 4& 5\\ \alpha (n)& 3& 5& 0& 1& 2& 4\end{array}$

• sekwencja $0$, $\alpha (0)=3$, ${\alpha }^2(0)=1$, ${\alpha }^3(0)=5$, ${\alpha }^4(0)=4$, ${\alpha }^5(0)=2$ pokwywa całe ${\mathbb{\mathbb{Z}}}_6$,

• zatem $\alpha =(0,3,1,5,4,2)$ jest cyklem.

Rysunek: 2.8 Szkic na kartce.

1 {Rozkład permutacji na rozłączne cykle.}

Dowolną permutację $\alpha$ zbioru $X$ można rozłożyć na rozłączne cykle w sposób następujący:

1. wybierz dowolny element $x\in X$, który nie jest jeszcze w żadnym cyklu,

1. iteruj permutację $\alpha$ otrzymując kolejno:

$\alpha (x),{\alpha }^2(x),{\alpha }^3(x),\dots$ aż do uzyskania ${\alpha }^j(x)=x$,

1. dodaj do rozkładu cykl $x,\dots ,{\alpha }^{j-1}(x)$,

1. jeśli w zbiorze $X$ pozostały jeszcze elementy niepokryte przez żaden cykl,

to wróć do pierwszego punktu.

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)\dots$ 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\le i<j$. Gdyby $i\ne 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,\dots )(x_1,\dots )\dots (x_{k-1},\dots )$, gdzie w kolejnych nawiasach są elementy kolejnych cykli startujące od odpowiednio: $x_0,\dots ,x_{k-1}$.

#1

Przykład

Rozważmy jeszcze raz permutację $\alpha \in S_7$:

$\begin{array}{cccccccc}n& 0& 1& 2& 3& 4& 5& 6\\ \alpha (n)& 2& 3& 6& 0& 4& 1& 5\end{array}$

Rozkład $\alpha$ na cykle:

• $0$, $\alpha (0)=2$, $\alpha (2)=6$, $\alpha (6)=5$, $\alpha (5)=1$, $\alpha (1)=3$, $\alpha (3)=0$,

• $4$, $\alpha (4)=4$,

• $\alpha =(026513)(4)$.