Strona główna › Matematyka dyskretna 1 › Wykłady

Zliczanie zbiorów i funkcji

strict warning: Only variables should be passed by reference in /usr/share/drupal6/modules/book/book.module on line 559.
czw., 01/13/2011 - 10:42 — Mirek Rachelski

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:

  • \( \forall x\in X \ \exists y \in Y \ \ \langle x,y \rangle\in f \)
  • \( \forall x\in X \ \forall y_1,y_2\in Y \ \ (\langle x,y_1 \rangle\in f \wedge \langle x,y_2 \rangle\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

\( \forall x\in X \ \exists! y \in Y \ \ \langle x,y \rangle\in f, \)

gdzie kwantyfikator \( \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 \longrightarrow Y \) lub \( X \stackrel{f}{\longrightarrow} 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{R} \longrightarrow \mathbb{R} \).

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{N}, \mathbb{R} \)), ale można mówić o funkcjach na różnych zbiorach.

  • \( f : \mathbb{N} \ni n \mapsto 2n \in \mathbb{N} \),
    • jest zwartym zapisem, że \( f \) jest funkcją postaci \( f : \mathbb{N} \longrightarrow \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{N} \longrightarrow \mathbb{R}, \ g(n) = n/2 \),
    • określenie \( g : \mathbb{N} \longrightarrow \mathbb{N} \) nie byłoby tu prawidłowe, gdyż wartość \( n/2 \) nie zawsze jest liczbą naturalną
  • \( h : \mathbb{N} \longrightarrow {\{ {13} \}\ }, \ h(n) = 13 \),
    • to też jest poprawnie określona funkcja, mimo że niezbyt frapująca (tzw. funkcja stała)
  • \( f : \mathbb{N} \longrightarrow \mathbb{N}, \ f(n) = (1 + 3 + 5 + ... + (2n+1))^n \).
    • takie określenie też jest poprawne, choć nie od razu widać, ile to jest
  • \( g : \mathbb{R} \ni x \mapsto \sin\frac{x}{\pi}\in \mathbb{R} \) jest całkiem poprawną funkcją.
  • \( h : \mathbb{R} \ni x \mapsto \sin\frac{\pi}{x}\in \mathbb{R} \),
    • 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{R}-{\{ {0} \}\ } \longrightarrow \mathbb{R} \)
  • \( {\{ {0,1} \}\ }^* \ni w \mapsto w1 \in {\{ {0,1} \}\ }^* \),
    • to funkcja określona na słowach nad alfabetem dwuelementowym \( {\{ {0,1} \}\ } \)
    • każdemu słowu przypisuje to słowo rozszerzone na końcu o symbol \( 1 \)
  • \( d: {\{ {0,1} \}\ }^* \longrightarrow \mathbb{N}, \ d(w) = \) długość słowa \( w \)

Wielomian to funkcja:

\( x \mapsto a_nx^n + a_{n-1}x^{n-1} + \ldots + a_2x^2 + a_1 x + a_0 \)
gdzie

  • liczby \( a_n, a_{n-1}, \ldots, 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}, \ldots, a_1,a_0 \in \mathbb{N} \)
      • całkowitych - jeśli \( a_n, a_{n-1}, \ldots, a_1,a_0 \in \mathbb{Z} \)
      • wymiernych - jeśli \( a_n, a_{n-1}, \ldots, a_1,a_0 \in \mathbb{Q} \)
      • rzeczywistych - jeśli \( a_n, a_{n-1}, \ldots, a_1,a_0 \in \mathbb{R} \)
    • liczba \( n \) zwana jest stopniem wielomianu, ale tylko o ile \( a_n \neq 0 \).

Surjekcje, injekcje i bijekcje

Surjekcja to funkcja \( f : X \longrightarrow Y \) spełniająca warunek

