Relazioni tra insiemi Flashcards
Definizione di relazione tra due insiemi S e T.
Siano S e T insiemi. Un sottoinsieme R di S × T e detto una relazione o corrispondenza tra S e T.
Se x ∈ S e y ∈ T sono tali che (x, y) ∈ R si scrive x R y e si dice che “x è nella relazione R con y”,
Definizione di relazione opposta tra insiemi S e T.
Se R e una relazione tra insiemi S e T, si definisce **relazione opposta **(o inversa di R) e si indica con R^op, la relazione tra T e S definita ponendo:
R^op := {(y, x) : (x, y) ∈ R}.
Definizione di funzione.
Con S e T insiemi, una relazione R tra S e T tale che ogni elemento x di S ha in T uno e un solo corrispondente è detta applicazione o funzione di S in T.
R applicazione di S in T : ⇐⇒ ∀x ∈ S, ∃! y ∈ T : x R y.
Definizione di funzione iniettiva.
Una funzione f : S → T è detta iniettiva se è tale che elementi distinti di S hanno immagini distinte in T:
f iniettiva ⇐⇒ (x1, x2 ∈ S, x1 != x2 ⇒ f(x1) != f(x2)).
Equivalentemente: f iniettiva ⇐⇒ (f(x1) = f(x2) con x1, x2 ∈ S ⇒ x1 = x2),
Definizione di funzione suriettiva.
Una funzione f : S → T è detta suriettiva se l’imma-
gine di f coincide con T, cioè f è tale che ogni elemento di T è corrispondente di almeno un elemento di S:
f suriettiva : ⇐⇒ f(S) = T ⇐⇒ (∀y ∈ T, ∃x ∈ S : f(x) = y).
Definizione di funzione biettiva.
Una funzione* f : S → T* è detta biettiva se è sia iniettiva che suriettiva.
Siano S e T insiemi finiti dello stesso ordine n. Allora un’applicazione f : S → T è iniettiva se e solo se è suriettiva.
Dare la dimostrazione.
Sia S = {x1, x2, . . . , xn}. Se f è iniettiva, gli elementi f(x1), f(x2), . . . , f(xn) sono a due a due distinti, sicché f(S) ha ordine n e dunque coincide con T. Pertanto f è suriettiva.
Viceversa, sia f suriettiva e dunque si abbia f(S) = T. Da (2.2.2) si ottiene allora |T| = |S| ≥ |f(S)| = |T|, quindi |f(S)| = |S| ed f è iniettiva.
