Relazioni tra insiemi

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

1 - Introduzione alle relazioni

Definizione: relazione $n$-aria

Dati $n\ge 1$ insiemi non vuoti $A_0,A_1,\dots ,A_{n-1}$, si definisce relazione $n$-aria o relazione di grado $n$ e si denota "$\mathcal{R}$" un sottoinsieme del prodotto cartesiano tra tutti gli insiemi:

$$\mathcal{R}\subseteq A_0\times A_1\times \dots \times A_{n-1}$$

Ogni insieme $A_0,A_1,\dots ,A_{n-1}$ viene detto dominio di $\mathcal{R}$.

Se gli insiemi $A_0,A_1,\dots ,A_{n-1}$ coincidono tutti con uno stesso insieme $A$, si parla di relazione $n$-aria su $A$.

Inoltre, quando $n=1$, oltre a “relazione unaria” si parla anche di predicato, mentre quando $n=2$, oltre a “relazione binaria”, si parla anche semplicemente di “relazione” e, dati due elementi $a\in A_0$ e $b\in A_1$, si scrive:

$$a\mathcal{R}b$$

invece di $(a,b)\in \mathcal{R}$.

Esempio: relazione binaria tra due insiemi

Dati due insiemi:

$$\begin{array}{rl}& A=\{1,2,3\}\\ & B=\{3,4,5\}\end{array}$$

Una loro possibile relazione è:

$$\mathcal{R}=\{(1,3),(3,3),(2,4)\}\subseteq A\times B$$

Esempio: gli ordinamenti sono relazioni binarie

Le usuali operazioni di ordine sui numeri naturali $\mathbb{N}$ sono relazioni binarie su $\mathbb{N}$ (es. l’ordine non-decrescente $\le$ è una relazione binaria e la coppia $(2,7)$ è un elemento di tale relazione perché $2\le 7$, mentre la coppia $(5,1)$ non lo è).

Inoltre, essendo una relazione binaria, si può notare come solitamente si scriva $2\le 7$ anziché $(2,7)\in \le$.

Osservazione: database relazionali come relazioni $n$-arie

I database relazionali sono esempi di relazioni $n$-arie dove:

• $n$ è il numero di colonne.
• Ogni colonna rappresenta l’insieme degli oggetti che compaiono (o possono comparire) in tale colonna.
• Il database visto come relazione è un sottoinsieme del prodotto cartesiano dei suddetti insiemi.
• Ogni riga costituisce una $n$-upla di tale prodotto cartesiano che dichiariamo appartenere alla relazione.

In altre parole: la tabella di un database è una rappresentazione grafica di una relazione $n$-aria in cui vengono esplicitamente elencati gli elementi (ovvero le $n$-uple) di tale relazione.

Esempio: database relazionale come relazione $n$-aria

Consideriamo il seguente (ipotetico) database dell’anagrafe:

Cognome	Nome	Data di nascita	Luogo di nascita
Rossi	Mario	05/10/1976	Firenze
Verdi	Luigi	25/01/2001	Torino
Bianchi	Carla	22/06/1983	Napoli
Neri	Marco	19/03/1969	Milano

In termini di relazioni, questo database si può considerare come una relazione quaternaria (cioè con $n=4$):

$$\mathcal{R}\subseteq A\times B\times C\times D$$

dove:

• $A$: è l’insieme di tutti i cognomi.
• $B$: è l’insieme di tutti i nomi.
• $C$: è l’insieme di tutte le date di nascita.
• $D$: è l’insieme di tutti i luoghi di nascita.

Le righe forniscono l’elenco completo delle $4$-uple che sono elementi di $\mathcal{R}$, ad esempio:

$$⟨\text{Neri, Marco, 19/03/1969, Milano}⟩\in \mathcal{R}$$

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

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

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

1.2 - Rappresentazioni grafiche delle relazioni con il piano cartesiano

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

1.3 - Dominio e immagine di una relazione

1.3.1 - Rappresentazioni grafiche di dominio e immagine tramite diagrammi di Eulero-Venn

1.4 - Relazione inversa

Definizione: relazione inversa

Dati due insiemi $A$ e $B$ e una loro relazione binaria $\mathcal{R}\subseteq A\times B$, si definisce relazione inversa di $\mathcal{R}$ e si indica con "${\mathcal{R}}^{-1}$" un sottoinsieme del prodotto cartesiano $B\times A$:

$${\mathcal{R}}^{-1}=\{(b,a)\in B\times A\mid (a,b)\in \mathcal{R}\}\subseteq B\times A$$

In altre parole, per ogni $b\in B$ e per ogni $a\in A$ si ha:

$$b{\mathcal{R}}^{-1}a⟺a\mathcal{R}b$$

Esempio

Se $\mathcal{R}$ è la relazione $\le$ di minore o uguale su $\mathbb{N}$, allora ${\mathcal{R}}^{-1}$ sarà la relazione $\ge$ di maggiore o uguale su $\mathbb{N}$ perché:

$$a\le b⟺b\ge a$$

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

1.5 - Proprietà delle relazioni binarie

Definizione: proprietà delle relazioni binarie

Dati un insieme $A$ e una relazione binaria $\mathcal{R}$ su $A$ (cioè $\mathcal{R}\subseteq A^2$), essa può avere le seguenti proprietà:

• Riflessività: $\forall a\in A(a\mathcal{R}a)$.
• Irriflessività: $\forall a\in A(\neg (a\mathcal{R}a))$.
• Simmetria: $\forall a,b\in A(a\mathcal{R}b⟹b\mathcal{R}a)$.
• Antisimmetria: $\forall a,b\in A(a\mathcal{R}b\wedge b\mathcal{R}a⟹a=b)$.
• Transitività: $\forall a,b,c\in A(a\mathcal{R}b\wedge b\mathcal{R}c⟹a\mathcal{R}c)$.
• Totalità: $\forall a,b\in A(a\mathcal{R}b\vee b\mathcal{R}a)$.

Osservazione: relazione simmetrica solo se $\mathcal{R}={\mathcal{R}}^{-1}$

Dati un insieme $A$ e una relazione binaria $\mathcal{R}$ su $A$ (cioè $\mathcal{R}\subseteq A^2$), $\mathcal{R}$ è simmetrica se e solo se $\mathcal{R}={\mathcal{R}}^{-1}$, ovvero se:

$$\forall (a,b)\in A^2(a\mathcal{R}b⟺a{\mathcal{R}}^{-1}b)$$

Relazione	Riflessività	Simmetria	Transitività	Totalità
Relazione di equivalenza	✅	✅	✅	➖
Relazione di ordine	✅	❌	✅	➖
Relazione di ordine totale	✅	❌	✅	✅
Relazione di successione immediata	✅	❌	✅	➖
Relazione di ordine stretto	❌	➖	✅	➖
Relazione di pre-ordine	✅	➖	✅	➖

1.5.1 - Rappresentazioni grafiche delle proprietà delle relazioni

2 - Relazioni di equivalenza

Definizione: relazione di equivalenza

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

• Riflessività: $\forall a\in A(a\mathcal{R}a)$.
• Simmetria: $\forall a,b\in A(a\mathcal{R}b⟹b\mathcal{R}a)$.
• Transitività: $\forall a,b,c\in A(a\mathcal{R}b\wedge b\mathcal{R}c⟹a\mathcal{R}c)$.

Esempio: relazione di divisibilità per $n$ tra due interi

Dato un numero naturale $n\in \mathbb{N}$, un numero intero $x\in \mathbb{Z}$ si dice divisibile per $n$ e si denota con "$n|x$" se esiste un $k\in \mathbb{Z}$ tale che $k\cdot n=x$. Si può definire una relazione di equivalenza sull’insieme dei numeri interi $\mathbb{Z}$ affermando che, dati due elementi $x,y\in \mathbb{Z}$, $x$ è in relazione a $y$ se la loro differenza è divisibile per $n$:

$$x\sim y⟺n|(x-y)$$

Si può dimostrare che questa è una relazione di equivalenza verificando le tre proprietà:

1. Riflessività: $n|(x-x)⟹n|0$ vale, perché $0$ è divisibile per qualsiasi numero naturale $n$.
2. Simmetria: $n|(x-y)⟹n|(y-x)$ vale, perché se $x-y$ è divisibile per $n$, allora è divisibile anche il suo opposto $y-x$ (es. $2|(12-6)⟹2|(6-12)$, con $n=2,x=12,y=6$).
3. Transitività: $n|(x-y),n|(y-z)⟹n|(x-z)$ vale, perché se $x-y$ e $y-z$ sono divisibili per $n$, lo è anche $x-z$ (es. $2|(12-6),2|(6-4)⟹2|(12-4)$, con $n=2,x=12,y=6,z=4$).

Notazioni alternative per le relazioni di equivalenza

Oltre al simbolo "$\sim$", spesso per denotare le relazioni di equivalenza si usano le lettere $\mathcal{E}$, $\mathcal{F}$, ecc., oppure simboli che, in qualche misura, richiamano la relazione d’uguaglianza, quali ad esempio "$\equiv$", "$\simeq$", "$\cong$", "$\approx$", ecc.

Definizione: classe di equivalenza

Dati un insieme $A$ e una relazione di equivalenza $\sim$ su $A$, la classe di equivalenza di un elemento $a\in A$ rispetto alla relazione di equivalenza $\sim$, indicata con "$[a{]}_{\sim }$", è l’insieme degli elementi di $A$ che hanno la relazione di equivalenza $\sim$ con $a$:

$$[a{]}_{\sim }=\{x\in A\mid x\sim a\}$$

Quando la relazione $\sim$ è chiara dal contesto, si può scrivere anche solo $[a]$ al posto di $[a{]}_{\sim }$.

Definizione: insieme quoziente

Dati un insieme $A$ e una relazione di equivalenza $\sim$ su $A$, l’insieme delle classi di equivalenza $[a{]}_{\sim }$ si dice insieme quoziente di $X$ per la relazione $\sim$ e si indica con "$A/\sim$":

$$A/\sim =\{[a{]}_{\sim }\mid a\in A\}$$

Esempio: relazione di equivalenza su automobili con stesso colore

Dati un insieme $A$ e una relazione di equivalenza $\sim$ su $A$ letta come “ha lo stesso colore di”, allora una classe di equivalenza $[a{]}_{\sim }$ può essere quella che comprende tutte le automobili verdi, mentre l’insieme quoziente $A/\sim$ è l’insieme dei colori delle automobili.

Esempio: insieme $\mathbb{Q}$ dei numeri razionali come insieme quoziente

L’insieme $\mathbb{Q}$ dei numeri razionali può essere espresso come un insieme quoziente. Data una coppia $(p,q)$ ottenuta dal prodotto cartesiano $\mathbb{Z}\times (\mathbb{Z}\setminus \{0\})$ (quindi $p$ può essere qualsiasi numero intero, mentre $q$ qualsiasi numero intero eccetto lo $0$), si può definire una relazione di equivalenza come:

$$(p,q)\sim (p^{\prime },q^{\prime })⟺p{q}^{\prime }=p^{\prime }q$$

Ciò è verificabile se si interpreta la coppia $(p,q)$ come una frazione $\frac{p}{q}$, quindi questa relazione di equivalenza indica che due frazioni sono in relazione tra loro se sono uguali il prodotto tra il numeratore di uno e il denominatore dell’altro: $\frac{p}{q}=\frac{p^{\prime }}{q^{\prime }}⟺p{q}^{\prime }=p^{\prime }q$ (es. prendendo le frazioni $\frac{2}{3}$ e $\frac{4}{6}$, si può constatare che $2\cdot 6=3\cdot 4$). Se si prende l’insieme quoziente di questa relazione, ossia $[\mathbb{Z}\times (\mathbb{Z}\setminus \{0\})]/\sim$, si può notare come esso corrisponda proprio all’insieme $\mathbb{Q}$ dei numeri razionali perché comprende tutte le combinazioni possibili di numeri presenti in $\mathbb{Q}$.

Osservazione: $(A/\sim )\subseteq \mathcal{P}(A)$

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

$$(A/\sim )\subseteq \mathcal{P}(A)$$

Per costruzione, infatti, ogni elemento di $A/\sim$ è una classe di equivalenza $[a{]}_{\sim }$, e ogni classe di equivalenza è un sottoinsieme di $A$. Quindi:

$$\forall a\in A([a{]}_{\sim }\subseteq A)$$

Poiché $A/\sim$ è formato unicamente dalle classi di equivalenza, ogni elemento di $A/\sim$ è un sottoinsieme di $A$.

L’insieme delle parti $\mathcal{P}(A)$ è definito come l’insieme di tutti i sottoinsiemi di $A$ e, dal momento che ogni classe di equivalenza è un sottoinsieme di $A$, si ha che $A/\sim \subseteq \mathcal{P}(A)$.

Esempio: campionato di serie A come insieme quoziente

Dato un insieme $X$ di tutti i giocatori di squadre di serie A e una relazione binaria $\mathcal{R}$ su $X$ stabilendo che due giocatori $a,b\in X$ sono in relazione ($a\mathcal{R}b$) se e solo se $a$ e $b$ giocano nella stessa squadra.

La relazione $\mathcal{R}$ è chiaramente riflessiva, simmetrica e transitiva, quindi è una relazione di equivalenza su $X$. Le classi di equivalenza sono le squadre del campionato di serie A, mentre il quoziente $X/\mathcal{R}$ consiste nel campionato di serie A, ossia è l’insieme delle squadre che giocano in quel campionato.

Esempio: regioni italiane come insieme quoziente

Dato un insieme $X$ di tutti i comuni italiani e una relazione binaria $\mathcal{R}$ su $X$ stabilendo che due comuni $a,b\in X$ sono in relazione ($a\mathcal{R}b$) se e solo se $a$ e $b$ si trovano nella stessa regione.

La relazione $\mathcal{R}$ è chiaramente riflessiva, simmetrica e transitiva, quindi è una relazione di equivalenza su $X$. Le classi di equivalenza sono le regioni italiane, mentre il quoziente $X/\mathcal{R}$ consiste nell’insieme di tutte le regioni italiane.

Proposizione: due classi di equivalenza o sono disgiunte o coincidono

Data una relazione di equivalenza $\sim$ su un insieme $A$ e due elementi $a,b\in A$, se $a\sim b$, allora $[a{]}_{\sim }=[b{]}_{\sim }$:

$$a\sim b⟹[a{]}_{\sim }=[b{]}_{\sim }$$

Inoltre, se $a\nsim b$, cioè se $\neg (a\sim b)$, allora $[a{]}_{\sim }\cap [b{]}_{\sim }=\varnothing$:

$$a\nsim b⟹[a{]}_{\sim }\cap [b{]}_{\sim }=\varnothing$$

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

Esempio: relazione di congruenza modulo $3$

Consideriamo l’insieme $A=\{0,1,2,3,4,5\}$ e la relazione di equivalenza $\sim$ definita dalla congruenza modulo $3$:

$$a\sim b⟺a\equiv b(\text{mod}3)$$

Questo significa che due numeri sono equivalenti se hanno lo stesso resto quando divisi per $3$.

Le classi di equivalenza, in base alla relazione $\sim$, sono i gruppi di numeri che danno lo stesso resto modulo $3$. Ecco le classi di equivalenza possibili:

• $[0{]}_{\sim }=\{0,3\}$ perché $0\equiv 3(\text{mod}3)$.
• $[1{]}_{\sim }=\{1,4\}$ perché $1\equiv 4(\text{mod}3)$.
• $[2{]}_{\sim }=\{2,5\}$ perché $2\equiv 5(\text{mod}3)$.

Verifichiamo la proposizione quindi in entrambi i casi:

• Se $a\sim b$, allora le classi di equivalenza $[a{]}_{\sim }$​ e $[b{]}_{\sim }$​ devono essere uguali. Ad esempio:
  • Se $a=0$ e $b=3$, allora $0\sim 3$, quindi $[0{]}_{\sim }=[3{]}_{\sim }=\{0,3\}$.
  • Se $a=1$ e $b=4$, allora $1\sim 4$, quindi $[1{]}_{\sim }=[4{]}_{\sim }=\{1,4\}$.
  In entrambi i casi, le classi di equivalenza coincidono.
• Se $a\nsim b$, allora le classi di equivalenza $[a{]}_{\sim }$​ e $[b{]}_{\sim }$​ sono disgiunte, cioè non hanno elementi in comune. Ad esempio, se $a=0$ e $b=1$, allora $0\nsim 1$, quindi $[0{]}_{\sim }=\{0,3\}$ e $[1{]}_{\sim }=\{1,4\}$ e possiamo vedere che $[0{]}_{\sim }\cap [1{]}_{\sim }=\varnothing$ In questo caso, le classi di equivalenza sono disgiunte.

2.1 - Relazioni di equivalenza e partizioni

Osservazione: insieme quoziente $A/\sim$ partizione di $A$

Data una relazione di equivalenza $\sim$ su un insieme $A$, l’insieme quoziente $A/\sim$ è una partizione di $A$, infatti:

• Ogni $[a{]}_{\sim }\subseteq A$ è non vuota.
• Due classi di equivalenza distinte sono disgiunte (per la proposizione precedente).
• Per ogni $a\in A$, si ha $a\in [a{]}_{\sim }\in A/\sim$.

Viceversa, data una partizione $\mathcal{C}$ di A, la relazione $\sim$ su $A$ definita da:

$$a\sim b⟺a,b\text{appartengono allo stesso}X\in \mathcal{C}$$

è una relazione di equivalenza su $A$, ovvero è riflessiva, simmetrica e transitiva (se $a,b\in X\in \mathcal{C}$ e $b,c\in Y\in \mathcal{C}$, allora $X=Y$ poiché $b\in X\cap Y$ e $\mathcal{C}$ è una partizione: perciò $a,c\in X\in C$), e $A/\sim =\mathcal{C}$.

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

3 - Relazioni di ordine

Definizione: relazione di ordine

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

• Riflessività: $\forall a\in A(a\le a)$.
• Antisimmetria: $\forall a,b\in A(a\le b\wedge b\le a⟹a=b)$.
• Transitività: $\forall a,b,c\in A(a\le b\wedge b\le c⟹a\le c)$.

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

$$(A,\le )$$

Esempio: ordine non-decrescente $\le$ è una relazione di ordine

Un esempio canonico per la relazione di ordine è l’ordine non-decrescente $\le$ su $\mathbb{N}$, cioè l’insieme:

$$\{(n,m)\in {\mathbb{N}}^2\mid n\le m\}$$

Analogamente, $\le$ è un ordine anche sugli insiemi $\mathbb{Z}$, $\mathbb{Q}$ ed $\mathbb{R}$.

Notazioni alternative per le relazioni di ordine

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

3.1 - Relazione di ordine totale

Definizione: relazione di ordine totale

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

$$\forall a,b\in A(a\le b\vee b\le a)$$

3.2 - Relazione di successione immediata e diagrammi di Hasse

Definizione: relazione di successione immediata

Dato un insieme ordinato $(A,\le )$, un elemento $y\in A$ è un successore immediato di $x\in A$ (e $x$ è un predecessore immediato di $y$), in simboli $x⊲y$, se:

$$x\le y\wedge x\ne y\wedge \forall z\in A(x\le z\wedge z\le y⟹z=x\vee z=y)$$

3.3 - Massimi e minimi di un ordine

Definizione: massimo e minimo di un ordine

Dato un insieme ordinato $(A,\le )$, un elemento $a\in A$ si dice:

• Massimo (rispetto a $\le$) se $\forall b\in A(b\le a)$.
• Minimo (rispetto a $\le$) se $\forall b\in A(a\le b)$.

Esempi

L’ordine $\le$ su $\mathbb{N}$ ha minimo (il numero $0$), ma non ha massimo. L’ordine $\le$ su $\mathbb{Z}$ non ha né minimo, né massimo. L’ordine $\le$ sull’intervallo $(0;1]:=\{x\in R\mid 0<x\le 1\}$ ha massimo (il numero $1$) ma non ha minimo. L’ordine $\subseteq$ su $\mathcal{P}(A)$ ha minimo (l’insieme $\varnothing$) e massimo (l’insieme $A$), poiché $\varnothing \subseteq B\subseteq A$ per ogni $B\subseteq A$.

3.4 - Relazione di ordine stretto

Definizione: relazione di ordine stretto

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

• Irriflessività: $\forall a\in A(\neg (a<a))$.
• Transitività: $\forall a,b,c\in A(a<b\wedge b<c⟹a<c)$.

3.5 - Relazione di pre-ordine

Definizione: relazione di pre-ordine

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

• Riflessività: $\forall a\in A(a\precsim a)$.
• Transitività: $\forall a,b,c\in A(a\precsim b\wedge b\precsim c⟹a\precsim c)$.

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

$$(A,\precsim )$$

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 $(A,\precsim )$ e un sottoinsieme $X\subseteq A$:

• Un maggiorante di $X$ è un elemento $a\in A$ tale che $\forall x\in X(x\precsim a)$.
• Un minorante di $X$ è un elemento $a\in A$ tale che $\forall x\in X(a\precsim x)$.
• Un estremo superiore di $X$, denotato con "$\sup X$", è un elemento $a\in A$ che è maggiorante di $X$ e tale che, per ogni $b\in A$, se $b$ è un maggiorante di $X$, allora $a\precsim b$.
• Un estremo inferiore di $X$, denotato con "$\inf X$", è un elemento $a\in A$ che è minorante di $X$ e tale che, per ogni $b\in A$, se $b$ è un minorante di $X$, allora $b\precsim a$.

3.5.2 - Massimi e minimi di un pre-ordine

Definizione: massimo e minimo di un pre-ordine

Dato un insieme parzialmente ordinato $(A,\precsim )$, un elemento $a\in A$ si dice:

• Massimo (rispetto a $\precsim$) se $\forall b\in A(b\precsim a)$.
• Minimo (rispetto a $\precsim$) se $\forall b\in A(a\precsim b)$.

4 - Reticoli

Definizione: reticolo

Un reticolo è un insieme parzialmente ordinato non vuoto $(R,\precsim )$ in cui, per ogni coppia di elementi $x,y\in R$, esistono un estremo superiore $\sup \{x,y\}$ e un estremo inferiore $\inf \{x,y\}$.

4.1 - Algebra reticolare

Definizione: algebra reticolare

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

• $\forall x,y(x\wedge y=y\wedge x)$ e $\forall x,y(x\vee y=y\vee x)$.
• $\forall x,y,z(x\wedge (y\wedge z)=(x\wedge y)\wedge z)$ e $\forall x,y,z(x\vee (y\vee z)=(x\vee y)\vee z)$.
• $\forall x,y((x\vee y)\wedge y=y)$ e $\forall x,y((x\wedge y)\vee y=y)$.

5 - Grafi

Definizione: grafo

Un grafo è una coppia ordinata $(V,E)$ dove:

• $V$: è un insieme non vuoto i cui elementi sono detti vertici.
• $E$: è una relazione binaria su $V$ che è simmetrica e irriflessiva, cioè $\forall v\in V(\neg (vEv))$.

Se due vertici $v,w\in V$ soddisfano la relazione binaria $vEw$, essi si dicono adiacenti.

Fonti

• Lezioni dei Prof. Chen Yu e Terracini Lea del corso di Matematica Discreta (canale C), Corso di Laurea in Informatica presso l’Università di Torino, A.A. 2023-24.
• Lezioni del Prof. Radeschi Marco del corso di Algebra Lineare (canale C), Corso di Laurea in Informatica presso l’Università di Torino, A.A. 2023-24.
• 🏫 Lezioni e slide del Prof. Viale Matteo del corso di Logica Matematica (canale B), Corso di Laurea in Informatica presso l’Università di Torino, A.A. 2024-25:
  • 2.2 - Relazioni_moodle.pdf