Relazioni

Corrispondenze e relazioni

Definizione 1.5

Siano e insiemi, una corrispondenza tra e è un sottoinsieme del prodotto cartesiano . Se , con e , diremo che è in corrispondenza biunivoca con oppure .

 


Definizione 1.6

Se diremo che è una relazione su .

 



Sia una funzione, se considero il suo grafico ovvero le coppie , questa è una corrispondenza.


Esempio 1.4

Sia e , e con . è una corrispondenza con .


Sia e e sia . è una corrispondenza in ma non è il grafico di una funzione da in , perché all'elemento vengono associati due elementi di .

 

Proprietà delle relazioni

  1. Una relazione si dice riflessiva se ogni è in relazione con se stesso, cioè se .
  2. Una relazione si dice simmetrica se, dati , implica .
  3. Una relazione si dice transitiva se e implicano .
  4. Una relazione si dice antisimmetrica se implica se e solo se .


L'unica relazione che è contemporaneamente riflessiva, simmetrica, transitiva e antisimmetrica è l'uguaglianza sull'insieme tale che ogni elemento è associato a se stesso.

Definizione 1.7

Una relazione riflessiva, simmetrica e transitiva si dice relazione di equivalenza.

 


Esempio 1.5

Se è l'insieme delle rette nel piano, la relazione che associa due rette se sono parallele è una relazione di equivalenza.

 


Esercizio 1.3

Sia un insieme finito e sia . Dimostrare che la relazione tale che se ha cardinalità pari è una relazione di equivalenza. Soluzione:

  1. è riflessiva, perché la differenza simmetrica di un insieme con se stesso è sempre uguale all'insieme vuoto, che ha cardinalità 0 che è pari.
  2. è simmetrica, infatti se , è pari, ma , quindi anche è pari e quindi .
  3. è transitiva. Considero tre sottoinsiemi di , . Se , allora ha cardinalità pari, e se , allora ha cardinalità pari.Scrivo come insiemi disgiunti.
    quindi chiamo
    quindi
    e chiamo
    quindi
    quindi
    Allora siccome , si ha che è la somma delle cardinalità degli insiemi che costituiscono e ma che non sono comuni ai due insiemi.
    ( e che compaiono sia in che in non vanno contate).
    allora, siccome per ipotesi e sono pari, si ha che la loro somma è pari:
    e siccome è pari, anche è pari, e si ha che
    cioè è pari.

cvd

 


Esercizio 1.4

Sia e la relazione tale che se è pari. Dimostrare che è una relazione di equivalenza.

  1. è riflessiva perché che è pari.
  2. è simmetrica perché implica pari, allora
    quindi se è pari, anche il suo opposto è pari, quindi .
  3. è transitiva, infatti implica è pari, implica è pari, allora
    è pari perché somma di numeri pari.

Se è tale che se è dispari, allora non è una relazione di equivalenza perché non è riflessiva.

 


Esempio 1.6

Sia e sia

non è una relazione di equivalenza perché non è riflessiva. Se aggiungo a le coppie e , la relazione non è riflessiva perché manca la coppia .

 


Definizione 1.8

Sia un insieme e sia una relazione su , cioè . Dico che è di equivalenza se e solo se il grafo è unione di grafi completi. Un grafo si dice completo se per ogni , la coppia .

 


Esempio 1.7

Sia . Sia

La relazione è riflessiva perché ci sono frecce entranti e uscenti dallo stesso vertice, inoltre è simmetrica perché si può andare da un vertice all'altro e poi tornare indietro, ed è transitiva.

 

Insieme quoziente

Definizione 1.9

Sia un insieme e sia una relazione di equivalenza su , e sia . La classe di equivalenza di per la relazione è l'insieme

Sono tutti e soli gli elementi in relazione con . Un elemento nella classe si dice rappresentante della classe di equivalenza.

 


Esempio 1.8

Sia la relazione di uguaglianza, allora .

 


Esempio 1.9

Sia , allora e sono equivalenti se è pari. Allora è l'insieme di tutti i numeri pari.

 


Esempio 1.10

Sia , e considero la relazione tale che se e solo se è pari. Allora è l'insieme degli insiemi con cardinalità pari.

 


Definizione 1.10

L'insieme quoziente è l'insieme costituito dalle classi di equivalenza al variare di .

 


Proposizione 1.1

Valgono le seguenti proprietà:

  1. La classe di equivalenza di un elemento non è mai vuota perché un elemento sta sempre nella sua classe di equivalenza per la riflessività.
  2. Siano , allora o o .Dim. Supponiamo che e non siano disgiunte, allora esiste ; prendo , allora , e per simmetria . Per transitività, siccome e per ipotesi, allora . Inoltre, , allora per simmetria, ma allora per transitività e implica . Quindi e . Per simmetria anche , cioè .
 


Esempio 1.11

Data la relazione tale che se è pari, segue che è la classe dei numeri pari.


La classe di equivalenza di 1 è formata dai numeri dispari. Queste sono le uniche due classi di equivalenza di questa relazione.

 


L'insieme è unione delle classi di equivalenza di , che costituiscono una partizione di e sono quindi disgiunte.

L'insieme quoziente NON è l'unione insiemistica delle classi di equivalenza, come mostrano i seguenti esempi:


Esempio 1.12

Nella relazione in cui se è pari, si hanno le classi (dei pari) e (dei dispari). L'insieme quoziente è

ed è un insieme di due elementi. Invece

 


Esempio 1.13

Nella relazione di uguaglianza ( è costituito da coppie di coordinate uguali), , e in questo caso

cioè è unione delle sue classi di equivalenza. L'insieme quoziente è

 

Relazioni d'ordine

Definizione 1.11

Sia un insieme e una relazione su , è una relazione d'ordine se è riflessiva, transitiva e antisimmetrica.

 


Esempio 1.14

Sia , e sia . è data dalle coppie tali che è divisibile per , cioè se per qualche . Questa è una relazione d'ordine, infatti:

  1. è riflessiva, perché .
  2. è transitiva, infatti date coppie e , allora dimostro che . con , con . Allora sommando le equazioni:
    allora è divisibile per .
  3. supponiamo che e che . Allora e , quindi
    allora ci sono due possibilità, o , o . Ma se , la relazione diventa la relazione di uguaglianza e quindi è antisimmetrica. Invece, se , con , segue che , e quindi si ottiene e quindi .

Se e è la relazione tale che se è divisibile per , di equivalenza è d'ordine solo se e diventa la relazione di uguaglianza.

 


La relazione d'ordine sui numeri reali, oltre alle tre proprietà richieste, ha un'altra proprietà: dati due numeri , o oppure (non possono avvenire entrambe le cose contemporaneamente oppure nessuna delle due). Questo non avviene nella relazione di divisibilità, infatti, nella relazione precedente, ponendo , e , si ha che rispetto a questa relazione d'ordine, non è in relazione con e non vale nemmeno il viceversa. Per questa relazione d'ordine due elementi possono essere incomparabili.

Altre relazioni in cui gli elementi sono incomparabili sono l'uguaglianza, oppure la relazione di inclusione tra insiemi, tale che e sono in relazione se .

 PrecedenteSuccessivo