Set bine ordonat

În matematică , un set ordonat ( E , ≤) este bine ordonat și relația ≤ este o ordine bună dacă se îndeplinește următoarea condiție:

Orice porțiune care nu este goală de E are cel mai mic element .

Dacă ( E , ≤) este bine ordonat, atunci ≤ este neapărat un ordin total , adică orice două elemente x și y din E sunt întotdeauna comparabile. Într-adevăr, mulțimea { x , y } are un element mai mic, deci avem x ≤ y sau y ≤ x .

Dacă, în plus, se verifică axioma alegerii dependente , această proprietate (să fie bine ordonată) este echivalentă, pentru o ordine totală presupusă, cu condiția lanțului descendent „nu există o secvență infinită strict descrescătoare”. Conform teoremei lui Zermelo , axioma alegerii în toată forța sa este echivalentă cu faptul că orice mulțime poate fi bine ordonată.

Exemple și contra-exemple

Orice parte a unui set bine ordonat este ea însăși bine ordonată (pentru ordinea indusă).
Mulțimea goală este bine ordonată de singura sa relație : (Ø, Ø) (este cel mai mic ordinal ).
Mai general, orice set finit complet ordonat este bine ordonat. O astfel de mulțime ordonată este caracterizată (în izomorfism aproape ) de numărul n de elemente ale mulțimii, ceea ce justifică notația n pentru potrivirea tipului de ordine .
Dacă definește o ordine bună pe baza și un șir de , restricția este o ordine bună. ${\ displaystyle \ leq}$ ${\ displaystyle (E, \ leq)}$ $VS$ ${\ displaystyle (E, \ leq)}$ ${\ displaystyle (C, \ leq)}$
Mulțimea (ℕ, ≤) a numerelor întregi naturale , prevăzută cu ordinea sa obișnuită, este bine ordonată; se remarcă adesea ω în acest context.
Dacă este o familie de seturi bine ordonate și dacă este dotată cu o ordine bună, atunci: (Eeu,≤eu)eu∈Eu{\ displaystyle (E_ {i}, \ leq _ {i}) _ {i \ in I}} ${\ displaystyle (E_ {i}, \ leq _ {i}) _ {i \ in I}}$ Eu{\ displaystyle I} $Eu$
- dacă este finit, pe
produs , ordinea lexicografică este o comandă bună. Pentru patru exemple de produse ale unei perechi de comenzi bune, vezi n × p , 2 × N , N × 2 și N × N (izomorfă la ordinalii produselor pn , ω2, 2ω (= ω) și respectiv ω 2 ) ;Eu{\ displaystyle I} $Eu$ ∏eu∈EuEeu={(Xeu)eu∈Eu∣∀eu∈Eu, Xeu∈Eeu}{\ displaystyle \ prod _ {i \ in I} E_ {i} = \ {(x_ {i}) _ {i \ in I} \ mid \ forall i \ in I, \ x_ {i} \ in E_ { i} \}} ${\ displaystyle \ prod _ {i \ in I} E_ {i} = \ {(x_ {i}) _ {i \ in I} \ mid \ forall i \ in I, \ x_ {i} \ in E_ { i} \}}$
uniunea disjunctă este bine ordonate după: dacă sau ( și ). Această ordine corectă se numește suma ordinală a familiei. Rețineți că . Se notează suma ordinală a câteva ordine bune . Pentru trei exemple, consultați ω + ω (= ω2) și 3 + ω, ω + 3 (⊂ ω2) . ${\ displaystyle \ bigsqcup _ {i \ in I} E_ {i} = \ {(i, x) \ mid i \ in I, \ x \ in E_ {i} \}}$ ${\ displaystyle (i, x) \ leq (j, y)}$ $i <j$ $i = j$ ${\ displaystyle x \ leq _ {i} y}$ ${\ displaystyle \ sum _ {i \ in I} E = I \ times E}$ $(A, B)$ $A + B$

Demonstrație

Produs cartezian (finit): avem un motiv de inducție pe cardinalitatea : Eu{\ displaystyle I} $Eu$
- inițializare: dacă , adică , atunci se reduce la un singleton (riguros, cel care conține secvența goală :) , deci bine ordonat; ${\ displaystyle | I | = 0}$ ${\ displaystyle I = \ varnothing}$ $\ prod_ {i \ in I} E_i$ ${\ displaystyle \ {() \}}$
- ereditate: proprietatea se presupune că este generic adevărată pentru orice set de indici ai cardinalului $n$ ; presupunem . Fie $A$ o parte care nu este goală . $Eu$ fiind bine ordonat, admite un element mai mic $i$ $0$ ; stabilim , atunci și (unde denotă proiecția canonică pe componenta $i$ $0$ ). Apoi definim $A$ $'$ prin , ceea ce este legitim deoarece $A$ $i$ $0$ este o parte non-goală (prin ne-golul lui $A$ ) din setul ordonat $E$ $i$ $0$ și, prin urmare, admite într-adevăr un minim. $A$ $'$ nu este gol atunci (întotdeauna pentru că nici $A$ nu este); acum este o parte a mulțimii $E$ $'$ , care este bine ordonată (pentru ordinea lexicografică indusă) prin ipoteza inducției , deoarece , în consecință, $A$ $'$ are un element mai mic . Notând , obținem cu un minim de $A$ : într-adevăr, dacă , atunci ; există o alternativă: fie , și apoi , fie , și avem atunci , deci prin minimalitate de în $A$ $'$ , care, conform definiției recursive a ordinii lexicografice , dă înapoi bine . ${\ 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 {și } \ 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 \ în I}}$ ${\ displaystyle (x_ {i}) _ {i \ în I} \ în 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 \ în I '} \ în 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}}$

