Premessa

Ciao! Se è la prima volta che capiti su questo sito, ti consiglio di consultare la pagina principale di questo cosiddetto Giardino Digitale per scoprire meglio cos’è e come navigarlo.

Lo stato di questa nota è al momento: 🔴 Bozza.


Le relazioni tra insiemi descrivono i legami che possono esistere tra due o più insiemi. Queste relazioni sono fondamentali in teoria degli insiemi.

1 - Introduzione alle relazioni

Definizione: relazione -aria

Dati insiemi non vuoti , si definisce relazione -aria o relazione di grado e si denota "" un sottoinsieme del prodotto cartesiano tra tutti gli insiemi:

Nel caso di una relazione sottoinsieme di una potenza -sima , si parla di relazione -aria su :

Inoltre, quando , oltre a “relazione unaria” si parla anche di predicato, mentre quando , oltre a “relazione binaria”, si parla anche semplicemente di “relazione” e, dati due elementi e , si scrive:

invece di .

1.1 - Rappresentazioni grafiche delle relazioni con i diagrammi di Eulero-Venn

Le relazioni -arie si possono rappresentare graficamente tramite i diagrammi di Eulero-Venn.

Una relazione -aria su uno stesso insieme si può rappresentare o come una generica relazione -aria su “copie” dell’insieme , oppure come insieme di frecce tra i punti della stessa copia di .

1.2 - Rappresentazioni grafiche delle relazioni con il piano cartesiano

Esattamente come il prodotto cartesiano si può rappresentare sul piano cartesiano, anche le relazioni -arie si possono rappresentare su quest’ultimo essendo sottoinsiemi del prodotto.

1.3 - Relazione inversa

Definizione: relazione inversa

Dati due insiemi e e una loro relazione binaria , si definisce relazione inversa di e si indica con "" un sottoinsieme del prodotto cartesiano :

In altre parole, per ogni e per ogni si ha:

Esempio

Se è la relazione di minore o uguale su , allora sarà la relazione di maggiore o uguale su perché:

1.3.1 - Rappresentazione grafica di una relazione inversa tramite diagrammi di Eulero-Venn

1.4 - Proprietà delle relazioni binarie

Definizione: proprietà delle relazioni binarie

Dati un insieme e una relazione binaria su (cioè ), essa può avere le seguenti proprietà:

  • Riflessività: .
  • Irriflessività: .
  • Simmetria: .
  • Antisimmetria: .
  • Transitività: .
  • Totalità: .

Osservazione: relazione simmetrica solo se

Dati un insieme e una relazione binaria su (cioè ), è simmetrica se e solo se , ovvero se:

RelazioneRiflessività
SimmetriaTransitivitàTotalità
Relazione di equivalenza
Relazione di ordine
Relazione di ordine totale
Relazione di successione immediata
Relazione di ordine stretto
Relazione di pre-ordine

1.4.1 - Rappresentazioni grafiche delle proprietà delle relazioni

2 - Relazioni di equivalenza

Definizione: relazione di equivalenza

Dato un insieme , si definisce relazione di equivalenza su e si denota con "" una relazione binaria che rispetta le seguenti proprietà:

  • Riflessività: .
  • Simmetria: .
  • Transitività: .

Notazioni alternative per le relazioni di equivalenza

Oltre al simbolo "", spesso per denotare le relazioni di equivalenza si usano le lettere , , ecc., oppure simboli che, in qualche misura, richiamano la relazione d’uguaglianza, quali ad esempio "", "", "", "", ecc.

Definizione: classe di equivalenza

Dati un insieme e una relazione di equivalenza su , la classe di equivalenza di un elemento rispetto alla relazione di equivalenza , indicata con "", è l’insieme degli elementi di che hanno la relazione di equivalenza con :

Quando la relazione è chiara dal contesto, si può scrivere anche solo al posto di .

Definizione: insieme quoziente

Dati un insieme e una relazione di equivalenza su , l’insieme delle classi di equivalenza si dice insieme quoziente di per la relazione e si indica con "":

Osservazione:

Dati un insieme e una relazione di equivalenza su , l’insieme quoziente è una famiglia di sottoinsiemi di , cioè è un sottoinsieme dell’insieme delle parti di :

Per costruzione, infatti, ogni elemento di è una classe di equivalenza , e ogni classe di equivalenza è un sottoinsieme di . Quindi:

Poiché è formato unicamente dalle classi di equivalenza, ogni elemento di è un sottoinsieme di .

L’insieme delle parti è definito come l’insieme di tutti i sottoinsiemi di e, dal momento che ogni classe di equivalenza è un sottoinsieme di , si ha che .

Proposizione: due classi di equivalenza o sono disgiunte o coincidono

Data una relazione di equivalenza su un insieme e due elementi , se , allora :

Inoltre, se , cioè se , allora :

In particolare, due classi di equivalenza o sono disgiunte o coincidono.

