CAPITOLO 3

Relazioni d'ordine e d'equivalenza

 

3.1 Insiemi ordinati e reticoli     3.2  Il lemma di Zorn ed una sua applicazione     3.3  Relazioni d'equivalenza e insiemi quoziente     3.4  Alcune osservazioni sulle funzioni     3.5  Esercizi

3.1  Insiemi ordinati e reticoli

Sia S un insieme non vuoto.

DEFINIZIONE 1 Un sottoinsieme  del prodotto cartesiano S×S prende il nome di relazione binaria in S o piú semplicemente relazione su S. Se la coppia (a,b) Î S×S appartiene ad Â, si dice che a é in relazione con b e si scrive a Âb; in questo caso si dice anche che a e b sono confrontabili rispetto ad Â. ¨

DEFINIZIONE 2 Una relazione  su S si dice d'ordine se sono verificate le seguenti tre proprietá: 
1. a Âa per ogni a Î S (proprietá riflessiva) 
2. a,b Î S, aÂb e bÂa Þ a = b (proprietá antisimmetrica) 
3. a,b,c Î S, aÂbÂc Þ aÂc (proprietá transitiva). 
Se  é una relazione d'ordine su S, la coppia (S, Â) si chiama insieme ordinato. La relazione  si dice di ordine totale se, per ogni a,b Î S, risulta aÂb o bÂa. In questo caso si dice che (S, Â) é un insieme totalmente ordinato o catena o anche insieme linearmente ordinato. ¨

Di solito le relazioni d'ordine si denotano con i seguenti simboli: £  ,  Í . Quando si usa la notazione £ , la scrittura a £ b si legge a minore o uguale a b.

