Tekst źródłowy

==Funkcje==

Ten fragment wykładu przypomina poznany już wcześniej materiał.
Służy jedynie ustaleniu terminologii i notacji. 

{{kotwica|funkcja|'''Funkcja'''}} o dziedzinie <math>X</math> i przeciwdziedzinie <math>Y</math> to dowolna relacja <math>f \subseteq X \times Y</math> taka, że:
* <math>\forall x\in X \ \exists y \in Y \ \ \left\langle x,y \right\rangle\in f</math>

* <math>\forall x\in X \ \forall y_1,y_2\in Y \ \ \left(\left\langle x,y_1 \right\rangle\in f \wedge \left\langle x,y_2 \right\rangle\in f\right) \rightarrow y_1=y_2</math>

Pierwszy warunek mówi, że każdy element dziedziny ma jakąś wartość przypisaną funkcją <math>f</math>. 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


<center><math>\forall x\in X \ \exists! y \in Y \ \ \left\langle x,y \right\rangle\in f,
</math></center>


gdzie kwantyfikator <math>\exists!</math> 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 <math>f : X \longrightarrow Y</math> lub <math>X \stackrel{f}{\longrightarrow} Y</math> na oznaczenie funkcji o nazwie <math>f</math>, której dziedziną jest zbiór <math>X</math>, a przeciwdziedziną zbiór <math>Y</math>.
** elementy dziedziny nazywamy argumentami funkcji
** elementy przeciwdziedziny im przyporządkowane nazywamy wartościami funkcji.
* Piszemy <math>f(x) = y</math> lub <math>f : x \mapsto y</math> na oznaczenie tego, że funkcja <math>f</math> elementowi <math>x</math> przyporządkowuje element <math>y</math>
** mówimy wtedy, że <math>y</math> jest wartością funkcji <math>f</math> na argumencie <math>x</math>.
* Często podaje się ''przepis'' na funkcję, wykorzystując 
** operacje arytmetyczne:                <math>f(x) = 3x + 7</math>
** lub inne powszechnie znane funkcje    <math>g(x) = 2\sin(x)\cos(x)</math>. 
* 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. <math>f : \mathbb{R} \longrightarrow \mathbb{R}</math>.

====Przykłady funkcji====

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

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

{{kotwica|wielomian|'''Wielomian'''}} to funkcja:


<center><math>x \mapsto a_nx^n + a_{n-1}x^{n-1} + \ldots + a_2x^2 + a_1 x + a_0
</math></center>


gdzie
* liczby <math>a_n, a_{n-1}, \ldots, a_1,a_0</math> zwane są ''współczynnikami'' wielomianu
** mówimy więc o wielomianach o współczynnikach 
*** naturalnych - jeśli <math>a_n, a_{n-1}, \ldots, a_1,a_0 \in \mathbb{N}</math> 
*** całkowitych - jeśli <math>a_n, a_{n-1}, \ldots, a_1,a_0 \in \mathbb{Z}</math> 
*** wymiernych - jeśli <math>a_n, a_{n-1}, \ldots, a_1,a_0 \in \mathbb{Q}</math> 
*** rzeczywistych - jeśli <math>a_n, a_{n-1}, \ldots, a_1,a_0 \in \mathbb{R}</math>
** liczba <math>n</math> zwana jest stopniem wielomianu, ale tylko o ile <math>a_n \neq 0</math>.

===Surjekcje, injekcje i bijekcje===

<div class="thumb tright"><div style="width:250px;">
[[Grafika:Surjekcja.png]]
<div.thumbcaption>Przykład surjekcji</div>
</div></div>

{{kotwica|surjekcja|'''Surjekcja'''}} to funkcja  <math>f : X \longrightarrow Y</math> spełniająca warunek


<center>
<math>\forall y\in Y \ \exists x\in X \ \ f(x) = y
</math>
</center>


* 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 <math>f : X \twoheadrightarrow Y</math>.

{{przyklad|||
Funkcja <math>\mathbb{R} \ni x \mapsto x^3 \in \mathbb{R}</math> jest surjekcją.
<br>
Funkcja <math>\mathbb{Q} \ni x \mapsto x^3 \in \mathbb{Q}</math> nie jest surjekcją.
<br>
Funkcja <math>\mathbb{N} \ni x \mapsto 2x \in \mathbb{N}</math> nie jest surjekcją.
<br>
Funkcja <math>\mathbb{Q} \ni x \mapsto 2x \in \mathbb{Q}</math>  jest surjekcją.
<br>
Funkcja <math>\mathbb{Z} \ni x \mapsto \left\lfloor x\right\rfloor \in \mathbb{Z}</math>  jest surjekcją.
<br>
Funkcja <math>\mathbb{R} \ni x \mapsto \left\lfloor x\right\rfloor \in \mathbb{Z}</math>  jest surjekcją.
<br>
Funkcja <math>\mathbb{Z} \ni x \mapsto \left\lfloor x\right\rfloor \in \mathbb{Q}</math> nie jest suriekcją.
<br>
Funkcja <math>\mathbb{R} \ni x \mapsto \sin{x} \in \mathbb{R}</math> nie jest surjekcją.
<br>
Funkcja <math>{\left\{ {0,1} \right\}\ }^* \ni w \mapsto w1 \in {\left\{ {0,1} \right\}\ }^*</math> nie jest suriekcją.
<br>
Funkcja <math>{\left\{ {0,1} \right\}\ }^* \ni w \mapsto d(w) \in \mathbb{N}</math>  jest suriekcją.
}}

<div class="thumb tright"><div style="width:250px;">
<flash>file=SW_2.2.swf|width=250|height=200</flash>
<div.thumbcaption>Przykład injekcji</div>
</div></div>

{{kotwica|injekcja|'''Injekcja'''}} to funkcja  <math>f : X \longrightarrow Y</math> spełniająca warunek:


<center>
<math>\forall x_1,x_2 \in X \ \ x_1\neq x_2 \rightarrow f(x_1)\neq f(x_2)
</math>
</center>


* 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 <math>f : X \hookrightarrow Y</math>.

{{przyklad|||
Funkcja <math>\mathbb{R} \ni x \mapsto x^3 \in \mathbb{R}</math> jest injekcją.
<br>
Funkcja <math>\mathbb{R} \ni x \mapsto x^2 \in \mathbb{R}</math> nie jest injekcją.
<br>
Funkcja <math>\mathbb{Z} \ni x \mapsto \left\lfloor x\right\rfloor \in \mathbb{Z}</math>  jest injekcją.
<br>
Funkcja <math>\mathbb{R} \ni x \mapsto \left\lfloor x\right\rfloor \in \mathbb{Z}</math>  nie jest injekcją.
<br>
Funkcja <math>\mathbb{N} \ni x \mapsto 2x \in \mathbb{N}</math>  jest injekcją.
<br>
Funkcja <math>\mathbb{Q} \ni x \mapsto 2x \in \mathbb{Q}</math>  jest injekcją.
<br>
Funkcja <math>\mathbb{R} \ni x \mapsto \sin{x} \in \mathbb{R}</math> nie jest injekcją.
<br>
Funkcja <math>{\left\{ {0,1} \right\}\ }^* \ni w \mapsto w1 \in {\left\{ {0,1} \right\}\ }^*</math>  jest injekcją.
<br>
Funkcja <math>{\left\{ {0,1} \right\}\ }^* \ni w \mapsto d(w) \in \mathbb{N}</math>  nie jest injekcją.
}}

