3.3 Relazioni[1YV]
[1WY]Una relazione fra elementi di due insiemi \(A,B\) è definita come un sottoinseme \(R⊆ A× B\) del prodotto cartesiano. In genere si usa la notazione infissa \(aRb\) invece di scrivere \((a,b)∈ R\).
[23X]Una relazione \(R\) fra elementi di \(A\) è detta:
irriflessiva o anti-riflessiva se \(\lnot xRx\) per ogni \(x∈ A\);
antisimmetrica se \(aRb\) e \(bRa\) implicano \(a=b\), per ogni \(a,b∈ A\);
tricotomica se per ogni \(x,y \in A\) vale esattamente una fra \(xRy\), \(yRx\) e \(x = y\);
transitiva se \(xRy\) e \(yRz\) implicano \(xRz\), per ogni \(x,y,z∈ A\).
Una relazione \(R\) fra elementi di \(A\) e elementi di \(B\) è detta:
iniettiva se \(xRy\) e \(zRy\) implicano \(x = z\), per ogni \(x,z∈ A,y∈ B\);
funzionale se \(xRy\) e \(xRz\) implicano \(y = z\), per ogni \(x∈ A,y,z∈ B\); una tale relazione è anche detta una “funzione parziale” (si vedano anche 3.5,17);
totale (a sinistra) se per ogni \(x∈ A\) esiste un \(y∈ B\) tale che \(xRy\);
surgettiva (cioè “totale a destra”) se per ogni \(y∈ B\) esiste un \(x∈ A\) tale che \(xRy\).
[1W5]Una relazione di equivalenza è una relazione fra elementi di \(A\) che gode delle proprietà: riflessiva, simmetrica, transitiva.
Le relazioni di equivalenza vengono in genere indicate con i simboli “\(∼\)” , “\(≈\)” , “\(≃\)” , “\(≅\)” , “\(≊\)” etc.
[1Y5] Una relazione d’ordine (o ordinamento) è una relazione fra elementi di \(A\) che gode delle proprietà: riflessiva, antisimmetrica, transitiva.
Una relazione d’ordine è totale se tutti gli elementi sono comparabili, cioè se per ogni \(a,b ∈ A\) si ha \(aRb ∨ bRa\).
(Quando una relazione d’ordine non è totale, si dice che è parziale).
In genere si usano simboli come “\(≤\)” o “\(⊆\)” o “\(⪯\)” o simili.
[24W]Abbiamo sopra ricalcato le definizioni in [ 3 ] ; in altri testi una relazione fra elementi di \(A\) che gode delle proprietà: riflessiva, antisimmetrica, transitiva è direttamente chiamata ordine parziale. (cf Example 2.1.1 in [ 13 ] dove inoltre gli ordinamenti totali sono detti linear order). Per questa ragione aggiungeremo “(parziale)” quando vorremo indicare che l’ordinamento che stiamo discutendo potrebbe essere parziale.
Per le relazioni d’ordine rimandiamo alla sezione 3.4
- E51
[1WH]Prerequisiti:46.(Proposto il 2022-12) Per ogni insieme \(A\) e relazione \(R\) fra elementi di \(A\), dire se è riflessiva, simmetrica, antisimmetrica e/o transitiva; se è una relazione d’ordine, dire se è totale.
- E51
[1WK]Sia \(f:A→ B\) una funzione, sia \(∼\) una relazione di equivalenza su \(B\): dimostrate che la relazione \(R\) fra elementi di \(A\) data da
\[ xRy\iff f(x)∼ f(y) \]è una relazione di equivalenza.
- E51
-
Date due relazioni \(a≤ b\) e \(a{\lt} b\) per \(a,b\in A\), mostrate che sono equivalenti:
\(a≤ b\) è una relazione d’ordine (possibilmente parziale) e identifichiamo
\[ a{\lt}b = (a≤ b\land a\neq b)\quad ; \]\(a{\lt} b\) è una relazione irriflessiva e transitiva e \(\forall x,y\in A\) al più una condizione fra \(x{\lt}y~ ,~ x=y ~ ,~ y{\lt}x\) è vera; e identifichiamo
\[ a≤ b = (a{\lt} b\lor a= b)\quad . \]
Questa relazione \(a{\lt} b\) è chiamata ordinamento (parziale) stretto.
- E51
[24K]Prerequisiti:46,48,3. Date due relazioni \(a≤ b\) e \(a{\lt} b\) per \(a,b\in A\), mostrate che sono equivalenti:
\(a≤ b\) è una relazione d’ordine totale e
\[ a{\lt}b = (a≤ b\land a\neq b)\quad , \]\(a{\lt} b\) è una relazione irriflessiva, tricotomica e transitiva e
\[ a≤ b = (a{\lt} b\lor a= b)\quad . \]
Questa relazione \(a{\lt} b\) è chiamata ordinamento totale stretto.
- E51
[1YH] Consideriamo \(A=ℝ^ 2\) e consideriamo la relazione
\[ (x,y)∼ (x',y') \iff ( x-x'∈ℤ∧ y-y'∈ℤ) \]fra elementi di \(ℝ^ 2\) :
mostrate che è una relazione di equivalenza;
rappresentate graficamente le classi di equivalenza;
descrivete l’insieme \(A/∼\).