: Ordinamenti<a class="btn btn-sm" href="/UUID/EDB/1YY/?lang=ita"><span class="ttfamily"><small class="scriptsize">[1YY]</small></span></a>

2.4 Ordinamenti[1YY]

Sia $(X, \leq)$ un insieme non vuoto e ordinato (cf definizione 48)

Definizione 52

[229]Dati $x, y \in X$ ricordiamo che $x < y$ significa $x \leq y \land x \neq y$ .

Quando si ha che $x \leq y$ oppure $y \leq x$ diremo che i due elementi sono “comparabili”. Viceversa se non si ha ne $x \leq y$ ne $y \leq x$ diremo che i due elementi sono “incomparabili”.
Un elemento $m \in X$ si dice massimale se non esiste alcun elemento $z \in X$ tale che $m < z$ .
Un elemento $m \in X$ si dice minimale se non esiste alcun elemento $z \in X$ tale che $z < m$ .
Un elemento $m \in X$ si dice massimo se, per ogni elemento $z \in X$ , si ha $z \leq m$ .
Un elemento $m \in X$ si dice minimo se, per ogni elemento $z \in X$ , si ha $m \leq z$ .

Invertendo la relazione d’ordine, le definizioni di minimo/minimale divengono le definizioni di massimo/massimale (e viceversa).

E52

[1WJ]Dato un insieme ordinato, mostrate che il massimo, se esiste, è unico.

E52

[067] (Svolto il 2022-10-13) Mostrate che per ogni due $x, y \in X$ si ha uno di questi casi mutualmente esclusivi

$x = y$ ,
$x < y$ ,
$x > y$ ,
$x, y$ sono incomparabili.

Soluzione nascosta: [UNACCESSIBLE UUID ’068’]

E52

[29D]Mostrate che se $x < y \land y \leq z$ oppure $x \leq y \land y < z$ allora $x < z$ .

E52

[069]Mostrate che $m \in X$ è massimale se e solo se ”per ogni $z \in X$ si ha che $z \leq m$ oppure $z, m$ sono incomparabili”.

Soluzione nascosta: [UNACCESSIBLE UUID ’06B’]

E52

[1WM]Sia $f : A \to B$ una funzione, sia $⪯$ una relazione d’ordine su $B$ ; consideriamo la relazione $R$ fra elementi di $A$ data da

x R y ⟺ f (x) ⪯ f (y);

è una relazione d’ordine? E se assumiamo inoltre che $f$ sia iniettiva?

E52

[1WN] Mostrare che se ogni sottoinsieme non-vuoto ammette minimo, allora l’ordinamento è totale.

E52

[1YJ] Consideriamo $A = ℝ^{2}$ e consideriamo la relazione

(x, y) ⪯ (x^{'}, y^{'}) ⟺ (x \leq x^{'} \land y \leq y^{'})

mostrate che è una relazione di ordine; è parziale o totale?
Preso $B = {(x, y) : x^{2} + y^{2} \leq 1}$ , consideriamolo come insieme ordinato con l’ordinamento $⪯$ : vi sono massimi? minimi? massimali? minimali?

E52

[06C](Proposto il 2022-12) Sia $(X, \leq)$ un insieme non vuoto finito e ordinato allora ammette massimali e minimali. Soluzione nascosta: [UNACCESSIBLE UUID ’06D’]

E52

[06F]Si costruisca un ordinamento $⪯$ su $ℕ$ con questa proprietà: per ogni $n \in ℕ$

l’insieme ${k \in ℕ, k \neq n, k ⪯ n}$ degli elementi che precedono $n$ ha esattamente due massimali,
l’insieme ${k \in ℕ, k \neq n, n ⪯ k}$ degli elementi che seguono $n$ ha esattamente due minimali.

E52

[06J](Proposto il 2022-12) Sia $X$ insieme non vuoto e $R \subseteq X^{2}$ una relazione d’ordine, allora esiste una relazione di ordine totale $T$ che estende $R$ (cioè $R \subseteq T$ , considerando le relazioni come sottoinsiemi di $X^{2}$ ).

E52

[263] Prerequisiti:133,1.(Svolto il 2022-10-13) Sia $X$ ordinato (parzialmente). Mostrate che sono equivalenti

