4.4 Le relazioni di ordinamento

1 Insiemi, proposizioni e relazioni 4.4 Le relazioni di ordinamento Consideriamo le seguenti relazioni: Q nell insieme delle persone, «essere discendente ; Q nell insieme dei numeri naturali, «essere minore o uguale . La prima relazione è antisimmetrica e transitiva, la seconda è riflessiva, antisimmetrica e transitiva. Quindi, sono entrambe sia antisimmetriche sia transitive. Entrambe le relazioni danno un ordine agli elementi dell insieme: Q le persone sono ordinate secondo la loro discendenza; Q i numeri naturali sono ordinati secondo l usuale ordinamento. DEFINIZIONE Una relazione antisimmetrica e transitiva è detta relazione d ordine o, più semplicemente, ordinamento. KEYWORDS K rel relazione d ordine / ordering relation Le due relazioni precedenti sono ordinamenti. Hanno, tuttavia, caratteristiche diverse. La relazione «essere discendente non è riflessiva, mentre la relazione «essere minore o uguale è anche riflessiva. Nella definizione data si specifica che devono almeno valere le proprietà antisimmetrica e transitiva; nulla si dice su altre proprietà che esse possono avere. Per questo le due relazioni sono entrambe ordinamenti. Se si considerano due numeri naturali x e y e se x non è minore o uguale a y, allora necessariamente y è minore o uguale a x: per ogni x, y N, x y y x Quindi, per ogni coppia di numeri vale una delle due seguenti relazioni: x y oppure y x cioè sempre possibile mettere in relazione due elementi qualunque. Possiamo anche dire che tutti gli elementi sono confrontabili rispetto alla relazione «essere minore o uguale . Una relazione d ordine in cui tutti gli elementi sono confrontabili, come per la relazione «essere minore o uguale , si dice ordinamento totale o lineare. In tale caso gli elementi si possono rappresentare su una linea retta. E sulla retta si rappresentano infatti i numeri naturali sulla base della relazione . Nella relazione «essere discendente la situazione è diversa; se A e B sono due fratelli, allora né A è discendente di B, né B è discendente di A. Non tutti gli elementi sono confrontabili tra loro rispetto a questa relazione. Gli elementi di un insieme che sono ordinati secondo una relazione di ordinamento non totale, come la relazione «essere discendenti , non possono, invece, essere rappresentati linearmente. Una delle rappresentazioni per un insieme ordinato in modo non totale è l albero, che è un grafo ottenuto disponendo gli elementi sui nodi e sottintendendo che sono in relazione due elementi se vi è una sequenza di frecce che portano dall uno all altro. L albero genealogico di una famiglia è un esempio di rappresentazione della relazione di discendenza, come puoi vedere in figura a lato. 29

Il Maraschini-Palma - volume 1
Il Maraschini-Palma - volume 1