3.9 Buoni ordinamenti[1YQ]

[222]La teoria dei buoni ordinamenti è molto legata alla teoria degli ordinali, di cui abbiamo dato pochi cenni in Sez. ??. Ci limitiamo a dire che ogni ordinale è il rappresentante standard di un tipo di buon ordinamento. Usando la teoria standard degli ordinali (dovuta a Von Neumann) molti degli esercizi successivi si possono riformulare e semplificare.

E104

[07W]Se \((X,≤)\) è un insieme bene ordinato e \(Y⊆ X\) è un sottoinsieme, allora \(Y\) con (la restrizione de) l’ordinamento \(≤\) è un insieme bene ordinato.

E104

[07X] Prerequisiti:134.(Svolto il 2023-01-17) (Proposto il 2022-12) Sia \(X\) un insieme totalmente ordinato. Mostrate che sono equivalenti:

1. \(X\) è bene ordinato;

2. non esistono funzioni \(f:ℕ→ X\) strettamente decrescenti.

(È un caso particolare di 11)

E104

[22F]Prerequisiti:72,64,69,2.Difficoltà:*.Note:Esercizio 3 del compito del 29 Gennaio 2021.(Svolto il 2022-10-13
in parte)

Sia dato \((X,≤_ X )\) dove \(X\) un insieme infinito e \(≤_ X\) è un buon ordinamento.

• Se \(X\) non ha massimo, allora esiste \((Y,≤_ Y )\) tale che posto \(Z=Y× ℕ\) con \(≤_ Z\) l’ordinamento lessicografico, allora \((X,≤_ X)\) e \((Z,≤_ Z)\) hanno lo stesso tipo d’ordine.

• Se invece \(X\) ha massimo, allora esistono \((Y,≤_ Y )\) e \(k∈ℕ\) tale che, posto \(Z\) essere la concatenazione di \(Y× ℕ\) e di \(\{ 0,\ldots k\} \) (dove \(Y×ℕ\) ha l’ordinamento lessicografico, come sopra), allora \((X,≤_ X)\) e \((Z,≤_ Z)\) hanno lo stesso tipo d’ordine.

• Mostrate che, nei casi precedenti, \(Y\) è bene ordinato.

Soluzione nascosta: [UNACCESSIBLE UUID ’22G’]

E104

[0DQ]Difficoltà:*.(Proposto il 2022-12) Sia dato l’insieme (parzialmento) ordinato \((X,≤)\); definiamo

\[ P_ x {\stackrel{.}{=}}\{ w∈ X: w {\lt} x\} \quad . \]

supponiamo che \((X,≤)\) soddisfi questi due requisiti:

• \[ ∀ x,y∈ X~ ,~ P_ x = P_ y ⇒ x=y \]

• ogni insieme non-vuoto \(A⊆ X\) contiene almeno un elemento minimale, cioè

  \[ ∃ a∈ A, ∀ b∈ A ¬(b{\lt}a)\quad ; \]

allora \((X,≤)\) è bene ordinato.

Soluzione nascosta: [UNACCESSIBLE UUID ’26R’]

Successore

E105

[1Z1]Prerequisiti:105. (Proposto il 2023-01-17)

Supponiamo che \(X\) non abbia massimo; sia \(S\) definito come in 105; si dimostri che è una funzione iniettiva

\[ S:X→ X\quad , \]

e che \(S(x)≠ 0_ X\), per ogni \(x\) (cioè, \(0_ X\) non è successore di nessun elemento).

Soluzione nascosta: [UNACCESSIBLE UUID ’223’]

Notiamo che in generale \(S\) non sarà surgettiva come funzione \(S: X→ X⧵ \{ 0_ X\} \): vi potrebbero essere altri elementi \(y∈ S, y≠ 0_ X\) che non sono successori di alcun elemento. Se però, dato \(y∈ X\), esiste \(x∈ X\) per cui \(y=S(x)\), diremo che \(x\) è il predecessore di \(y\).

E105

[22H]Prerequisiti:105,1.Se \(x≤ y≤ S(x)\) allora \(y=x∨ y=S(x)\).

Soluzione nascosta: [UNACCESSIBLE UUID ’22J’]

(Il senso di questo risultato è che \(S(x)\) è l’immediato successore di \(x\), non ci sta niente in mezzo...).

Segmenti e buoni ordinamenti

Nel seguito \((X,\le _ X)\) sarà un insieme ben ordinato.

E106

[07Z] Mostrate che l’unione di segmenti iniziali è un segmento iniziale.

E106

[080] (Svolto il 2023-01-17) Se \(S⊆ X\) è un segmento iniziale e \(S≠ X\), mostrate che esiste ed è unico \(s ∈ X⧵ S\) (detto l’elemento successivo a \(S\)) che estende \(S\), tale cioè che \(S ∪ \{ s\} \) è un segmento iniziale. Soluzione nascosta: [UNACCESSIBLE UUID ’081’] (Si noti che vi sono analogie con il concetto di "successore" visto in 105...potremmo dire che \(s\) è il successore del segmento \(S\)).

E106