in ogni sottoinsieme $A \subseteq X$ non-vuoto esiste almeno un elemento minimale;
non esistono funzioni $f : ℕ \to X$ strettamente decrescenti.

Soluzione nascosta: [UNACCESSIBLE UUID ’07Y’]

Si veda anche la Proposizione 82.

[UNACCESSIBLE UUID ’06K’] [UNACCESSIBLE UUID ’1YZ’]

Ordinamento diretto e filtrante[2FJ]

Definizione 53

[06M] (Svolto il 2022-11-24) Sia $(X, \leq)$ un insieme (parzialmente) ordinato, diremo che è filtrante ¹ se

\forall x, y \in X \exists z \in X, x < z \land y < z .

Gli insiemi

ℝ, ℕ, ℚ, ℤ

con i loro usuali ordinamenti sono filtranti.

Definizione 55

[06N] Un insieme diretto è un insieme (parzialmente) ordinato $(X, \leq)$ per cui

\forall x, y \in X \exists z \in X, x \leq z \land y \leq z .

Ovviamente un ordinamento filtrante è anche diretto.

Nota 57

[0NB]Abbiamo aggiunto la proprietà antisimmetrica alla usuale definizione di "Insieme Diretto", si veda [ 15 ] (o altre referenze in [ 34 ] ).

Questa scelta semplifica il trattamento (in particolare, ci permette di usare concetti già visti per insiemi ordinati, quali massimo o massimale) e allo stesso tempo, per quanto spiegato in 235, non cambia l’utilità della teoria sviluppata in questa sezione e in Sezione 6.4.

Definizione 58

[06P] Dato un insieme diretto $(X, \leq_{X})$ un suo sottoinsieme $Y \subseteq X$ si dice cofinale se

\forall x \in X \exists y \in Y, y \geq_{X} x

Più in generale, un altro insieme diretto $(Z, \leq_{Z})$ si dice cofinale in $X$ se esiste una mappa $i : Z \to X$ monotona debolmente crescente tale che $i (Z)$ è cofinale in $X$ , cioè

(\forall z_{1}, z_{2} \in Z, z_{1} \leq_{Z} z_{2} \Rightarrow i (z_{1}) \leq_{X} i (z_{2})) \land (\forall x \in X \exists z \in Z, i (z) \geq_{X} x)

(Questo secondo caso generalizza il precedente, decidendo che $i : Y \to X$ è l’identità e $\leq_{Y}$ è la restrizione di $\leq_{X}$ a $Y$ .)

Definizione 61

[231] Se $X$ è filtrante, “un intorno di $\infty$ in $X$ ” è un sottoinsieme $U \subseteq X$ tale che

\exists k \in X \forall j \in X, j \geq k \Rightarrow j \in U .

E61

[06Q] (Proposto il 2022-11) Sia $(X, \leq)$ un insieme ordinato filtrante, si mostri che è un insieme infinito. Soluzione nascosta: [UNACCESSIBLE UUID ’06R’]

E61

[06S] (Svolto il 2022-10-27) Sia $(X, \leq)$ un insieme diretto: si mostri che se esiste un elemento massimale in $X$ allora è il massimo. Soluzione nascosta: [UNACCESSIBLE UUID ’06T’]

E61

[06V] Prerequisiti:53,2.(Svolto il 2022-11-24) Sia $(X, \leq)$ un insieme diretto. Si mostri che sono equivalenti queste proprietà:

$(X, \leq)$ soddisfa la proprietà filtrante 54,
$(X, \leq)$ non ha massimo,
$(X, \leq)$ non ha massimali.

Soluzione nascosta: [UNACCESSIBLE UUID ’06W’]

E61

[06X]Prerequisiti:58.Sia $(X, \leq)$ un insieme diretto, sia $Y \subseteq X$ cofinale: si mostri che $(Y, \leq_{| Y})$ è un insieme diretto.

Similmente se $(X, \leq)$ è filtrante, si mostri che $(Y, \leq_{| Y})$ è filtrante.

E61

[232]Prerequisiti:61.Dati $U_{1}, U_{2} \subseteq J$ due intorni di $\infty$ si mostri che l’intersezione $U_{1} \cap U_{2}$ è un intorno di $\infty$ . Soluzione nascosta: [UNACCESSIBLE UUID ’236’] .

