Velordnet sæt

I matematik er et ordnet sæt ( E , ≤) ordnet og forholdet ≤ er en god rækkefølge, hvis følgende betingelse er opfyldt:

Enhver del, der ikke er tom for E, har et mindste element .

Hvis ( E , ≤) er ordnet godt, er ≤ nødvendigvis en samlet rækkefølge , dvs. at to elementer x og y af E altid er sammenlignelige. Sættet { x , y } har faktisk et mindre element, så vi har x ≤ y eller y ≤ x .

Hvis desuden det afhængige valgaksiom er verificeret, svarer denne egenskab (velordnet) for en formodet total rækkefølge til den faldende kædetilstand "der er ingen strengt faldende uendelig rækkefølge". Ifølge Zermelo's sætning svarer det valgte aksiom i al sin styrke til det faktum, at ethvert sæt kan ordnes ordentligt.

Eksempler og modeksempler

Enhver del af et velordnet sæt er i sig selv ordnet (til den inducerede ordre).
Det tomme sæt er ordnet efter dets eneste forhold : (Ø, Ø) (det er den mindste ordinal ).
Mere generelt er ethvert endeligt totalt bestilt sæt velordnet. Sådan ordnet sæt er karakteriseret (i isomorfi nær ) med antallet n af elementer i sættet, hvilket begrunder notationen n for ordretype matchning.
Hvis definerer en god ordre baseret på og en streng af , er begrænsningen en god ordre. ${\ displaystyle \ leq}$ ${\ displaystyle (E, \ leq)}$ $VS$ ${\ displaystyle (E, \ leq)}$ ${\ displaystyle (C, \ leq)}$
Sættet (ℕ, ≤) af naturlige heltal , forsynet med sin sædvanlige rækkefølge, er velordnet; det bemærkes ofte ω i denne sammenhæng.
Hvis er en familie af velordnede sæt, og hvis den er udstyret med en god orden, så: (Ejeg,≤jeg)jeg∈jeg{\ displaystyle (E_ {i}, \ leq _ {i}) _ {i \ i I}} ${\ displaystyle (E_ {i}, \ leq _ {i}) _ {i \ i I}}$ jeg{\ displaystyle I} $jeg$
- hvis det er endeligt, på
produktet er den leksikografiske rækkefølge en god ordre. For fire eksempler på produkter af et par gode ordrer, se n × p , 2 × N , N × 2 og N × N (henholdsvis isomorf til ordinaler for produkter pn , ω2, 2ω (= ω) og ω 2 );jeg{\ displaystyle I} $jeg$ ∏jeg∈jegEjeg={(xjeg)jeg∈jeg∣∀jeg∈jeg, xjeg∈Ejeg}{\ displaystyle \ prod _ {i \ i I} E_ {i} = \ {(x_ {i}) _ {i \ i I} \ mid \ forall i \ i I, \ x_ {i} \ i E_ { i} \}} ${\ displaystyle \ prod _ {i \ i I} E_ {i} = \ {(x_ {i}) _ {i \ i I} \ mid \ forall i \ i I, \ x_ {i} \ i E_ { i} \}}$
den usammenhængende union er velordnet af: if eller ( and ). Denne korrekte rækkefølge kaldes den ordinære sum af familien. Bemærk, at . Den ordinære sum af et par gode ordrer bemærkes . For tre eksempler, se ω + ω (= ω2) og 3 + ω, ω + 3 (⊂ ω2) . ${\ displaystyle \ bigsqcup _ {i \ i I} E_ {i} = \ {(i, x) \ mid i \ i I, \ x \ i E_ {i} \}}$ ${\ displaystyle (i, x) \ leq (j, y)}$ $jeg <j$ $jeg = j$ ${\ displaystyle x \ leq _ {i} y}$ ${\ displaystyle \ sum _ {i \ i I} E = I \ gange E}$ $(A, B)$ $A + B.$

Demonstration

Kartesisk produkt (endeligt): vi resonnerer ved induktion på kardinaliteten af : jeg{\ displaystyle I} $jeg$
- initialisering: hvis , dvs. , derefter reduceres til a ugifte (strengt, den ene indeholder den tomme sekvens :) derfor velordnet; ${\ displaystyle | I | = 0}$ ${\ displaystyle I = \ varnothing}$ $\ prod_ {i \ i I} E_i$ ${\ displaystyle \ {() \}}$
- arvelighed: ejendommen antages at være generisk sand for ethvert sæt indeks for kardinal $n$ ; antager vi . Lad $A være$ en ikke-ubehagelig del af . $Jeg$ er velordnet, det indrømmer et mindre element $i$ $0$ ; vi indstiller , derefter og (hvor betegner den kanoniske projektion på komponenten $i$ $0$ ). Derefter definerer vi $A$ $'$ ved , hvilket er legitimt, da $A$ $i$ $0$ er en ikke-frit del (ved ikke-tomhed af $A$ ) af det bestilte sæt $E$ $i$ $0$ og derfor faktisk indrømmer et minimum. $A$ $'$ er ikke tom da (altid fordi $A$ heller ikke er); nu er det en del af sættet $E$ $'$ , som er ordnet (for den inducerede leksikografiske rækkefølge) ved induktionshypotese, da og følgelig $A$ $'$ har et mindre element . Ved at bemærke opnår vi med et minimum af $A$ : ja, hvis , så ; der er et alternativ: enten , og derefter , eller , og vi har derefter , derfor ved minimalitet i $A$ $'$ , som ifølge den rekursive definition af den leksikografiske rækkefølge giver godt tilbage . ${\ displaystyle | I | = n + 1}$ $\ prod_ {i \ i I} E_i$ ${\ displaystyle I '= I \ setminus \ {i_ {0} \}}$ ${\ displaystyle E '= \ prod _ {i \ i I'} E_ {i}}$ ${\ displaystyle A_ {i_ {0}} = \ pi _ {i_ {0}} (A)}$ ${\ displaystyle \ pi _ {i_ {0}}}$ ${\ displaystyle A '= \ {(x_ {i}) _ {i \ i I'} \ i E '\ mid (x_ {i}) _ {i \ i I} \ i A \ \ \ mathrm {og } \ x_ {i_ {0}} = \ operatornavn {min} (A_ {i_ {0}}) \}}$ ${\ displaystyle | I '| = n}$ ${\ displaystyle (m_ {i}) _ {i \ i I '}}$
  ${\ displaystyle m_ {i_ {0}} = \ operatorname {min} (A_ {i_ {0}})}$ ${\ displaystyle (m_ {i}) _ {i \ i I}}$ ${\ displaystyle (x_ {i}) _ {i \ i I} \ i 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 \ i I '} \ i A'}$ ${\ displaystyle (m_ {i}) _ {i \ i I '} \ leq _ {\ mathrm {lex} _ {I'}} (x_ {i}) _ {i \ i I '}}$ ${\ displaystyle (m_ {i}) _ {i \ i I '}}$ ${\ displaystyle (m_ {i}) _ {i \ in I} \ leq _ {\ mathrm {lex} _ {I}} (x_ {i}) _ {i \ in I}}$

Uoverensstemmende sum: lad $A være$ en ikke- frit del af . Vi udgør ; $I$ $A$ er en ikke-frit del af $I,$ da $A$ er ikke-frit, derfor er $jeg$ velordnet, $I$ $A$ indrømmer et minimum $i$ $0$ . Vi definerer derefter $E '$ ved ; $E '$ er en nonempty del af $E$ $i$ $0$ ved konstruktion, men sidstnævnte er ordnet, så $E'$ har et mindste element $x$ $0$ . Vi verificerer derefter, at $($ $i$ $0$ $,$ $x$ $0$ $)$ er minimum $A$ for rækkefølgen af den ordinære sum: hvis , så og derfor ; hvis vi har , hvis ikke, og derefter hvorfra , hvilket resulterer derefter . ${\ displaystyle \ bigsqcup _ {i \ i I} E_ {i}}$ ${\ displaystyle I_ {A} = \ {i \ i I \ mid \ eksisterer x \ i E_ {i}, (i, x) \ i A \}}$ ${\ displaystyle E '= \ {x \ i E_ {i_ {0}} \ mid (i_ {0}, x) \ i A \}}$
${\ displaystyle (i, x) \ i A}$ ${\ displaystyle i \ i 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) \ i A}$ ${\ displaystyle x \ i E_ {i_ {0}}}$ ${\ displaystyle x_ {0} \ leq _ {i_ {0}} x}$ ${\ displaystyle (i_ {0}, x_ {0}) \ leq (i, x)}$

