Manual · pagina 93

Exercițiul 10 · Mulțimi finite cu același număr de elemente

Se consideră

A

și

B

două mulțimi,

n \in \mathbb N^*

și

|A| = |B| = n

. Justifică faptul că

f

surjectivă

\Leftrightarrow

f

injectivă.

Se consideră $A$ și $B$ două mulțimi, $n \in \mathbb N^*$ și $|A| = |B| = n$ . Justifică faptul că, pentru o funcție $f : A \to B$ , $f$ surjectivă $\Leftrightarrow$ $f$ injectivă.

Numără câte elemente are imaginea

f(A)

. Cel mult câte poate avea, și când le are pe toate?

1. Câte elemente are imaginea
$|A| = n$ înseamnă că $A$ are $n$ elemente: $A = \{a_1, a_2, \dots, a_n\}$ . Imaginea este mulțimea valorilor, $f(A) = \{f(a_1), f(a_2), \dots, f(a_n)\}$ . Ea are cel mult $n$ elemente, și exact $n$ dacă cele $n$ valori sunt distincte, adică dacă $f$ e injectivă (manual, p. 85).
Cu $A = \{1, 2, 3\}$ , $B = \{a, b, c\}$ , iată o funcție care nu e injectivă:
$f(1) = f(2) = a$ : două săgeți în același element. Elementul $b$ rămâne fără săgeată.
Verifică-te
În general, dacă două elemente diferite din $A$ au aceeași imagine, câte elemente poate avea cel mult $f(A)$ ?
2. Injectivă ⇒ surjectivă
Dacă $f$ este injectivă, valorile $f(a_1), \dots, f(a_n)$ sunt distincte, deci $f(A)$ are $n$ elemente. Totodată $f(A) \subseteq B$ , iar $B$ are tot $n$ elemente.
Verifică-te
De ce rezultă de aici că $f(A) = B$ ?
Deci $f(A) = B$ , adică $f$ este surjectivă (manual, p. 90).
3. Surjectivă ⇒ injectivă
Folosim reducerea la absurd (din capitolul 1). Presupunem că $f$ este surjectivă, dar nu este injectivă: există $a_i \ne a_j$ cu $f(a_i) = f(a_j)$ .
Atunci, ca la pasul 1, $f(A)$ are cel mult $n - 1$ elemente. Dar $f$ e surjectivă, deci $f(A) = B$ , care are $n$ elemente. Contradicție: $n \le n - 1$ este fals.
Presupunerea a fost greșită, deci $f$ este injectivă.
Ideea, pe scurt
Sunt $n$ săgeți (câte una din fiecare element al lui $A$ ) și $n$ ținte în $B$ . Fiecare țintă primește cel puțin o săgeată (surjectivă) exact atunci când nicio țintă nu primește două (injectivă).
4. Verificare prin numărare
Pentru $n = 3$ , cu $A = \{1, 2, 3\}$ și $B = \{a, b, c\}$ , sunt $3 \cdot 3 \cdot 3 = 27$ de funcții (fiecare element alege o imagine dintre $3$ ).
Verifică-te
Câte dintre ele sunt injective?
Dacă le scrii pe toate cele $27$ , vezi că și cele surjective sunt tot $6$ , și anume aceleași $6$ funcții: cele în care $a$ , $b$ , $c$ apar fiecare exact o dată.
Doar pentru mulțimi finite
Pe mulțimi infinite echivalența nu mai are loc. La exercițiul 2 (manual, p. 93), $g : \mathbb N \to \mathbb N$ , $g(n) = n + 1$ , este injectivă, dar nu e surjectivă: $0$ nu are preimagine.

Răspuns

Imaginea $f(A) = \{f(a_1), \dots, f(a_n)\}$ are exact $n$ elemente dacă $f$ este injectivă și cel mult $n - 1$ dacă nu este.

Dacă $f$ e injectivă, $f(A) \subseteq B$ are $n = |B|$ elemente, deci $f(A) = B$ : $f$ e surjectivă. Dacă $f$ e surjectivă, $f(A) = B$ are $n$ elemente, deci $f$ nu poate fi neinjectivă.

Exercițiul 10 · Mulțimi finite cu același număr de elemente

Se consideră AAA și BBB două mulțimi, n∈N∗n \in \mathbb N^*n∈N∗ și ∣A∣=∣B∣=n|A| = |B| = n∣A∣=∣B∣=n. Justifică faptul că, pentru o funcție f:A→Bf : A \to Bf:A→B, fff surjectivă ⇔\Leftrightarrow⇔ fff injectivă.

1. Câte elemente are imaginea ✓

2. Injectivă ⇒ surjectivă ✓

3. Surjectivă ⇒ injectivă ✓

4. Verificare prin numărare ✓

Se consideră $A$ și $B$ două mulțimi, $n \in \mathbb N^*$ și $|A| = |B| = n$ . Justifică faptul că, pentru o funcție $f : A \to B$ , $f$ surjectivă $\Leftrightarrow$ $f$ injectivă.

1. Câte elemente are imaginea

2. Injectivă ⇒ surjectivă

3. Surjectivă ⇒ injectivă

4. Verificare prin numărare