<div class="thumb tright"><div style="width:250px;">
<flash>file=SW_2.3.swf|width=250|height=200</flash>
<div.thumbcaption>Przykład bijekcji</div>
</div></div>

{{kotwica|bijekcja|'''Bijekcja'''}} to funkcja, która jest jednocześnie surjekcją i injekcją.   

{{przyklad|||
Funkcja <math>\mathbb{R} \ni x \mapsto x^3 \in \mathbb{R}</math> jest bijekcją.
<br>
Funkcja <math>\mathbb{Q} \ni x \mapsto x^3 \in \mathbb{Q}</math> nie jest bijekcją.
<br>
Funkcja <math>\mathbb{N} \ni x \mapsto 2x \in \mathbb{N}</math> nie jest bijekcją.
<br>
Funkcja <math>\mathbb{Q} \ni x \mapsto 2x \in \mathbb{Q}</math>  jest bijekcją.
<br>
Funkcja <math>\mathbb{Z} \ni x \mapsto \left\lfloor x\right\rfloor \in \mathbb{Z}</math>  jest bijekcją.
<br>
Funkcja <math>\mathbb{R} \ni x \mapsto \left\lfloor x\right\rfloor \in \mathbb{Z}</math>  nie jest bijekcją.
<br>
Funkcja <math>\mathbb{Z} \ni x \mapsto \left\lfloor x\right\rfloor \in \mathbb{Q}</math> nie jest bijekcją.
<br>
Funkcja <math>{\left\{ {0,1} \right\}\ }^* \ni w \mapsto w1 \in {\left\{ {0,1} \right\}\ }^*</math> nie jest bijekcją.
<br>
Funkcja <math>{\left\{ {0,1} \right\}\ }^* \ni w \mapsto d(w) \in \mathbb{N}</math>  nie jest bijekcją.
}}

===Funkcje odwrotne===

Traktując funkcję <math>f : X \longrightarrow Y</math> jako relację <math>f \subseteq X \times Y</math> (zbiór par), 
możemy rozważać relację <math>f^{-1}</math> odwrotną do <math>f</math>.

Kiedy ta relacja jest funkcją?
* ponieważ <math>f^{-1}</math> ma spełniać warunek, że każdy element dziedziny <math>f^{-1}</math> (tzn. zbioru <math>Y</math>) ma przypisaną jakąś wartość, oznacza to, że sama funkcja <math>f</math> wyczerpuje wszystkie elementy przeciwdziedziny, a zatem, że <math>f</math> jest surjekcją,
* nadto <math>f^{-1}</math> ma przypisywać dokładnie jeden taki element, czyli że każdy element z <math>Y</math> jest przypisany poprzez <math>f</math> jednemu elementowi z <math>X,</math> a zatem <math>f</math> 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 <math>f</math> nie była surjekcją, to przy próbie odwrócenia strzałek niektóre elementy zbioru <math>Y</math> nie miałyby przyporządkowanego żadnego elementu z <math>X</math>.
* Gdyby zaś <math>f</math> nie była injekcją, to przy próbie odwrócenia strzałek niektóre strzałki byłyby "rozdwojone".

{{przyklad|||

* Funkcja <math>f : \mathbb{R} \ni x \mapsto 2x \in \mathbb{R}</math> jest bijekcją, a zatem posiada funkcję odwrotną. Tę funkcję odwrotną można wyliczyć: skoro <math>y = f(x) = 2x</math>, to <math>f^{-1}(y) = x = y/2</math>. Zatem <math>f^{-1} : \mathbb{R} \ni x \mapsto x/2 \in \mathbb{R}</math>.
* Funkcja <math>\mathbb{R} \ni x \mapsto \left\lfloor x\right\rfloor \in \mathbb{Z}</math>  nie jest injekcją. Nie posiada więc funkcji odwrotnej.
* Funkcja <math>\mathbb{N} \ni x \mapsto 2x \in \mathbb{N}</math> nie jest surjekcją. Nie posiada więc funkcji odwrotnej. Ale rozważając tę funkcję z przeciwdziedziną <math>\mathbb{P}</math> będącą zbiorem liczb parzystych, tzn. <math>\mathbb{N} \ni x \mapsto 2x \in \mathbb{P}</math> staje się ona bijekcją i posiada funkcję odwrotną <math>\mathbb{P} \ni x \mapsto x/2 \in \mathbb{N}</math>.
* Funkcja <math>\mathbb{R} \ni x \mapsto x^2 \in \mathbb{R}</math>  nie jest ani injekcją ani surjekcją. Nie posiada więc funkcji odwrotnej. Surjektywność można by "uratować", rozważając

<center><math>f : \mathbb{R} \ni x \mapsto x^2 \in [0, +\infty).</math></center>


Wciąż jednak brakowałoby injektywności. Ograniczając jednak, tę funkcję do liczb nieujemnych, tzn. traktując ją jako:


<center><math>f|_{[0, +\infty)}: [0, +\infty) \ni x \mapsto x^2 \in [0, +\infty),</math></center>


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


<center><math>[0, +\infty) \ni x \mapsto \sqrt{x} \in [0, +\infty).</math></center>


}}

===Składanie funkcji===

{{kotwica|zlozenie|'''Złożenie'''}} funkcji  <math>f : X \longrightarrow Y</math> i funkcji <math>g : Y \longrightarrow Z</math> to funkcja 


<center><math>gf: X \longrightarrow Z
</math></center>


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

* Nieformalnie - najpierw obliczamy wartość funkcji <math>f</math> dla elementu <math>x</math>,<br> a następnie obliczamy wartość funkcji <math>g</math> dla wyniku tego obliczenia; czyli "idziemy dalej wzdłuż następnej strzałki" 

<center><math>X \longrightarrow Y \longrightarrow Z</math></center>

* Piszemy <math>gf</math> (a nie <math>fg</math>) na oznaczenie złożenia, w którym najpierw obliczana jest wartość funkcji <math>f</math>, a potem funkcji <math>g</math>.
* W praktyce, przy złożeniu <math>gf</math>, dziedzina funkcji <math>g</math> nie musi być tym samym zbiorem, co przeciwdziedzina funkcji <math>f</math> - wystarczy, by była większa.

{{przyklad|||

* Niech <math>f : \mathbb{N} \ni n \mapsto n + 2 \in \mathbb{N}</math> i <math>g : \mathbb{N} \ni n \mapsto 3n \in \mathbb{N}</math>. Wówczas dla <math>gf : \mathbb{N} \longrightarrow \mathbb{N}</math> mamy <math>(gf)(n) = g(f(n)) = g(n + 2) = 3(n + 2)= 3n+6</math> a dla <math>fg : \mathbb{N} \longrightarrow \mathbb{N}</math> mamy <math>(fg)(n) = f(g(n)) = f(3n) = 3n + 2</math>.
Morał: złożenia <math>fg</math> i <math>gf</math>  to (na ogół) różne funkcje.
* Niech <math>f : \mathbb{R} \ni x \mapsto \sin 3x \in \mathbb{R}</math>  i <math>g : \mathbb{R} \ni x \mapsto  (x + \pi)^2 \in\mathbb{R}</math>. Wówczas złożenie <math>fg: \mathbb{R} \longrightarrow \mathbb{R}</math> dane jest wzorem

<center><math>(fg)(x) = f(g(x)) = f((x + \pi)^2) = \sin(3(x + \pi)^2). </math></center>


Morał: Nie zawsze da się łatwo wyliczyć przepis na funkcję złożoną.
* Gdy <math>f : X \longrightarrow Y</math> jest bijekcją, to istnieje funkcja odwrotna <math>f^{-1} : Y \longrightarrow X</math>. Jeśli złożymy <math>f^{-1} f</math>, to uzyskamy funkcję <math>X \longrightarrow X</math>, która "nic nie robi":

<center><math>(f^{-1} f)(x) = f^{-1}(f(x)) = x.
</math></center>


Taka funkcja zwana jest identycznością na zbiorze <math>X</math> i oznaczana <math>id_X</math>. Podobnie - składając <math>f f^{-1} : Y \longrightarrow Y</math>, otrzymamy identyczność na zbiorze <math>Y</math>.

}}

