Funkcja (odwzorowanie) $f\colon X \to Y$ przyporządkowuje każdemu elementowi $x \in X$ dokładnie jeden element $f(x) \in Y$.
Funkcję $f\colon X \to Y$ nazywamy różnowartościową (injektywną, „jeden do jednego"), jeśli: \[ \forall\, x_1, x_2 \in X\colon\; x_1 \neq x_2 \implies f(x_1) \neq f(x_2). \]
\[ \forall\, x_1, x_2 \in X\colon\; f(x_1) = f(x_2) \implies x_1 = x_2. \]
Intuicja: różne argumenty dają różne wartości — żadna wartość nie jest „trafiona" więcej niż raz.
$f$ nie jest różnowartościowa $\iff$ \[ \exists\, x_1, x_2 \in X\colon\; x_1 \neq x_2 \;\wedge\; f(x_1) = f(x_2). \]
Aby obalić różnowartościowość, wystarczy znaleźć jeden kontrprzykład — parę różnych argumentów o tej samej wartości.
$f\colon \mathbb{R} \to \mathbb{R}$, $f(x) = 2x + 3$.
Dowód: Niech $f(x_1) = f(x_2)$, tzn. $2x_1 + 3 = 2x_2 + 3$. Odejmujemy $3$: $2x_1 = 2x_2$, dzielimy przez $2$: $x_1 = x_2$. $\checkmark$
Ogólnie: każda funkcja liniowa $f(x) = ax + b$ z $a \neq 0$ jest różnowartościowa.
$f\colon \mathbb{R} \to \mathbb{R}$, $f(x) = x^3$.
Dowód: Niech $x_1^3 = x_2^3$. Wtedy $x_1^3 - x_2^3 = 0$, czyli $(x_1 - x_2)(x_1^2 + x_1 x_2 + x_2^2) = 0$. Jeśli $x_1, x_2 \in \mathbb{R}$, to $x_1^2 + x_1 x_2 + x_2^2 = \frac{1}{2}(x_1^2 + (x_1+x_2)^2 + x_2^2) \geq 0$, z równością $0$ tylko gdy $x_1 = x_2 = 0$. W obu przypadkach $x_1 = x_2$. $\checkmark$
$f\colon \mathbb{R} \to \mathbb{R}$, $f(x) = e^x$.
Dowód: Funkcja $e^x$ jest ściśle rosnąca na $\mathbb{R}$, więc jest różnowartościowa (bo $x_1 \lt x_2 \implies e^{x_1} \lt e^{x_2}$, a więc $e^{x_1} \neq e^{x_2}$). $\checkmark$
$f\colon \mathbb{R} \setminus \{0\} \to \mathbb{R}$, $f(x) = \frac{1}{x}$.
Dowód: $\frac{1}{x_1} = \frac{1}{x_2} \implies x_1 = x_2$ (mnożymy obie strony przez $x_1 x_2 \neq 0$). $\checkmark$
$f\colon \mathbb{R} \to \mathbb{R}$, $f(x) = x^2$.
Kontrprzykład: $f(2) = 4 = f(-2)$, ale $2 \neq -2$. Zatem $f$ nie jest różnowartościowa. $\times$
Uwaga: $g(x) = x^2$ ograniczona do $[0, +\infty) \to \mathbb{R}$ jest różnowartościowa (bo na $[0,+\infty)$ jest ściśle rosnąca).
$f\colon \mathbb{R} \to \mathbb{R}$, $f(x) = \sin x$.
Kontrprzykład: $\sin 0 = 0 = \sin \pi$, ale $0 \neq \pi$. $\times$
Uwaga: $\sin x$ ograniczony do $\left[-\frac{\pi}{2}, \frac{\pi}{2}\right]$ jest różnowartościowy.
$f\colon \mathbb{R} \to \mathbb{R}$, $f(x) = |x|$.
Kontrprzykład: $|3| = 3 = |-3|$, ale $3 \neq -3$. $\times$
Jeśli $|X| \geq 2$, to $f$ nie jest różnowartościowa (wszystkie argumenty mają tę samą wartość). $\times$
Jeśli $f\colon X \to \mathbb{R}$ ($X \subseteq \mathbb{R}$) jest ściśle monotoniczna (ściśle rosnąca lub ściśle malejąca), to $f$ jest różnowartościowa.
Niech $f$ będzie ściśle rosnąca i niech $x_1 \neq x_2$. Bez straty ogólności $x_1 \lt x_2$. Wtedy $f(x_1) \lt f(x_2)$, więc $f(x_1) \neq f(x_2)$. $\square$
Implikacja odwrotna nie zachodzi: $f(x) = \begin{cases} x & x \in \mathbb{Q} \\ -x & x \notin \mathbb{Q} \end{cases}$ jest różnowartościowa, ale nie jest monotoniczna.
Funkcja $f$ jest różnowartościowa $\iff$ każda pozioma prosta $y = c$ przecina wykres $f$ co najwyżej w jednym punkcie.
Funkcję $f\colon X \to Y$ nazywamy surjekcją (funkcją „na" $Y$), jeśli: \[ \forall\, y \in Y\;\;\exists\, x \in X\colon\; f(x) = y. \]
Równoważnie: $f(X) = Y$, tzn. zbiór wartości pokrywa się z całą przeciwdziedziną.
Intuicja: każdy element $Y$ jest „trafiony" — żaden element przeciwdziedziny nie jest pominięty.
$f$ nie jest surjekcją $\iff$ \[ \exists\, y \in Y\;\;\forall\, x \in X\colon\; f(x) \neq y. \]
Aby obalić surjektywność, wystarczy znaleźć jeden element $y \in Y$, który nie ma przeciwobrazu.
To, czy $f$ jest „na", zależy od wyboru zbioru $Y$. Np. $f(x) = x^2$ z $\mathbb{R} \to \mathbb{R}$ nie jest surjekcją ($-1$ nie ma przeciwobrazu), ale $f(x) = x^2$ z $\mathbb{R} \to [0, +\infty)$ jest surjekcją.
Dowód: Niech $y \in \mathbb{R}$. Szukamy $x$ takiego, że $2x + 3 = y$, czyli $x = \frac{y - 3}{2} \in \mathbb{R}$. Sprawdzamy: $f\!\left(\frac{y-3}{2}\right) = 2 \cdot \frac{y-3}{2} + 3 = y$. $\checkmark$
Dowód: Dla każdego $y \in \mathbb{R}$ istnieje $x = \sqrt[3]{y} \in \mathbb{R}$ takie, że $x^3 = y$. $\checkmark$
Surjekcja, bo dla każdego $y \in [-1, 1]$ istnieje $x = \arcsin y$ takie, że $\sin x = y$. $\checkmark$
Surjekcja, bo dla każdego $y \gt 0$ istnieje $x = \ln y$ takie, że $e^x = y$. $\checkmark$
Nie jest surjekcją: $y = -1 \in \mathbb{R}$, ale nie istnieje $x \in \mathbb{R}$ takie, że $x^2 = -1$. $\times$
Nie jest surjekcją: $y = -1 \in \mathbb{R}$, ale $e^x \gt 0$ dla każdego $x$, więc $e^x \neq -1$. $\times$
Uwaga: ta sama funkcja $e^x\colon \mathbb{R} \to (0, +\infty)$ jest surjekcją (zmieniliśmy przeciwdziedzinę).
Nie jest surjekcją: $y = 2 \in \mathbb{R}$, ale $|\sin x| \leq 1$, więc $\sin x \neq 2$. $\times$
Funkcję $f\colon X \to Y$ nazywamy bijekcją, jeśli jest jednocześnie iniekcją i surjekcją, tzn.: \[ \forall\, y \in Y\;\;\exists!\, x \in X\colon\; f(x) = y. \]
Symbol $\exists!$ oznacza „istnieje dokładnie jeden". Bijekcja ustanawia wzajemnie jednoznaczną odpowiedniość między $X$ a $Y$.
Niech $f\colon X \to Y$ i $g\colon Y \to Z$. Wtedy:
Niech $(g \circ f)(x_1) = (g \circ f)(x_2)$, tzn. $g(f(x_1)) = g(f(x_2))$.
Ponieważ $g$ jest iniekcją: $f(x_1) = f(x_2)$.
Ponieważ $f$ jest iniekcją: $x_1 = x_2$. $\square$
Niech $z \in Z$. Ponieważ $g$ jest surjekcją, istnieje $y \in Y$ takie, że $g(y) = z$.
Ponieważ $f$ jest surjekcją, istnieje $x \in X$ takie, że $f(x) = y$.
Zatem $(g \circ f)(x) = g(f(x)) = g(y) = z$. $\square$
Niech $f\colon X \to Y$ i $g\colon Y \to Z$. Wtedy:
Niech $f(x_1) = f(x_2)$. Wtedy $g(f(x_1)) = g(f(x_2))$, czyli $(g \circ f)(x_1) = (g \circ f)(x_2)$. Ponieważ $g \circ f$ jest iniekcją: $x_1 = x_2$. Zatem $f$ jest iniekcją. $\square$
Niech $z \in Z$. Ponieważ $g \circ f$ jest surjekcją, istnieje $x \in X$ takie, że $(g \circ f)(x) = z$, czyli $g(f(x)) = z$. Biorąc $y = f(x) \in Y$, mamy $g(y) = z$. Zatem $g$ jest surjekcją. $\square$
Zbiory $X$ i $Y$ są równoliczne (mają tę samą moc), co zapisujemy $|X| = |Y|$ lub $X \sim Y$, jeśli istnieje bijekcja $f\colon X \to Y$.
Bijekcja jest narzędziem do porównywania „rozmiarów" zbiorów, także nieskończonych.