E61

[234]Prerequisiti:58,61.Se $(X, \leq)$ un insieme filtrante, $Y \subseteq X$ è cofinale, e $U \subseteq X$ è un intorno di $\infty$ in $X$ , si mostri che $U \cap Y$ è un intorno di $\infty$ in $Y$ . Soluzione nascosta: [UNACCESSIBLE UUID ’235’]

Un insieme diretto $(X, \leq)$ è un ambiente a cui si può facilmente generalizzare la nozione già vista 159.

Definizione 62

[06Y] (Svolto il 2022-10-27) Sia P(x) una proposizione logica che dipende da una variabile libera $x \in X$ . Diremo che

P(x) vale definitivamente per $x \in X$ se	$\exists y \in X, \forall x \in X, x \geq y$ vale P(x) ;
P(x) vale frequentemente per $x \in X$ se	$\forall y \in X, \exists x \in X, x \geq y$ per cui P(x) .

E62

[070] (Proposto il 2022-10-27) La proprietà 3 si riformula in questo modo.

Mostrate che «P(x) vale frequentemente in $x \in X$ » se e solo se l’insieme

Y = {x \in X : P (x)}

è cofinale in $X$ .

E62

[233]Prerequisiti:62,5.Mostrate che «P(x) vale definitivamente in $x \in X$ » se e solo se l’insieme

U = {x \in X : P (x)}

è un intorno di $\infty$ in $X$ .

E62

[06Z]Si verifichi per esercizio che le proprietà 1, 2, 4 e 5 viste in Sez. 3.7 valgono anche in questo caso 62 più generale.

E62

[2B2]Supponiamo che l’insieme $X$ abbia associato una relazione $R$ che sia riflessiva e transitiva e per cui

\forall x, y \in X \exists z \in X, x R z, y R z .

(come visto in ??)

Questa coppia $(X, R)$ è un "Insieme Diretto" secondo la definizione usuale (cfr. [ 15 ] o altre referenze in [ 34 ] ).

Mostrate che esiste un’altra relazione $\leq$ tale che

$\leq$ è un ordine parziale che soddisfa ??;
$R$ estende $\leq$ cioè

$\forall x, y \in X x \leq y \Rightarrow x R y;$
inoltre $(X, \leq)$ è cofinale in $(X, R)$ .

Soluzione nascosta: [UNACCESSIBLE UUID ’2GM’]

Altri esercizi sull’argomento sono 174,8, e in Sezione 6.4.

Ordinamento lessicografico[2FH]

Definizione 64

[071] Dati due insiemi ordinati $(X, \leq_{X})$ e $(Y, \leq_{Y})$ , posto $Z = X \times Y$ , definiamo l’ordinamento lessicografico $\leq_{Z}$ su $Z$ come segue; siano $z_{1} = ⦗ x_{1}, y_{1} ⦘ \in Z$ e $z_{2} = ⦗ x_{2}, y_{2} ⦘ \in Z$ , allora:

nel caso $x_{1} \neq x_{2}$ , allora $z_{1} \leq_{Z} z_{2}$ se e solo se $x_{1} \leq_{X} x_{2}$ ;
nel caso $x_{1} = x_{2}$ , allora $z_{1} \leq_{Z} z_{2}$ se e solo se $y_{1} \leq_{Y} y_{2}$ .

Questo si estende al prodotto di più insiemi: dati due vettori, si considerano i primi elementi, se sono diversi si usa il primo ordinamento, se sono uguali si passa ai secondi elementi, ecc.

E64: [1WP]Si verifichi che $\leq_{Z}$ è un ordinamento.
E64: [072] Se $(X, \leq_{X})$ e $(Y, \leq_{Y})$ sono ordinamenti totali, si mostri che $(Z, \leq_{Z})$ è un ordinamento totale.
E64: [073] Se $(X, \leq_{X})$ e $(Y, \leq_{Y})$ sono buoni ordinamenti, si mostri che $(Z, \leq_{Z})$ è un buon ordinamento.
E64: [074] Sia $X = ℕ^{ℕ}$ ordinato con l’ordinamento lessicografico. Si costruisca una funzione $f : X \to ℝ$ strettamente crescente. Soluzione nascosta: [UNACCESSIBLE UUID ’075’]
E64: [076]Consideriamo $X = ℝ \times {0, 1}$ ordinato con l’ordinamento lessicografico. Si mostri che non esiste una funzione $f : X \to ℝ$ strettamente crescente. Soluzione nascosta: [UNACCESSIBLE UUID ’077’]

