Valg af aksiom

I matematik er det valgte aksiom , forkortet som " AC ", et aksiom af sætteori, som "bekræfter muligheden for at konstruere sæt ved at gentage en valgmæssig handling et uendeligt antal gange, selvom det ikke udtrykkeligt er specificeret. "

Det blev først formuleret af Ernest Zermelo i 1904 til bevis for Zermelos sætning . Valgets aksiom kan accepteres eller afvises afhængigt af den valgte aksiomatiske sætteori .

Stater

Det valgte aksiom kan angives som følger:

(0) "For ethvert sæt X i nonempty sæt , eksisterer der en funktion defineret på X, kaldet en valg-funktion , som til hvert sæt A tilhører X knytter et element af dette sæt A."

Dette er formelt skrevet . ${\ displaystyle \ forall X \ left [\ varnothing \ notin X \ Longrightarrow \ findes f: X \ rightarrow \ bigcup X \; \ forall A \ i X \; (f (A) \ i A) \ højre]}$

Opkaldet til dette aksiom er ikke nødvendigt, hvis X er et endeligt sæt, fordi det er en konsekvens af definitionen af ikke-frit sæt (dvs. der findes et element, der hører til dette sæt). I dette tilfælde vises resultatet ved induktion af antallet af elementer X .

Der er andre tilfælde, hvor en funktion af valg f kan defineres uden det valgte aksiom. For eksempel, for et sæt X af ikke-enkle sæt af naturlige heltal, kan vi definere en valgfunktion ved at indstille, for A et element af X , f ( A ) svarende til det mindste element af A (vi betjenes fra egenskaben god rækkefølge over naturlige tal og ikke fra det valgte aksiom). Men i det generelle tilfælde er eksistensen af en valgfunktion afhængig af ovenstående aksiom, for eksempel for at bevise Königs sætning .

Andre formuleringer

Vi finder andre formuleringer af det valgte aksiom, meget tæt på det foregående, herunder følgende:

