Definizioni

$f \subseteq S \times T$ è applicazione se $\forall x \in S$ $\exist ! y \in T : (x,y) \in f$ ($f(x) = y$)

$S$ è detto Dominio di $f$, $T$ è detto Codominio di $f$

Immagine: $Im(f) = \{ y \in T|(x,y) \in f \} = \{f(x)|x \in S \}$

Iniettiva, suriettiva, biettiva

• $f \subseteq S\times T$ è iniettiva se $\forall x_1, x_2 \in S$ con $x_1 \neq x_2 \Rightarrow f(x_1) \neq f(x_2)$
• $f \subseteq S \times T$ è suriettiva se $Im(f) = T$ cioè se $\forall y \in T, \exist x \in S : f(x) = y$
• è biettiva se è sia iniettiva che suriettiva

Proposizione

Dati $S$, $T$ finiti e non vuoti

• $\exist f:S \rightarrow T$ iniettiva $\Leftrightarrow |S| \le |T|$
• $\exist f: S \rightarrow T$ suriettiva $\Leftrightarrow |S| \ge |T|$
• $\exist f: S \rightarrow T$ biettiva $|S| = |T|$

Controimmagine, composizione, inversa

Controimmagine: $f^{-1}(Y) = \{ x \in S|f(x) \in Y \} = \{ x \in S|(x,y) \in f$ per qualche $y \in Y \}$ ($Y \subseteq T$)

Composizione: $f \subseteq S \times T, g \subseteq T \times W$ $(g \circ f)(x) = g(f(x))$ , con $g \circ f \subseteq S \times W$

La composizione non è commutativa, ma è associativa