3.3 Relazioni[1YV]

Definizione 45

[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\).

Definizione 46

[23X]Una relazione \(R\) fra elementi di \(A\) è detta:

  • riflessiva se \(xRx\) per ogni \(x∈ A\);

  • irriflessiva o anti-riflessiva se \(\lnot xRx\) per ogni \(x∈ A\);

  • simmetrica se \(xRy\) implica \(yRx\) per ogni \(x,y∈ 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\).

Definizione 47

[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.

Definizione 48

[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.

Nota 49

[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

Nota 50

[1Y7]È uso scrivere \(a≥ b\) come sinonimo di \(b≤ a\). Se \(a≤ b∧ a≠ b\) scriveremo \(a{\lt}b\); similmente se \(a≥ b∧ a≠ b\) scriveremo \(a{\gt}b\). Attenzione che se la relazione non è totale, non è detto che \(¬ (a≤ b)\) sia equivalente a \(a{\gt}b\).

Vedete a questo proposito l’esercizio 2.

Definizione 51

[1X0]Un ordinamento totale 1 su un insieme \(X\) è detto un buon ordinamento se ogni sottoinsieme di \(X\) non-vuoto ha minimo.

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.

  • In \(A=ℕ⧵\{ 0\} \) , \(nRm\) sse il massimo comun divisore fra \(n\) e \(m\) è 1

  • In \(A=ℕ⧵\{ 0\} \) , \(nRm\) se e solo se \(n\) divide \(m\)

  • In \(A=ℕ⧵\{ 0\} \) , \(nRm\) se e solo se \(2n\) divide \(m\)

  • In \(A={\mathcal P}(ℕ)\), \(aRb\) se e solo se \(a⊆ b\).

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

[224]Prerequisiti:46,48.

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/∼\).

  1. In realtà la condizione di buon ordinamento per un ordinamento implica che è totale; lo lasciamo come esercizio 6.