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+\dots +(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$
• $d:{\left\{0,1\right\}}^{*}⟶\mathbb{\mathbb{N}},d(w)=$ długość słowa $w$

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

<div.thumbcaption>Przykład surjekcji

Surjekcja 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$.

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

Przykład injekcji

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

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

Przykład bijekcji

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

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 3.1

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

Obserwacja 3.2

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

Liczenie samochodów na parkingu

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{array}{rl}{\mathbb{\mathbb{Z}}}_0& =\mathrm{\varnothing },\\ {\mathbb{\mathbb{Z}}}_1& =\left\{0\right\},\\ {\mathbb{\mathbb{Z}}}_2& =\left\{0,1\right\},\\ & ⋮\\ {\mathbb{\mathbb{Z}}}_k& =\left\{0,\dots ,k-1\right\}.\end{array}$

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 3.3

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

SW 2.5.swf

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 math>n_0>1</math>. 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$.

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

$g(x)=\{\begin{array}{cl}f(x),& \text{dla}x\ne a\\ b,& \text{dla}x=a\end{array}$

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 3.4

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 3.4 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 $\left|X\right|$.

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 3.5

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ą 3.3.

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{dla parzystych }x,\\ \frac{-1-x}{2},& \text{dla nieparzystych }x,\end{array}$

jest bijekcją z $\mathbb{\mathbb{N}}$ w $\mathbb{\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{\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 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 $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:

$xRy\iff$ 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 $\left\{1,2,3,\dots ,2n\right\}$? Co najwyżej $n$, gdyż tyle może być liczb nieparzystych w zbiorze $\left\{1,2,\dots ,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:

$|A\cup B|=\left|A\right|+\left|B\right|$.

Dowód

Niech liczności zbiorów $\left|A\right|=m$, $\left|B\right|=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{dla }x\in \left\{0,\dots ,m-1\right\}\\ g(x-m),& \text{dla }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 3.7

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

$|A_1\cup \dots \cup A_n|=\left|A_1\right|+\dots +\left|A_n\right|$

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

$\begin{array}{rlr}& & |A_1\cup A_2\cup \dots \cup A_n|=\sum _{I\subseteq \left\{1,\dots ,n\right\}}{(-1)}^{\left|I\right|+1}\left|\bigcap _{i\in I}{A}_i\right|\\ & & \begin{array}{lr}=\left|A_1\right|+\left|A_2\right|+\left|A_3\right|+\dots & +\left|A_{n-2}\right|+\left|A_{n-1}\right|+\left|A_n\right|\\ -|A_1\cap A_2|-|A_1\cap A_3|-\dots & -|A_{n-2}\cap A_n|-|A_{n-1}\cap A_n|\\ +|A_1\cap A_2\cap A_3|+\dots & +|A_{n-2}\cap A_{n-1}\cap A_n|\\ -|A_1\cap A_2\cap A_3\cap A_4|-\dots & -|A_{n-3}\cap A_{n-2}\cap A_{n-1}\cap A_n|\\ +\dots & \\ {(-1)}^{n+1}|A_1\cap A_2\cap \dots \cap A_n|& \end{array}\end{array}$

W szczególności, $|A\cup B|=\left|A\right|+\left|B\right|-|A\cap B|$, 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{array}{rl}|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{array}$

skąd już natychmiast dostajemy:

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

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 (1) otrzymujemy:

$\begin{array}{r}\left|\bigcup _{k=1}^n{A}_k\right|=\left|\bigcup _{k=1}^{n-1}{A}_k\right|+\left|A_n\right|-|\bigcup _{k=1}^{n-1}{A}_k\cap A_n|.\end{array}$

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

$\begin{array}{rl}\left|\bigcup _{k=1}^n{A}_k\right|& =\sum _{I\subseteq \left\{1,\dots ,n-1\right\}}{(-1)}^{\left|I\right|+1}\left|\bigcap _{i\in I}{A}_i\right|+\left|A_n\right|-\sum _{I\subseteq \left\{1,\dots ,n-1\right\}}{(-1)}^{\left|I\right|+1}|\bigcap _{i\in I}{A}_i\cap A_n|\\ & =\sum _{I\subseteq \left\{1,\dots ,n-1\right\}}{(-1)}^{\left|I\right|+1}\left|\bigcap _{i\in I}{A}_i\right|+\sum _{I\subseteq \left\{1,\dots ,n-1\right\}}{(-1)}^{|I\cup \left\{n\right\}|+1}\left|\bigcap _{i\in I\cup \left\{n\right\}}{A}_i\right|.\end{array}$

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

$\begin{array}{r}\left|\bigcup _{k=1}^n{A}_k\right|=\sum _{I\subseteq \left\{1,\dots ,n\right\}}{(-1)}^{\left|I\right|+1}\left|\bigcap _{i\in I}{A}_i\right|,\end{array}$

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 $|A_1\cup \dots \cup A_n|=\left|A_1\right|\cup \dots \cup \left|A_n\right|$. 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$:

$|X\times Y|=\left|X\right|\cdot \left|Y\right|$

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 $\left|X\right|=m$ i $\left|Y\right|=n$. Wtedy, z poczynionej wyżej obserwacji, dowód Zasady Mnożenia jest natychmiastowy, gdyż

$|X\times Y|=|{\mathbb{\mathbb{Z}}}_m\times {\mathbb{\mathbb{Z}}}_n|=m\cdot n=\left|X\right|\cdot \left|Y\right|$

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$.
• $|C\times N|=\left|C\right|\cdot \left|N\right|=12\cdot 15=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:

$\begin{array}{cccccc}n& 0& 1& 2& 3& \dots \\ p_n& 1& 2& 4& 8& \dots \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^{\prime }$. Podobnie jak w dowodzie Zasady Włączania-Wyłączania, podzbiory zbioru $Z$ można podzielić na dwa typy:

• albo mają w sobie element $a$,
• albo go nie mają.

W drugim przypadku są to podzbiory zbioru $Z^{\prime }$. 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^{\prime }\cup \left\{a\right\}$ dla pewnego $A^{\prime }\subseteq Z^{\prime }$. A zatem podzbiorów zbioru $Z$, w których jest element $a$ jest też tyle ile podzbiorów zbioru $Z^{\prime }$, 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ę.

Obserwacja 3.8

Dla dowolnego, skończonego zbioru $X$

$|{𝒫}(X)|=2^{\left|X\right|}$

Zliczanie funkcji

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

Obserwacja 3.9

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

$\left|Y^X\right|={\left|Y\right|}^{\left|X\right|}$

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:

$|\underset{mrazy}{\underbrace{Y\times \dots \times Y}}|=\underset{mrazy}{\underbrace{\left|Y\right|\times \dots \times \left|Y\right|}}=n^m={\left|Y\right|}^{\left|X\right|}$

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 $\left\{\text{Bartek},\text{Paweł},\text{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 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\to {\mathbb{\mathbb{Z}}}_2$ w następujący sposób:

${\chi }_Y(x)=\{\begin{array}{cl}0,& \text{dla }x\in X-A\\ 1,& \text{dla }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 $|{𝒫}(X)|=\left|{\mathbb{\mathbb{Z}}}_2^X\right|=2^{\left|X\right|}$.

Obserwacja 3.10

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

$\left|Y\right|(\left|Y\right|-1)\cdot \dots \cdot (\left|Y\right|-\left|X\right|+1)=\frac{\left|Y\right|!}{(\left|Y\right|-\left|X\right|)!}$

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 3.11

Liczba bijekcji pomiędzy skończonymi zbiorami $X$ i $Y$, gdzie $\left|X\right|=\left|Y\right|$ wynosi $\left|X\right|!$.

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 $|f(X)|<\left|Y\right|$ 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 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 \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 3.2 dostajemy:

Obserwacja 3.12

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 3.11.

Wniosek 3.13

Zbiór $n$-elementowy ma dokładnie $n!$ permutacji, $\left|S_n\right|=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$.

7 książek

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

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,
2. iteruj permutację $\alpha$ otrzymując kolejno: $\alpha (x),{\alpha }^2(x),{\alpha }^3(x),\dots$ aż do uzyskania ${\alpha }^j(x)=x$,
3. dodaj do rozkładu cykl $x,\dots ,{\alpha }^{j-1}(x)$,
4. 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}$.

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)$.