Ordinamento totale, sup e inf[2FM]

Sia $\leq$ un ordinamento totale su $X$ insieme non vuoto.

Definizione 65

[22R] Sia $A \subseteq X$ . I maggioranti di $A$ sono

M_{A} \dot{=} {x \in X : \forall a \in A, a \leq x} .

Un insieme $A$ è superiormente limitato quando esiste un $x \in X$ tale che $\forall a \in A, a \leq x$ , cioè esattamente quando $M_{A} \neq \emptyset$ .

Se $M_{A}$ ha minimo $s$ , $s$ è l’estremo superiore di $A$ , e scriveremo $s = sup A$ .

Invertendo la relazione d’ordine, otteniamo le definizione maggioranti, inferiormente limitato, estremo inferiore.

Lemma 66

[22S]Sia $A \subseteq X$ non vuoto. Ricordiamo queste proprietà dell’estremo superiore.

Se $A$ ha massimo $m$ allora $m = sup A$ .
Sia $s \in X$ . Si ha $s = sup A$ se e solo se
- per ogni $x \in A$ si ha $x \leq s$ .
- per ogni $x \in X$ con $x < s$ esiste $y \in A$ con $x < y$ .

Quest’ultima proprietà è di larghissimo uso nell’analisi!

La dimostrazione è lasciata come (utile) esercizio. Soluzione nascosta: [UNACCESSIBLE UUID ’22T’]

E66

[078] (Proposto il 2022-10-13) Sia $B$ un insieme non vuoto che è limitato dal basso, sia $L$ l’insieme dei minoranti di $B$ ; notiamo che $L$ è superiormente limitato, e supponiamo che esista $𝛼 = sup L$ : allora $𝛼 \in L$ e $𝛼 = inf B$ . Soluzione nascosta: [UNACCESSIBLE UUID ’079’]

E66

[07B]Prerequisiti:1.(Proposto il 2022-10-13) Mostrate che se per l’ordinamento totale di $X$ esistono i“sup” allora esistono anche gli “inf”; e viceversa. Precisamente, mostrate che sono equivalenti:

Ogni insieme non vuoto inferiormente limitato in $X$ ammette estremo inferiore;
ogni insieme non vuoto superiormente limitato in $X$ ammette estremo superiore.

Soluzione nascosta: [UNACCESSIBLE UUID ’207’]

Ordinamento totale, intervalli[2DW]

Sia $\leq$ un ordinamento totale su $X$ insieme non vuoto.

Definizione 67

[07C] Un insieme $I \subseteq X$ è un intervallo se per ogni $x, z \in I$ e ogni $y \in X$ con $x < y < z$ si ha $y \in I$ .

Notate che l’insieme vuoto è un intervallo.

Definizione 68

[07D] Dati $x, z \in X$ si definiscono i seguenti intervalli standard

\begin{aligned} (x, z) & = & {y \in X : x < y < z} \\ (x, z] & = & {y \in X : x < y \leq z} \\ (x, \infty) & = & {y \in X : x < y} \\ [x, z) & = & {y \in X : x \leq y < z} \\ [x, z] & = & {y \in X : x \leq y \leq z} \\ [x, \infty) & = & {y \in X : x \leq y} \\ (- \infty, z) & = & {y \in X : y < z} \\ (- \infty, z] & = & {y \in X : y \leq z} \\ (- \infty, \infty) & = & X . \end{aligned}

[24Y]Notate che vi sono 9 casi, combinazioni di tre per l’estremo destro e tre per l’estremo sinistro. Intendiamo che

\infty, - \infty

sono simboli e non elementi di

X

; per questo motivo se

X

ha massimo

m

, allora gli intervalli si scrivono preferibilmente come

(x, \infty) = (x, m]

[x, \infty) = [x, m]

; similmente se ha un minimo.

E68

[07F] Prerequisiti:67,68,3.

Sia $F$ una famiglia non vuota di intervalli.

Mostrate che la intersezione $⋂_{―} F$ di tutti gli intervalli è un intervallo.

Supponiamo che l’intersezione $⋂_{―} F$ sia non vuota, mostrate che la unione $⋃_{―} F$ è un intervallo.

Soluzione nascosta: [UNACCESSIBLE UUID ’07G’]

E68

[07H] Prerequisiti:67,68.(Svolto il 2022-10-13)

Si trovi un esempio di insieme $X$ con ordinamento totale, in cui vi è un intervallo $I$ che non ricade in nessuna delle categorie viste in 68.

Soluzione nascosta: [UNACCESSIBLE UUID ’07J’]

E68

[07K] Prerequisiti:67,68,1.(Proposto il 2022-10-13)

Sia $A \subseteq X$ un insieme non vuoto; sia $I$ il più piccolo intervallo che contiene $A$ ; questo è definito come l’intersezione di tutti gli intervalli che contengono $A$ (e l’intersezione è un intervallo, per 1). Sia $M_{A}$ la famiglia dei maggioranti di $A$ , $M_{I}$ di $I$ ; si mostri che $M_{A} = M_{I}$ . In particolare $A$ è superiormente limitato se e solo $I$ è superiormente limitato; se inoltre $A$ ha estremo superiore, si avrà $sup A = sup I$ . (Similmente per minoranti e estremi inferiori). Soluzione nascosta: [UNACCESSIBLE UUID ’07M’]

E68

[07N] Prerequisiti:67,68,1,3.

Sia $X$ un insieme totalmente ordinato. Mostrate che le due seguenti sono equivalenti.

Ogni $A \subseteq X$ non vuoto limitato dall’alto e dal basso ammette estremo superiore e inferiore.
Ogni intervallo $I \subseteq X$ non vuoto ricade in una delle categorie viste in 68.

Soluzione nascosta: [UNACCESSIBLE UUID ’07P’]

E68

[206]Prerequisiti:67,68,1.Difficoltà:*.

All’inizio della sezione abbiamo assunto che l’ordinamento $\leq$ su $X$ sia totale. Le definizioni di intervallo in 67 e in 68 si possono però dare anche per un ordinamento che non sia (necessariamente) totale. Cosa succede nell’esercizio 1 quando l’ordinamento non è totale? Quale risultato è vero, quale è falso, e nel caso che controesempio possiamo dare?

[UNACCESSIBLE UUID ’07Q’]

Tipi di ordine

Definizione 69

[07V]Dati due insiemi non vuoti ordinati $(X, \leq_{X})$ e $(Y, \leq_{Y})$ , diremo che “hanno lo stesso tipo d’ordine”, o più brevemente che sono “equiordinati” ² , se esiste una funzione bigettiva monotona strettamente crescente $f : X \to Y$ , la cui inversa $f^{- 1}$ è strettamente crescente. La funzione $f$ è detta “isomorfismo d’ordine”, o “isotonia”.

Nota 70

[21R]Notate che se $(X, \leq_{X})$ e $(Y, \leq_{Y})$ sono equiordinati allora $X$ e $Y$ sono equipotenti; però dato un insieme infinito $X$ , esistono su di esso ordinamenti di diverso tipo — anche se consideriamo solo i buoni ordinamenti. (Si veda ad esempio l’esercizio 1)

Nota 71

[21V]Notate che, se due insiemi sono equiordinati, allora godono delle stesse proprietà: se uno è totalmente ordinato, lo è anche l’altro; se uno è bene ordinato, lo è anche l’altro; etc etc.... Si veda 2.

E71

[220]Mostrate che la relazione "avere lo stesso tipo d’ordine" è una relazione d’equivalenza. Dato un insieme $X$ , consideriamo tutti i possibili ordinamenti su $X$ , la relazione definisce dunque classi di equivalenza, e ogni classe è (per l’appunto) un “tipo d’ordine” su $X$ .

E71

[22P](Proposto il 2023-01-17) Dati due insiemi non vuoti ordinati $(X, \leq_{X})$ e $(Y, \leq_{Y})$ , sia $f : X \to Y$ come da definizione 69.