Sættet med relative heltal eller det reelle interval ] 0, 1 [(med deres respektive sædvanlige ordrer) er ikke ordnet godt, da de selv ikke har et mindste element. De reelle intervaller [0, 1 [og [0, 1] er heller ikke ordnet, da deres del ikke er tom] 0, 1 [.
Sættet af uendelige følger af 0 og 1, som kan skrives og være forsynet med det tilhørende leksikografisk orden (induceret af 0 <1 og den sædvanlige rækkefølge på , derfor to gode ordrer), derefter ikke godt bestilt, da det er en ikke-tom del, der ikke tillader et minimum (faktisk 1…> 01…> 001…> 0001…>…); dette udgør et modeksempel på ejendommen på det kartesiske produkt nævnt ovenfor i det tilfælde, hvor det er uendeligt. ${\ displaystyle \ prod _ {i \ in \ mathbb {N}} \ {0.1 \}}$ ${\ mathbb N}$ ${\ displaystyle \ {0 ^ {i} 1 ^ {\ omega} \ mid i \ in \ mathbb {N} \}}$ $jeg$

Forgjengere og efterfølgere

Lad ( E , ≤) være et velordnet ikke-frit sæt.

Det har et mindre element, men kan (som i tilfældet E = ω, sættet med naturlige tal for den sædvanlige rækkefølge) ikke have et større; men intet forhindrer at tilføje en til den - dette er begyndelsen på en naiv konstruktion af transfinite ordinaler .
Lad α være et element i E : hvis α ikke er det største element i E , findes der blandt elementerne i E strengt større end α et mindre element β, kaldet efterfølger af α og ofte bemærket α + 1 , hvoraf α er forgængeren .
Et element i E har højst en forgænger; det mindste element har naturligvis ikke en, og dette er det eneste tilfælde for E = ω, men generelt, i et velordnet sæt E , har mange elementer ikke en forgænger - det er desuden en karakteristisk egenskab ved transfinite ordinals> ω. Et medlem E har en forgænger af nævnte første type (eller efterfølger ) og andet stof (eller grænse ) hvis ikke, og hvis der ikke er den mindste element i E . Denne skelnen er ofte nyttig til ræsonnement ved transfinit induktion .

Indledende segment

Et indledende segment af et ordnet sæt ( E , ≤) er en delmængde S af E således, at enhver nedre grænse for et element af S er i S. Selve sættet E er et indledende segment af ( E , ≤), og alle andre siges at være rene .

For x ∈ E er sættet S x : = { y ∈ E | y < x } er altid et korrekt initialsegment af E , og kortet x ↦ S x stiger fra ( E , ≤) til ( P ( E ) , ⊂).

Hvis ( E , ≤) er en god orden, sådan indledende eget segment S er lig med S x , hvor x er det mindste element i den komplementære af S . Kortet x ↦ S x er derefter bindende for E i sættet med dets korrekte indledende segmenter.

Et velordnet sæt er aldrig isomorft til et af dets rette indledende segmenter.

Sammenligning af gode ordrer og ordinaler

Gode ordrer kan sammenlignes med morfisme; en morfisme af ordrer er en voksende applikation. En god ordens isomorfisme er derfor et stigende en-til-en-kort, hvor det omvendte derefter også stiger (fordi en god ordre er total). For eksempel definerer applikationen x ↦ S x i det foregående afsnit en isomorfisme mellem et velordnet sæt og sættet med dets korrekte indledende segmenter.

Hvis to gode ordrer er isomorfe, er isomorfismen mellem dem unik.

Ordenisomorfier gør det muligt at klassificere gode ordrer takket være en grundlæggende egenskab (demonstreret af Georg Cantor ):

Sætning. - Givet to gode ordrer, er den ene isomorf til et indledende segment af den anden.

For eksempel viser vi, at ethvert velordnet uendeligt sæt har et indledende segment isomorft til ω (den sædvanlige rækkefølge på ℕ), ved definitionssætningen ved induktion på ℕ.

Teoremet udledes let fra definitionssætningen ved induktion i en god orden . Mere direkte: lad og to gode ordrer, hvor de korrekte indledende segmenter er noteret henholdsvis og ; derefter er det sæt par , der er isomorfisk, grafen for en isomorfisme mellem to indledende segmenter, og som ikke begge kan være ordentlige. ${\ displaystyle (E, \ leq)}$ ${\ displaystyle (F, \ leq)}$ ${\ displaystyle S_ {e}}$ $T_ {f}$ ${\ displaystyle (e, f) \ i E \ gange F}$ ${\ displaystyle S_ {e}}$ $T_ {f}$ $S \ delmængde E.$ ${\ displaystyle T \ delmængde F}$

Denne egenskab udtrykker i det væsentlige, at bortset fra isomorfisme bestiller sammenligningen efter det første segment fuldstændigt de korrekte ordrer. Man kan specificere ved at begrænse sig til alle de gode ordrer, som man kan definere på et givet sæt E ; derefter er sættet af isomorfe klasser ( ækvivalensklasse for isomorfisme-forholdet) af disse gode ordrer totalt ordnet af forholdet "at være isomorf til et indledende segment", og endda godt ordnet som vi udleder af karakteriseringen af de indledende segmenter de gode ordrer (det er en konstruktion af Hartogs ordinal forbundet med sættet E ).

Vi kalder ordinal en god orden set op til isomorfisme. I sætteori kommer definitionen af isomorfe klasser som en klasse af ækvivalenser op mod de sædvanlige paradokser, da disse klasser ikke kan være sæt. En løsning er at være i stand til på en ensartet måde at definere en repræsentant efter klasse: det er konstruktionen af ordener på grund af von Neumann (den består i at definere en ordinal som sættet af sine egne indledende segmenter).

Denne konstruktion udføres i teorien om Zermelo-Fraenkel-sæt , det kræver absolut ordningen med udskiftningsaksiomer . Zermelo's sætteori (uden dette aksiomskema) tillader os ikke at vise eksistensen af von Neumann-ordinalen ω + nor (eller de derudover), hvorimod en god rækkefølge af typen ω + ω let kan defineres ved sum i denne teori.

Teorem (ZF). - Ethvert velordnet sæt er isomorf til en og kun en von Neumann-ordinær .

God ordre færdig

I et endeligt velordnet sæt har enhver ikke-fri del også et større element, det vil sige den modsatte rækkefølge er også en god ordre. Denne egenskab er karakteristisk for gode færdige ordrer. I sætteori kan det give en definition:

naturlige tal , som derefter er endelige ordinaler (i denne forstand);
endelige sæt, det vil sige i forbindelse med et naturligt heltal, som derefter er de sæt, der kan forsynes med en god endelig rækkefølge.

Noter og referencer

Paul Halmos , Introduktion til sætteori [ detaljer i udgaver ], s. 82 af den engelske udgave, forhåndsvisning på Google Books .
(i) Kenneth Kunen , Set Teori: En introduktion til Independence Beviser , Elsevier,2014( læs online ) , s. 14-15, Lemma 6.1.
Kunen 2014 , s. 15, Lemma 6.2.
Moschovakierne 2006 , s. 99, sætning 7.31.
Kunen 2014 , s. 15, sætning 6.3.
Kunen 2014 , s. 17, sætning 7.4.

Se også

Bibliografi

(en) Yiannis Moschovakis , Notes on Set Theory [ detalje af udgaver ]

Relateret artikel

Velbegrundet forhold