Suma disjuncte: lasa $O sa fie$ o parte a nevid . Noi pozăm ; $I$ $A$ este o parte non-goală din $I,$ deoarece $A$ este non-vid, prin urmare, $eu$ fiind bine ordonat, $I$ $A$ admite un minim $i$ $0$ . Apoi definim $E '$ prin ; $E '$ este o parte non-goală a lui $E$ $i$ $0$ prin construcție, dar acesta din urmă este bine ordonat, deci $E'$ are cel mai mic element $x$ $0$ . Verificăm apoi că $($ $i$ $0$ $,$ $x$ $0$ $)$ este minimul lui $A$ pentru ordinea sumei ordinale: dacă , atunci și deci ; dacă avem , dacă nu, și apoi de unde , ceea ce rezultă atunci . ${\ displaystyle \ bigsqcup _ {i \ in I} E_ {i}}$ ${\ displaystyle I_ {A} = \ {i \ in I \ mid \ există x \ în E_ {i}, (i, x) \ în A \}}$ ${\ displaystyle E '= \ {x \ în E_ {i_ {0}} \ mid (i_ {0}, x) \ în A \}}$
${\ displaystyle (i, x) \ în 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) \ în A}$ ${\ displaystyle x \ în E_ {i_ {0}}}$ ${\ displaystyle x_ {0} \ leq _ {i_ {0}} x}$ ${\ displaystyle (i_ {0}, x_ {0}) \ leq (i, x)}$

