MIKY & GENNY

RELAZIONI D'ORDINE ---> INDICE

Considerato un insieme E, si chiama relazione d'ordine sull'insieme E ogni relazione R su E, cio


che verifica i seguenti due assiomi di relazione d'ordine:

RO-1)
(x, y)R  (y, z)R (x, z)R,

RO-2)
 (x, y) (y, x)R  x = y.

Si pu considerare anche la
relazione d'ordine opposta: se R una relazione d'ordine sull'insieme E, e si considera


risulta


inoltre S una relazione d'ordine chiamata opposta di R.

Per dimostrare che
S una relazione d'ordine, S deve verificare i due assiomi di relazione d'ordine:

RO-1)
(x, y)S  (y, z)S (y, x)R  (z, y)R (z, x)R (x, z)S,

RO-2)
 (x, y)S  (y, x)S (y, x)R (x, y)R  x = y.

Nota bene
Si osserva ora che:

1)-al posto della relazione d'ordine R sull'insieme E si usa frequentemente il simbolo ≤, quindi gli assiomi suddetti si possono riformulare come segue

RO-1)
(xy)  (y z)  x z,

RO-2)
 (xy)  (y x)  x = y.

2)-La coppia ordinata (E,
) si chiama insieme ordinato; la prima coordinata l'insieme E, mentre la seconda una relazione d'ordine.

3)-Considerato l'
insieme ordinato (E, ), si dice che una relazione di totale ordine su E se e solo se, quali che siano x ed y elementi di E, risulta (x y) v (y x), cio x ed y sono paragonabili per .

4)-
La coppia ordinata (E, ) si chiama insieme totalmente ordinato se la relazione d'ordine assegnata sull'insieme E una relazione di totale ordine.

5)-Se sull'insieme E  
assegnata una relazione d'ordine ≤, considerati due elementi

x
E, yE, x y, x ≠ y,

si dice che x strettamente minore di y e si scrive x < y.

6)-Quando y
x, si pu anche scrivere x ≥ y; una relazione d'ordine cos definita si chiama relazione d'ordine opposta a quella data.

7)-
xE, yE, zE, (x y), (y < z) x < z.

Infatti, dire che

x < z 
(x ≤ z) (x  z)

e, supponendo per assurdo x = z, comporta che da un lato x
≤ y e dall'altro y < x; inoltre

y < x
(y x), (y  x).

Associando le due condizioni,
per il secondo assioma, si ottiene x = y, e ci assurdo perch x = y, quindi x z, e di conseguenza x < z.

8)-
(x < y)  (y  z) x < z.

Infatti, dire che

x < z 
(x ≤ z) (x  z)

e, supponendo per assurdo x = z, comporta che da un lato
z < y e dall'altro y ≤ z; inoltre

z < y
(z y), (z y).

Associando le due condizioni, per il secondo assioma, si ottiene x = y, e ci assurdo perch x = y, quindi x
z, e di conseguenza x < z.

8)-
(x < y)  (y < z) x < z.

9)-Spesso, invece di dire che
x ≤ y, si dice che x inferiore ad y, mentre se x < y, si dice che x strettamente inferiore ad y.

Si suppone ora d'avere la relazione d'ordine R sull'insieme E e sia data una parte A, non vuota, dell'insieme E, cio:


Essendo


si pu considerare



che prende il nome di relazione indotta da R su A; si dimostra che
RA una relazione d'ordine su A, cio deve verificare i due assiomi:

RO-1) 
xA  yA zAxRAy, yRAz xRAz,

RO-2)
  xA  yA : xRAy, yRAx  x = y.

Dimostrazione
RO-1).

xA  yA zA : xRAy,  yRAz  (x, y)RA, (y, z)RA

(x, y)R (y, z)R (x, y)A X A (y, z)A X A  (x, z) (x, z)A X A 

(x, z)R xRAz.

Dimostrazione
RO-2).
 
xA  yA : xRAy, yRAx (x, y)RA, (y, x)RA (x, y)R (y, x)R

(x, y)A X A (y, x)A X A x = y.

Quando si assume
≤ come relazione d'ordine, la relazione d'ordine indotta su A, parte di E, si denota con A, cio:

(x, y)
≤, (x, y)A X A  x A y.

Si dice che


una parte ordinata dell'insieme E, se e solo se gode anch'essa della relazione d'ordine su E, vale a dire:

xA  yA : x A  x y.

Se poi ≤ una
relazione di totale ordine su E, allora la relazione indotta su una parte


anch'essa una 
relazione di totale ordine.
Allo scopo, basta dimostrare che due elementi qualsiasi x ed y, appartenenti ad A, sono paragonabili per
A.

Infatti
x ed y, essendo elementi di A, risultano anche elementi di E, e quindi sono paragonabili per la relazione d'ordine ≤ ovunque definita su E, per cui essi risultano paragonabili anche per A.

In generale, se (E, 
) non totalmente ordinato, ogni sua parte A non totalmente ordinata; se (E, ) totalmente ordinato, ogni sua parte A totalmente ordinata.

Comunque, non escluso che, su un'opportuna parte A, ci sia una
relazione di totale ordine indotta dalla relazione che non di totale ordine.