[082] Prerequisiti: 67, 68, 4.(Svolto il 2023-01-17) Sia \(X\) un insieme bene ordinato. Mostrate che se \(I⊆ X\) è un intervallo allora \(I=[a,b)\) oppure \(I=[a,b]\) oppure \(I=[a,∞)\) con \(a,b∈ X\). (Il viceversa è ovviamente vero).

In particolare un segmento iniziale è \([0_ X,b)\) o \([0_ X,b]\) oppure tutto \(X\). Soluzione nascosta: [UNACCESSIBLE UUID ’083’]

E106

[084] Siano \((X,≤_ X),(Y,≤_ Y)\) insiemi non vuoti totalmente ordinati. Sia \(f:X→ Y\) una funzione bigettiva strettamente crescente. Allora per ogni \(S⊆ X\) segmento iniziale si ha che \(f(S)\) è un segmento iniziale di \(Y\); e viceversa. Soluzione nascosta: [UNACCESSIBLE UUID ’085’]

E106

[086] Prerequisiti:2,134,69.

Sia \((X,≤_ X)\) un insieme non vuoto bene ordinato. Mostrate che se \(S⊆ X\) è un segmento iniziale e \((X,≤_ X)\) e \((S,≤_ X)\) sono equiordinati dalla mappa \(f:S→ X\) allora \(X=S\) e \(f\) è l’identità.

Soluzione nascosta: [UNACCESSIBLE UUID ’087’][UNACCESSIBLE UUID ’088’]

(Notate la differenza con la teoria delle cardinalità: un insieme infinito è in corrispondenza biunivoca con una sua parte propria, cf 2 e 2. Inoltre se due insiemi hanno la stessa cardinalità allora vi sono molte bigezioni fra essi.)

E106

[089](Svolto il 2023-01-17) Date un esempio di un insieme totalmente ordinato \((X,≤_ X)\) che ha minimo, e di un segmento iniziale \(S\) tali che \((X,≤_ X)\) e \((S,≤_ X)\) sono equiordinati. Soluzione nascosta: [UNACCESSIBLE UUID ’08B’]

E106

[08C]Prerequisiti:5.(Proposto il 2022-12) Siano \((X,≤_ X)\) e \((Y,≤_ Y)\) bene ordinati; supponiamo che esista \(f:X→ T\) funzione bigettiva monotona strettamente crescente, dove \(T\) un segmento iniziale di \(Y\); allora \(f\) è unica (e unico è \(T\)). Soluzione nascosta: [UNACCESSIBLE UUID ’08D’]

E106

[08F]Prerequisiti:17, 1, 4, 2, 7.

Siano dati due insiemi non vuoti bene ordinati \((X,≤_ X)\) e \((Y,≤_ Y)\). Mostrate che

1. esiste un segmento iniziale \(S\) di \(X\) e una funzione bigettiva monotona strettamente crescente \(g:S→ Y\); oppure ²

2. esiste un segmento iniziale \(T\) di \(Y\) e una funzione bigettiva monotona strettamente crescente \(g:X→ T\).

Nel primo caso scriveremo che \((Y,≤_ Y)⪯ (X,≤_ X)\), nel secondo che \((X,≤_ X)⪯ (Y,≤_ Y)\). (Notate che nel primo caso si ha \(|Y|≤ |X|\) e nel secondo \(|X|≤ |Y|\)). Per l’esercizio precedente la mappa \(g\) e il relativo segmento sono uniche.

Soluzione nascosta: [UNACCESSIBLE UUID ’08G’]

E106

[08H]Prerequisiti:8.Mostrate che se \((X,≤_ X)⪯ (Y,≤_ Y)\) e anche \((Y,≤_ Y)⪯ (X,≤_ X)\), allora sono equiordinati.

Soluzione nascosta: [UNACCESSIBLE UUID ’08J’]

La relazione \(⪯\) è dunque una relazione di ordine totale fra tipi di buoni ordinamenti.

Esempi

E106

[08K] Prerequisiti:3.Il tipo di buon ordinamento di \(ℕ\) è chiamato \(𝜔\). Dato \(k≥ 2\) naturale, \(ℕ^ k\) dotato dell’ordinamento lessicografico è un insieme bene ordinato (per 3), e il suo tipo di buon ordinamento è chiamato \(𝜔^ k\). Mostrate che \(𝜔^ k⪯𝜔^ h \) per \(h{\gt}k\), e che \(𝜔^ k,𝜔^ h \) non hanno lo stesso tipo d’ordine.

E106

[08M] Difficoltà:*.Costruite un buon ordinamento su un insieme numerabile \(X\) tale che \(X=⋃_{n=1}^∞ S_ n\) dove \(S_ n\) sono segmenti iniziali, ciascuno con tipo di ordinamento \(𝜔^ n\). L’ordinamento così costruito su \(X\) si indica con \(𝜔^𝜔\). Soluzione nascosta: [UNACCESSIBLE UUID ’08N’]

E106

[08P]Difficoltà:*.Costruite una mappa crescente fra \(𝜔^𝜔\) e \(ℝ\). Soluzione nascosta: [UNACCESSIBLE UUID ’08Q’]

[UNACCESSIBLE UUID ’08R’]

[UNACCESSIBLE UUID ’08S’]