Setul de numere întregi relative sau intervalul real ] 0, 1 [(cu ordinele lor obișnuite respective) nu sunt bine ordonate, deoarece ele însele nu au un element mai mic. Nici intervalele reale [0, 1 [și [0, 1] nu sunt bine ordonate, deoarece partea lor nu este goală] 0, 1 [.
Setul de secvențe infinite de 0 și 1, care poate fi scris și furnizat cu ordinea lexicografică asociată (indusă de 0 <1 și ordinea obișnuită pe , deci două ordine bune), nu este atunci bine ordonat, deoarece este parte ne-goală care nu admite un minim (într-adevăr, 1 ...> 01 ...> 001 ...> 0001 ...> ...); aceasta constituie un contraexemplu al proprietății de pe produsul cartezian menționat mai sus în cazul în care este infinit. ${\ displaystyle \ prod _ {i \ in \ mathbb {N}} \ {0.1 \}}$ ${\ mathbb N}$ ${\ displaystyle \ {0 ^ {i} 1 ^ {\ omega} \ mid i \ in \ mathbb {N} \}}$ $Eu$

Predecesori și succesori

Fie ( E , ≤) o mulțime neocupată bine ordonată.

Are un element mai mic, dar poate (ca în cazul E = ω, setul de numere naturale pentru ordinea obișnuită) să nu aibă unul mai mare; dar nimic nu împiedică adăugarea unuia la acesta - acesta este chiar începutul unei construcții naive a ordinalelor transfinite .
Fie α un element al lui E : dacă α nu este cel mai mare element al lui E , există, printre elementele lui E strict mai mari decât α, un element mai mic β, numit succesor al lui α și adesea notat α + 1 , dintre care α este predecesorul .
Un element al lui E are cel mult un predecesor; cel mai mic element evident nu are unul și acesta este singurul caz pentru E = ω, dar în general, într-o mulțime bine ordonată E , multe elemente nu au un predecesor - este de altfel o proprietate caracteristică a ordinalelor transfinite> ω. Un membru E are un predecesor menționat primul tip (sau succesor ) și specie a doua (sau limita ) în cazul în care nu, iar dacă nu este cel mai mic element al E . Această distincție este adesea utilă pentru raționamentul prin inducție transfinită .

Segment inițial

Un segment inițial al unei mulțimi ordonate ( E , ≤) este un subset S al lui E astfel încât orice limită inferioară a unui element al lui S este în S. Mulțimea E în sine este un segment inițial al lui ( E , ≤) și toate se spune că altele sunt curate .

Pentru x ∈ E , mulțimea S x : = { y ∈ E | y < x } este întotdeauna un segment inițial adecvat al lui E , iar harta x ↦ S x crește de la ( E , ≤) la ( P ( E ) , ⊂).

Dacă ( E , ≤) este o ordine, astfel inițial propriul segment S este egal cu S x , unde x este cel mai mic element al complementar al S . Harta x ↦ S x este apoi bijectivă a lui E în setul de segmente inițiale proprii.

Un set bine ordonat nu este niciodată izomorf pentru unul dintre segmentele sale inițiale adecvate.

Compararea comenzilor bune și a ordinalelor

Ordinele bune pot fi comparate prin morfism; un morfism de ordine este o aplicație în creștere. Un izomorfism de ordine bună este, prin urmare, o hartă crescândă de la unu la unu, și inversul crește atunci (pentru că o ordine bună este totală). De exemplu, aplicația x ↦ S x a paragrafului anterior definește un izomorfism între o mulțime bine ordonată și mulțimea segmentelor sale inițiale corespunzătoare.

Dacă două ordine bune sunt izomorfe, izomorfismul dintre ele este unic.

Izomorfismele de ordine fac posibilă clasificarea ordinelor bune, datorită unei proprietăți fundamentale (demonstrată de Georg Cantor ):

Teorema. - Având în vedere două ordine bune, una este izomorfă pentru un segment inițial al celuilalt.

De exemplu, arătăm că orice mulțime infinită bine ordonată are un segment inițial izomorf la ω (ordinea obișnuită pe ℕ), prin teorema definiției prin inducție pe ℕ.

Teorema este ușor dedusă din teorema definiției prin inducție pe o ordine bună . Mai direct: let și două ordine bune, în care se notează respectiv segmentele inițiale corespunzătoare și ; atunci, mulțimea de perechi astfel încât este izomorfă la este graficul unui izomorfism între două segmente inițiale și , care nu pot fi ambele corecte. ${\ displaystyle (E, \ leq)}$ ${\ displaystyle (F, \ leq)}$ ${\ displaystyle S_ {e}}$ $T_ {f}$ ${\ displaystyle (e, f) \ în E \ times F}$ ${\ displaystyle S_ {e}}$ $T_ {f}$ $S \ subset E$ ${\ displaystyle T \ subset F}$

Această proprietate exprimă în esență că, cu excepția izomorfismului, comparația pe segmentul inițial ordonează complet ordinele corecte. Se poate specifica limitându-se la toate comenzile bune pe care le putem defini pe un set dat E ; atunci, mulțimea claselor izomorfe ( clasa de echivalență pentru relația de izomorfism) a acestor ordine bune este complet ordonată de relația „a fi izomorfă la un segment inițial”, și chiar bine ordonată așa cum deducem din caracterizarea segmentelor inițiale ale ordinele bune (este o construcție a ordinalului Hartogs asociat cu mulțimea E ).

Numim ordinal o ordine bună văzută până la izomorfism. În teoria mulțimilor, definiția claselor izomorfe ca o clasă de echivalențe se opune paradoxurilor obișnuite, deoarece aceste clase nu pot fi mulțimi. O soluție este de a putea defini într-un mod uniform un reprezentant pe clase: este construcția de ordinali datorată lui von Neumann (constă în definirea unui ordinal ca setul propriilor segmente inițiale).

Această construcție se face în teoria mulțimilor Zermelo-Fraenkel , necesită în mod imperativ schema axiomelor de înlocuire . Teoria mulțimilor lui Zermelo (fără această schemă axiomatică) nu ne permite să arătăm existența ordinalului von Neumann ω + ω (nici a celor de dincolo), în timp ce o bună ordine de tip ω + ω este ușor definită prin sumă în această teorie.

Teorema (ZF). - Orice mulțime bine ordonată este izomorfă pentru un singur și ordinal von Neumann .

Bună comandă terminată

Într-un set finit bine ordonat, orice parte neocupată are, de asemenea, un element mai mare, adică ordinea opusă este, de asemenea, o ordine bună. Această proprietate este caracteristică comenzilor terminate. În teoria mulțimilor, poate oferi o definiție:

numere naturale, care sunt apoi ordinale finite (în acest sens);
mulțimi finite, adică în bijecție cu un întreg natural, care sunt apoi mulțimile care pot fi prevăzute cu o bună ordine finită.

Note și referințe

Paul Halmos , Introducere în teoria mulțimilor [ detaliile edițiilor ], p. 82 din ediția în limba engleză, previzualizare pe Google Cărți .
(în) Kenneth Kunen , Set Theory: An Introduction to Independence Proofs , Elsevier,2014( citiți online ) , p. 14-15, Lema 6.1.
Kunen 2014 , p. 15, Lema 6.2.
Moschovakis 2006 , p. 99, Teorema 7.31.
Kunen 2014 , p. 15, Teorema 6.3.
Kunen 2014 , p. 17, Teorema 7.4.

Vezi și tu

Bibliografie

(ro) Yiannis Moschovakis , Note despre teoria seturilor [ detaliile edițiilor ]

Articol asociat

Relație bine întemeiată