Relazioni A
volte si possono stabilire legami fra elementi di uno stesso insieme,
tra elementi di insiemi diversi o tra insiemi. Tali legami si dicono relazioni binarie perchè legano due elementi.
Esempi di relazione
Sono quelli di appartenenza o di inclusione:
aA esprime che a è elemento di A,
A B, B A esprimono che A è contenuto in B e che B è contenuto in A.
Dalla validità della doppia inclusione, segue che
A = B.
In generale, una relazione si indica con erre corsivo o con , erre gotica.
Se due elementi a e b dello stesso insieme E sono legati dalla stessa relazione , si scrive
ab.
Proprietà delle relazioni Se è una relazione sull'insieme E, si dice che essa gode delle proprietà
1)-riflessiva, se e soltanto se xE : xx;
2)-simmetrica, se e soltanto se xE, yE xy yx;
3)-transitiva, se e soltanto se xE, yE, zE xy yz xz.
Si dice che è una relazione di equivalenza sull'insieme E, se e soltanto se essa gode contemporaneamente delle proprietà suddette, cioè:
è una relazione di equivalenza sull'insieme E è riflessiva, simmetrica e transitiva.
Se è una relazione di equivalenza sull'insieme E ed aE, si può considerare la parte di E, indicata con C(a), costituita da quegli elementi xE che sono in relazione con aE, cioè
A tale sottoinsieme di E si dà il nome di classe di equivalenza relativa all'elemento a.
La proprietà riflessiva permette di asserire che la classe di equivalenza relativa all'elemento a non è vuota, perchè contiene almeno l'elemento a, cioè
C(a) ≠ .
Proprietà delle classi di equivalenza
1)-Dato l'insieme E, ogni suo elemento appartiene ad una classe di equivalenza, cioè
xE : x C(x).
2)-Assegnati l'insieme E, a e b elementi di E, se risulta ab, segue che xE : xa se e solo se xb, cioè se
aE, bE, xE ab,
xa xb.
Dimostrazione Essendo per ipotesi
ab, xa,
per la proprietà simmetrica, si ha
ba, ax,
per la proprietà transitiva
bx,
ed infine, per la proprietà simmetrica, risulta
xb,
come volevasi dimostrare.
Viceversa, è noto per ipotesi che
ab, xb,
per la proprietà simmetrica, si ha
ab, bx,
per la proprietà transitiva
ax,
ed infine, per la proprietà simmetrica, risulta
xa,
come volevasi dimostrare.
3)-Assegnati
l'insieme E, a e b elementi di E non equivalenti, segue che la classe
di equivalenza relativa ad a è distinta da quella relativa a b, cioè
non hanno elementi comuni, in altri termini
a non equivalente a b C(a) C(b) distinte xE xC(a) xC(b).
Infatti, ragionando per assurdo, si supponga che esiste un elemento x comune alle due classi, cioè che
xE xC(a) xC(b) xE xa xb xE ax xb
xE ab,
e ciò è contro l'ipotesi. Dunque, le due classi di equivalenza non hanno elementi comuni, cioè sono disgiunte. Nota bene Se
si considerano le classi di equivalenza degli elementi di un insieme E,
esse costituiscono una partizione di tale insieme. Quindi, le
classi di equivalenza sono elementi di un nuovo insieme chiamato
insieme quoziente dell'insieme E relativo alla relazione di equivalenza
, e si indica con
In altri termini:
Relazione d'ordine Si consideri un insieme E ed una sua relazione ; la relazione si chiama relazione d'ordine nell'insieme E, se sono soddisfatte le seguenti due condizioni:
1)-xE, yE, zE xy yz xz,
2)-xE, yE, xy yx x = y.
L'insieme E munito di tale relazione d'ordine, si chiama ordinato. Esaminando la proprietà b), se per l'insieme E è verificata la condizione xy v yx, allora la relazione si chiama di totale ordine, cioè
xE, yE : yx v xy.
L'insieme E munito di tale relazione d'ordine, si chiama totalmente ordinato.
Legge di composizione interna Assegnato un insieme E, si dice che in E è assegnata una legge
di composizione interna, se è assegnato un procedimento secondo il
quale ad ogni coppia ordinata (a, b) di elementi di E è associato un
unico elemento c di E. Se si considera l'insieme N dei numeri interi naturali, la legge di composizione interna è l'addizione, quindi
aN, bN è associato cN c = a + b.
Applicazioni composte Si considerino le applicazioni
di modo che alla prima, ad ogni elemento di E, corrisponda un elemento di F ed alla seconda, ad ogni elemento di f, corrisponda un elemento di G. A tal punto, si considera la relazione intercorrente fra gli elementi di E e G che sia verificata da xE ed yG, cioè
y = g(f(x)).
In altri termini, y è il corrispondente di f(x) mediante l'applicazione g. Si può quindi affermare che ad ogni xE rimane associato uno ed un solo elemento appartenente a G, cioè
xE : y = g(f(x)).
Si può pertanto definire una nuova applicazione che, ad ogni elemento di E, fa corrispondere un elemento di G, cioè:
In
tal modo, si è associato alla coppia ordinata di applicazioni (f, g)
un'altra applicazione h, si dice quindi che h è uguale a g composto f e
si scrive
h = g ο f,
o semplicemente
g·f oppure gf.
Quindi, ad ogni elemento x di E, il corrispondente è
h(x) = (g ο f)(x) = g(f(x)).
Si considerino le applicazioni
e si indichi con l il loro composto, scrivendo pertanto
l = h ο g ο f = hgf.
La nuova applicazione l è così definita:
Proprietà associativa del prodotto operativo dell'applicazione Si considerino le applicazioni
si dimostra che:
h ο (g ο f) = (h ο g) ο f.
Infatti, per definizione,
xE : (g ο f)(x) = g(f(x)), xE : (h ο g)(x) = h(g(x)).
Si osserva ora che,
xE : h ο (g ο f)(x) = h ο g(f(x)) = h(g(f(x)) = (h ο g)f(x) = (h ο g) ο f(x),
quindi risulta
h ο (g ο f) = (h ο g) ο f,
come volevasi dimostrare.
Considerate le surgezioni
si dimostra che anche l'applicazione composta
è surgettiva. Siccome per ipotesi f e g sono surgettive, risulta
f(E) = F e g(F) = G;
si deve dimostrare che g ο f è surgettiva, cioè
(g ο f)(E) = G.
Infatti,
(g ο f)(E) = g(f(E)) = g(F) = G.
Considerate le ingezioni
si dimostra che anche l'applicazione composta
è ingettiva. Siccome per ipotesi f e g sono ingettive, risulta che se
xE, yE x ≠ y : f(x) ≠ f(y) xE, yE x ≠ y : g(f(x)) ≠ g(f(y))
xE, yE x ≠ y : (g ο f)(x) ≠ (g ο f)(y),
e ciò dimostra che l'applicazione composta g ο f è ingettiva.
Avendo dimostrato che g ο f è surgettiva ed ingettiva, per definizione essa è bigettiva.
Considerata la bigezione
si definisce un'altra bigezione, indicata con f, che fa corrispondere ad ogni elemento di F un elemento di E, cioè
Considerate le bigezioni
ha senso parlare di applicazione inversa dell'applicazione composta g ο f, cioè dell'applicazione
Inoltre, ha anche senso parlare delle applicazioni inverse di f e g, cioè di
Si dimostra che l'applicazione inversa di g ο f e uguale al prodotto dell'inversa di f per l'inversa di g, cioè
(gf)-1 = f-1g-1.
E' noto che
(gf)(gf)-1 = iG g-1(gf)(gf)-1 = g-1iG. (1)
Si è potuto considerare l'applicazione composta mediante g-1 perchè
Applicando la proprietà associativa all'uguaglianza (1), si ha: