5 RELAZIONI DI ORDINE

5.1 - Definizioni.

Sia un insieme.A

Si dice relazione in A una relazione tra e (cioè un sottoinsieme del prodottoA A cartesiano ).A‚A

Sia una relazione in . Essa si dice4 A

 riflessiva sse a a4 a −a A;

 simmetrica sse a b4 Ê b a4 aa b, −A;

 antisimmetrica sse Ða b4 •b a4 Ñ Ê Ð œ Ña b aa b, −A;

 transitiva sse Ða b4 •b c4 Ñ Ê Ða c4 Ñ aa b c, , −A.

Sia una relazione in . Due elementi , 4 A a b−A si dicono confrontabili (secondo ) se4 si verifica almeno una delle seguenti situazioni: a b b a4 , 4 . La relazione si dice 4 totale sse comunque presi , a b−A essi sono confrontabili.

Esempi

5.1.1 Per ogni insieme , la relazione “vuota” (secondo la quale nessun elemento è inA relazione con alcun elemento: si tratta di pensato come sottoinsieme di g A‚A) è simmetrica, antisimmetrica e transitiva (ma non riflessiva).

5.1.2 La relazione in definita ponendo 4  + ,4 sse ± +  , ±  " è riflessiva e simmetrica ma non transitiva.

5.1.3 La relazione nell’insieme dei cerchi del piano definita ponendo4

V 4V" # sse l’area di è minore o uguale all’area di V" V#

è riflessiva, transitiva e totale ma non simmetrica né antisimmetrica. Per quest’ultima affermazione, si osservi che se e hanno la stessa area essi sono V" V# congruenti ma non è in generale V" œV#, cioè non sono in generale uguali!.

5.1.4 La relazione in definita ponendo4 

+ ,4 sse , sono entrambi pari+ , è simmetrica e transitiva ma non riflessiva (non è infatti, ad es., " "4 ).

5.2 - Relazioni di ordine. Sia un insieme.A

Una relazione in si dice una A relazione di ordine in se è riflessiva, antisimmetrica eA transitiva. Una relazione di ordine in si indica spesso con A £ oppure con Ÿ (quest’ultimo simbolo, in caso di ambiguità, è riservato alla relazione di “minore o uguale” in , e , cfr. ™  1.6, 1.7 e 1.8).

Sia £ una relazione di ordine in , e siano , A a b−A. Se a£b, si dice che a precede b (secondo £); si usa anche la scrittura b¤a, che si considera equivalente.

Se una relazione di ordine in non è totale e si vuol mettere in rilievo questo fatto, siA dice che è parziale. In tal caso, esistono in almeno due elementi che non sono confrontabili.A

Esempi

5.2.1 L’usuale relazione di “minore o uguale” è una relazione di ordine totale in .

5.2.2 La relazione di “divisibilità” tra numeri naturali è una relazione di ordine parziale in .

5.2.3 La relazione di “inclusione” tra sottoinsiemi di un dato insieme è una relazione diI ordine parziale nell’insieme ( ) definito in 3.5.c I

Una relazione in si dice una 4 A relazione di ordine stretto in se è transitiva e inoltreA comunque presi , a b−A si verifica al più una delle seguenti due situazioni: a b4 , oppure b a4 .

Se £ è una relazione di ordine in , la relazione A ¡ in definita ponendoA a¡b sse a£b e aÁb

è una relazione di ordine stretto, che si dice associata a £. Analogamente, se ¡ è una relazione di ordine stretto in , la relazione A £ in definita ponendoA

a£b sse a¡b oppure aœb è una relazione di ordine, che si dice associata a ¡.

Sia £ una relazione di ordine in , e sia A ¡ la relazione di ordine stretto associata a £: la relazione di ordine associata a ¡ coincide con £. Viceversa, sia ¡ una relazione di ordine stretto in , e sia A £ la relazione di ordine associata a ¡ : la relazione di ordine stretto associata a £ coincide con ¡. Ciò si esprime dicendo che il concetto di “relazione di ordine” e il concetto di “relazione di ordine stretto” sono equivalenti.

5.3 - Intervalli.

Siano un insieme e A Ÿ una relazione di ordine in . Introduciamo una notazione cheA sarà molto utile più avanti.

Siano , elementi di tali che a b A ab. Si dicono intervalli limitati di estremi( ) , ia b seguenti sottoinsiemi di :A

Ða b, Ñ ³ ÖB −A a/  B  ×b (intervallo aperto)

Ða b, Ó ³ ÖB −A a/  B Ÿ ×b (intervallo chiuso a destra) Òa b, Ñ ³ ÖB −A a/ Ÿ B  ×b (intervallo chiuso a sinistra) Òa b, Ó ³ ÖB −A a/ Ÿ B Ÿ ×b (intervallo chiuso)

Si dicono intervalli illimitati i seguenti sottoinsiemi di :A

Ð  _, bÑ ³ ÖB −A/ (B  ×b intervallo aperto, illimitato a sinistra) Ð  _, bÓ ³ ÖB −A/ (B Ÿ ×b intervallo chiuso, illimitato a sinistra) Ða,  _Ñ ³ ÖB −A a/ ( B× intervallo aperto, illimitato a destra) Òa,  _Ñ ³ ÖB −A a/ (Ÿ B× intervallo chiuso, illimitato a destra) Ð  _ _Ñ ³, (A intervallo aperto, illimitato a sinistra e a destra)

5.4 - Minimo e massimo.

Siano un insieme, A Ÿ una relazione di ordine in , e un sottoinsieme di .A X A Un elemento di si dice m X il minimo di , e si indica con X minX, se

mŸ B aB −X.

Analogamente, un elemento M di si dice X il massimo di , e si indica con X maxX, se B Ÿ M aB −X.

Teorema 5.4.1

Siano un insieme, A Ÿ una relazione di ordine in , e un sottoinsieme di .A X A Se ha un minimo [un massimo], questo è unico.X

Dimostrazione  Siano , m m’ minimi di . Poiché è minimo e X m m’−X m, Ÿm’;

poiché m’ è minimo e m−X m’, Ÿ m. Per la proprietà antisimmetrica, mœm’ come si voleva.

Esempi

5.4.2 Nell’insieme dotato dell’ordinaria relazione di “minore o uguale”, l’insieme Xœ Ö#! $! '! )! "!!×, , , ,

ha per minimo #! e per massimo "!!.

5.4.3 Nell’insieme dotato della relazione di “divisibilità” (cfr. esempio 5.2.2), l’insieme Xœ Ö#! $! '! )! "!!×, , , ,

non ha minimo né massimo.

5.4.4 Nell’insieme dotato dell’ordinaria relazione di “minore o uguale”, l’insieme Xœ ÖB −  / B œ ₈", con 8 −\Ö!××

non ha minimo; il suo massimo è ."

5.5 - Limitazioni inferiori e limitazioni superiori.

Siano un insieme, A Ÿ una relazione di ordine in A , e un sottoinsiemeX non vuoto di .A

Un elemento di si dice a A limitazione inferiore (o minorante) di seX aŸ B aB −X;

si dice invece limitazione superiore (o maggiorante) di seX B Ÿ a aB −X.

Il sottoinsieme non vuoto di si dice X A inferiormente superiormente limitato [ ] se esiste in una limitazione inferiore [superiore] per .A X

Esempi

5.5.1 Nell’insieme dotato dell’ordinaria relazione di “minore o uguale”, il sottoinsieme formato dai multipli di &( non è superiormente limitato.

5.5.2 Nell’insieme  dotato dell’ordinaria relazione di “minore o uguale”, ogni sottoinsieme è inferiormente limitato (da ).!

5.5.3 Nell’insieme dotato dell’ordinaria relazione di “minore o uguale”, l’insieme Xœ ÖB − / B Ÿ #×#

è inferiormente limitato (ad es., da  $_#) ed è superiormente limitato (ad es., da ).$_# 5.5.4 Nell’insieme dotato dell’ordinaria relazione di “minore o uguale”, l’insieme

Xœ ÖB − / B   #×#

5.6 - Estremo superiore.

Siano un insieme, A Ÿ una relazione di ordine in , e un sottoinsieme non vuoto diA X A superiormente limitato.

Se l’insieme delle limitazioni superiori di ha minimo, tale minimo si dice X estremo

superiore di , e si indica con X supX. Dal teorema 5.4.1 segue subito che l’estremo superiore,

qualora esista, è unico.

Teorema 5.6.1

Siano un insieme, A Ÿ una relazione di ordine in , e un sottoinsieme non vuoto di . SeA X A X ha un massimo, questo è anche estremo superiore per .X

Dimostrazione  Sia il massimo di . Per definizione di massimo, è unam X m

limitazione superiore per ; dobbiamo provare che per ogni limitazione superiore di si haX a X mŸa: ma ciò è ovvio (poiché m−X) per definizione di limitazione superiore.

Teorema 5.6.2

Siano un insieme, A Ÿ una relazione di ordine in , e un sottoinsieme non vuoto di A X A dotato di estremo superiore. Se sup X appartiene a , esso è il massimo di .X X

Dimostrazione Sia l’estremo superiore di . Poiché è una limitazione x! X x!

superiore per , si ha che X xŸx! per ogni x−X; poiché per ipotesi x! −X, si ha l’asserto.

I teoremi 5.6.1 e 5.6.2 suggeriscono che l’estremo superiore di può essere assuntoX come “surrogato” del massimo di quando tale massimo manca. Vedremo tuttavia (EsempioX 5.6.4) che anche l’estremo superiore può mancare.

Esempio 5.6.3

Nell’insieme dotato dell’ordinaria relazione di “minore o uguale”, l’insieme Xœ ÖB − / B œ _8"8 , con 8 − ×

ha per estremo superiore il numero ."

Dimostrazione  È chiaro che è una limitazione superiore per ; resta da provare" X

che ogni limitazione superiore per è maggiore o uguale a , ossia che nessun numeroX " razionale strettamente minore di è limitazione superiore per .C " X

Sia dunque C − , C  ". Possiamo scrivere C œ 7₈ , con ,7 8 −, 8 Á ! 7  8, (ossia 7  " Ÿ 8); allora C œ 7₈ Ÿ _7"7 œ _#7##7  _#7"#7

Esempio 5.6.4

Nell’insieme dotato dell’ordinaria relazione di “minore o uguale”, l’insieme Xœ ÖB − / B Ÿ #×#

è superiormente limitato e non ha estremo superiore.

Dimostrazione  Osserviamo intanto che ogni numero razionale positivo tale che!

!#   _{# è una limitazione superiore per . In effetti, da X} !_{ B con B −} _segue !# _{ B}#_;

dunque se B −X deve essere B Ÿ!, dovendosi altrimenti avere # Ÿ!# Ÿ B#.

Supponiamo ora per assurdo che esista B œ! sup X . Poiché (osservazione 1.8.1) non può essere B œ #!# , sarà B  #!# oppure B  #!# .

Se B  #_!# , è B −! X e dunque B œ! max : mostriamo che ciò non è possibile,X determinando & − tale che B  −! & X. Se & Ÿ ", si ha

(B ! &)# œ B  # B #! & ! &# Ÿ B  # B  œ B #! & ! & !# &(#B  "! ).

Possiamo determinare in modo che sia & B !# &(#B  " œ #! ) : se risulta &− ! "( , ], abbiamo dimostrato che B ! & appartiene a . In effetti si haX

& œ _{#B "}#B! !

#

;

dunque & !, perché B  #_!# per ipotesi (e B  !! ). Inoltre & Ÿ ", perché ciò significa #  B Ÿ #B  "!# ! , ossia " Ÿ B B  #!( ! ), e questo è ovvio essendo B   "! (infatti " −X).

Resta da considerare la possibilità che sia B  #_!# . Mostriamo che in questo caso si può determinare &− tale che B  −! &  e (B ! &)#  #. Ciò conduce ad un assurdo, perché B ! & risulta una limitazione superiore per strettamente minore di X B!. Si ha

(B ! &)# œ B  # B #! & ! &#  B  # B!# & !.

Basta allora determinare in modo che sia & B  # B œ #!# & ! ; si trova & œ B #_#B!

! #

(e si noti che &  ! perché B  #_!# per ipotesi, e B  !! ).

5.7 - Estremo inferiore.

Siano un insieme, A Ÿ una relazione di ordine in , e un sottoinsieme non vuoto diA X A inferiormente limitato.

Se l’insieme delle limitazioni inferiori di ha massimo, tale massimo si dice X estremo

inferiore di , e si indica con X infX. Ancora dal teorema 5.4.1 segue che l’estremo inferiore,

Teorema 5.7.1

Siano un insieme, A Ÿ una relazione di ordine in , e un sottoinsieme non vuoto di . SeA X A X ha un minimo, questo è anche estremo inferiore per .X

Dimostrazione  La dimostrazione è analoga a quella del teorema 5.6.1, e si lascia al

lettore come esercizio [*].

Teorema 5.7.2

Siano un insieme, A Ÿ una relazione di ordine in , e un sottoinsieme non vuoto di A X A dotato di estremo inferiore. Se inf X appartiene a , esso è il minimo di .X X

Dimostrazione  La dimostrazione è analoga a quella del teorema 5.6.2, e si lascia al

lettore come esercizio [*].

Esempio 5.7.3

Nell’insieme dotato dell’ordinaria relazione di “minore o uguale”, l’insieme Xœ ÖB −  / B œ ₈", con 8 −\Ö!××

ha per estremo inferiore il numero . (Cfr. esempio 5.4.4).!

Dimostrazione  È chiaro che è una limitazione inferiore per ; resta da provare! X

che ogni limitazione inferiore per è minore o uguale a , ossia che nessun numero razionaleX ! positivo è limitazione inferiore per .C X

Sia dunque C −. Possiamo scrivere C œ 7 , con , 7 8 − ÏÖ!× ; allora

8

C œ 7₈ œ #7_#8 œ #7_#8"  _#8" con _#8" − X, come si voleva.

Esempio 5.7.4

Nell’insieme dotato dell’ordinaria relazione di “minore o uguale”, l’insieme Xœ ÖB − / B   #×#

è inferiormente limitato ma non ha estremo inferiore. (La dimostrazione è analoga a quella di 5.6.4).

Esercizio 5.7.5

Nell’insieme dotato della relazione di “divisibilità” (cfr. esempio 5.2.2), si consideri l’ insieme

Xœ Ö#! $! '! )! "!!×, , , , (cfr. esempio 5.4.3). Determinare (qualora esistano) estremo inferiore ed estremo superiore per X.

5.8 - Completezza.

Siano un insieme e A Ÿ una relazione di ordine in .A

A si dice completo se ogni sottoinsieme non vuoto di che sia superiormente limitatoA ha estremo superiore.

Esempio 5.8.1

L’insieme con l’ordinaria relazione di “minore o uguale” è completo. (In effetti, in ogni™ ™ sottoinsieme non vuoto che sia superiormente limitato ha massimo.)

Esempio 5.8.2

L’insieme con l’ordinaria relazione di “minore o uguale” non è completo (cfr. esempio 5.7.4).

Osservazione 5.8.3

È ovvio, ma importante, che proprietà quali la completezza dipendono non tanto dall’insieme che si sta considerando quanto dalla relazione d’ordine che vi si è definita (e che non è mai l’unica possibile!). Per convincersene, definiamo in una relazione d’ordine come segue: Rappresentiamo ogni elemento di con la frazione  7₈ tale che , sono primi fra loro e7 8 8  ! (tale frazione resta univocamente determinata da queste condizioni); diciamo altezza di

7

8 il numero naturale ± 7 ±  8. Poniamo poi 78 Ÿ 78 se e solo se l’altezza di 78 è

" # "

" # "

strettamente minore dell’altezza di 7₈# 7₈" e 7₈# hanno la stessa altezza e

# oppure " # 7 Ÿ 7" #

(secondo l’usuale relazione d’ordine fissata in ).™

È facile Ð Ñ11 vedere che rispetto a questa relazione d’ordine  ogni sottoinsieme non vuoto di ha minimo;

 ogni sottoinsieme non vuoto di che sia superiormente limitato ha massimo (e quindi, in particolare, ha estremo superiore).

Teorema 5.8.4

Siano un insieme e A Ÿ una relazione di ordine in .A

A è completo se e solo se ogni sottoinsieme non vuoto di che sia inferiormente limitato haA estremo inferiore.

Dimostrazione  Omettiamo la dimostrazione di questo teorema.

11 _{Si tratta in sostanza di osservare che per ogni 2 −  esiste solo un numero finito di frazioni aventi} altezza .2

Nel documento Istituzioni di Matematica (pagine 49-57)