Widzieliśmy, że nie zawsze <math>fg = gf</math>.

{{obserwacja|3.1|obs 3.1|
Dla funkcji <math>X \stackrel{h}{\longrightarrow} Y \stackrel{g}{\longrightarrow} Z \stackrel{f}{\longrightarrow} W</math>
zachodzi <math>f(gh) = (fg)h</math>.
}}

{{obserwacja|3.2|obs 3.2|
Nadto dla <math>X \stackrel{f}{\longrightarrow} Y \stackrel{g}{\longrightarrow} Z</math> mamy:
* Jeśli <math>f, g</math> są surjekcjami, to <math>gf</math>  jest surjekcją.
* Jeśli <math>f, g</math> są injekcjami, to <math>gf</math>  jest injekcją.
* Jeśli <math>f, g</math> są bijekcjami, to <math>gf</math>  jest bijekcją.
* Pierwsza i trzecia z powyższych własności nie zachodzą, jeśli dziedzina funkcji <math>g</math> jest większa niż przeciwdziedzina funkcji <math>f</math>.

}}

{{przyklad|||
Zbadaj czy dla funkcji <math>X \stackrel{f}{\longrightarrow} Y \stackrel{g}{\longrightarrow} Z</math> zachodzi:
* jeśli <math>gf</math> jest surjekcją, to <math>f</math> jest surjekcją
* jeśli <math>gf</math> jest surjekcją, to <math>g</math> jest surjekcją
* jeśli <math>gf</math> jest injekcją, to <math>f</math> jest injekcją
* jeśli <math>gf</math> jest injekcją, to <math>g</math> jest injekcją

}}

===Funkcje wielu zmiennych===

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

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

* <math>\mathbb{R} \times \mathbb{R} \ni (x,y) \mapsto x+y \in \mathbb{R}</math>
* <math>\mathbb{R} \times \mathbb{R} \ni (x,y) \mapsto x-y \in \mathbb{R}</math>
* <math>\mathbb{R} \times \mathbb{R} \ni (x,y) \mapsto xy \in \mathbb{R}</math>
* <math>\mathbb{R} \times \mathbb{R}-{\left\{ {0} \right\}\ } \ni (x,y) \mapsto \frac{x}{y} \in \mathbb{R}</math>
* <math>\mathbb{N} \times \mathbb{N} \ni (x,y) \mapsto x^y \in \mathbb{N}</math>

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

* <math>X^* \times X^* \ni (v,w) \mapsto vw \in X^*</math>, gdzie <math>vw</math> oznacza słowo (krotkę) powstałe z doklejenia słowa <math>w</math> na końcu słowa <math>v</math>.

}}

==Zliczanie zbiorów==

[[grafika:Parking.jpg|thumb|250px|right|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:


<center>
<math>\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</math>
</center>


Załóżmy, że na parkingu stoi <math>n</math> samochodów. Zliczając je wybieramy elementy <math>\mathbb{Z}_n</math> (zazwyczaj kolejne liczby) i przypisujemy je do samochodów na parkingu. Uwaga: wybierając liczby z <math>\mathbb{Z}_n</math> zaczynamy od <math>0</math> i kończymy na <math>n-1</math> (na ogół nie-informatycy zliczają od <math>1</math> do <math>n</math>). Określamy zatem w trakcie tego zliczania bijekcję <math>f:\mathbb{Z}_n\rightarrow S</math>,
gdzie <math>S</math> 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|obs 3.3|
Gdy <math>m<n</math>, to nie istnieje injekcja z <math>\mathbb{Z}_n</math> w <math>\mathbb{Z}_m</math>.
}}

<div class="thumb tright"><div style="width:250px;">
<flash>file=SW 2.5.swf|width=250|height=250</flash>
<div.thumbcaption>SW 2.5.swf</div></div>
</div>

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

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

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

Wtedy funkcja <math>g:\ N_{n_0-1}\rightarrow\mathbb{Z}_{m-1}</math> zadana przez


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


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

{{wniosek|3.4|wn 3.4|
Jeśli istnieje bijekcja ze zbioru <math>\mathbb{Z}_m</math> na <math>\mathbb{Z}_n</math>, to <math>m=n</math>.
}}

{{kotwica|zbskon|'''Zbiór skończony'''}} to zbiór bijektywny z pewnym zbiorem postaci <math>\mathbb{Z}_n</math>.

{{kotwica|zbnieskon|'''Zbiór nieskończony'''}} to zbiór, który nie jest skończony.

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

{{kotwica|lelem|'''Liczba elementów'''}} skończonego zbioru <math>X</math>, to
jedyna liczba naturalna <math>n</math> taka, że istnieje bijekcja z <math>\mathbb{Z}_n</math> w <math>X</math>. Liczbę te oznaczamy <br> przez <math>\left\vert X\right\vert</math>. 

{{przyklad|||
Oczywiście <math>\left\vert\mathbb{Z}_n\right\vert = n</math>.
W szczególności zbiór pusty ma, zgodnie z intuicją, liczbę elementów równą <math>0</math>.
}}

