Set ben ordinato

In matematica , un insieme ordinato ( E , ≤) è ben ordinato e la relazione ≤ è un buon ordine se la seguente condizione è soddisfatta:

Qualsiasi porzione non vuota di E ha un elemento più piccolo .

Se ( E , ≤) è ben ordinata quindi ≤ è necessariamente un ordine totale , ossia due qualsiasi elementi x e y di E sono sempre comparabili. Infatti, l'insieme { x , y } ha un elemento più piccolo, quindi abbiamo x ≤ y o y ≤ x .

Se inoltre si verifica l' assioma della scelta dipendente , questa proprietà (per essere ben ordinata) è equivalente, per un ordine totale presupposto, alla condizione di catena discendente "non c'è sequenza infinita strettamente decrescente". Secondo il teorema di Zermelo , l' assioma della scelta in tutta la sua forza è equivalente al fatto che qualsiasi insieme può essere ben ordinato.

Esempi e controesempi

Qualsiasi parte di un insieme ben ordinato è essa stessa ben ordinata (per l'ordine indotto).
L'insieme vuoto è ben ordinato dalla sua unica relazione : (Ø, Ø) (è il più piccolo ordinale ).
Più in generale, qualsiasi insieme finito totalmente ordinato è ben ordinato. Tale insieme ordinato è caratterizzato (in isomorfismo vicino ) dal numero n di elementi dell'insieme, che giustifica la notazione n per la corrispondenza del tipo di ordine .
Se definisce un buon ordine basato su e una stringa di , la restrizione è un buon ordine. ${\ displaystyle \ leq}$ ${\ displaystyle (E, \ leq)}$ $VS$ ${\ displaystyle (E, \ leq)}$ ${\ displaystyle (C, \ leq)}$
L'insieme (ℕ, ≤) di interi naturali , fornito con il suo normale ordine, è ben ordinato; è spesso notato ω in questo contesto.
Se è una famiglia di insiemi ben ordinati e se è dotata di un buon ordine, allora: (Eio,≤io)io∈io{\ displaystyle (E_ {i}, \ leq _ {i}) _ {i \ in I}} ${\ displaystyle (E_ {i}, \ leq _ {i}) _ {i \ in I}}$ io{\ displaystyle I} $io$
- se è finito, sul
prodotto l' ordine lessicografico è un buon ordine. Per quattro esempi di prodotti di una coppia di buoni ordini, vedere n × p , 2 × N , N × 2 e N × N (isomorfi agli ordinali dei prodotti pn , ω2, 2ω (= ω) e ω 2, rispettivamente ) ;io{\ displaystyle I} $io$ ∏io∈ioEio={(Xio)io∈io∣∀io∈io, Xio∈Eio}{\ displaystyle \ prod _ {i \ in I} E_ {i} = \ {(x_ {i}) _ {i \ in I} \ mid \ forall i \ in I, \ x_ {i} \ in E_ { io} \}} ${\ displaystyle \ prod _ {i \ in I} E_ {i} = \ {(x_ {i}) _ {i \ in I} \ mid \ forall i \ in I, \ x_ {i} \ in E_ { io} \}}$
l' unione disgiunta è ben ordinata da: if o ( e ). Questo ordine corretto è chiamato somma ordinale della famiglia. Notatelo . Viene annotata la somma ordinale di un paio di buoni ordini . Per tre esempi, vedere ω + ω (= ω2) e 3 + ω, ω + 3 (⊂ ω2) . ${\ displaystyle \ bigsqcup _ {i \ in I} E_ {i} = \ {(i, x) \ metà i \ in I, \ x \ in E_ {i} \}}$ ${\ displaystyle (i, x) \ leq (j, y)}$ $io <j$ $i = j$ ${\ displaystyle x \ leq _ {i} y}$ ${\ Displaystyle \ sum _ {i \ in I} E = I \ volte E}$ $(A, B)$ $A + B$

Dimostrazione

Prodotto cartesiano (finito): abbiamo ragione per induzione sulla cardinalità di : io{\ displaystyle I} $io$
- inizializzazione: se , cioè , si riduce a un singoletto (rigorosamente, quello contenente la sequenza vuota :) , quindi ben ordinato; ${\ displaystyle | I | = 0}$ ${\ displaystyle I = \ varnothing}$ $\ prod_ {i \ in I} E_i$ ${\ displaystyle \ {() \}}$
- ereditarietà: si presume che la proprietà sia genericamente vera per qualsiasi insieme di indici del cardinale $n$ ; supponiamo . Sia $A$ una parte non vuota di . $Io$ essendo ben ordinato, ammette un elemento più piccolo $i$ $0$ ; poniamo quindi e (dove denota la proiezione canonica sul componente $i$ $0$ ). Definiamo quindi $A$ $'$ di , il che è legittimo poiché $A$ $i$ $0$ è una parte non vuota (per non vuoto di $A$ ) dell'insieme ordinato $E$ $i$ $0$ e quindi ammette effettivamente un minimo. $A$ $'$ non è vuoto allora (sempre perché $A$ non lo è neanche); ora fa parte dell'insieme $E$ $'$ , che è ben ordinato (per l'ordine lessicografico indotto) per ipotesi di induzione poiché , e di conseguenza, $A$ $'$ ha un elemento più piccolo . Notando , otteniamo con un minimo di $A$ : anzi, se , allora ; c'è un'alternativa: o , e quindi , oppure , e abbiamo quindi , quindi per minimalità di in $A$ $'$ , che, secondo la definizione ricorsiva dell'ordine lessicografico , restituisce bene . ${\ displaystyle | I | = n + 1}$ $\ prod_ {i \ in I} E_i$ ${\ displaystyle I '= I \ setminus \ {i_ {0} \}}$ ${\ displaystyle E '= \ prod _ {i \ in I'} E_ {i}}$ ${\ displaystyle A_ {i_ {0}} = \ pi _ {i_ {0}} (A)}$ ${\ displaystyle \ pi _ {i_ {0}}}$ ${\ displaystyle A '= \ {(x_ {i}) _ {i \ in I'} \ in E '\ mid (x_ {i}) _ {i \ in I} \ in A \ \ \ mathrm {e } \ x_ {i_ {0}} = \ operatorname {min} (A_ {i_ {0}}) \}}$ ${\ displaystyle | I '| = n}$ ${\ displaystyle (m_ {i}) _ {i \ in I '}}$
  ${\ displaystyle m_ {i_ {0}} = \ operatorname {min} (A_ {i_ {0}})}$ ${\ displaystyle (m_ {i}) _ {i \ in I}}$ ${\ displaystyle (x_ {i}) _ {i \ in I} \ in A}$ ${\ displaystyle m_ {i_ {0}} \ leq x_ {i_ {0}}}$ ${\ displaystyle m_ {i_ {0}} <x_ {i_ {0}}}$ ${\ displaystyle (m_ {i}) _ {i \ in I} \ leq _ {\ mathrm {lex} _ {I}} (x_ {i}) _ {i \ in I}}$ ${\ displaystyle m_ {i_ {0}} = x_ {i_ {0}}}$ ${\ displaystyle (x_ {i}) _ {i \ in I '} \ in A'}$ ${\ displaystyle (m_ {i}) _ {i \ in I '} \ leq _ {\ mathrm {lex} _ {I'}} (x_ {i}) _ {i \ in I '}}$ ${\ displaystyle (m_ {i}) _ {i \ in I '}}$ ${\ displaystyle (m_ {i}) _ {i \ in I} \ leq _ {\ mathrm {lex} _ {I}} (x_ {i}) _ {i \ in I}}$

Somma disgiunta: sia $A$ una parte non vuota di . Ci mettiamo in posa ; $I$ $A$ è un non vuota parte $I$ poiché $A$ non è vuota, pertanto, $che$ essendo ben ordinato, $ho$ $Un$ ammette minimo $i$ $0$ . Definiamo quindi $E '$ di ; $E '$ è una parte non vuota di $E$ $i$ $0$ per costruzione, ma quest'ultima è ben ordinata, quindi $E'$ ha un elemento più piccolo $x$ $0$ . Verifichiamo quindi che $($ $i$ $0$ $,$ $x$ $0$ $)$ è il minimo di $A$ per l'ordine della somma ordinale: se , allora e quindi ; se , abbiamo , se no, e poi da dove , che risulta allora . ${\ displaystyle \ bigsqcup _ {i \ in I} E_ {i}}$ ${\ displaystyle I_ {A} = \ {i \ in I \ mid \ esiste x \ in E_ {i}, (i, x) \ in A \}}$ ${\ displaystyle E '= \ {x \ in E_ {i_ {0}} \ mid (i_ {0}, x) \ in A \}}$
${\ displaystyle (i, x) \ in A}$ ${\ displaystyle i \ in I_ {A}}$ ${\ displaystyle i_ {0} \ leq i}$ ${\ displaystyle i_ {0} <i}$ ${\ displaystyle (i_ {0}, x_ {0}) \ leq (i, x)}$ ${\ displaystyle i_ {0} = i}$ ${\ displaystyle (i_ {0}, x) \ in A}$ ${\ displaystyle x \ in E_ {i_ {0}}}$ ${\ displaystyle x_ {0} \ leq _ {i_ {0}} x}$ ${\ displaystyle (i_ {0}, x_ {0}) \ leq (i, x)}$

L'insieme degli interi relativi o l' intervallo reale ] 0, 1 [(con i rispettivi ordini usuali) non sono ben ordinati poiché essi stessi non hanno un elemento più piccolo. Anche gli intervalli reali [0, 1 [e [0, 1] non sono ben ordinati poiché la loro parte non è vuota] 0, 1 [.
L'insieme delle sequenze infinite di 0 e 1, che possono essere scritte e fornite con l'ordine lessicografico associato (indotto da 0 <1 e il solito ordine su , quindi due buoni ordini), non è quindi ben ordinato, poiché è un parte non vuota che non ammette un minimo (anzi, 1…> 01…> 001…> 0001…>…); ciò costituisce un controesempio alla proprietà sul prodotto cartesiano sopra citata nel caso in cui sia infinita. ${\ displaystyle \ prod _ {i \ in \ mathbb {N}} \ {0.1 \}}$ ${\ mathbb N}$ ${\ displaystyle \ {0 ^ {i} 1 ^ {\ omega} \ mid i \ in \ mathbb {N} \}}$ $io$

Predecessori e successori

Sia ( E , ≤) un insieme non vuoto ben ordinato.

Ha un elemento più piccolo, ma può (come nel caso E = ω, l'insieme dei numeri naturali per l'ordine usuale) non averne uno più grande; ma nulla impedisce di aggiungerne uno: questo è l'inizio di un'ingenua costruzione di ordinali transfiniti .
Sia α un elemento di E : se α non è l'elemento più grande di E , esiste, tra gli elementi di E strettamente maggiore di α, un elemento minore β, detto successore di α e spesso indicato α + 1 , di cui α è il predecessore .
Un elemento di E ha al massimo un predecessore; l'elemento più piccolo ovviamente non ne ha uno e questo è l'unico caso per E = ω, ma in generale, in un insieme ben ordinato E , molti elementi non hanno un predecessore - è inoltre una proprietà caratteristica degli ordinali transfiniti> ω. Un membro E avente un predecessore di detto primo tipo (o successore ) e seconda specie (o limite ) se no, e se non v'è l'elemento più piccolo di E . Questa distinzione è spesso utile per ragionare per induzione transfinita .

Segmento iniziale

Un segmento iniziale di un insieme ordinato ( E , ≤) è un sottoinsieme S di E tale che qualsiasi limite inferiore di un elemento di S è in S. L'insieme E stesso è un segmento iniziale di ( E , ≤), e tutti i si dice che altri siano puliti .

Per x ∈ E , l'insieme S x : = { y ∈ E | y < x } è sempre un segmento iniziale proprio di E , e la mappa x ↦ S x è crescente da ( E , ≤) a ( P ( E ) , ⊂).

Se ( E , ≤) è un ordine buona, tale iniziale proprio segmento S è uguale a S x , dove x è l'elemento più piccolo della complementare di S . La mappa x ↦ S x è quindi biiettiva di E nell'insieme dei suoi segmenti iniziali propri.

Un insieme ben ordinato non è mai isomorfo a uno dei suoi segmenti iniziali propri.

Confronto tra buoni ordini e ordinali

I buoni ordini possono essere confrontati dal morfismo; il morfismo di un ordine è un'applicazione in crescita. Un buon isomorfismo di ordine è quindi una mappa uno-a-uno crescente, il contrario essendo quindi anche crescente (perché un buon ordine è totale). Ad esempio, la mappa x ↦ S x del paragrafo precedente definisce un isomorfismo tra un insieme ben ordinato e l'insieme dei suoi segmenti iniziali propri.

Se due buoni ordini sono isomorfi, l'isomorfismo tra di loro è unico.

Gli isomorfismi degli ordini consentono di classificare i buoni ordini, grazie a una proprietà fondamentale (dimostrata da Georg Cantor ):

Teorema. Dati due buoni ordini, uno è isomorfo a un segmento iniziale dell'altro.

Ad esempio, mostriamo che ogni insieme infinito ben ordinato ha un segmento iniziale isomorfo a ω (il solito ordine su ℕ), per il teorema di definizione per induzione su ℕ.

Il teorema è facilmente deducibile dal teorema di definizione per induzione su un buon ordine . Più direttamente: let e due buoni ordini, in cui sono annotati rispettivamente i segmenti iniziali propri e ; quindi, l'insieme di coppie tale che è isomorfo a è il grafico di un isomorfismo tra due segmenti iniziali, e , che non possono essere entrambi propri. ${\ displaystyle (E, \ leq)}$ ${\ displaystyle (F, \ leq)}$ ${\ displaystyle S_ {e}}$ $T_ {f}$ ${\ displaystyle (e, f) \ in E \ times F}$ ${\ displaystyle S_ {e}}$ $T_ {f}$ $S \ sottoinsieme E$ ${\ displaystyle T \ subset F}$

Questa proprietà esprime essenzialmente che, ad eccezione dell'isomorfismo, il confronto per segmento iniziale ordina completamente gli ordini corretti. Si può specificare limitandosi a tutti i buoni ordini che si possono definire su un dato insieme E ; quindi, l'insieme delle classi isomorfe ( classe di equivalenza per la relazione di isomorfismo) di questi buoni ordini è totalmente ordinato dalla relazione "per essere isomorfo a un segmento iniziale", e anche ben ordinato come deduciamo dalla caratterizzazione dei segmenti iniziali di i buoni ordini (è una costruzione dell'ordinale di Hartogs associato all'insieme E ).

Chiamiamo ordinale un buon ordine visto fino all'isomorfismo. Nella teoria degli insiemi , la definizione di classi isomorfiche come classe di equivalenze si scontra con i soliti paradossi, poiché queste classi non possono essere insiemi. Una soluzione è poter definire in modo uniforme un rappresentante per classe: è la costruzione degli ordinali dovuta a von Neumann (consiste nel definire un ordinale come l'insieme dei propri segmenti iniziali).

Questa costruzione è fatta nella teoria degli insiemi di Zermelo-Fraenkel , richiede imperativamente lo schema degli assiomi di sostituzione . La teoria degli insiemi di Zermelo (senza questo schema assioma) non ci permette di mostrare l'esistenza dell'ordinale di von Neumann ω + ω (né di quelli successivi), mentre un buon ordine di tipo ω + ω è facilmente definito dalla somma in questa teoria.

Teorema (ZF). - Qualsiasi insieme ben ordinato è isomorfo a uno e un solo ordinale di von Neumann .

Buon ordine finito

In un insieme ben ordinato finito, qualsiasi parte non vuota ha anche un elemento più grande, cioè anche l' ordine opposto è un buon ordine. Questo immobile è caratteristico di buone commesse rifinite. Nella teoria degli insiemi, può fornire una definizione:

numeri naturali, che sono quindi ordinali finiti (in questo senso);
insiemi finiti, cioè in biiezione con un intero naturale, che sono quindi gli insiemi che possono essere forniti con un buon ordine finito.

Note e riferimenti

Paul Halmos , Introduzione alla teoria degli insiemi [ dettaglio di edizioni ], p. 82 dell'edizione inglese, anteprima su Google Libri .
(a) Kenneth Kunen , Set Theory: An Introduction to Independence Proofs , Elsevier,2014( leggi in linea ) , p. 14-15, Lemma 6.1.
Kunen 2014 , p. 15, Lemma 6.2.
Moschovakis 2006 , p. 99, Teorema 7.31.
Kunen 2014 , p. 15, Teorema 6.3.
Kunen 2014 , p. 17, Teorema 7.4.

Vedi anche

Bibliografia

(it) Yiannis Moschovakis , Notes on Set Theory [ dettaglio delle edizioni ]

Articolo correlato

Rapporto fondato