Se $A \subseteq X$ e $m = max A$ allora $f (m) = max f (A)$ ; similmente per i minimi;
$(X, \leq_{X})$ è totalmente ordinato se e solo se $(Y, \leq_{Y})$ lo è;
$(X, \leq_{X})$ è bene ordinato se e solo se $(Y, \leq_{Y})$ lo è.
Supponiamo che $(X, \leq_{X})$ e $(Y, \leq_{Y})$ siano bene ordinati; siano $S_{X}$ e rispettivamente $S_{Y}$ le funzioni “successore” 104, allora si ha che $x$ non è il massimo di $X$ se e solo se $f (x)$ non è il massimo di $Y$ , e in questo caso $y = S_{X} (x)$ se e solo se $f (y) = S_{Y} (f (x))$ .

E71

[21P]Dati due insiemi non vuoti totalmente ordinati $(X, \leq_{X})$ e $(Y, \leq_{Y})$ , supponiamo che esista una funzione bigettiva monotona strettamente crescente $f : X \to Y$ : si mostri che allora la sua inversa $f^{- 1}$ è strettamente crescente, e conseguentemente $(X, \leq_{X})$ e $(Y, \leq_{Y})$ sono equiordinati. Soluzione nascosta: [UNACCESSIBLE UUID ’21T’]

E71

[21Q]Trovate un semplice esempio di due insiemi non vuoti (parzialmente) ordinati $(X, \leq_{X})$ e $(Y, \leq_{Y})$ , per cui esiste una funzione bigettiva monotona strettamente crescente $f : X \to Y$ , la cui inversa $f^{- 1}$ non è strettamente crescente. Soluzione nascosta: [UNACCESSIBLE UUID ’21S’]

Concatenazione

Definizione 72

[21W]Dati due insiemi ordinati $(X, \leq_{X})$ e $(Y, \leq_{Y})$ , con $X, Y$ disgiunti, la concatenazione di $X$ con $Y$ si ottiene definendo $Z = X \cup Y$ e dotandolo dell’ordinamento $\leq_{Z}$ dato da:

se $z_{1}, z_{2} \in X$ allora $z_{1} \leq_{Z} z_{2}$ se e solo se $z_{1} \leq_{X} z_{2}$ ;
se $z_{1}, z_{2} \in Y$ allora $z_{1} \leq_{Z} z_{2}$ se e solo se $z_{1} \leq_{Y} z_{2}$ ;
se $z_{1} \in X$ e $z_{2} \in Y$ allora si ha sempre $z_{1} \leq_{Z} z_{2}$ .

Questa operazione è alle volte indicata con la notazione $Z = X ⧺ Y$ .

Se gli insiemi non sono disgiunti, possiamo sostituirli con insiemi disgiunti definiti da $\tilde{X} = {0} \times X$ e $\tilde{Y} = {1} \times Y$ , poi potremo "ricopiare" i rispettivi ordinamenti, e infine potremo eseguire la concatenazione di $\tilde{X}$ e $\tilde{Y}$ .

E72: [21X]Sia $k \in ℕ$ e sia $I = {0, \dots, k}$ con l’usuale ordinamento di $ℕ$ : si mostri che la concatenazione di $I$ con $ℕ$ ha lo stesso tipo d’ordine di $ℕ$ ; mentre invece la concatenazione di $ℕ$ con $I$ non ha lo stesso tipo d’ordine.
E72: [21Y]Prerequisiti:64,69.Siano $(X_{1}, \leq_{1})$ , $(X_{2}, \leq_{2})$ due insiemi disgiunti e ordinati (parzialmente) e con lo stesso tipo d’ordine. Sia $I = {1, 2}$ con l’usuale ordinamento; sia $Z = I \times X_{1}$ dotato dell’ordinamento lessicografico; sia $W$ la concatenazione di di $X_{1}$ con $X_{2}$ : mostrate che $Z$ e $W$ hanno lo stesso tipo d’ordine. Soluzione nascosta: [UNACCESSIBLE UUID ’221’]
E72: [21Z]Siano $X_{1}, X_{2}$ due insiemi disgiunti e bene ordinati. Sia $W$ la concatenazione di di $X_{1}$ con $X_{2}$ : mostrate che è bene ordinato.