{{przyklad|||
Zbiór liczb parzystych <math>\mathbb{P}</math> jest nieskończony.

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

{{obserwacja|3.5|obs 3.5|
Zbiór <math>X</math> jest nieskończony wtedy i tylko wtedy, gdy istnieje injekcja z <math>\mathbb{N}</math> w <math>X</math>.
}}

{{dowod|||
Załóżmy, że <math>X</math> jest nieskończony i zdefiniujmy indukcyjnie funkcję 
<math> f:\mathbb{N}\longrightarrow X </math>, kładąc:

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

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

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

{{kotwica|zbprzeli|'''Zbiór przeliczalny'''}} to zbiór skończony lub bijektywny z <math>\mathbb{N}</math>.

{{przyklad|||
* zbiór pusty jest przeliczalny, bo jest skończony,
* zbiór liczb parzystych jest przeliczalny, bo <math>f(x)=2x</math> jest bijekcją <math>\mathbb{N}\longrightarrow\mathbb{P}</math> 
* zbiór liczb całkowitych jest przeliczalny, bo


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


jest bijekcją z <math>\mathbb{N}</math> w <math>\mathbb{Z}</math>.

}}

===Zasada Szufladkowa===

Wróćmy jeszcze do [[#obs_3.3|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]|3.6|
Jeśli <math> n </math> obiektów jest rozmieszczonych w <math> m </math> szufladach i <math> n>m </math>, to istnieje szuflada z przynajmniej dwoma obiektami.
}}

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

{{przyklad|||
Proste przykłady:

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

{{dowod|||
Rzeczywiście, liczba włosów na głowie człowieka nie przekracza <math>500 000</math>, natomiast liczba mieszkańców Krakowa przekracza <math>800 000</math>. Weźmy <math>500 000</math> szufladek ponumerowanych kolejnymi liczbami naturalnymi od <math> 0 </math> do <math>499 999</math> 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 <math>800 000</math>, a szufladek <math>500 000</math>, z Zasady Szufladkowej wynika, że w jednej szufladce muszą znaleźć się co najmniej dwie osoby.
}}

* W grupie <math>13</math> osób muszą być co najmniej dwie, które urodziły się w tym samym miesiącu.

{{dowod|||
Weźmy <math>12</math> szufladek z nazwami miesięcy i wkładajmy do nich osoby, które urodziły się w danym miesiącu. Ponieważ osób jest <math>13</math>, a szufladek <math>12</math>, w jednej z nich muszą być co najmniej dwie osoby.
}}

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

{{przyklad|||
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 <math> n </math> osób, to każda z nich przywita <math> 0 </math> lub <math> 1 </math> lub <math> 2 </math> lub ... <math> n-1 </math> osób.
* Utwórzmy więc <math> n </math> szuflad z etykietami <math>k=0,1,2,\ldots, n-1</math> i umieśćmy osobę w szufladzie o etykiecie <math>k</math>, jeśli witała się z dokładnie <math>k</math> osobami.
* Skoro jest <math> n </math> osób i <math> n </math> szuflad, to ... <br> 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 <math> 0 </math> i <math> n-1 </math> 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 <math> n </math> osób zajęło co najwyżej <math> n-1 </math> szuflad, więc w jednej z nich są co najmniej dwie osoby - takie, które przywitały tę samą liczbę osób.

}}

{{przyklad|||
Wybierając <math> n+1 </math> liczb spośród <math>1,2,3,\ldots, 2n</math>, wśród wybranych liczb zawsze znajdziemy dwie, z których jedna dzieli drugą.

Istotnie:

* Określmy relacje <math>xRy</math> na liczbach naturalnych, tak by:

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


Oznacza to, że <math>xRy</math> jeśli liczby <math>x, y</math> mają ten sam największy czynnik nieparzysty.
* Szufladami niech będą klasy równoważności relacji <math> R </math>.
* Ile jest klas-szuflad dla liczb ze zbioru <math>{\left\{ {1,2,3,\ldots, 2n} \right\}\ }</math>? Co najwyżej <math> n </math>, gdyż tyle może być liczb nieparzystych w zbiorze <math>{\left\{ {1, 2, ..., 2n} \right\}\ }</math>.
* Skoro wybrano <math> n + 1 </math>, to rozkładając je do naszych szuflad jakieś dwie,  powiedzmy <math> a,b </math> muszą trafić do wspólnej szuflady.
Oznacza to, że któryś z ilorazów <math>\frac{a}{b}, \frac{b}{a}</math> 
jest dodatnią potęgą dwójki, a zatem <math> a </math> dzieli <math> b </math> lub <math> b </math> dzieli <math> a </math>.

}}

{{przyklad|||
Wybierzmy dowolnie <math>10</math> różnych liczb naturalnych 
<math>a_1,a_2,\ldots,a_{10}</math> spośród <math>1,2,3,\ldots,100</math>. 
Pokażemy, że w zbiorze <math>{\left\{ {a_1,a_2,\ldots,a_{10}} \right\}\ }</math> 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 <math>{\left\{ {1,2,3,\ldots,100} \right\}\ }</math>. Ponieważ największa możliwa taka suma to <math>91+92+93+\cdots+99+100 = 955</math>, to mamy <math> 955 </math> szuflad z etykietami: <math>0,1,2,3,\ldots, 955</math>
* z drugiej strony <math>10</math>-cio elementowy zbiór <math>{\left\{ {a_1,a_2,\ldots,a_{10}} \right\}\ }</math> ma <math>2^{10}=1024</math> podzbiory, więc muszą być dwa podzbiory zbioru <math>{\left\{ {a_1,a_2,\ldots,a_{10}} \right\}\ }</math> 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 <math>\mathbb{Z}_n</math> 
w nasz zbiór dla pewnego naturalnego <math> n </math>. 
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.

===={{kotwica|zasdod|Zasada dodawania}}====

''Dla skończonych i rozłącznych zbiorów <math>A</math> i <math>B</math> mamy:


<center><math>\left\vert A\cup B\right\vert=\left\vert A\right\vert+\left\vert B\right\vert.</math></center>''


{{dowod|||
Niech liczności zbiorów <math>\left\vert A\right\vert=m</math>, <math>\left\vert B\right\vert=n</math> będą poświadczone bijekcjami <math>f:\mathbb{Z}_m\rightarrow A</math> i <math>g:\mathbb{Z}_n\rightarrow B</math>. Wtedy funkcja <math>h:\mathbb{Z}_{m+n}\rightarrow A\cup B</math>  zadana przez:


<center><math>h(x)=
\left\{
\begin{array} {ll}
f(x),&\textrm{dla }x\in{\left\{ {0,\ldots,m-1} \right\}\ }
\\ 
g(x-m),& \textrm{dla } x\in{\left\{ {m,\ldots,m+n-1} \right\}\ }
\end{array} 
\right.
</math></center>


jest bijekcją. Istotnie, skoro zbiory <math> A </math> i <math> B </math> są rozłączne, to dla dowolnych <math>x_1\in{\left\{ {0,\ldots,m-1} \right\}\ }</math>, <math>x_2\in{\left\{ {m,\ldots,m+n-1} \right\}\ }</math> zachodzi <math>h(x_1)\neq h(x_2)</math>. Ponadto restrykcje <math> h </math> do zbiorów zbiorów <math>{\left\{ {0,\ldots,m-1} \right\}\ }</math> i <math>{\left\{ {m,\ldots,m+n-1} \right\}\ }</math> są injekcjami. A zatem <math> h </math> jest injekcją. 

Dla dowodu surjektywności <math> h </math> weźmy dowolny element <math>y\in A\cup B</math>. Załóżmy, że <math>y\in A</math> (w drugim przypadku dowód przebiega analogicznie). Wtedy z surjektywności <math>f</math> wiemy, 
że istnieje <math>x\in\mathbb{Z}_m</math> takie, że <math>f(x)=y</math>.  
Ale <math>h(x)=f(x)=y</math>. Zatem <math> h </math> jest surjekcją.
}}

Łatwy dowód indukcyjny pozwala uogólnić zasadę dodawania 
na dowolnie wiele skończonych zbiorów.

{{wniosek|3.7|wn 3.7|
Dla zbiorów <math>A_1,\ldots,A_n</math> skończonych i parami rozłącznych:


<center><math>\left\vert A_1\cup\ldots\cup A_n\right\vert=\left\vert A_1\right\vert+\ldots+\left\vert A_n\right\vert.
</math></center>


}}

Więcej pracy wymaga analiza sytuacji, gdy zbiory <math>A,B</math> nie są rozłączne.

===={{kotwica|zaswlwyl|Zasada włączania i wyłączania}}====

''Dla zbiorów skończonych <math>{\left\{ {A_1,A_2,\ldots,A_n} \right\}\ }</math> zachodzi''

<center><math>\aligned &&\left\vert A_1\cup A_2\cup\ldots\cup A_n\right\vert\ =\  \sum_{I\subseteq{\left\{ {1,\ldots,n} \right\}\ }}\left(-1\right)^{\left\vert I\right\vert+1}\left\vert\bigcap_{i\in I}A_i\right\vert\\
&&\begin{array} {lr}
= \left\vert A_1\right\vert+\left\vert A_2\right\vert+\left\vert A_3\right\vert+\ldots &+\left\vert A_{n-2}\right\vert+\left\vert A_{n-1}\right\vert+\left\vert A_n\right\vert\\
-\left\vert A_1\cap A_2\right\vert-\left\vert A_1\cap A_3\right\vert-\ldots&-\left\vert A_{n-2}\cap A_n\right\vert-\left\vert A_{n-1}\cap A_n\right\vert\\
+\left\vert A_1\cap A_2 \cap A_3\right\vert+\ldots&+\left\vert A_{n-2}\cap A_{n-1} \cap A_n\right\vert\\
-\left\vert A_1\cap A_2 \cap A_3\cap A_4\right\vert-\ldots&-\left\vert A_{n-3}\cap A_{n-2}\cap A_{n-1} \cap A_n\right\vert\\
+\ldots&\\
\left(-1\right)^{n+1}\left\vert A_1\cap A_2\cap\ldots\cap A_n\right\vert&
\end{array} 
\endaligned</math></center>


''W szczególności, <math>\left\vert A\cup B\right\vert=\left\vert A\right\vert+\left\vert B\right\vert-\left\vert A\cap B\right\vert</math>, 
o ile tylko <math> A,B </math> są skończone.
''

{{dowod|||
Zaczniemy od dowodu drugiego zdania. Ponieważ trzy zbiory <math>A - B, A\cap B</math> i <math>B- A</math> są parami rozłączne i sumują się do <math>(A - B) \cup (A\cap B) \cup (B- A) = A \cup B</math>, na mocy [[#wn_3.7|Wniosku 3.7]] mamy:


<center><math>|A \cup B| = |(A - B) \cup (A\cap B) \cup (B- A)| = 
|A - B| + |A\cap B| + |B- A| 
</math></center>


skąd


<center><math>\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</math></center>
}}


skąd już natychmiast dostajemy:


{{wzor|wzor 1|1|
<math>
\left\vert A\cup B\right\vert=\left\vert A\right\vert+\left\vert B\right\vert-\left\vert A\cap B\right\vert.
</math>}}


W sytuacji dowolnie wielu <math>n</math> zbiorów użyjemy rozumowania indukcyjnego. Oczywiście  <math> n=1,2 </math> twierdzenie jest prawdziwe. 
Załóżmy, że <math> n>2 </math>. Na mocy równości ([[#wzor_1|1]]) otrzymujemy:


<center><math>\aligned \left\vert\bigcup_{k=1}^nA_k\right\vert\ =\ \left\vert\bigcup_{k=1}^{n-1}A_k\right\vert+\left\vert A_n\right\vert-\left\vert\bigcup_{k=1}^{n-1}A_k\cap A_n\right\vert.
\endaligned</math></center>


Wykorzystując założenie indukcyjne dla wartości <math> n-1 </math> zachodzi


<center><math>\aligned \left\vert\bigcup_{k=1}^nA_k\right\vert&=\sum_{I\subseteq{\left\{ {1,\ldots,n-1} \right\}\ }}\left(-1\right)^{\left\vert I\right\vert+1}\left\vert\bigcap_{i\in I}A_i\right\vert+\left\vert A_n\right\vert-\sum_{I\subseteq{\left\{ {1,\ldots,n-1} \right\}\ }}\left(-1\right)^{\left\vert I\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\vert I\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\vert I\cup{\left\{ {n} \right\}\ }\right\vert+1}\left\vert\bigcap_{i\in I\cup{\left\{ {n} \right\}\ }}A_i\right\vert.
\endaligned</math></center>


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

* pierwsza składa się z tych <math>I</math>, które nie zawierają <math>n</math>, czyli <math>{\left\{ {I:I\subseteq{\left\{ {1,\ldots,n-1} \right\}\ }} \right\}\ }, </math>
* druga jest rodziną tych <math>I</math>, które zawierają <math>n</math>, czyli <math>{\left\{ {I\cup{\left\{ {n} \right\}\ }:I\subseteq{\left\{ {1,\ldots,n-1} \right\}\ }} \right\}\ } </math>.

W rezultacie otrzymujemy, że


<center><math>\aligned\left\vert\bigcup_{k=1}^nA_k\right\vert\ =\  \sum_{I\subseteq{\left\{ {1,\ldots,n} \right\}\ }}\left(-1\right)^{\left\vert I\right\vert+1}\left\vert\bigcap_{i\in I}A_i\right\vert,\endaligned</math></center>


co kończy dowód.

[[#wn3.7|Wniosek 3.7]] pozwala uogólnić Zasadę Szufladkową. Załóżmy, że pewna ilość obiektów jest rozmieszczona w <math>n</math> szufladach. Niech <math>A_i</math> będzie zbiorem obiektów w <math>i</math>-tej szufladce. Ponieważ zbiory obiektów w różnych szufladach są rozłączne, to ilość obiektów we wszystkich szufladach wynosi <math>\left\vert A_1\cup\ldots\cup A_n\right\vert=\left\vert A_1\right\vert\cup\ldots\cup\left\vert A_n\right\vert</math>. Zatem jeśli każda szufladka ma co najwyżej <math>r</math> obiektów, to w sumie jest co najwyżej <math>nr</math> obiektów.

===={{kotwica|uzasszufl|Uogólniona Zasada Szufladkowa}}====

''Jeśli <math>m</math> obiektów rozmieszczonych jest w <math>n</math> szufladach i <math>m>nr</math>, dla pewnego naturalnego <math>r</math>, to istnieje szufladka z co najmniej <math>r+1</math> obiektami.
''

Przypomnijmy, że {{kotwica|ilkart|iloczyn kartezjański}} (produkt) zbiorów <math>X</math> i <math>Y</math> to zbiór 


<center><math>X\times Y={\left\{ {(x,y): x\in X, y\in Y} \right\}\ }.
</math></center>

===={{kotwica|zasmnoz|Zasada Mnożenia}}====

''Dla skończonych zbiorów <math>X,Y</math>:


<center><math>\left\vert X\times Y\right\vert=\left\vert X\right\vert\cdot\left\vert Y\right\vert.
</math></center>


''

{{dowod|||
Najpierw pokażemy, że <math>\left\vert\mathbb{Z}_m\times\mathbb{Z}_n\right\vert=m \cdot n</math>. W tym celu pokażemy, że funkcja 


<center><math>f:\mathbb{Z}_m\times\mathbb{Z}_n \ni (i,j) \mapsto in+j \in \mathbb{Z}_{mn}
</math></center>


jest bijekcją. 

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

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

Załóżmy teraz, że <math>\left\vert X\right\vert=m</math> i <math>\left\vert Y\right\vert=n</math>. Wtedy, z poczynionej wyżej obserwacji, dowód Zasady Mnożenia jest natychmiastowy, gdyż


<center><math>\left\vert X\times Y\right\vert=\left\vert\mathbb{Z}_m\times \mathbb{Z}_n\right\vert=m\cdot n=\left\vert X\right\vert\cdot\left\vert Y\right\vert.
</math></center>


}}

{{przyklad|||
Rozważ turniej rycerski między bractwem czerwonych a bractwem niebieskich. Bractwo czerwonych ma <math>12</math> rycerzy, bractwo niebieskich <math>15</math>. Ile różnych indywidualnych pojedynków może być stoczonych,
jeśli rycerze z tego samego bractwa nigdy ze sobą nie walczą?

* Niech <math>C</math> i <math>N</math> będą zbiorami rycerzy, odpowiednio z bractwa czerwonych i z bractwa niebieskich,
* każdy pojedynek może być interpretowany jako uporządkowana para <math>(c,n)</math>, gdzie <math>c\in C</math>, <math>n\in N</math>. Zatem liczba pojedynków to liczność zbioru <math>C\times N</math>.
* <math>\left\vert C\times N\right\vert=\left\vert C\right\vert\cdot\left\vert N\right\vert=12\cdot15=300</math>.

}}

===Zliczanie podzbiorów===

{{kotwica|zbpoteg|'''Zbiór potegowy'''}}, lub inaczej zbiór podzbiorów, zbioru <math>X</math> oznaczamy przez <math>\mathcal{P}(X)</math>.

{{przyklad|||

* <math>\mathcal{P}(\emptyset)={\left\{ {\emptyset} \right\}\ }</math> i <math>\left\vert\mathcal{P}(\emptyset)\right\vert=1</math>
* <math>\mathcal{P}({\left\{ {\emptyset} \right\}\ })={\left\{ {\emptyset,{\left\{ {\emptyset} \right\}\ }} \right\}\ }</math> i <math>\left\vert\mathcal{P}({\left\{ {\emptyset} \right\}\ })\right\vert=2</math>
}}

{{przyklad|||
Ile podzbiorów ma skończony zbiór <math>n</math>-elementowy? Łatwo jest odpowiedzieć na to pytanie dla małych liczb <math>n</math>. Np. zbiór <math>{\left\{ {a,b} \right\}\ }</math> ma następujące cztery podzbiory:


<center><math>\emptyset,{\left\{ {a} \right\}\ }, {\left\{ {b} \right\}\ }, {\left\{ {a,b} \right\}\ }
</math></center>


a zbiór trzyelementowy <math>{\left\{ {a,b,c} \right\}\ }</math> ma osiem podzbiorów:


<center><math>\emptyset, {\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\}\ }</math></center>


Spróbujmy odpowiedzieć na to pytanie w ogólnej sytuacji i w sposób rekurencyjny.
Niech <math>p_n</math> oznacza liczbę podzbiorów zbioru <math>n</math>-elementowego. Na podstawie dotychczasowych przykładów mamy:}}


<center><math>\begin{array} {|c||c|c|c|c|c}
\hline
n&0&1&2&3&\ldots\\
\hline
p_n&1&2&4&8&\ldots\\
\hline
\end{array} 
</math></center>


i można wysunąć hipotezę, że w ogólności <math>p_n = 2^n</math>. Ale jak ją uzasadnić?

Załóżmy, że znamy liczbę <math>p_n</math> i chcemy policzyć <math>p_{n+1}</math>. Niech więc zbiór <math>Z</math> ma <math>n+1</math> elementów,
czyli po usunięciu ze zbioru <math>Z</math> elementu <math>a\in Z</math>
dostajemy <math>n</math>-elementowy zbiór <math>Z'</math>. Podobnie jak w dowodzie Zasady Włączania-Wyłączania, podzbiory zbioru <math>Z</math> można podzielić na dwa typy:

* albo mają w sobie element <math>a</math>,
* albo go nie mają.

W drugim przypadku są to podzbiory zbioru <math>Z'</math>. Jest więc ich dokładnie <math>p_n</math>.

Każdy zaś podzbiór pierwszego typu, czyli <math>A \subseteq Z</math> takie, że <math>a\in A</math> jest jednoznacznie wyznaczony przez swoje pozostałe elementy, tzn. elementy różne od <math>a</math>. A zatem każdy taki zbiór <math>A</math>, że <math>a \in A \subseteq Z</math>, jest postaci
<math>A'\cup {\left\{ {a} \right\}\ }</math> dla pewnego <math>A'\subseteq Z'</math>. A zatem podzbiorów zbioru <math>Z</math>, w których jest element <math>a</math> jest też tyle ile podzbiorów zbioru <math>Z'</math>, tzn.&nbsp;<math>p_n</math>.

Łącznie więc zbiór <math>Z</math> ma <math>p_n + p_n</math> podzbiorów, czyli
<math>p_{n+1} = 2\cdot p_n </math> Teraz już bez trudu stwierdzamy, że to wraz z warunkiem <math>p_0 = 1</math> jest spełnione przez 


<center><math>p_n = 2^n
</math></center>


co można łatwo uzasadnić przez indukcję.


{{obserwacja|3.8|obs 3.8|
Dla dowolnego, skończonego zbioru <math>X</math>


<center><math>\left\vert\mathcal{P}(X)\right\vert=2^{\left\vert X\right\vert}.
</math></center>


}}

==Zliczanie funkcji==

{{kotwica|zbiorfun|'''Zbiór funkcji'''}} postaci  <math>X \longrightarrow Y</math> oznaczamy przez <math>Y^X</math>.    

{{obserwacja|3.9|obs 3.9|
Dla  skończonych zbiorów <math>X,Y</math> mamy:


<center><math>\left\vert Y^X\right\vert=\left\vert Y\right\vert^{\left\vert X\right\vert}.
</math></center>


}}

{{dowod|||
Niech <math>X={\left\{ {x_0,\ldots,x_{m-1}} \right\}\ }</math> oraz <math>Y={\left\{ {y_0,\ldots, y_{n-1}} \right\}\ }</math>. Każda funkcja <math>f: X \longrightarrow Y</math> to krotka wartości dla kolejnych <math>x_i</math>:


<center><math>(f(x_0),f(x_1),\ldots,f(x_{m-1}))\in \underbrace{Y\times\ldots\times Y}_{m\ razy}.
</math></center>


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


<center><math>\vert\underbrace{Y\times\ldots\times Y}_{m\ razy}\vert
=\underbrace{\left\vert Y\right\vert\times\ldots\times\left\vert Y\right\vert}_{m\ razy}
=n^m= \left\vert Y\right\vert^{\left\vert X\right\vert}.
</math></center>


}}

{{przyklad|||
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 <math>3</math> osoby możemy interpretować jako funkcję ze zbioru <math>{\left\{ {\textrm{Bartek},\textrm{Paweł},\textrm{Piotrek}} \right\}\ }</math> w pięcioelementowy zbiór marek piwa. A więc istnieje <math>5^3=125</math> sposobów spożycia pierwszej kolejki.
I tyleż sposobów dla każdej nastepnej...... 
}}

{{przyklad|||
Kod PIN jest kodem autoryzującym właściciela karty bankomatowej. Składa się on z <math>4</math> cyfr dziesiętnych. Ile jest różnych kodów PIN?

Każdy kod PIN to funkcja z czteroelementowego zbioru pozycji <math>{\left\{ {0,1,2,3} \right\}\ }</math> w dziesięcioelementowy zbiór cyfr <math>{\left\{ {0,1,\ldots,9} \right\}\ }</math>. Z [[#obs_3.9|Obserwacji 3.9]] wynika że kodów PIN jest dokładnie <math>10^4=10000.</math>
}}

Posługując się [[#obs_3.8|Obserwacją 3.8]] udowodnimy jeszcze raz wzór na ilość podzbiorów skończonego zbioru. Zatem [[#obs_3.9|Obserwację 3.9]] możemy traktować jako uogólnienie [[#obs_3.8|Obserwacji 3.8]].

{{dowod|||
Alternatywny dowód [[#obs_3.8|Obserwacji 3.8]]<br>
Zauważmy, że dowolny podzbiór <math>A\subseteq X</math> wyznacza jednoznacznie funkcję <math>\chi_A:X\rightarrow \mathbb{Z}_2</math> w następujący sposób:


<center><math>\chi_Y(x)=
\left\{
\begin{array} {cl}
0,&\textrm{dla }x\in X- A
\\ 
1,&\textrm{dla }x\in A
\end{array} 
\right.
</math></center>


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


<center><math>\mathcal{P}(X) \ni A \mapsto \chi_A \in \mathbb{Z}_2^X
</math></center>


jest bijektywna. Zatem <math>\left\vert\mathcal{P}(X)\right\vert=\left\vert\mathbb{Z}_2^X\right\vert =2^{\left\vert X\right\vert}</math>.
}}

{{obserwacja|3.10|obs 3.10|
Liczba injekcji ze zbioru skończonego <math>X</math> w zbiór skończony <math>Y</math> wynosi:


<center><math>\left\vert Y\right\vert(\left\vert Y\right\vert-1)\cdot\ldots\cdot(\left\vert Y\right\vert-\left\vertX\right\vert+1)= \frac{\left\vert Y\right\vert!}{(\left\vert Y\right\vert-\left\vert X\right\vert)!}.
</math></center>


}}

{{dowod|||
Niech <math>X={\left\{ {x_0,\ldots,x_{m-1}} \right\}\ }</math> i  <math>Y={\left\{ {y_0,\ldots,y_{n-1}} \right\}\ }</math>. Każdą injekcję z <math>X</math> w <math>Y</math> możemy utożsamić z uporządkowanym wyborem <math>m</math> różnych elementów ze zbioru <math>Y</math>: 


<center><math>f(x_0),f(x_1),\ldots,f(x_{m-1}).
</math></center>


Pierwszy element możemy wybrać na <math>n</math> sposobów, drugi na <math>n-1</math>, bo musi być różny od poprzednio wybranego, trzeci już tylko na <math>n-2</math> sposoby, itd., aż wreszcie <math>m</math>-ty na <math>n-m+1</math> sposobów. Zatem liczba injekcji równa jest <math>n(n-1)\cdot\ldots\cdot(n-m+1)</math>.
}}

{{przyklad|||
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 <math>{\left\{ {0,1,2,3} \right\}\ }</math> w <math>10</math>-elementowy zbiór cyfr <math>{\left\{ {0,1,\ldots,9} \right\}\ }</math>. Zatem jest ich dokładnie <math>10\cdot9\cdot8\cdot7=5040</math>.
}}

{{obserwacja|3.11|obs 3.11|
Liczba bijekcji pomiędzy skończonymi zbiorami <math>X</math> i <math>Y</math>, gdzie <math>\left\vert X\right\vert=\left\vert Y\right\vert</math> wynosi
<math>\left\vert X\right\vert!.</math>
}}

{{dowod|||
Pokażemy najpierw, że każda injekcja <math>f: X \longrightarrow Y</math> jest bijekcją. Istotnie, gdyby <math>f</math> nie było surjekcją, to <math>f(X)</math> byłoby właściwym podzbiorem zbioru <math>Y</math>. A zatem <math>\left\vert f(X)\right\vert < \left\vert Y\right\vert</math> i funkcja <math>f : X \longrightarrow f(X)</math> 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 [[#obs_3.3|Obserwacji 3.3]]. Udowodniliśmy, że liczba bijekcji z <math>X</math> w <math>Y</math> równa jest liczbie injekcji z <math>X</math> w <math>Y</math>, czyli, z [[#obs_3.10|Obserwacji 3.10]]), wynosi ona:


<center><math>n(n-1)\cdot\ldots\cdot(n-n+2)(n-n+1)=n!.
</math></center>


Zauważmy jeszcze, że <math>\emptyset \subseteq \emptyset \times \emptyset</math> jest nie tylko funkcją <math>\emptyset : \emptyset \longrightarrow \emptyset</math>, ale i bijekcją i jest to jedyna bijekcja <math>\emptyset \longrightarrow \emptyset</math>.
}}

{{przyklad|||
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 <math>C</math> będzie zbiorem chłopaków, a <math>D</math> zbiorem dziewcząt. Matematycznym modelem doboru par do tańca jest bijekcja <math>f:C\rightarrow D</math>. Zatem możliwych wyborów jest tyle samo co bijekcji pomiędzy <math>5</math>-elementowymi zbiorami, czyli <math>5!=5\cdot4\cdot3\cdot2\cdot1=120</math>.
}}

==Permutacje==

{{kotwica|permutacja|'''Permutacja'''}} zbioru skończonego <math>X</math> to bijekcja z <math>X</math> w <math>X</math>. 

{{kotwica|zbpermzb|'''Zbiór permutacji zbioru <math>\mathbb{Z}_n</math>'''}} oznaczamy przez <math>S_n</math>, a permutacje bedziemy w tym kursie oznaczać małymi literami greckimi. 

{{przyklad|||
Rozważ funkcję <math>\alpha:\mathbb{Z}_7\rightarrow\mathbb{Z}_7</math> zadaną przez poniższą tabelę:


<center><math>\begin{array} {|c||c|c|c|c|c|c|c|}
\hline
n&0&1&2&3&4&5&6\\
\hline
\alpha(n)&2&3&6&0&4&1&5\\
\hline
\end{array} 
</math></center>


Funkcja <math>\alpha</math> jest bijekcją z <math>\mathbb{Z}_7</math> w <math>\mathbb{Z}_7</math>, zatem jest permutacją i <math>\alpha\in S_7</math>.
}}

{{przyklad|||
Dla permutacji <math>\alpha,\beta\in S_5</math> zadanych przez poniższą tabelę:


<center><math>\begin{array} {|c||c|c|c|c|c|}
\hline
n&0&1&2&3&4\\
\hline
\alpha(n)&4&2&3&0&1\\
\hline
\beta(n)&2&3&1&4&0\\
\hline
\end{array} 
</math></center>


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


<center><math>\begin{array} {|c||c|c|c|c|c|}
\hline
n&0&1&2&3&4\\
\hline
\beta\alpha(n)&0&1&4&2&3\\
\hline
\alpha\beta(n)&3&0&2&1&4\\
\hline
\end{array} 
</math></center>


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

Ponieważ permutacje są bijekcjami, to natychmiast z [[#obs_3.2|Obserwacji 3.2]] dostajemy:

{{obserwacja|3.12|obs 3.12|
Dla dowolnych permutacji <math>\alpha,\beta</math> skończonego zbioru <math>X</math>:

* <math>\alpha\beta,\beta\alpha</math> są permutacjami <math>X</math>,
* <math>\alpha^{-1}</math> jest permutacją <math>X</math> taką, że <math>\alpha\alpha^{-1}=id_{X}=\alpha^{-1}\alpha=</math>.

}}

Następne spostrzeżenie jest natychmiastowym wnioskiem z [[#obs_3.11|Obserwacji 3.11]].

{{wniosek|3.13|wn 3.13|
Zbiór <math>n</math>-elementowy ma dokładnie <math>n!</math> permutacji, <math>\left\vert S_n\right\vert=n!</math>.
}}

{{przyklad|||
Oto wszystkie (<math>3!=6</math>) permutacje zbioru <math>S_3</math>:


<center><math>\begin{array} {ccccccccccc}
0&1&2&\qquad&0&1&2&\qquad&0&1&2\\
\downarrow&\downarrow&\downarrow&&\downarrow&\downarrow&\downarrow&&\downarrow&\downarrow&\downarrow\\
0&1&2&\qquad&0&2&1&\qquad&1&0&2\\
\\
0&1&2&\qquad&0&1&2&\qquad&0&1&2\\
\downarrow&\downarrow&\downarrow&&\downarrow&\downarrow&\downarrow&&\downarrow&\downarrow&\downarrow\\
1&0&2&\qquad&2&0&1&\qquad&2&1&0
\end{array} 
</math></center>


}}


Permutację <math>\alpha</math> zbioru <math>X={\left\{ {x_0,\ldots,x_{n-1}} \right\}\ }</math> wygodnie jest identyfikować z krotką <math>(\alpha(x_0),\ldots,\alpha(x_{n-1}))\in X^n</math>. Często też permutację interpretuje się jako uporządkowanie zbioru <math>X</math>.

<div class="thumb tleft"><div style="width:250px;">
<flash>file=7ksiazek.jpg|width=250|height=250</flash>
</div></div>

<div class="thumb tright"><div style="width:250px;">
<flash>file=MD1-2-8.swf|width=250|height=250</flash>
</div></div>

{{przyklad|||
Na ile sposobów można poukładać koło siebie na półce <math>7</math> książek?

Na dokładnie tyle, ile jest permutacji zbioru siedmio-elementowego, a więc <math>7!=5040</math>.
}}

{{kotwica|cykl|'''Cykl'''}} zbioru <math>n</math>-elementowego <math>X</math> to taka permutacja zbioru <math>X</math>, dla której <math>{\left\{ {x,\alpha(x),\alpha^2(x),\ldots,\alpha^{n-1}(x)} \right\}\ }=X</math>, przy dowolnym <math>x\in X</math>. Łatwo zauważyć, że jeśli dla pewnego <math>x_0\in X</math> mamy <math>{\left\{ {x,\alpha(x),\alpha^2(x),\ldots,\alpha^{n-1}(x)} \right\}\ }=X</math>, to jest tak dla wszystkich <math>x\in X</math>, czyli <math>\alpha</math> jest cyklem na <math>X</math>. Cykl <math>\alpha</math> zbioru <math>X</math> zapisujemy jako <math>(x,\alpha(x),\ldots,\alpha^{n-1}(x))</math> dla dowolnie wybranego <math>x\in X</math>.

{{przyklad|||
Rozważmy <math>\alpha\in S_6</math> daną przez

<center>
<math>\begin{array} {|c||c|c|c|c|c|c|}
\hline
n&0&1&2&3&4&5\\
\hline
\alpha(n)&3&5&0&1&2&4\\
\hline
\end{array} 
</math>
</center>

* sekwencja <math>0</math>, <math>\alpha(0)=3</math>, <math>\alpha^2(0)=1</math>, <math>\alpha^3(0)=5</math>, <math>\alpha^4(0)=4</math>, <math>\alpha^5(0)=2</math> pokwywa całe <math>\mathbb{Z}_6</math>,
* zatem <math>\alpha=(0,3,1,5,4,2)</math> jest cyklem.

}}

====Rozkład permutacji na rozłączne cykle====

Dowolną permutację <math>\alpha</math> zbioru <math>X</math> można rozłożyć na rozłączne cykle w sposób następujący:
# wybierz dowolny element <math>x\in X</math>, który nie jest jeszcze w żadnym cyklu,
#iteruj permutację <math>\alpha</math> otrzymując kolejno: <math>\alpha(x),\alpha^2(x),\alpha^3(x),\ldots </math> aż do uzyskania <math>\alpha^j(x)=x</math>,
#dodaj do rozkładu cykl <math>x,\ldots,\alpha^{j-1}(x)</math>,
#jeśli w zbiorze <math>X</math> pozostały jeszcze elementy niepokryte przez żaden cykl, to wróć do pierwszego punktu.

{{dowod|||
Dla dowodu poprawności algorytmu rozkładu pokażemy najpierw, że iteracja w drugim punkcie zawsze osiąga element wyjściowy <math>x</math>. Ponieważ zbiór <math>X</math> jest skończony iteracja <math>x,\alpha(x),\alpha^2(x)\ldots</math> w pewnym kroku musi wrócić do elementu już rozważanego, zatem <math>\alpha^i(x)=\alpha^j(x)</math> dla pewnych <math>i<j</math>. Weźmy najmniejsze takie <math>j</math>, że <math>\alpha^i(x)=\alpha^j(x)</math> dla pewnego <math>0\leq i<j</math>. Gdyby <math>i\neq 0</math> to z faktu, że <math>\alpha</math> jest permutacją mamy <math>\alpha^{i-1}(x)=\alpha^{j-1}(x)</math>, co stoi w sprzeczności z minimalnością <math>j</math>. A zatem <math>\alpha^j(x)=x</math>.

Pozostaje jeszcze pokazać, że otrzymane cykle są rozłączne. Załóżmy, że nie są i weźmy pierwszy napotkany element <math>y=\alpha^i(x)</math>, który był już w którymś z poprzednich cykli. Zauważmy, że <math>i>0</math> gdyż <math>x</math> był wybrany jako element nie pokryty przez żaden cykl (patrz punkt pierwszy). Wiemy, że istnieje element <math>z</math> w tym samym cyklu co <math>y</math> taki, że <math>\alpha(z)=y</math>, ale także <math>\alpha(\alpha^{i-1}(x))=y</math>. Ponieważ <math>\alpha</math> jest permutacją, otrzymujemy <math>\alpha^{i-1}(x)=z</math>, co stoi w sprzeczności z faktem, że <math>y</math> jest jedynym elementem z poprzedniego cyklu.
}}

Jeśli permutacja <math>\alpha</math> złożona jest z <math>k</math> rozłącznych cykli, to zapisujemy <math>\alpha=(x_0,\ldots)(x_1,\ldots)\ldots(x_{k-1},\ldots)</math>, gdzie w kolejnych nawiasach są elementy kolejnych cykli startujące od odpowiednio: <math>x_0,\ldots,x_{k-1}</math>.


{{przyklad|||
Rozważmy jeszcze raz permutację <math>\alpha\in S_7</math>:


<center><math>\begin{array} {|c||c|c|c|c|c|c|c|}
\hline
n&0&1&2&3&4&5&6\\
\hline
\alpha(n)&2&3&6&0&4&1&5\\
\hline
\end{array} 
</math></center>


Rozkład <math>\alpha</math> na cykle: 
* <math>0</math>, <math>\alpha(0)=2</math>, <math>\alpha(2)=6</math>, <math>\alpha(6)=5</math>, <math>\alpha(5)=1</math>, <math>\alpha(1)=3</math>, <math>\alpha(3)=0</math>,

* <math>4</math>, <math>\alpha(4)=4</math>,

* <math>\alpha=(026513)(4)</math>.

}}