Algebra e geometria - relazione d'ordine

Relazioni d'ordine

Definizione di relazione d'ordine

Una relazione d'ordine R è definita in base a tre proprietà: riflessiva, asimmetrica e transitiva.

Riflessiva: Per ogni elemento x, deve valere x R x.

Asimmetrica: Se x R y e y R x, allora x = y.

Transitiva: Se x R y e y R z, allora x R z.

Se una relazione possiede queste tre proprietà, si chiama relazione d'ordine.

Esempi di relazioni d'ordine

Relazione di minore o uguale (≤)

La relazione ≤ è un esempio di relazione d'ordine sull'insieme dei numeri naturali ℕ. Formalmente, è definita come:

• Riflessiva: Ogni n ≤ n.
• Asimmetrica: Se n ≤ m e m ≤ n, allora n = m.
• Transitiva: Se n ≤ m e m ≤ t, allora n ≤ t.

Relazione di multiplo

Definiamo una relazione sull'insieme dei numeri interi basata sul concetto di multipli. Un numero n è un multiplo di m se esiste un altro numero h tale che n = m * h. La relazione si definisce come segue:

• Riflessiva: Ogni n è un multiplo di sé stesso poiché n = n * 1.
• Simmetrica: Se n è multiplo di m e m è multiplo di n, allora n = m (caso raro a meno che n = m).
• Transitiva: Se n = m * h e m = l * k, allora n = l * k * h. Quindi n è multiplo di l.

Non è simmetrica perché, ad esempio, 10 R 2 ma non 2 R 10.

Esempio con parole

Consideriamo l'insieme A = {a, b, c, d}. Possiamo definire una relazione basata sulla lunghezza delle parole formate con le lettere di A. La relazione R è definita come:

• (u, v) è in R se il numero di lettere (lunghezza) di u è minore o uguale a quello di v.

Esempi: ba R abc, aab R abcd.

Diagrammi di Hasse

Un diagramma di Hasse è un modo di rappresentare una relazione d'ordine. Nel diagramma, ogni elemento dell'insieme è rappresentato come un punto, e due punti sono collegati se uno copre l'altro. Un elemento y copre x se x R y e non esiste un z tale che x R z e z R y.

Esempio: nell'insieme dei numeri naturali con ≤, 3 copre 2 ma 4 non copre 2.

Esempi di diagrammi

Consideriamo l'insieme A = {1, 3, 4, 6, 8, 10, 12}. Le coppie coperte sono: (3, 1), (4, 1), (6, 1), (8, 1), (10, 1), (12, 1), (6, 3), (8, 4), (12, 4), (12, 6), (12, 3). L'elemento 1 è minimo, non esiste un massimo.

Altro esempio: A = {2, 3, 4, 5, 10, 22, 21, 36}. Le coppie coperte sono: 36 copre 12, 24 copre 12, 10 copre 2.

Relazione di inclusione

Per l'insieme A = {a, b}, consideriamo l'insieme delle parti P(A) = {∅, {a}, {b}, {a, b}}. La relazione di inclusione tra i sottoinsiemi è un esempio di relazione d'ordine.