ESERCIZIO 3 Sia £ una relazione d'ordine su S. Provare che la restrizione di £ ad ogni sottoinsieme non vuoto X di S é una relazione d'ordine su X (relazione d'ordine indotta).

ESEMPIO 4 Gli insiemi N_o,N,Z,Q,R con le usuali relazioni di minore o uguale sono insiemi totalmente ordinati. ¨

ESEMPIO 5 Siano p e s due partizioni di un insieme non vuoto S. Diciamo che p é piú fine di s, e scriviamo p £ s, se ogni blocco di p é contenuto in qualche blocco di s. La relazione £ é una relazione d'ordine nell'insieme P(S) di tutte le partizioni di S. ¨

ESERCIZIO 6 Sia £ una relazione d'ordine su S e si definisca su S la seguente relazione £ ^*

DEFINIZIONE 7 Per un sottoinsieme X di un insieme ordinato (S, £ ) si danno le definizioni riportate nel seguente schema:        

¨  

ESERCIZIO 8 Sia X un sottoinsieme non vuoto di un insieme ordinato (S, £ ). Provare che valgono le seguenti proprietá:

1. Un estremo inferiore (risp. superiore) di X, se esiste, é unico (e si denota con inf(X) (risp. max(X)).

2. Un minimo (risp. massimo) di X, se esiste, é unico (e si denota con min(X) (risp. max(X)).

3. Il minimo (risp. massimo) di X, se esiste, é l'estremo superiore (risp. inferiore) dei suoi minoranti (maggioranti).

DEFINIZIONE 9 Un insieme ordinato (S, £ ) si chiama reticolo se ogni suo sottoinsieme { a,b} con due elementi possiede l'estremo inferiore (che si denota con aÙb) e l'estremo superiore (che si denota con aÚb). Il minimo e il massimo di un reticolo, se esistono, si denotano rispettivamente con 0 e 1. ¨

ESERCIZIO 10 Provare che ogni insieme totalmente ordinato é un reticolo e calcolare aÙb e aÚb, per ogni coppia (a,b) di suoi elementi.

ESERCIZIO 11 Provare che N, ordinato con la relazione di divisibilitá, é un reticolo e calcolare aÙb e aÚb, per ogni coppia (a,b) di suoi elementi.

ESERCIZIO 12 Provare che l'insieme P(S) delle parti di un insieme S, ordinato con la relazione di inclusione, é un reticolo e calcolare XÙY e XÚY, per ogni coppia (X,Y) di suoi elementi (tale reticolo si chiama algebra di Boole dei sottoinsiemi di S).

ESERCIZIO 13 Provare che l'insieme P(S) delle partizioni di un insieme S, ordinato con la relazione di finezza, é un reticolo e calcolare pÙs e pÚs, per ogni coppia (X,Y) di suoi elementi (tale reticolo si chiama reticolo delle partizioni di S).

Un insieme ordinato finito si puó rappresentare graficamente sul piano mediante un disegno, che si chiama diagramma di Hasse, costruito nel seguente modo: si fa corrispondere iniettivamente ad ogni elemento dell'insieme un punto del piano in modo che se a £ b il punto che rappresenta a stia sotto quello che rappresenta b e si congiungono con una linea due punti se corrispondono a due elementi a,b tali che a £ b e non esiste alcun x ¹ a,b per cui a £ x £ b.

ESEMPIO 14 Nell'insieme N degli interi positivi la relazione  definita da

ESEMPIO 15 Sia X un insieme non vuoto e S = P(X) l'insieme delle parti di X. La relazione di inclusione fra sottoinsiemi di X é una relazione d'ordine su S. Per esempio, la figura  3.4  riporta il diagramma di Hasse dei sottoinsiemi di un insieme con tre elementi. ¨

3.2  Il lemma di Zorn ed una sua applicazione

DEFINIZIONE 1 Un insieme ordinato (S, £ ) si dice induttivo se ogni suo sottoinsieme totalmente ordinato é superiormente limitato. ¨

Per gli insiemi induttivi vale il seguente importante teorema, del quale omettiamo la dimostrazione.

TEOREMA 2 (lemma di Zorn) Ogni insieme induttivo é dotato di almeno un elemento massimale.

Mostriamo un'applicazione del lemma di Zorn agli spazi vettoriali. A tale scopo ricordiamo alcuni risultati e definizioni noti dal corso di Geometria I.

Sia V uno spazio vettoriale sopra un campo K. Ricordiamo le seguenti definizioni.

DEFINIZIONE 3 I vettori u₁ , u₂ , ... , u_n , n intero positivo, si dicono linearmente indipendenti, se

DEFINIZIONE 4 Un insieme X di vettori di V si dice libero se ogni suo sottoinsieme finito risulta linearmente indipendente; nel caso contrario si dice legato. Un sottoinsieme B di vettori di V si chiama base di V se é libero e massimale rispetto a questa proprietá. ¨

OSSERVAZIONE 5 Le nozioni di insieme linearmente indipendente e di insieme libero coincidono solo nel caso degli insiemi finiti. ¨

PROPOSIZIONE 6 Siano B una base di V e v Î V. Allora esiste un unico insieme finito u₁ , u₂ , ... , u_n di vettori di B tale che

DIMOSTRAZIONE.   E' lasciata per esercizio al Lettore. ¨

ESEMPIO 7 Nello spazio vettoriale Rⁿ, l'insieme finito B costituito dai vettori

ESEMPIO 8 Nello spazio vettoriale R[x] dei polinomi a coefficienti reali, l'insieme infinito

DEFINIZIONE 9 Uno spazio vettoriale si dice di dimensione finita se possiede una base finita. Nel caso contrario si dice di dimensione infinita.¨

TEOREMA 10 Siano V uno spazio vettoriale su un campo K e X un sottoinsieme libero di V. Allora esiste una base di V contenente X.

DIMOSTRAZIONE.   Sia L(X) l'insieme delle parti libere di V contenenti X. L(X) é non vuoto perché contiene X ed é un insieme ordinato rispetto alla relazione di inclusione.

Sia C un sottoinsieme di L(X) totalmente ordinato e osserviamo che

Resta cosí provato che L(X) é un insieme induttivo e quindi, per il lemma di Zorn, ammette un elemento massimale B.

B risulta un insieme libero e massimale fra tutti i sottoinsiemi liberi di V e contiene X. Allora B é una base di V e il nostro asserto é provato. ¨

COROLLARIO 11 Ogni spazio vettoriale su un campo ammette almeno una base.

OSSERVAZIONE 12 Nell'ipotesi che V sia finitamente generato, si puó costruire una base di V senza usare il lemma di Zorn. ¨

3.3  Relazioni d'equivalenza e insiemi quoziente

Sia S un insieme non vuoto.

DEFINIZIONE 1 Una relazione  su S si dice d'equivalenza se sono verificate le seguenti tre proprietá:

1. a Âa , per ogni a Î S (proprietá riflessiva)

2. a,b Î S , aÂb Þ bÂa (proprietá simmetrica)

3. a,b,c Î S , aÂbÂc Þ aÂc (proprietá transitiva). ¨

Di solito una relazione d'equivalenza si denota con uno dei simboli ~  ,  @  ,  @  ,  »  ,  º e due elementi di S che sono in relazione si dicono equivalenti.

ESEMPIO 2 Sia S l'insieme degli studenti presenti in un'aula. Le relazioni di nascita nello stesso anno, residenza in uno stesso comune, avere lo stesso nome, avere lo stesso voto all'esame di maturitá sono tutte relazioni d'equivalenza in S. ¨

ESEMPIO 3 Sia S un insieme non vuoto. In P(S) la relazione XÂY se, e solo se, X e Y sono equipotenti ¹  é d'equivalenza in P(S). ¨

ESERCIZIO 4 Sia n un intero. Provare che la relazione su Z definita da

Sia  una relazione d'equivalenza su un insieme S.

DEFINIZIONE 5 Per ogni elemento a Î S, si chiama classe d'equivalenza di a rispetto a  l'insieme di tutti gli elementi di S che sono nella relazione  con a. La classe d'equivalenza dell'elemento a si denota con Â[a] , o con [a]_ , o semplicemente con [a] se non vi é possibilitá di equivoci. ¨

Le classi d'equivalenza degli elementi di S verificano le seguenti proprietá:

· a Î [a];

· a Î [b]  Û   b Î [a];

· a ~ b   Û  [a] = [b];

· [a] Í [b]  Û  [a] = [b];

· a\not ~ b  Û  [a]Ç[b] = Æ;

· l'unione di tutte le classi d'equivalenza é uguale ad S;

· le classi d'equivalenza formano una partizione di S.

DEFINIZIONE 6 L'insieme i cui elementi sono le classi d'equivalenza di S rispetto ad  si chiama insieme quoziente di S rispetto ad  e si denota con S/ Â. L'applicazione suriettiva

OSSERVAZIONE 7 L'insieme quoziente S/Â é un sottoinsieme di P(S). ¨

ESERCIZIO 8 Sia  una relazione d'equivalenza su un insieme con un numero finito n di elementi. Si supponga che le classi d'equivalenza di  contengano tutte lo stesso numero di elementi m. Provare che m é un divisore di n.

ESERCIZIO 9 Sull'insieme S = Z×Z^* si consideri la seguente relazione Â:

3.4  Alcune osservazioni sulle funzioni

DEFINIZIONE 1 Siano S,T,U insiemi e f  :  S ®T, g  :  S ®U, h  :  U ®T tre funzioni. Se accade che f = gh, si dice che il diagramma

Sia f  : S® T un'applicazione tra due insiemi S,T e denotiamo con Â_f la relazione in S definita da

PROPOSIZIONE 2 La relazione Â_f é d'equivalenza in S.

DIMOSTRAZIONE.   E' lasciata per esercizio al Lettore. ¨

ESERCIZIO 3 Sia  una relazione d'equivalenza su un insieme non vuoto S. Provare che esiste una funzione f : S ®S tale che  = Â_f.

TEOREMA 4 Denotata con p la proiezione canonica di S su S/ Â_f, esiste un'unica applicazione iniettiva j  :  S/ Â_f ® T per cui é commutativo il seguente diagramma

DIMOSTRAZIONE.   Osserviamo che per definizione abbiamo:

aÂf b   Þ  f(a) = f(b).

Ne segue che é ben definita ²  la seguente applicazione:

j  :  [a]Âf Î S/ Âf  ®  f(a) Î T.

L'applicazione j verifica la proprietá f = pj ed é iniettiva. Sia ora g  :  S/ Â_f ® T un'applicazione tale che f = pg. Per ogni a Î S abbiamo

g([a]Âf) = g(p(a)) = f(a) = j([a]Âf),

e cioé g = j. ¨

COROLLARIO 5 Gli insiemi S/ Â_f e f(S) sono equipotenti.

Figure 3.6: Un esempio di funzione

ESEMPIO 6 Siano S = { 6,8,9,11,12,15,17,18} , T = { 0,1,2,3,4,5} ed f la funzione che ad ogni elemento a Î S associa il resto della divisione tra a e 6, che é un elemento di T. Allora risulta

S / Âf = { { 6,12,18} , { 8} , { 9,15} , { 11,17} }     e    f(S) = { 0,2,3,5}

e il risultato del precedente teorema puó visualizzarsi nella figura  3.6. ¨

ESERCIZIO 7 Siano n,k interi positivi, con n ³ k, e A,B due insiemi finiti d'ordine rispettivamente n e k. Provare che il numero delle funzioni suriettive di A su B é

k! S(n,k) ,

ove S(n,k) denota il numero di Stirling di secondo tipo di indici n e k.

3.5  Esercizi

1    Dire quali dei seguenti insiemi é limitato inferiormente e, in caso di risposta affermativa, calcolare l'estremo inferiore.

A = { n Î Z  :  n2 £ 36 }  ,  B = { n Î Z  :  n = 3a ,  a Î Z }  ,  C = { n Î Z  :  n2 £ 50n }  .

2    Disegnare il diagramma di Hasse dell'algebra di Boole (P(S), Í ) dei sottoinsiemi di un insieme S con 4 elementi e verificare che il duale (P(S), Í ) ha lo stesso diagramma. Si puó generalizzare questa proprietá?

3    Sia S = { (x,y) Î R²}, ove R denota il campo dei numeri reali. Sia  la relazione in S definita da

(x,y)Â(z,t)     Û    x2+y2 = z2+t2.

Provare che  é d'equivalenza in S e dare una descrizione geometrica delle sue classi d'equivalenza.

4    Sull'insieme R dei numeri reali si definisca la seguente relazione:

aÂb   Û    a-b   é un intero.

Provare che  é d'equivalenza e descriverne le relative classi d'equivalenza.

5    Provare che la relazione di similitudine sull'insieme di tutti i triangoli del piano é d'equivalenza.

6    Sia V^* l'insieme dei vettori non nulli di uno spazio vettoriale V su un campo. Provare che la relazione

u ~ v  Û  u ,v    appartengono ad uno stesso sottospazio di dimensione 1

é d'equivalenza in V^* e descrivere il corrispondente insieme quoziente.

 

---

Note:

¹  Due insiemi X,Y si dicono equipotenti se esiste una funzione biunivoca tra X e Y, e quindi una tra Y e X. Due insiemi finiti sono equipotenti se, e solo se, hanno lo stesso numero di elementi.

²  Questo significa che l'immagine della classe [a]_Âf non dipende dalla scelta dell'elemento a nella classe stessa.

---

File translated from T_EX by T_TH, version 2.51.
On 3 Mar 2002, 16:24.