2.1 - Relazioni di equivalenza e partizioni

Osservazione: insieme quoziente partizione di

Data una relazione di equivalenza su un insieme , l’insieme quoziente è una partizione di , infatti:

  • Ogni è non vuota.
  • Due classi di equivalenza distinte sono disgiunte (per la proposizione precedente).
  • Per ogni , si ha .

Viceversa, data una partizione di A, la relazione su definita da:

è una relazione di equivalenza su , ovvero è riflessiva, simmetrica e
transitiva (se e , allora poiché e è una partizione: perciò ), e .

Quindi, in sostanza, si può concludere che partizioni su e insiemi quozienti di sono la stessa cosa.

3 - Relazioni di ordine

Definizione: relazione di ordine

Dato un insieme , una relazione di ordine su (o, più semplicemente, un ordine o un ordinamento su ) è una relazione che rispetta le seguenti proprietà:

  • Riflessività: .
  • Antisimmetria: .
  • Transitività: .

L’insieme è detto ordinato e, per esplicitarne la relazione di ordine che insiste su di esso, si può scrivere come:

Notazioni alternative per le relazioni di ordine

Oltre al simbolo "", spesso per denotare le relazioni di ordine si usano altri simboli che in qualche misura gli somigliano, come "", "", "", "", ecc.

3.1 - Relazione di ordine totale

Definizione: relazione di ordine totale

Dato un insieme , una relazione di ordine su si dice totale (o lineare) se:

3.2 - Relazione di successione immediata e diagrammi di Hasse

Definizione: relazione di successione immediata

Dato un insieme ordinato , un elemento è un successore immediato di (e è un predecessore immediato di ), in simboli , se:

3.3 - Massimi e minimi di un ordine

Definizione: massimo e minimo di un ordine

Dato un insieme ordinato , un elemento si dice:

  • Massimo (rispetto a ) se .
  • Minimo (rispetto a ) se .

3.4 - Relazione di ordine stretto

Definizione: relazione di ordine stretto

Dato un insieme , una relazione binaria su si dice stretta se rispetta le seguenti proprietà:

  • Irriflessività: .
  • Transitività: .

3.5 - Relazione di pre-ordine

Definizione: relazione di pre-ordine

Dato un insieme , una relazione di pre-ordine su (o relazione di quasi-ordine) è una relazione che rispetta le seguenti proprietà:

  • Riflessività: .
  • Transitività: .

L’insieme è detto parzialmente ordinato e, per esplicitarne la relazione di ordine che insiste su di esso, si può scrivere come:

3.5.1 - Maggioranti e minoranti in una relazione di pre-ordine

Definizione: maggiorante, minorante, estremo superiore ed estremo inferiore

Dato un insieme parzialmente ordinato e un sottoinsieme :

  • Un maggiorante di è un elemento tale che .
  • Un minorante di è un elemento tale che .
  • Un estremo superiore di , denotato con "", è un elemento che è maggiorante di e tale che, per ogni , se è un maggiorante di , allora .
  • Un estremo inferiore di , denotato con "", è un elemento che è minorante di e tale che, per ogni , se è un minorante di , allora .

3.5.2 - Massimi e minimi di un pre-ordine

Definizione: massimo e minimo di un pre-ordine

Dato un insieme parzialmente ordinato , un elemento si dice:

  • Massimo (rispetto a ) se .
  • Minimo (rispetto a ) se .

4 - Reticoli

Definizione: reticolo

Un reticolo è un insieme parzialmente ordinato non vuoto in cui, per ogni coppia di elementi , esistono un estremo superiore e un estremo inferiore .

4.1 - Algebra reticolare

Definizione: algebra reticolare

Un’algebra reticolare è un insieme dotato di due operazioni binarie e per cui valgano le seguenti proprietà:

  • e .
  • e .
  • e .

5 - Grafi

Definizione: grafo

Un grafo è una coppia ordinata dove:

  • : è un insieme non vuoto i cui elementi sono detti vertici.
  • : è una relazione binaria su che è simmetrica e irriflessiva, cioè .

Se due vertici soddisfano la relazione binaria , essi si dicono adiacenti.


Fonti

  • 🏫 Corso di Laurea in Informatica (L-31 R) presso l’Università di Torino:
    • Corso di Matematica Discreta, Algebra e Geometria - parte di Matematica Discreta & Algebra (parte 1) - canale C, A.A. 2023-24 (pagina Moodle):
      • Lezioni in aula dei Proff. Chen Yu e Terracini Lea.
    • Corso di Matematica Discreta, Algebra e Geometria - parte di Algebra Lineare & Geometria (parte 2) - canale C, A.A. 2023-24 (pagina Moodle):
      • Lezioni in aula del Prof. Radeschi Marco.
    • Corso di Logica Matematica, A.A. 2022-23 (pagina Moodle):
      • Slide dei Proff. Andretta Alessandro, Motto Ros Luca e Viale Matteo: