Sia \(n \geq 1\). Una relazione \(n\)-aria è un sottoinsieme di un prodotto cartesiano della forma \(A_{0} \times \dots \times A_{n-1}\). Se gli insiemi \(A_{0} , \dotsc, A_{n-1}\) sono tutti lo stesso insieme \(A\), parleremo di relazione \(n\)-aria su \(A\).
Se \(n = 1\) parleremo di relazione unaria o predicato, se \(n = 2\) parleremo di relazione binaria, se \(n = 3\) parleremo di relazione ternaria, ecc...
Sia \(R \subseteq A_{0} \times \dots \times A_{n-1}\) una relazione \(n\)-aria. Diciamo che gli elementi \(a_{0}, \dotsc, a_{n-1}\) sono in relazione \(R\) se \((a_{0}, \dotsc, a_{n-1}) \in R\).
Spesso le relazioni binarie si dicono semplicemente relazioni e si scrive \[a \mathrel{R} b\]
invece di \(( a , b ) \in R\).
Dominio e immagine di relazioni binarie
Sia \(R\subseteq A\times B\) una relazione binaria.
Il sottoinsieme di \(A\) definito da
\(\mathrm{dom}(R)=\{a\in A \mid (a,b)\in R\) per qualche \(b \in B\}\)
è detto dominio della relazione \(R\).
Il sottoinsieme di \(B\) definito da
\(\mathrm{rng}(R)=\{b\in B \mid (a,b)\in R\) per qualche \(a \in A\}\)
è detto range o immagine della relazione \(R\).
Relazione inversa
Se \(R \subseteq A \times B\) è una relazione (binaria), allora la relazione inversa di \(R\), che indichiamo con \(R^{-1}\) e che è ancora una relazione binaria, è il sottoinsieme di \(B \times A\) definito da \[R^{-1} = \{ (b,a) \in B \times A \mid (a,b) \in R \}.\]
In altre parole, per ogni \(b \in B\) e \(a \in A\) si ha
\(b \mathrel{R}^{-1} a\) se e solo se \(a \mathrel{R} b\).
Chiaramente per ogni relazione binaria \(R\)
\((R^{-1})^{-1} = R,\) \(\mathrm{rng}(R^{-1})=dom(R),\) \(dom(R^{-1})=\mathrm{rng}(R).\)
Esempio
Se \(R\) è la relazione \(\leq\) di minore o uguale su \(\mathbb{N}\), allora \(R^{-1}\) è la relazione \(\geq\) di maggiore o uguale su \(\mathbb{N}\).
Alcune proprietà
Diremo che una relazione (binaria) \(R\) su un insieme \(A\) è
se \(a \mathrel{R} a\) per ogni \(a \in A\);
se da \(a \mathrel{R} b\) segue che \(b \mathrel{R} a\);
se da \(a \mathrel{R} b\) e \(b \mathrel{R} a\) segue che \(a = b\);
se da \(a \mathrel{R} b\) e \(b \mathrel{R} c\) segue che \(a \mathrel{R} c\).
Osservazione: Una relazione \(R\) su un insieme \(A\) è simmetrica se e solo se \(R = R^{-1}\), ovvero se per ogni \((a,b) \in A^2\)
\(a \mathrel{R} b\) se e solo se \(a \mathrel{R}^{-1} b\).
Inoltre, \(R\) è riflessiva/simmetrica/antisimmetrica/transitiva se e solo se \(R^{-1}\) lo è.
Una relazione di equivalenza su \(A\) è una relazione (binaria) riflessiva, simmetrica e transitiva su \(A\).
Oltre ad utilizzare lettere maiuscole come \(E\), \(F\), ecc..., per indicare relazioni d’equivalenza spesso useremo simboli che in qualche misura richiamano la relazione d’uguaglianza, quali ad esempio
\(\equiv\) \(\sim\) \(\simeq\) \(\cong\) \(\approx\) \(\dotsc\)
Quando vorremo esplicitare l’insieme \(A\) su cui è definita la relazione d’equivalenza \(E\) scriveremo \(\langle A, E \rangle\).
Classi di equivalenza e insieme quoziente
Sia \(E\) una relazione di equivalenza su \(A\). La classe di equivalenza di un elemento \(a \in A\) rispetto ad \(E\) è \[{\boldsymbol [}{a}{\boldsymbol ]}_{E} \stackrel{\text{def}}{=}\left \{x \in A \boldsymbol\mid x \mathrel{E} a \right\}.\]
Quando la relazione \(E\) è chiara dal contesto, si può scrivere solo \({\boldsymbol [}{a}{\boldsymbol ]}\) invece di \({\boldsymbol [}{a}{\boldsymbol ]}_{E}\).
L’insieme quoziente è l’insieme di tutte le classi di equivalenza: \[A / E \stackrel{\text{def}}{=}\left \{ {\boldsymbol [}{a}{\boldsymbol ]}_{E} \boldsymbol\mid a \in A \right\}.\]
L’insieme quoziente è una famiglia di sottoinsiemi di \(A\), cioè \(A / E \subseteq \mathscr{P} ( A )\).
Esempio: campionato di serie A
Sia \(X\) l’insieme di tutti i giocatori di squadre di serie \(A\). Definiamo ora una relazione binaria \(E\) sull’insieme \(X\) stabilendo che \(a \mathrel{E} b\) se e solo se \(a\) e \(b\) giocano nella stessa squadra.
La relazione \(E\) è chiaramente riflessiva, simmetrica e transitiva, quindi è una relazione di equivalenza su \(X\).
Le classi di equivalenza sono le squadre del campionato di serie \(A\).
Il quoziente \(X/E\) consiste nel campionato di serie \(A\), ossia è l’insieme delle squadre che giocano in quel campionato.
Esempio: le regioni
Sia \(X\) l’insieme di tutti i comuni italiani. Definiamo ora una relazione binaria \(E\) sull’insieme \(X\) stabilendo che \(a \mathrel{E} b\) se e solo se \(a\) e \(b\) si trovano nella stessa regione.
La relazione \(E\) è chiaramente riflessiva, simmetrica e transitiva, quindi è una relazione di equivalenza su \(X\).
Le classi di equivalenza sono le regioni italiane.
Il quoziente \(X/E\) consiste nell’insieme di tutte le regioni italiane.
Esempio: congruenza modulo \(2\)
Dati due interi \(a,b \in \mathbb{Z}\), \(a\) è congruente a \(b\) modulo \(2\) se \(a-b\) è un numero pari (ovvero se \(a-b = 2 \cdot k\) per qualche \(k\in\mathbb{Z}\)). In questo caso scriviamo \[a \equiv b (\mathrm{mod}\ 2)\] La relazione di congruenza modulo \(2\) è una relazione di equivalenza:
\(a-a = 0\) è pari, quindi \(a \equiv a (\mathrm{mod}\ 2)\).
\(b-a = - (a-b)\), quindi \(a - b\) è pari se e solo se \(b - a\) lo è.
\(a-c = (a-b) + (b-c)\), per cui se \(a - b\) e \(b - c\) sono pari, allora anche \(a - c\) lo è.
Esempio: congruenza modulo \(2\)
Ci sono due classi di equivalenza per questa relazione:
i numeri pari, ossia \([0]=\{n \mid n-0=n\) è pari \(\}\),
i numeri dispari, ossia \([1]=\{n \mid n-1\) è pari \(\}\),
Dunque l’insieme quoziente risultante \[\mathbb{Z}_{2} \stackrel{\text{def}}{=}\{[0],[1]\}\] ha esattamente \(2\) elementi.
Esempio: congruenza modulo \(n\)
Più in generale, dato \(0 \neq n \in \mathbb{N}\) e due interi \(a,b \in \mathbb{Z}\), \(a\) è congruente a \(b\) modulo \(n\) se \(a-b\) è un multiplo di \(n\) (ovvero se \(a-b = n \cdot k\) per qualche \(k \in \mathbb{Z}\)). In questo caso scriviamo \[a \equiv b (\mathrm{mod}\ n)\] La relazione di congruenza modulo \(n\) è una relazione di equivalenza:
\(a-a = 0\) è sempre multiplo di \(n\), quindi \(a \equiv a (\mathrm{mod}\ n)\).
\(b-a = - (a-b)\), quindi \(a \equiv b (\mathrm{mod}\ n)\) se e solo se \(b \equiv a (\mathrm{mod}\ n)\).
\(a-c = (a-b) + (b-c)\), per cui se \(a \equiv b (\mathrm{mod}\ n)\) e \(b \equiv c (\mathrm{mod}\ n)\) allora \(a \equiv c (\mathrm{mod}\ n)\).
Esempio: congruenza modulo \(n\)
Ciascuna classe di equivalenza rispetto alla relazione di congruenza modulo \(n\) è del tipo \[[k] = \left \{a \in \mathbb{Z} \boldsymbol\mid \text{la divisione intera di a per n ha resto k} \right\}\] per qualche \(k \in \{ 0, \dotsc, n-1 \}\).
Dunque l’insieme quoziente risultante \[\mathbb{Z}_{n} \stackrel{\text{def}}{=}\left \{[k] \boldsymbol\mid 0 \leq k \leq n-1 \right\}\] ha esattamente \(n\) elementi.
Sia \(E\) una relazione d’equivalenza su \(A\) e consideriamo \(a,b \in A\). Se \(a \mathrel{E} b\) allora \([a]_{E} = [b]_{E}\), mentre se \(a \not\mathrel{E} b\) allora \([a]_{E} \cap [b]_{E} = \emptyset\). In particolare, due classi di equivalenza sono disgiunte o coincidono.
Supponiamo \(a \mathrel{E} b\). Sia \(c \in {\boldsymbol [}{a}{\boldsymbol ]}_{E}\): allora \(c \mathrel{E} a\) e per la proprietà transitiva \(c \mathrel{E} b\), quindi \(c \in {\boldsymbol [}{b}{\boldsymbol ]}_{E}\). Essendo \(c\) arbitrario, abbiamo dimostrato che \({\boldsymbol [}{a}{\boldsymbol ]}_{E} \subseteq {\boldsymbol [}{b}{\boldsymbol ]}_{E}\). Sia ora \(c \in {\boldsymbol [}{b}{\boldsymbol ]}_{E}\): allora \(c \mathrel{E} b\). Per la proprietà simmetrica \(b \mathrel{E} a\), da cui \(c \mathrel{E} a\) per la proprietà transitiva: quindi \(c \in {\boldsymbol [}{a}{\boldsymbol ]}_{E}\). Segue che \({\boldsymbol [}{b}{\boldsymbol ]}_{E} \subseteq {\boldsymbol [}{a}{\boldsymbol ]}_{E}\). Per il principio della doppia inclusione abbiamo quindi \({\boldsymbol [}{a}{\boldsymbol ]}_{E} = {\boldsymbol [}{b}{\boldsymbol ]}_{E}\).
Supponiamo ora \(a \not\mathrel{E} b\). Verifichiamo che in questo caso \({\boldsymbol [}{a}{\boldsymbol ]}_{E} \cap {\boldsymbol [}{b}{\boldsymbol ]}_{E} = \emptyset\). Supponiamo, per assurdo, che ci sia un \(c \in {\boldsymbol [}{a }{\boldsymbol ]}_{E} \cap {\boldsymbol [}{b}{\boldsymbol ]}_{E}\). Allora \(c \mathrel{E} b\), da cui \(b \mathrel{E} c\) per simmetria. Inoltre \(c \mathrel{E} a\), quindi \(b \mathrel{E} a\) per transitività, e \(a \mathrel{E} b\) per simmetria. Ma questo contraddice la nostra assunzione che \(a \not\mathrel{E} b\).
Partizioni
Una partizione di un insieme \(A \neq \emptyset\) è una famiglia \(\mathcal{C}\) di sottoinsiemi non vuoti di \(A\), a due a due disgiunti, che ricoprono \(A\), cioè
se \(X \in \mathcal{C}\) allora \(\emptyset\neq X \subseteq A\),
se \(X , Y \in \mathcal{C}\) e \(X \neq Y\) allora \(X \cap Y = \emptyset\),
ogni elemento di \(A\) appartiene a qualche \(X \in \mathcal{C}\).
Ad esempio, sia \(A = \mathbb{Z}\), \(\mathbb{P}\) la collezione degli interi pari e \(\mathbb{D}\) la collezione degli interi dispari. Allora \[\mathcal{C} = \{ \mathbb{P}, \mathbb{D} \}\] è una partizione di \(\mathbb{Z}\) poichè
\(\mathbb{P} \neq \emptyset\) e \(\mathbb{D} \neq \emptyset\);
\(\mathbb{P} \cap \mathbb{D} = \emptyset\);
ogni \(k \in \mathbb{Z}\) è pari o dispari, quindi \(\mathbb{Z} = \mathbb{P} \cup \mathbb{D}\).
Una partizione di un insieme \(A \neq \emptyset\) è una famiglia \(\mathcal{C}\) di sottoinsiemi non vuoti di \(A\), a due a due disgiunti, che ricoprono \(A\), cioè
se \(X \in \mathcal{C}\) allora \(\emptyset\neq X \subseteq A\),
se \(X , Y \in \mathcal{C}\) e \(X \neq Y\) allora \(X \cap Y = \emptyset\),
ogni elemento di \(A\) appartiene a qualche \(X \in \mathcal{C}\).
Se \(E\) è una relazione di equivalenza su \(A\), allora il quoziente \(A / E\) è una partizione di \(A\): ogni \({\boldsymbol [}{a}{\boldsymbol ]}_{E} \subseteq A\) è non vuota, due classi di equivalenza distinte sono disgiunte (Proposizione precedente) e per ogni \(a \in A\) si ha \(a \in {\boldsymbol [}{a}{\boldsymbol ]}_{E} \in A/E\).
Viceversa, data una partizione \(\mathcal{C}\) di \(A\), la relazione \(E\) su \(A\) definita da
\(a \mathrel{E} b\) se e solo se \(a\) e \(b\) 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 \mathcal{C}\)), e \(A/E = \mathcal{C}\).
Quindi partizioni su \(A\) e insiemi quozienti di \(A\) (rispetto a una qualche relazione di equivalenza su \(A\)) sono la stessa cosa!
Esempio
Sia \(\mathcal{C} = \{ \mathbb{P}, \mathbb{D} \}\) la partizione di \(\mathbb{Z}\) in numeri pari e dispari. Consideriamo la relazione di congruenza modulo \(2\) su \(\mathbb{Z}\), e sia \(\mathbb{Z}_{2}\) lo spazio quoziente. Allora \[\mathcal{C}= \mathbb{Z}_{2}.\] Infatti \(\mathbb{Z}_{2} = \{ [0], [1] \}\) e
\([0] = \mathbb{P}\) e \([1] = \mathbb{D}.\)
Esercizi su relazioni d’equivalenza (1)
Consideriamo la relazione \(E\) su \(\mathbb{R}\) definita da
\(x \mathrel{E} y\) se e solo se \(|x| = |y|\).
Dimostrare che \(E\) è una relazione d’equivalenza.
Siano \(x,y,z\) elementi arbitrari di \(\mathbb{R}\).
Ovvio, \(x \mathrel{E} x\) perchè \(|x|=|x|\).
Anche questo è facile: se \(x \mathrel{E} y\) allora \(|x| = |y|\), quindi anche \(y \mathrel{E} x\) perchè \(|y| = |x|\).
Supponiamo che \(x \mathrel{E} y\) e \(y \mathrel{E} z\): vogliamo dimostrare che \(x \mathrel{E} z\). Dalla prima condizione otteniamo \(|x| = |y|\), mentre dalla seconda \(|y| = |z|\): quindi \(|x|=|y|=|z|\), ovvero \(x \mathrel{E} z\).
Consideriamo la relazione di equivalenza \(E\) su \(\mathbb{R}\) definita da
\(x \mathrel{E} y\) se e solo se \(|x| = |y|\).
Come sono fatte le classi di equivalenza di \(E\)?
Sono del tipo \([r]_{E} = \{ r, - r \}\) per \(r \in \mathbb{R}\).
Quanti elementi ha ciascuna di tali classi?
Due elementi distinti se \(r \neq 0\), uno solo se \(r = 0\).
Quante classi di equivalenza distinte otteniamo?
Infinite, una per ogni \(r \geq 0\).
Com’è fatto l’insieme quoziente \(\mathbb{R}/E\)? \(\mathbb{R}/E = \{ \{ r,-r \} \mid r \in \mathbb{R} \}\).
Esercizi su relazioni d’equivalenza (2)
Consideriamo la relazione \(E\) su \(\mathbb{N}\) definita da \[\begin{aligned} n \mathrel{E} m \text{ se e solo se } n \text{ ed } m & \text{ hanno lo stesso numero di cifre} \\ & \text{ (in notazione decimale)}. \end{aligned}\] Dimostrare che \(E\) è una relazione d’equivalenza.
Siano \(n,m,l\) elementi arbitrari di \(\mathbb{N}\).
Ovvio, \(n \mathrel{E} n\) poichè ciascun numero si scrive con lo stesso numero di cifre di se stesso.
Ovvio, se \(n \mathrel{E} m\) vuol dire che \(n\) ha lo stesso numero di cifre di \(m\): quindi anche \(m \mathrel{E} n\), ovvero \(m\) ha lo stesso numero di cifre di \(n\).
Se \(n \mathrel{E} m\) e, in particolare, \(n\) e \(m\) hanno entrambi \(k\) cifre, e inoltre \(m \mathrel{E} l\), ovvero \(m\) e \(l\) hanno hanno lo stesso numero di cifre, allora anche \(l\) ha \(k\) cifre, per cui \(n \mathrel{E} l\).
Consideriamo la relazione di equivalenza \(E\) su \(\mathbb{N}\) definita da \[\begin{aligned} n \mathrel{E} m \text{ se e solo se } n \text{ ed } m & \text{ hanno lo stesso numero di cifre} \\ & \text{ (in notazione decimale)}. \end{aligned}\]
Come sono fatte le classi di equivalenza di \(E\)?
Sono del tipo \(C_{k} = \{ n \in \mathbb{N} \mid \text{n ha esattamente k}\) cifre } per \(k \in \mathbb{N} \setminus \{ 0 \}\). Più precisamente, \(C_{1} = \{ 0,1,2,3,4,5,6,7,8,9\}\) e \(C_{k} = \{ n \in \mathbb{N} \mid 10^{k-1} \leq n < 10^k \}\) se \(k \geq 2\).
Quanti elementi ha ciascuna di tali classi?
\(C_{k}\) ha \(10\) elementi se \(k = 1\), e ne ha \(9 \cdot 10^{k-1}\) se \(k > 1\).
Quante classi di equivalenza distinte otteniamo?
Infinite, una per ogni \(k \in \mathbb{N} \setminus \{ 0 \}\).
Com’è fatto l’insieme quoziente \(\mathbb{N}/E\)?
\(\mathbb{N}/E = \{ C_{k} \mid k \in \mathbb{N} \setminus \{ 0 \} \}\).
Esercizi su relazioni d’equivalenza (3)
Sia
\(\mathrm{Fin} = \{ X \subseteq \mathbb{N} \mid X\) è finito \(\}\) .
Consideriamo la relazione \(\approx\) su \(\mathrm{Fin}\) definita da
\(X \approx Y\) se e solo se \(X\) e \(Y\) hanno lo stesso numero di elementi.
Dimostrare che \(\approx\) è una relazione d’equivalenza.
Siano \(X,Y,Z\) arbitrari elementi di \(\mathrm{Fin}\).
Ovvio, ogni \(X\) ha lo stesso numero di elementi di se stesso.
Ovvio, se \(X \approx Y\) allora \(X\) e \(Y\) hanno lo stesso numero di elementi, quindi anche \(Y \approx X\).
Se \(X\) e \(Y\) hanno entrambi \(k\) elementi, e inoltre \(Y\) e \(Z\) hanno lo stesso numero di elementi, allora anche \(Z\) ha \(k\) elementi, da cui \(X \approx Z\).
Sia \(\mathrm{Fin} = \{ X \subseteq \mathbb{N} \mid X\) è finito \(\}\). Consideriamo la relazione di equivalenza \(\approx\) su \(\mathrm{Fin}\) definita da
\(X \approx Y\) se e solo se \(X\) e \(Y\) hanno lo stesso numero di elementi.
Come sono fatte le classi di equivalenza di \(\approx\)?
Sono del tipo \(I_{k} = \{ X \in \mathrm{Fin} \mid \text{X ha k}\) elementi} per \(k \in \mathbb{N}\). In particolare, \(I_{0} = \{ \emptyset \}\), \(I_{1} = \{ \{n \} \mid n \in \mathbb{N} \}\), \(I_{2} = \{ \{ n,m \} \mid n,m \in \mathbb{N}, n \neq m \}\) e così via.
Quanti elementi ha ciascuna di tali classi?
\(I_{0}\) ha un solo elemento, mentre tutte le altre classi \(I_{k}\) con \(k \geq 1\) ne hanno infiniti.
Quante classi di equivalenza distinte otteniamo?
Infinite, una per ogni \(k \in \mathbb{N}\).
Com’è fatto l’insieme quoziente \(\mathrm{Fin}/\approx\)?
\(\mathrm{Fin}/{\approx} = \{ I_{k} \mid k \in \mathbb{N} \}\).
Una relazione d’ordine su \(A\) (o, più semplicemente, un ordine o un ordinamento su \(A\)) è una relazione riflessiva, antisimmetrica e transitiva su \(A\).
L’esempio canonico di ordinamento è la relazione \(\leq\) su \(\mathbb{N}\), cioè l’insieme \[\left \{( n , m ) \in \mathbb{N}^2 \boldsymbol\mid n \leq m \right\}.\] Analogamente \(\leq\) è un ordinamento sugli insiemi \(\mathbb{Z}\), \(\mathbb{Q}\) e \(\mathbb{R}\).
Per indicare relazioni d’ordine spesso useremo, oltre a \(\leq\), simboli che in qualche misura gli somigliano, come
\(\preceq\) \(\unlhd\) \(\precsim\) \(\sqsubseteq\) \(\dotsc\)
Quando vorremo esplicitare l’insieme \(A\) su cui è definito l’ordine \(\preceq\) scriveremo \(\langle A, \preceq \rangle\). Questa notazione è comoda per distingure, ad esempio, l’ordine sui numeri naturali \(\langle \mathbb{N}, \leq \rangle\) dall’ordine sui numeri interi \(\langle \mathbb{Z} , \leq \rangle\).
Come disegnare (alcuni tipi di) ordini Dato un ordine \(\leq\) su \(A\) diciamo che \(y\) è un successore immediato di \(x\) se \[x \leq y \mathbin{ \wedge} x \neq y \mathbin{ \wedge } \forall z ( x \leq z \mathbin{ \wedge } z \leq y \to z = x \mathbin{ \vee } z = y ) .\] e lo disegniamo così
L’ordine lineare con tre elementi è descritto da
o dal diagramma di Hasse
L’ordinamento \(\leq\) su \(\mathbb{N}\), \(\mathbb{Z}\), \(\mathbb{Q}\) o \(\mathbb{R}\) è un ordine lineare, dove
Un ordine \(R\) su un insieme \(A\) è lineare o totale se \(a \mathrel{R} b\) o \(b \mathrel{R} a\) per ogni scelta di \(a , b \in A\).
L’inclusione \(\subseteq\) è un ordinamento su \(\mathscr{P} ( A ) = \left \{B \boldsymbol\mid B \subseteq A \right\}\). Tuttavia, se ad esempio \(A = \{ a,b \}\) quest’ordine non è lineare poichè \(\left \{ a \right \} \not \subseteq \left \{ b \right \}\) e \(\left \{ b \right \} \not \subseteq \left \{ a \right \}\).
Esercizio Disegnare il diagramma di Hasse degli ordini \(\langle\mathscr{P}(\{ 0 \}), {\subseteq}\rangle\), \(\langle\mathscr{P}(\{ 0,1 \}), {\subseteq}\rangle\) e \(\langle\mathscr{P}(\{0,1,2 \}), {\subseteq}\rangle\). In quali casi si ha un ordine lineare?
Sia \(\preceq\) un ordinamento su \(A\). Un elemento \(a \in A\) si dice
massimo (rispetto a \(\preceq\)) se \(b \preceq a\) per ogni \(b \in A\);
minimo (rispetto a \(\preceq\)) se \(a \preceq b\) per ogni \(b \in A\).
L’ordinamento \(\leq\) su \(\mathbb{N}\) ha minimo (il numero \(0\)), ma non ha massimo.
L’ordinamento \(\leq\) su \(\mathbb{Z}\) non ha nè minimo, nè massimo.
L’ordinamento \(\leq\) sull’intervallo \((0;1] \stackrel{\text{def}}{=}\left \{x \in \mathbb{R} \boldsymbol\mid 0 < x \leq 1 \right\}\) ha massimo (il numero \(1\)) ma non ha minimo.
L’ordinamento \(\subseteq\) su \(\mathscr{P} ( A )\) ha minimo (l’insieme \(\emptyset\)) e massimo (l’insieme \(A\)), poichè \(\emptyset \subseteq B \subseteq A\) per ogni \(B \subseteq A\).
Esempio: la relazione di divisibilità fra numeri naturali
Definiamo \(\preceq\) su \(\mathbb{N}\) come
\(n \preceq m\) se e solo se \(m = n \cdot k\) per qualche \(k \in \mathbb{N}\).
Dimostrare che \(\preceq\) è un ordine non totale su \(\mathbb{N}\) che ha minimo e massimo.
Siano \(n,m,l \in \mathbb{N}\) arbitrari.
\(n \preceq n\) poichè \(n = n \cdot 1\).
Supponiamo che \(n \preceq m\) e \(m \preceq n\). Allora esiste \(i \in \mathbb{N}\) tale che \(m = n \cdot i\) ed esiste \(j \in \mathbb{N}\) tale che \(n = m \cdot j\). Quindi \(m = m \cdot j \cdot i\), da cui, dividendo per \(m\), si ottiene \(j \cdot i = 1\). Perciò \(j = i = 1\), da cui \(m = n \cdot 1 = n\).
Supponiamo che \(n \preceq m\) e \(m \preceq l\). Siano \(i,j \in \mathbb{N}\) tali che \(l = m \cdot i\) e \(m = n \cdot j\). Allora \(l = n \cdot j \cdot i\), ovvero \(n \preceq l\) (basta porre \(k = j \cdot i\) nella definizione).
Ad esempio, \(2 \not\preceq 3\) e \(3 \not\preceq 2\).
è il numero \(1\): si ha sempre \(1 \preceq n\) poichè \(n = 1 \cdot n\).
è il numero \(0\): si ha sempre \(n \preceq 0\) perchè \(0 = n \cdot 0\).
La relazione di divisibilità spesso si denota con il simbolo \(|\):
\(n \mathrel{|} m\) se e solo se \(n\) divide \(m\),
ovvero \(m = n \cdot k\) per qualche \(k \in \mathbb{N}\).
Dato \(m \in \mathbb{N}\), l’insieme dei divisori di \(m\) è
\(\mathrm{Div}(m) = \left \{ n \in \mathbb{N} \boldsymbol\mid n \text{ divide } m \right\}\).
Si osservi che \(\mathrm{Div}(m) \neq \emptyset\) poichè, ad esempio, \(1\) ed \(m\) vi appartengono. Se \(m \neq 0\) l’insieme \(\mathrm{Div}(m)\) è un insieme finito e contiene solo numeri compresi tra \(1\) ed \(m\). Invece \(\mathrm{Div}(0) = \mathbb{N}\).
Esercizio Calcolare il diagrama di Hasse dei seguenti ordini: \(\langle \mathrm{Div}(6),{|}\rangle\), \(\langle\mathrm{Div(8)},{|}\rangle\), \(\langle\mathrm{Div}(9),{|}\rangle\), \(\langle\mathrm{Div}(12),{|}\rangle\) e \(\langle\mathrm{Div}(30),{|}\rangle\). Quali di questi sono ordini lineari?
Esercizio su ordini Definiamo \(\unlhd\) su \(\mathbb{N} \setminus \{ 0 \}\) ponendo
\(n \unlhd m\) se e solo se \(m = n^k\) per qualche \(k \in \mathbb{N}\).
Dimostrare che \(\unlhd\) è un ordine non lineare che ha massimo ma non ha minimo.
=0,45cm Siano \(n,m,l \in \mathbb{N} \setminus \{ 0 \}\) arbitrari.
\(n \unlhd n\) poichè \(n = n^1\).
Supponiamo che \(n \unlhd m\) e \(m \unlhd n\). Allora esistono \(i,j \in \mathbb{N}\) tali che \(m = n^i\) e \(n = m^j\). Quindi \(m = (m^j)^i = m^{j \cdot i}\), da cui o \(m = 1\) oppure \(j \cdot i = 1\). Nel primo caso, \(n = m^j = 1^j = 1\), da cui \(m =n\). Nel secondo caso \(j = i = 1\), da cui \(m = n^1 = n\).
Supponiamo che \(n \unlhd m\) e \(m \unlhd l\). Siano \(i,j \in \mathbb{N}\) tali che \(l = m^i\) e \(m = n^j\). Allora \(l = (n^j)^i = n^{j \cdot i}\), ovvero \(n \unlhd l\).
Ad esempio, \(\neg ( 2 \unlhd 3)\) e \(\neg (3 \unlhd 2)\).
Non esiste, perchè non esiste alcun \(n\) tale che \(n \unlhd 2\) e \(n \unlhd 3\).
è il numero \(1\): si ha sempre \(n^0 = 1\), perciò \(n \unlhd 1\).
Parte stretta di un ordine
Dato un qualunque ordine \(\preceq\) su un insieme \(A\), possiamo considerare la sua parte stretta \(\prec\) definita da
\(a \prec b\) se e solo se \(a \preceq b \wedge a \neq b\).
Si verifica facilmente che \(\prec\) è ancora una relazione transitiva.
(Supponiamo \(a \prec b \prec c\). Allora \(a \preceq c\) per la transitività di \(\preceq\). Se per
assurdo \(a = c\), allora si avrebbe \(a \preceq b\) e \(b \preceq c = a\), quindi \(a = b\) per
l’antisimmetria di \(\preceq\), assurdo. Segue che \(a \neq c\), e quindi \(a \prec c\).)
Inoltre è ancora antisimmetrica, ma per ragioni banali: non ci sono coppie \((a,b)\) tali che \(a \prec b\) e \(b \prec a\).
(Se \(a \prec b\) e \(b \prec a\), allora \(a = b\) per l’antisimmetria di \(\preceq\), contraddicendo
proprio \(a \prec b\).)
Tuttavia, \(\prec\) non è riflessiva. Anzi, per definizione non c’è nessun elemento \(a \in A\) per cui valga \(a \prec a\).
Ordini stretti
Una relazione \(R\) su \(A\) si dice irriflessiva se \(\neg (a \mathrel{R} a)\) per ogni \(a \in A\).
Un ordine stretto su \(A\) è una relazione irriflessiva \(\prec\) su \(A\) tale che la relazione \(\preceq\) su \(A\) definita
\(a \preceq b\) se e solo se \(a \prec b \vee a = b\)
è un ordine su \(A\) (detto ordine indotto da \(\prec\)). Equivalentemente, una relazione binaria è un ordine stretto se è la parte stretta di un ordine.
Esempio: La relazione \(<\) su \(\mathbb{N}\) o su \(\mathbb{R}\).
Per indicare gli ordini stretti spesso si usano i simboli per gli ordini senza la parte che richiama l’uguaglianza, ad esempio
\(<\) \(\prec\) \(\lhd\) \(\sqsubset\) \(\dotsc\)
Scriveremo ad esempio \(\langle A, {\prec} \rangle\) per indicare che \(\prec\) è definito su \(A\).
Esempio: discendenti e antenati
Sia \(A\) l’insieme di tutti gli esseri umani. Definiamo la relazione \(\lhd\) su \(A\) ponendo
\(a \lhd b\) se e solo se \(a\) è un/una discendente di \(b\).
(Equivalentemente, \(a \lhd b\) se e solo se \(b\) è un/una antenato/a di \(a\).)
La relazione \(\lhd\) è chiaramente irriflessiva, perchè nessuno è discendente di se stesso. Consideriamo ora la relazione \(\unlhd\) su \(A\) definita da
\(a \unlhd b\) se e solo se \(a\lhd b \vee a = b\).
è una relazione chiaramente riflessiva. Inoltre, se \(a \unlhd b\) e \(b \unlhd a\), allora \(a = b\) perchè non si può mai avere che \(a\) è un discendente di \(b\) e \(b\) è un discendente di \(a\). Infine, se \(a\) è un discendente di \(b\) e \(b\) è un discendente di \(c\), allora anche \(a\) è un discendente di \(c\), ovvero \(\lhd\) è transitiva. Mostriamo che anche \(\unlhd\) lo è. Supponiamo che \(a \unlhd b \unlhd c\): se \(a = b\) oppure \(b = c\), allora \(a \unlhd c\). Nel caso rimanente, \(a \lhd b \lhd c\), quindi \(a \lhd c\) e anche \(a \unlhd c\).
Questo mostra che \(\unlhd\) è un ordine, quindi \(\lhd\) è un ordine stretto.
Un pre-ordine o quasi ordine su \(A\) è una relazione binaria \(\precsim\) su \(A\) che è riflessiva e transitiva. In questo caso diremo che \(\langle A , {\precsim} \rangle\) è un insieme pre-ordinato o quasi ordinato.
Esempio
La classifica del campionato di serie A è un pre-ordine \(\precsim\) (lineare) sull’insieme delle squadre \(X\): se la squadra \(S\) ha \(n\) punti e la squadra \(T\) ha \(m\) punti, diciamo che \(S \precsim T\) (“\(S\) precede \(T\) nella classifica”) se e solo se \(n \geq m\). Si verifica allora che la relazione \(\precsim\) è:
riflessiva: \(S \precsim S\) per ogni \(S \in X\);
transitiva: per ogni \(S,T,U \in X\), se \(S \precsim T\) e \(T \precsim U\) allora \(S \precsim U\);
ma non è antisimmetrica: può accadere che \(S \precsim T\) e \(T \precsim S\) per due squadre distinte \(S,T \in X\) (\(S\) e \(T\) sono a parimerito).
Dunque si tratta di un pre-ordine e non di un ordine.
Se \(\precsim\) è un pre-ordine su \(A\), allora \[{a \sim b} \iff {{a \precsim b} \wedge {b \precsim a}}\] è una relazione di equivalenza su \(A\) (detta relazione di equivalenza indotta da \(\precsim\)) e la relazione su \(A / {\sim}\) \[{\boldsymbol [}{a}{\boldsymbol ]}_{\sim} \leq {\boldsymbol [}{b}{\boldsymbol ]}_{\sim} \iff a \precsim b\] è ben definita ed è un ordine (detto ordine indotto da \(\precsim\)).
Ad esempio, nella classifica del campionato di serie A (vista come pre-ordine \(\precsim\)), le classi di equivalenza rispetto alla relazione \(\sim\) indotta da \(\precsim\) sono gli insiemi di squadre a parimerito (cioè con lo stesso numero di punti). L’ordine \(\leq\) indotto su tali classi di equivalenza è quella che ordina questi gruppi di squadre in base al punteggio ottenuto: l’insieme delle squadre che hanno \(20\) punti formano una classe di equivalenza che precede la classe di equivalenza delle squadre che hanno \(19\) punti, e così via.
La relazione \(\sim\) definita da \({a \sim b} \iff {{a \precsim b} \wedge {b \precsim a}}\) è una relazione d’equivalenza.
è evidentemente riflessiva, dato che lo è \(\precsim\).
Se \(a \sim b\) allora \(a \precsim b \wedge b \precsim a\) e quindi \(b \precsim a \wedge a \precsim b\), cioè \(b \sim a\); quindi \(\sim\) è simmetrica.
Se \(a \sim b\) e \(b \sim c\), allora \(a \precsim b \wedge b \precsim a\) e \(b \precsim c \wedge c \precsim b\), da cui per transitività di \(\precsim\) si ha \(a \precsim c \wedge c \precsim a\), cioè \(a \sim c\).
La relazione su \(A / {\sim}\) \[{\boldsymbol [}{a}{\boldsymbol ]}_{\sim} \leq {\boldsymbol [}{b}{\boldsymbol ]}_{\sim} \iff a \precsim b\] è ben definita ed è un ordine.
Supponiamo che \(a \precsim b\) e \(a' \sim a\) e \(b' \sim b\): allora \(a' \precsim a\) e \(b \precsim b'\) quindi \(a' \precsim b'\) per la transitività di \(\precsim\). Ne segue che la definizione di \(\leq\) su \(A / {\sim}\) è ben posta, dato che non dipende dal rappresentante.
è immediato verificare che \(\leq\) è riflessiva e transitiva, quindi è sufficiente verificare che è antisimmetrica. Se \({\boldsymbol [}{a}{\boldsymbol ]}_{\sim} \leq {\boldsymbol [}{b}{\boldsymbol ]}_{\sim}\) e \({\boldsymbol [}{b}{\boldsymbol ]}_{\sim} \leq {\boldsymbol [}{a}{\boldsymbol ]}_{\sim}\), allora \(a \precsim b \wedge b \precsim a\), da cui \(a \sim b\) per definizione, e quindi \({\boldsymbol [}{a}{\boldsymbol ]}_{\sim} = {\boldsymbol [}{b}{\boldsymbol ]}_{\sim}\).
Esempio di pre-ordine (1)
Consideriamo la relazione \(\preceq\) su \(\mathbb{N}\) definita da \[\begin{aligned} n \preceq m \quad \text{se e solo se} \quad & m \text{ ha un numero di cifre maggiore o uguale}\\ & \text{a quelle di } n \text{ (in notazione decimale)}. \end{aligned}\]
Allora \(\preceq\) è una relazione riflessiva e transitiva, ma non è antisimmetrica poichè, ad esempio, \(10 \preceq 25\) e \(25 \preceq 10\) (ma \(10 \neq 25\)). Quindi \(\preceq\) è un esempio di un pre-ordine che non è un ordine.
La relazione di equivalenza associata a \(\preceq\) è la relazione \(E\) (“avere lo stesso numero di cifre”) della slide 11. L’ordine indotto sul quoziente \(\mathbb{N}/E\) rispetto a tale relazione d’equivalenza è un ordine lineare: \(C_{k}\) precede \(C_{k'}\) in tale ordine se e solo se \(k \leq k'\), dove le \(C_{k}\) sono le classi di equivalenza rispetto ad \(E\) definite nella slide18 .
Esempio di pre-ordine (2)
Consideriamo la relazione \(\precsim\) su \(\mathrm{Fin} = \{ X \subseteq \mathbb{N} \mid X \text{è finito} \}\) definita da \[\begin{aligned} X \precsim Y \text{ se e solo se } & \text{il numero di elementi di \( X \) è minore o uguale} \\ & \text{al numero di elementi di \( Y \).} \end{aligned}\]
La relazione \(\precsim\) è chiaramente riflessiva e transitiva, ma non è antisimmetrica poichè, ad esempio, \(\{ 1,2 \} \precsim \{ 5,14 \}\) e \(\{ 5,14 \} \precsim \{ 1,2 \}\), ma chiaramente \(\{ 1 , 2 \} \neq \{ 5,14 \}\). Quindi \(\precsim\) è un altro esempio di un pre-ordine che non è un ordine.
La relazione di equivalenza associata a \(\precsim\) è la relazione \(\approx\) (“avere lo stesso numero di elementi”) della slide precedente. Anche in questo caso, l’ordine indotto sul quoziente \(\mathrm{Fin}/{\approx}\) rispetto a tale relazione d’equivalenza è un ordine lineare: \(I_{k}\) precede \(I_{k'}\) in tale ordine se e solo se \(k \leq k'\), dove le \(I_{k}\) sono le classi di equivalenza rispetto a \(\approx\) definite nella slide precedente.
Esempio di pre-ordine (3)
Sia \(\subseteq^*\) la relazione su \(\mathscr{P}(\mathbb{N})\) definita per ogni \(A,B \subseteq \mathbb{N}\) da
\(A \subseteq^* B\) se e solo se \(A \setminus B\) è finito.
In altre parole, \(A \subseteq^* B\) se e solo se ogni \(n \in A\) appartiene anche a \(B\) tranne che per un numero finito di tali \(n\).
Dimostrare che \(\subseteq^*\) è un pre-ordine su \(\mathscr{P}(\mathbb{N})\).
Riflessività: \(A \subseteq^* A\) poichè \(A \setminus A = \emptyset\) è finito.
Transitività: Siano \(A \subseteq^* B \subseteq^* C\). Si ha \[A \setminus C \subseteq (A \setminus B) \cup (B \setminus C).\] Infatti, sia \(n \in A \setminus C\), ovvero \(n \in A\) ma \(n \notin C\). Distinguiamo due casi. Se \(n \notin B\), allora \(n \in A \setminus B\) e quindi \(n \in (A \setminus B) \cup (B \setminus C)\). Se invece \(n \in B\), allora \(n \in B \setminus C\) e quindi nuovamente \(n \in (A \setminus B) \cup (B \setminus C)\). Poichè \(A \setminus B\) e \(B \setminus C\) sono finiti, anche \(A \setminus C\) lo è, ovvero \(A \subseteq^* C\).
Per definizione, la relazione di equivalenza \(=^*\) indotta da \(\subseteq^*\) è data da
\(A = ^* B\) se e solo se \(A \subseteq^* B\) e \(B \subseteq^* A\) .
è facile vedere che \(A =^* B\) se e solo se \(A \mathop{\triangle} B\) è finito e che ogni classe di equivalenza rispetto alla relazione \(=^*\) è infinita.
Poichè \(A \mathop{\triangle} B \stackrel{\text{def}}{=}(A \setminus B) \cup (B \setminus A )\), si ha che \(A \mathop{\triangle} B\) è finito se e solo se entrambi gli insiemi \(A \setminus B\) e \(B \setminus A\) sono finiti, ovvero se e solo se \(A \subseteq^* B\) e \(B \subseteq^* A\).
Sia \(A \subseteq \mathbb{N}\). Se \(A\) è finito, allora per ogni insieme finito \(B \subseteq \mathbb{N}\) si ha che \(A \mathop{\triangle} B\) è finito poichè \(A \mathop{\triangle} B \subseteq A \cup B\), per cui \(A =^* B\). Poichè la collezione dei sottoinsiemi di \(\mathbb{N}\) finiti contiene infiniti elementi (ad esempio, contiene tutti gli \(\{ n \}\) per \(n \in \mathbb{N}\)), si ha che \([A]_{=^*}\) è infinita. Se invece \(A = \{ a_{0}, a_{1}, a_{2}, \dotsc \}\) è infinito, allora posto \(A_{n} = A \setminus \{ a_{n} \}\) per ogni \(n \in \mathbb{N}\) si ha che gli \(A_{n}\) sono a due a due distinti e tali che \(A_{n} =^* A\) (infatti \(A \mathop{\triangle} A_{n} = \{ a_{n} \}\)). Quindi anche in questo caso \([A]_{=^*}\) è infinita.
Esempio di pre-ordine (4)
La relazione di conseguenza logica \(\models\) sull’insieme di tutte le proposizioni è un pre-ordine.
Riflessività: Chiaramente \(\mathrm{P}\models \mathrm{P}\) per ogni proposizione \(\mathrm{P}\), quindi \(\models\) è riflessiva.
Transività: Assumiamo che \(\mathrm{P}\models \mathrm{Q}\) e \(\mathrm{Q}\models \mathrm{R}\) e dimostriamo che \(\mathrm{P} \models \mathrm{R}\). Costruiamo la tavola di verità di \(\mathrm{P},\mathrm{Q},\mathrm{R}\) su tutte le variabili proposizionali che compaiono in \(\mathrm{P}\) o in \(\mathrm{Q}\) o in \(\mathrm{R}\). Si ha che in ogni riga in cui \(\mathrm{P}\) è vera anche \(\mathrm{Q}\) risulta vera (poichè \(\mathrm{P}\models \mathrm{Q}\) ), e che in ogni riga in cui \(\mathrm{Q}\) è vera anche \(\mathrm{R}\) risulta vera (poichè \(\mathrm{Q}\models \mathrm{R}\)).
Quindi in ogni riga in cui \(\mathrm{P}\) è vera risulterà vera anche \(\mathrm{R}\), cioè \(\mathrm{P}\models \mathrm{R}\).
Tuttavia, la relazione \(\models\) non è un ordine. Infatti, \(\mathrm{A}\to \mathrm{B}\models \neg \mathrm{A}\vee \mathrm{B}\) e \(\neg \mathrm{A}\vee \mathrm{B}\models \mathrm{A} \to \mathrm{B}\) ma le due proposizioni sono distinte: quindi \(\models\) non è antisimmetrica. Le relazione d’equivalenza associata a \(\models\) è proprio la relazione di equivalenza logica \(\equiv\).