\( \forall y\in Y \ \exists x\in X \ \ f(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 ↠ Y \).

Przykład

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

Injekcja to funkcja \( f : X \longrightarrow Y \) spełniająca warunek:

\( \forall x_1,x_2 \in X \ \ x_1\neq x_2 \to f(x_1)\neq 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{R} \ni x \mapsto x^3 \in \mathbb{R} \) jest injekcją.
Funkcja \( \mathbb{R} \ni x \mapsto x^2 \in \mathbb{R} \) nie jest injekcją.
Funkcja \( \mathbb{Z} \ni x \mapsto \lfloor x\rfloor \in \mathbb{Z} \) jest injekcją.
Funkcja \( \mathbb{R} \ni x \mapsto \lfloor x\rfloor \in \mathbb{Z} \) nie jest injekcją.
Funkcja \( \mathbb{N} \ni x \mapsto 2x \in \mathbb{N} \) jest injekcją.
Funkcja \( \mathbb{Q} \ni x \mapsto 2x \in \mathbb{Q} \) jest injekcją.
Funkcja \( \mathbb{R} \ni x \mapsto \sin{x} \in \mathbb{R} \) nie jest injekcją.
Funkcja \( {\{ {0,1} \}\ }^* \ni w \mapsto w1 \in {\{ {0,1} \}\ }^* \) jest injekcją.
Funkcja \( {\{ {0,1} \}\ }^* \ni w \mapsto d(w) \in \mathbb{N} \) nie jest injekcją.

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

Przykład

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

Funkcje odwrotne

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

Kiedy ta relacja jest funkcją?

  • 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{R} \ni x \mapsto 2x \in \mathbb{R} \) 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{R} \ni x \mapsto x/2 \in \mathbb{R} \).
  • Funkcja \( \mathbb{R} \ni x \mapsto \lfloor x\rfloor \in \mathbb{Z} \) nie jest injekcją. Nie posiada więc funkcji odwrotnej.
  • Funkcja \( \mathbb{N} \ni x \mapsto 2x \in \mathbb{N} \) nie jest surjekcją. Nie posiada więc funkcji odwrotnej. Ale rozważając tę funkcję z przeciwdziedziną \( \mathbb{P} \) będącą zbiorem liczb parzystych, tzn. \( \mathbb{N} \ni x \mapsto 2x \in \mathbb{P} \) staje się ona bijekcją i posiada funkcję odwrotną \( \mathbb{P} \ni x \mapsto x/2 \in \mathbb{N} \).
  • Funkcja \( \mathbb{R} \ni x \mapsto x^2 \in \mathbb{R} \) nie jest ani injekcją ani surjekcją. Nie posiada więc funkcji odwrotnej. Surjektywność można by "uratować", rozważając

\( f : \mathbb{R} \ni x \mapsto x^2 \in [0, +\infty). \)

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


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

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


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

Składanie funkcji

Złożenie funkcji \( f : X \longrightarrow Y \) i funkcji \( g : Y \longrightarrow Z \) to funkcja


\( gf: X \longrightarrow Z \)

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

  • 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 \longrightarrow Y \longrightarrow 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{N} \ni n \mapsto n + 2 \in \mathbb{N} \) i \( g : \mathbb{N} \ni n \mapsto 3n \in \mathbb{N} \). Wówczas dla \( gf : \mathbb{N} \longrightarrow \mathbb{N} \) mamy \( (gf)(n) = g(f(n)) = g(n + 2) = 3(n + 2)= 3n+6 \) a dla \( fg : \mathbb{N} \longrightarrow \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{R} \ni x \mapsto \sin 3x \in \mathbb{R} \) i \( g : \mathbb{R} \ni x \mapsto (x + \pi)^2 \in\mathbb{R} \). Wówczas złożenie \( fg: \mathbb{R} \longrightarrow \mathbb{R} \) 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 \longrightarrow Y \) jest bijekcją, to istnieje funkcja odwrotna \( f^{-1} : Y \longrightarrow X \). Jeśli złożymy \( f^{-1} f \), to uzyskamy funkcję \( X \longrightarrow 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 \( id_X \). Podobnie - składając \( f f^{-1} : Y \longrightarrow Y \), otrzymamy identyczność na zbiorze \( Y \).

Widzieliśmy, że nie zawsze \( fg = gf \).

Obserwacja 3.1

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

Obserwacja 3.2

Nadto dla \( X \stackrel{f}{\longrightarrow} Y \stackrel{g}{\longrightarrow} Z \) mamy:

  • 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}{\longrightarrow} Y \stackrel{g}{\longrightarrow} 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 \longrightarrow 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{R} \times \mathbb{R} \ni (x,y) \mapsto x+y \in \mathbb{R} \)
  • \( \mathbb{R} \times \mathbb{R} \ni (x,y) \mapsto x-y \in \mathbb{R} \)
  • \( \mathbb{R} \times \mathbb{R} \ni (x,y) \mapsto xy \in \mathbb{R} \)
  • \( \mathbb{R} \times \mathbb{R}-{\{ {0} \}\ } \ni (x,y) \mapsto \frac{x}{y} \in \mathbb{R} \)
  • \( \mathbb{N} \times \mathbb{N} \ni (x,y) \mapsto x^y \in \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 \).