Funcții surjective

Un sistem de calcul are 4 procese, $P = \{p_1, p_2, p_3, p_4\}$, și 2 servere, $S = \{s_1, s_2\}$. Funcția de alocare $a\colon P \to S$ trimite fiecare proces pe exact un server.

Iată două alocări posibile. Amândouă sunt funcții: din fiecare proces pleacă exact o săgeată.

Imaginea unei funcții, $\operatorname{Im} f$, e mulțimea valorilor pe care le ia de fapt: elementele din dreapta în care ajunge cel puțin o săgeată. Ea e mereu o parte a codomeniului.

$f$ nu e surjectivă: $\operatorname{Im} f \ne B$. $g$ e surjectivă: $\operatorname{Im} g = B$. Asta e toată ideea: o funcție e surjectivă când imaginea ei este chiar codomeniul.

O companie de jocuri are 3 servere, numerotate $S = \{0, 1, 2\}$. Fiecare jucător are un număr de identificare (ID), iar funcția de alocare $f$ trimite jucătorul cu ID-ul $n$ pe serverul egal cu restul împărțirii lui $n$ la 3 (manual, p. 92).

Un server pornit consumă curent chiar dacă n-are jucători, deci compania vrea ca alocarea să fie surjectivă.

Dacă joacă un singur jucător, cu ID-ul 10, el ajunge pe serverul 1, iar serverele 0 și 2 stau degeaba: $\operatorname{Im} f = \{1\} \ne S$.

Cu jucătorii 10, 11, 12, resturile sunt 1, 2, 0: $\operatorname{Im} f = \{0, 1, 2\} = S$, deci alocarea e surjectivă.

Notăm cu $|A|$ numărul de elemente al unei mulțimi finite $A$. O funcție $f\colon A \to B$ are exact $|A|$ săgeți, deci atinge cel mult $|A|$ elemente din $B$.

Dacă $|A| < |B|$, cel puțin un element din $B$ rămâne neatins: funcția nu poate fi surjectivă. Ca să fie surjectivă, trebuie ca $|A| \ge |B|$.

Din grade Celsius în grade Fahrenheit: $f\colon \mathbb{R} \to \mathbb{R}$, $f(x) = 1{,}8x + 32$. Aici nu mai putem desena toate săgețile. Întoarcem întrebarea: alegem o valoare $y$ și căutăm $x$ cu $f(x) = y$.

Termometrul arată 50 °F. Atunci $1{,}8x + 32 = 50$, adică $1{,}8x = 18$ și $x = 10$. Arată $-4$ °F? $1{,}8x = -36$, deci $x = -20$.

Pentru un $y$ oarecare facem la fel:

$f\colon \mathbb{R} \to \mathbb{R}$, $f(x) = x^2$. Luăm $y = -4$: ecuația $x^2 = -4$ nu are soluție reală, pentru că pătratul unui număr real nu e niciodată negativ.

Deci $-4$ e în codomeniu, dar nu e imaginea niciunui $x$: $f$ nu e surjectivă.

Pentru „da” trebuie să rezolvi $f(x) = y$ pentru orice $y$. Pentru „nu” ajunge un singur $y$ fără preimagine: un contraexemplu, ca în capitolul 1.

Un punct $(x, y)$ e pe grafic exact când $f(x) = y$. Deci dreapta orizontală $y = k$ taie graficul exact în punctele în care $f(x) = k$.

Așa că $f$ e surjectivă când orice dreaptă orizontală $y = k$, cu $k$ din codomeniu, taie graficul cel puțin o dată. Două funcții de la $\mathbb{R}$ la $\mathbb{R}$ (manual, p. 91):

Ramura din stânga dă toate valorile din $(-\infty, 3]$, oricare ar fi $a$. Ramura din dreapta trebuie să acopere ce lipsește: toate valorile mai mari decât 3.

Dacă $a > 0$, ramura urcă și ia toate valorile mai mari decât $a \cdot 1 + 2 = a + 2$. Ca să nu rămână gol, ea trebuie să pornească cel mult de la 3: $a + 2 \le 3$, adică $a \le 1$.

Dacă $a = 0$, ramura e constantă, egală cu 2. Dacă $a < 0$, ramura coboară și ia doar valori mai mici decât $a + 2 < 2$. În ambele cazuri valorile mai mari decât 3 nu sunt atinse.

Deci $f$ e surjectivă exact pentru $a \in (0, 1]$.

$f\colon \mathbb{R} \to \mathbb{R}$, $f(x) = x^2$, nu e surjectivă: valorile negative nu sunt atinse. Schimbăm doar codomeniul: $f\colon \mathbb{R} \to [0, \infty)$, $f(x) = x^2$.

Acum, pentru orice $y \ge 0$, avem $x = \sqrt{y}$ cu $f(x) = y$. Aceeași lege, dar funcția e surjectivă.

O funcție e dată de trei lucruri: domeniu, codomeniu și lege. Dacă alegem codomeniul egal cu imaginea, funcția devine surjectivă.

Și domeniul contează: $f\colon [1, \infty) \to [0, \infty)$, $f(x) = x^2$, nu mai e surjectivă, pentru că $x \ge 1$ dă $x^2 \ge 1$, iar $0{,}5$ nu mai e atins.