(0 ') For ethvert sæt E eksisterer der en funktion, der til hver ikke-fri del af E forbinder et element af denne del.
(1) For enhver ækvivalensrelation R , der er et system med repræsentanter for klasser af R .
(2) Enhver overjektion har en sektion .
(3) Produktet ∏ i ∈ I X i af en familie ( X i ) i ∈ I af ikke-frit sæt er ikke frit

Demonstration af ækvivalenser

(0 ') ⇔ (0): (0') er et specielt tilfælde af (0). Omvendt udleder vi (0) fra (0 ') ved at tage et sæt E foreningen af sætene, der tilhører X : (0') giver en valgfunktion på de ikke-ufordelte dele af E , især på de dele, der tilhører X .
(0) ⇒ (1): enten R en ækvivalensrelation på et sæt E . Påføring (0) til sættet X af ækvivalens klasser R , opnås der en del F af E sådan, at ethvert element i E er R -ækvivalent til et enkelt element F .
(1) ⇒ (2): til enhver overvejelse s : E → I er knyttet en ækvivalensrelation R på E : to elementer er ækvivalente, hvis de har det samme billede ved s . En højre invers til s er givet ved et udvalg af repræsentanter fra R .
(2) ⇒ (3): for ( X i ) i ∈ I er en familie af ikke-ukompliserede sæt, betegnet med E den uensartede forening af X i , dvs. sættet af alle par ( i , x ) sådan at x hører til X i . Derefter er den første projektion, fra E til I , som til ( i , x ) associerer i , en overvejelse, hvoraf enhver sektion tilvejebringer et element af produktet af X i .
(3) ⇒ (0): lad X være et sæt ikke-sætte sæt. Ved at anvende (3) på familien af disse sæt, indekseret af X selv, konstruerer vi et element af deres produkt, dvs. en valgfunktion.

Ækvivalente udsagn

Det valgte aksiom bruges ofte gennem et af følgende to ækvivalente udsagn:

Zermelo's sætning : "Ethvert sæt kan udstyres med en god orden ";
Lemma of Zorn : "Hvert induktivt sæt indrømmer et maksimalt element ".

Zermelos sætning indebærer straks det valgte aksiom: som for naturlige heltal ( se ovenfor ), hvis E er udstyret med en god orden, giver minimumet for denne en valgfunktion på sættet af ikke-dele. Hulrum af E (sætning ( 0 ')).

Vi viser ganske let, at Zorns lemma indebærer Zermelo's sætning (og derfor valgets aksiom ifølge ovenstående) og, direkte men ved den samme metode, at Zorns lemma indebærer valgaksiomet .

Det er lidt vanskeligere at vise, at det valgte aksiom involverer Zorns lemma (og derfor Zermelos sætning). Vi kan i begge tilfælde helt naturligt bruge teorien om ordinaler , men det er muligt at bevise Zorns lemma ved at arbejde direkte på ordensstrukturen for inkludering på et sæt dele (det er et induktivt sæt).

Uafhængighed af det valgte aksiom i forhold til ZF

Valgets aksiom er ikke en del af sæt af aksiomer i sætteori ZF . Man kalder ZFC- teori , ZF-teorien tilvejebragt ud over det valgte aksiom.

I 1938 demonstrerede Kurt Gödel , at ZF + AC er en sammenhængende teori, hvis ZF er.

I 1963 demonstrerede Paul Cohen , at ZF + (ikke) AC også er en sammenhængende teori, hvis ZF er. Dette fuldender demonstrationen af uafhængigheden af det valgte aksiom over for ZF's andre aksiomer.

Dette aksiom er et af de valgfri og kontroversielle aksiomer inden for sætteori. Faktisk er eksistensen af et objekt defineret ud fra det valgte aksiom ikke en konstruktiv eksistens, det vil sige at aksiomet på ingen måde beskriver, hvordan man konstruerer det objekt, som vi bekræfter l 'eksistens af. At sige, at der findes et grundlag for vektorrummet for kontinuerlige funktioner fra ℝ i ℝ, tillader os således ikke på nogen måde at beskrive et sådant grundlag. Fra dette synspunkt kan valgets aksiom synes at være af begrænset interesse, og det er grunden til, at nogle matematikere er mere tilfredse med et bevis, hvis de kan undgå at benytte sig af dette valgaksiom. Men de fleste matematikere bruger det uden særlig tilbageholdenhed.

En illustration af Bertrand Russell

Bertrand Russell sagde om det valgte aksiom: ”For at vælge en sok i stedet for den anden for hvert par af en uendelig samling , har vi brug for det valgte aksiom. Men for skoene er det ikke det værd. "

Forklaring:

De to sokker af samme par kan ikke skelnes. Selvom det hver morgen lykkes os at vælge, hvilken vi vil sætte først, er der ingen generel procedure, der giver os mulighed for på forhånd at bestemme denne uendelige række;
For sko skelner vi venstre sko fra højre sko. Der er således en naturlig valgfunktion: Vælg for eksempel altid den venstre sko.

Eksempler på sætninger, der kræver det valgte aksiom

Den første eksplicitte anvendelse af dette aksiom skyldtes Peano i 1890 for at demonstrere eksistensen af visse løsninger af differentialligninger .
Den basen sætning ufuldstændige i enhver dimension (og endda blot eksistensen af en base for enhver vektorrum) er kun sandt ved at antage udvalgsaksiomet.
Den sætning af Krull (alle eget ideal af en kommutativ ring er indeholdt i en maksimal ideal ) svarer til den udvalgsaksiomet.
Den Banach-Tarski paradokset er (blandt andre) en konsekvens af udvalgsaksiomet.
Valgets aksiom gør det muligt at bekræfte eksistensen af ikke- målbare dele af R i Lebesgue forstand .
Sættet * R af hyperrealiteter skylder dets eksistens til det valgte aksiom.
I grafteori , de kromatiske tal af linjen og flyet afhænger af udvalgsaksiomet.

Svage former for det valgte aksiom

Der er svage former for det valgte aksiom, som matematikeren ofte bruger, det meste af tiden uden at vide det, medmindre han er en logiker eller " konstruktivist ", og som bruges til at "konstruere" sekvenser. De er absolut nødvendige for den sædvanlige præsentation af analysegrundlaget.

Axiom af tællbar valg

Dette aksiom, forkortet som " AC ω ", er begrænsningen af det valgte aksiom til tællbare familier :

”I betragtning af en tællelig familie af ikke-fri sæt findes der en funktion, som hver af dem forbinder et af dets elementer. "

Det bruges for eksempel til at demonstrere:

at en tællelig forening af tællelige sæt er tællelig;
at et sæt, der ikke er endeligt i den sædvanlige forstand, er uendeligt i Dedekinds forstand (dvs. ækvipotent til et af dets strenge undergrupper);
at en funktion defineret på R er kontinuerlig ved et punkt x, så snart den er sekventielt kontinuerlig ved x ;
at et tælleprodukt af kompakte rum er kompakt;
den Hahn-Banach teorem for en adskillelig Banach rum ;
den lukkede nestede sætning (en af konsekvenserne heraf er Baires sætning ).

Pas på en almindelig forvirring: det er familien af sæt, der kan tælles, og der antages ikke nogen antagelse om, at de sæt, der sammensætter denne familie. Aksiomet for det tællbare valg vedrører ikke spørgsmålet om valget af et element i et tællbart sæt, men muligheden for at foretage en tællbar uendelig række af valg samtidigt.

Axiom af afhængigt valg

Dette aksiom, forkortet "DC", sikrer, at hvis R er en relation på et ikke-frit sæt E, der tilfredsstiller

$\ forall x \ i E \ \ findes y \ i E \ xRy,$

så findes der en sekvens $( x n )$ af elementer af E således, at

$\ forall n \ x_ {n} Rx _ {{n + 1}}.$

En stærkere form for det valgte aksiom: Hilberts epsilon

David Hilbert introducerede operatøren ε, som til enhver ejendom P forbinder et objekt ε x . P ( x ) således, at hvis P er opfyldt af mindst et element, så er P tilfreds med ε x . P ( x ). Denne konstruktion gør det muligt at definere kvantificeringsmidler, og det bruges af Nicolas Bourbaki til at udvikle sin sætteori med en notationsvariant ved hjælp af bogstavet τ (tau).

Det er så ret simpelt at vise, at valgaksiomet bliver en sætning, det vil sige en konsekvens af de andre aksiomer, og af de logiske regler, der styrer brugen af tau. Operatøren tau leverer faktisk et universelt valg "funktion" , en konstruktion (som ikke er en funktion i sætmæssig forstand), der forbinder et element af den med ethvert ikke-frit sæt. Enhver udsagn om Bourbakis sætteori oversættes let til en sætteori af typen ZF, som vi har tilføjet et nyt relationssymbol og et aksiom, der bruger dette, der udtrykker, at denne relation er en relation af god orden på hele universet: princippet efter valg. Tau kan derefter fortolkes af "den mindste x, der verificerer en egenskab P, hvis den findes". Hvis denne relation ikke bekræftes af noget objekt, så er denne tau et objekt "som intet kan siges om" .

Vi forbinder på denne måde med enhver påviselig lukket udsagn i Bourbakis teori en oversat udsagn ved hjælp af dette nye symbol, som er påviselig i teorien om sæt ZF, hvis aksiomskemaer (vi kan begrænse os til udskiftningsaksiomskemaet ) blev udvidet til udsagn indeholdende det nye symbol og med princippet om valg. Ved at tilføje grundaksiomet er den nye teori konservativ i forhold til ZFC-teorien (dvs. med fundamentaksiom), det vil sige, at den ikke viser en ny erklæring om det oprindelige sprog.

Noter og referencer

Patrick Dehornoy , kap. 4 “ Valgets aksiom” , i logik og sætteori, forelæsningsnotater, FIMFA ENS ,2006( læs online ) , s. 104.
(De) E. Zermelo , " Beweis, daß jede Menge wohlgeordnet werden kann " , Mathematische Annalen , vol. 59,1 st december 1904, s. 514-516 ( DOI 10.1007 / BF01445300 , læst online , adgang til 18. april 2016 ).
Dehornoy 2006 , s. 106.
Dehornoy 2006 , s. 109.
(i) H. Rubin og jeg Rubin ækvivalenter af udvalgsaksiomet , Vol. II, North-Holland Publishing Company ,1985( læs online ) , s. 8.
(i) Kurt Gödel , " sammenhæng i udvalgsaksiomet og af den generelle kontinuumhypotesen, " , PNAS , vol. 24, nr . 12,1938, s. 556–557 ( DOI 10.1073 / pnas.24.12.556 ).
(i) Kurt Gödel, sammenhængen i udvalgsaksiomet og af den generelle kontinuumhypotesen med aksiomer-of Set Theory , Princeton University Press , 1940, 72 sider, ( ISBN 978-0-69107927-1 ) [ read linje ] .
En sådan konstruktion er desuden bevist umulig (kun ved hjælp af aksiomerne i ZF), fordi det ellers ville give et bevis på det valgte aksiom i ZF, hvilket modsiger Paul Cohens resultat.
Metaforen for sokker og sko findes i Introduktion til matematisk filosofi af Bertrand Russell, (1993) [1919], Dover , New York ( ISBN 978-0-486-27724-0 ) , s. 125-127 .
(i) Jon Barwise , Handbook of Mathematical Logic , Amsterdam / New York, Elsevier,1989, 8 th ed. , 1165 s. ( ISBN 978-0-444-86388-1 , læs online ) , s. 347, Citerer (in) Abraham Adolf Fraenkel , Yehoshua Bar-Hillel og Azriel Lévy , Foundation of Set Theory , Amsterdam, Elsevier al. "Studier i logik" ( nr . 67),1973, 2 nd ed. ( ISBN 978-0-7204-2270-2 ).
(i) John J. O'Connor og Edmund F. Robertson , "En historie om mængdelære" i MacTutor History of Mathematics arkivere , University of St. Andrews ( læses online ).
(in) Andreas Blass, " Existence of bases Implies the axiom of choice " [PDF] , Contemporary Mathematics , 31 (1984), 31-33.
(i) Horst Herrlich , udvalgsaksiomet , Springer ,2006( læs online ) , “Skjult valg” , s. 21-26.
I 1963 konstruerede Paul Cohen en (relativ) model af ZF, hvor en bestemt tællerparfamilie ikke har nogen valgfunktion, hvilket bekræfter Russells intuition . En sådan families genforening kan ikke tælles. Samme år konstruerede Solomon Feferman og Azriel Lévy en (relativ) model af ZF, hvor R i sig selv er en tællelig sammenslutning af tællbare sæt ( (en) P. Cohen, " Uafhængigheden af kontinuumhypotesen " , PNAS , bind 50 , nr . 6,1963, s. 1143-1148 ( JSTOR 71858 )og (en) Paul J. Cohen, " Uafhængigheden af kontinuumhypotesen, II " , PNAS , bind. 51, n o 1,1964, s. 105-110 ( JSTOR 72252 ) ; (en) S. Feferman og A. Lévy, ” Uafhængighed resulterer i sætteori ved Cohens metode II (abstrakt) ” , Meddelelser Amer. Matematik. Soc. , Vol. 10,1963, s. 593).
Mere præcist aksiom af tælleligt valg er en tilstrækkelig betingelse (men ikke nødvendigt) for enhver endelig mængde i den forstand, Dedekind at være begrænset i sædvanlig forstand: se f.eks Herrlich 2006 , kap. 4, s. 48. På den anden side viser vi i en teori uden et valgaksiom, at vi ikke kan udelukke eksistensen af sæt, der både er endelige i Dedekinds forstand og uendelige i den sædvanlige forstand.
Nicolas Bourbaki , Elementer i matematikens historie [ udgaverne ], afsnit “Grundlaget for matematik; logisk; sætteori ”, underafsnit“ Formalisering af logik ”, s. 21, skriver: “[…] det mest interessante [af de geniale modifikationer af nuværende formaliserede sprog] er utvivlsomt introduktionen af Hilbert af symbolet: τ , som gør det muligt at betragte kvantificeringsapparaterne ∃ og ∀ som forkortelsestegn for at undgå introduktionen af det "universelle" funktionelle symbol ι fra Peano og Russell (som kun gælder for funktionelle relationer) og slutter med at formulere det valgte aksiom i sætteori ([163 a], t. III, s. 183.) ” , Noten ([163 a], t.III, s. 183.), der henviser til: (de) D. Hilbert, Gesammelte Abhandlungen , 3 bind, Berlin (Springer), 1932 -35.
N. Bourbaki , Elements of mathematics , vol. I: Sætteori [ detalje af udgaver ] , del 1, kap. 3 ("Kvantificerede teorier").
Dette demonstreres ved hjælp af en simpel variant af tvangsmetoden , der ikke bruger kreditter, se Jean-Louis Krivine , Theory of sets [ detaljer om udgaver ], kap. 10.

Se også

Relateret artikel

Aksiom af beslutsomhed

eksterne links

Hadamard , Borel , Baire , Lebesgue : Fem bogstaver om sætteori (om numdam ), Bulletin de la SMF , t. 33, 1905, s. 261-273
(en) En startside for Axiom of Choice - en introduktion og linkssamling af Eric Schechter (en) fra Vanderbilt University
(en) Asaf Karagila, " Om delingsprincippet " ,2014
Xavier Caruso, valgfri aksiom (læs online)

Arbejder

(en) Paul Howard og Jean Rubin, Konsekvenser af Axiom of Choice , AMS , koll. " Matematiske undersøgelser og monografier (da) " ( nr . 59),1998( læs online )
(en) Thomas J. Jech , Valgets aksiom , Dover,2008( 1 st ed. 1973) ( læst linie )