Teorema Cantor-Bernstein

Teorema Cantor-Bernstein , de asemenea , cunoscut teorema lui Cantor-Schröder-Bernstein , este teorema lui teoria mulțimilor care afirmă existența unei bijectie între două seturi atunci când există două injecții , una dintre doua la prima celălalt de la primul la al al doilea.

Teorema - Dacă există o injecție de la un set E la un set F și o injecție de la F la E, atunci există o bijecție de la E la F.

Se numește astfel după matematicienii Georg Cantor , Felix Bernstein și Ernst Schröder . Cantor a dat o primă demonstrație în acest sens, dar care a folosit implicit axioma alegerii . Bernstein a dat o demonstrație care nu depindea de această axiomă. Cu toate acestea, toate demonstrațiile date folosesc principiul terțului exclus și, prin urmare, nu sunt acceptate de intuiționisti .

Istoric

Georg Cantor a afirmat această teoremă fără dovezi în 1887. În 1895, Cantor a remarcat în prima parte a Beiträge zur Begründung der transfiniten Mengenlehre („Pe fundamentele teoriei mulțimilor transfinite”) că teorema este dedusă din proprietatea trichotomiei pentru cardinali (Cantor consideră într-adevăr că orice set poate fi bine ordonat , ceea ce este echivalent cu axioma de alegere ), dar diferă dovada acestei proprietăți la o publicație ulterioară.

Felix Bernstein , un elev al acesteia, a făcut o demonstrație care nu a folosit ordinele corecte (și nu a necesitat axioma de alegere) încă din 1896 la vârsta de 18 ani. A fost publicat în 1898 la propunerea lui Cantor în Lecții despre teoria funcțiilor sub stilul lui Émile Borel .

Ernst Schröder a publicat și o demonstrație în 1898, dar sa dovedit a fi greșită. Eroarea a fost observată în 1902 de Alwin Korselt, care la informat pe Schröder la început.Mai 1902. Acesta din urmă recunoaște că autorul dovezii teoremei revine în întregime lui Bernstein, într-un răspuns trimis cu cincisprezece zile mai târziu (cu o lună înainte de moartea sa). El adaugă că el însuși a realizat problema în 1901 și i-a spus prietenului său Max Dehn despre asta .

Korselt trimite final Mai 1902un articol în Mathematische Annalen , unde expune eroarea lui Schröder și propune o altă dovadă, dar aceasta nu este publicată până în 1911. În acest timp, dovada lui Schröder este considerată corectă, în special de Cantor, Peano și Schönflies .

Richard Dedekind scrisese o dovadă a teoremei Cantor-Bernstein încă din 1887, pentru care și-a folosit teoria lanțurilor publicată în lucrarea Sa sind und was sollen die Zahlen? (1888). A fost găsit după moartea sa și publicat abia în 1930 .

Ignorând atunci această dovadă, Ernst Zermelo a publicat două dovezi ale teoremei în 1901 și apoi în 1908, ambele bazate pe teoria lanțului lui Dedekind, a doua dintre care se dovedește a fi foarte asemănătoare cu cea a lui Dedekind. Zermelo îi trimisese deja a doua dovadă lui Poincaré la începutul anului 1906 , ca răspuns la o critică a lui Poincaré cu privire la utilizarea inducției complete ( definiție prin recurență și raționament prin recurență ) în dovezile cunoscute atunci ale teoremei Cantor-Bernstein. Această recenzie este însoțită de o versiune detaliată a dovezii Bernstein-Borel care evidențiază utilizarea inducției complete. A fost publicat în Revue de métaphysique et de morale înIanuarie 1906. Dovada lui Zermelo nu folosește numere întregi și, prin urmare, evident nu există recurență. Ca răspuns, Poincaré a publicat în aceeași recenzie în luna mai a aceluiași an o adaptare în franceză a demonstrației lui Zermelo, despre care a criticat utilizarea nepredictivității , critici la care Zermelo a răspuns în 1908.

Trei demonstrații

Prima demonstrație

Lemă preliminară

Începem prin a arăta că dacă este o hartă injectivă a unui set la una din părțile sale , atunci există o bijecție de la . $tu$ $LA$ $B$ $v$ $LA$ $B$

Să se definească secvența prin: ${\ displaystyle (C_ {n}) _ {n \ in \ mathbb {N}}}$

{\ displaystyle \ left \ {{\ begin {matrix} C_ {0} = A \ setminus B \\\ forall n \ in \ mathbb {N} ^ {*}, C_ {n} = u (C_ {n- 1}) \ end {matrix}} \ right.}

Este întâlnirea tuturor mulțimilor : . $VS$ ${\ displaystyle (C_ {n}) _ {n \ in \ mathbb {N}}}$ ${\ displaystyle C = \ bigcup _ {n \ in \ mathbb {N}} C_ {n}}$

Fie atunci aplicația in definit de: $v$ $LA$ $B$

{\ begin {matrix} v: & x \ in C & \ mapsto & u (x) \\ & x \ notin C & \ mapsto & x \ end {matrix}}

$v$ este bine definit cu valori în , deoarece este cu valori în , și dacă atunci și, prin urmare . $B$ $tu$ $B$ $x \ notin C$ ${\ displaystyle x \ notin C_ {0}}$ $x \ în B$

$v$ trimite injectiv în ; și complementul identic în sine. Deci este o injecție. $VS$ $u (C) = \ cup _ {{n \ in \ mathbb {N}}} u (C_ {n}) = \ cup _ {{m \ in \ mathbb {N} ^ {*}}} C_ {m } \ subset C$ $VS$

Să arătăm că este surjectiv. Fie . Să arătăm că există așa ceva . $v$ ${\ displaystyle y \ în B}$ $x \ în A$ $v (x) = y$

Dacă : atunci există astfel încât ( este strict pozitiv deoarece , prin urmare ). Există, așadar, astfel încât . $y \ în C$ ${\ displaystyle i \ in \ mathbb {N} ^ {*}}$ ${\ displaystyle y \ în C_ {i}}$ $eu$ ${\ displaystyle y \ în B}$ ${\ displaystyle y \ notin C_ {0}}$ ${\ displaystyle x \ în C_ {i-1} \ subset C}$ $v (x) = u (x) = y$
Dacă : atunci ${\ displaystyle y \ notin C}$ $v (y) = y$

Astfel, este bijectiv, ceea ce dovedește prima propoziție. $v$

Interpretare

Putem da o interpretare a rezultatului prezentat mai sus. A este setul (infinit) de spectatori dintr-un teatru (infinit). Fiecare spectator și-a rezervat un loc și, inițial, se presupune că fiecare loc este ocupat de un spectator, dar nu neapărat de spectatorul care a rezervat acest loc. B este apoi setul de spectatori așezați. În plus, seturile fiind infinite, este posibil să rămână spectatori în picioare. Aplicația u este aplicația care asociază, cu un vizualizator x , vizualizatorul y = u ( x ) așezat în locul lui x .

$C_ {0}$ este ansamblul spectatorilor care stau inițial în picioare. Acești spectatori merg la locurile lor și îi dau afară pe ocupanți. Acestea formează apoi întregul . Ei fac la fel. desemnează spectatorii aflați în stadiul al n -lea. Ei merg în locurile pe care le-au rezervat și își expulză ocupanții. Iterăm un număr infinit de ori. C desemnează toți spectatorii care s-au ridicat cel puțin o dată (inclusiv cei care au stat inițial). $C_1$ $C_ {n}$

Aplicația v desemnează aplicația care se asociază, cu un spectator x , care trebuie să se ridice în picioare, spectatorul y că el va disloca, sau altceva care, cu un spectator x care rămâne întotdeauna așezat, asociați x însuși. Aplicarea reciprocă a v este aplicația care, la un spectator y , care este deranjat, asociază spectatorul x care vine să ia locul, sau care se asociază, cu un spectator y care nu deranjat, y el însuși.

Dovada finală a teoremei

Să arătăm apoi teorema inițială.

Fie B = g ( F ) imaginea lui F prin injecție g . Harta u = g o f este o injecție de E în B , cu . Deci , există o bijectie v de E pe B . Ca g este o injecție și g ( F ) = B , definește o restricție bijectie h din F pe B . Compusul h -1 ∘ v este o bijecție de la E la F , ceea ce dovedește teorema Cantor-Bernstein. $B \ subset E$

A doua demonstrație

O lemă preliminară

Această dovadă se bazează pe următoarea lemă, un caz particular al teoremei Knaster-Tarski .

Fie un set, setul părților sale și o aplicație în creștere, adică astfel încât . Apoi admiteți un punct fix , adică există o parte din astfel încât . $E$ $P (E)$ ${\ displaystyle G: P (E) \ to P (E)}$ ${\ displaystyle A \ subset B \ Rightarrow G (A) \ subset G (B)}$ $G$ $M$ $E$ $G (M) = M$

Demonstrație finală

Să fim acum injectivi în și injectivi în . Pentru orice parte a , punem , adică se obține prin luarea imaginii directe , apoi complementare în această imagine, apoi imaginea directă prin această complementară și, în final, complementară în această imagine. Nu este dificil de verificat că crește. $f$ $E$ $F$ $g$ $F$ $E$ $LA$ $E$ ${\ displaystyle G (A) = E \ setminus g \ left [F \ setminus f (A) \ right]}$ ${\ displaystyle G (A)}$ ${\ displaystyle f (A)}$ $F$ $g$ $E$ ${\ displaystyle G: P (E) \ to P (E)}$

Apoi introducem partea din lema preliminară. Această parte este invariantă de , ceea ce înseamnă că este complementul in . $M$ $G$ ${\ displaystyle g \ left [F \ setminus f (M) \ right]}$ $M$ $E$

Definim o bijecție prin prezentarea: ${\ displaystyle h: E \ to F}$

dacă ;

x \ în M, h (x) = f (x)

da .

x \ notin M, h (x) = g ^ {{- 1}} (x)

$M$ joacă un rol comparabil cu rolul din prima demonstrație sau cu demonstrația următoare. $VS$ ${\ displaystyle E_ {E} \ cup E _ {\ infty}}$

A treia demonstrație

Această demonstrație este în esență cea publicată de Julius König în 1906 și adesea repetată de atunci.

Să presupunem, fără pierderea generalității , că și sunt disjuncte . $E$ $F$

Pentru elementul de , asociem o secvență finită sau infinit definită prin inducție după cum urmează. Valoarea inițială este . Să presupunem că este definit (altfel nu este definit), apoi: $X$ $E$ ${\ displaystyle (x_ {0}, x_ {1}, \ dots)}$ ${\ displaystyle x_ {0} = x}$ $x_ {n}$ $x _ {{n + 1}}$

dacă are un antecedent cu g , atunci este acest antecedent (unic) (notă: în acest caz n este egal); ${\ displaystyle x_ {n} \ în E}$ $x _ {{n + 1}}$
dacă este definit și are un antecedent prin f , atunci este acest antecedent (unic) (notă: în acest caz n este impar); $x_ {n}$ ${\ displaystyle x_ {n} \ în F}$ $x _ {{n + 1}}$
în celelalte cazuri nu este definit. $x _ {{n + 1}}$

Trei cazuri sunt apoi posibile pentru continuare, ceea ce face posibilă împărțirea în trei seturi: ${\ displaystyle (x_ {0}, x_ {1}, \ dots)}$ $E$

${\ displaystyle E_ {E}}$ este mulțimea de astfel încât secvența corespunzătoare este finită și se oprește pe un element de (într-un mod echivalent, indicele ultimului element este egal); $x \ în E$ ${\ displaystyle (x_ {0}, x_ {1}, \ dots)}$ $E$
$E_F$ este mulțimea de astfel încât secvența corespunzătoare este finită și se oprește pe un element de (într-un mod echivalent, indicele ultimului element este impar); $x \ în E$ ${\ displaystyle (x_ {0}, x_ {1}, \ dots)}$ $F$
$E_ \ infty$ este mulțimea de astfel încât secvența corespunzătoare este infinită. $x \ în E$ ${\ displaystyle (x_ {0}, x_ {1}, \ dots)}$

Noi partiție într - un mod similar în , și . Asa de : $F$ ${\ displaystyle F_ {F}}$ ${\ displaystyle F_ {E}}$ $F _ {\ infty}$

$f$ este o bijecție de pe , precum și de pe ; ${\ displaystyle E_ {E}}$ ${\ displaystyle F_ {E}}$ $E_ \ infty$ $F _ {\ infty}$
$g$ este o bijecție de la , și reciprocă este, prin urmare, o bijecție de la . ${\ displaystyle F_ {F}}$ $E_F$ $E_F$ ${\ displaystyle F_ {F}}$

Obținem astfel o bijecție de pe . $E$ $F$

Generalizare

Să X un set de non-gol și o relație de echivalență pe setul de subseturi de X . Presupunem că îndeplinește cele două proprietăți: $\ sim$

în cazul în care există o bijectie astfel încât, pentru orice parte a , ; ${\ displaystyle A \ sim B}$ $f: de la A la B$ $VS$ $LA$ ${\ displaystyle f (C) \ sim C}$
dacă și și apoi . ${\ displaystyle A_ {1} \ cap A_ {2} = B_ {1} \ cap B_ {2} = \ varnothing}$ ${\ displaystyle A_ {1} \ sim B_ {1}}$ ${\ displaystyle A_ {2} \ sim B_ {2}}$ ${\ displaystyle A_ {1} \ cup A_ {2} \ sim B_ {1} \ cup B_ {2}}$

Fie două seturi și , un subset de și un subset de . Presupunem că și . Deci . $LA$ $B$ $A_1$ $LA$ $B_1$ $B$ ${\ displaystyle A \ sim B_ {1}}$ ${\ displaystyle B \ sim A_ {1}}$ ${\ displaystyle A \ sim B}$

Această generalizare poate fi demonstrată și fără axioma de alegere .

În cazul particular în care și este relația de echipotență , găsim rezultatul anterior. ${\ displaystyle X = E \ cup F}$ $\ sim$

Note și referințe

(în) Ettore Carruccio, Matematică și logică în istorie și în gândirea contemporană , editorii de tranzacții,2006( ISBN 978-0-202-30850-0 ) , p. 354
Georg Cantor, Despre fundamentele teoriei mulțimilor transfinite , trad. Franceză din 1899, declarație p. 347
demonstrație p. 395, pe Gallica.
F. Casiro, „Teorema Cantor-Bernstein”, Tangente , mai-iunie 2008, p. 42-44.
Émile Borel, Lecții despre teoria funcțiilor , p. 104 .
(De) Ernst Schröder , " Ueber zwei Definitionen der Endlichkeit und G. Cantor'sche Sätze " , Johann Ambrosius Barth Verlag , Halle a. S., Kaiserliche Leopoldino-Carolinische Deutsche Akademie der Naturforscher, vol. 71, nr . 6,1898, p. 303-362 (336-344) ( citiți online ).
" ... întrebarea de ce numele lui Schröder este atât de des asociat cu un rezultat pentru care singura sa contribuție a fost să ofere o dovadă eronată. " , (En) William W. Tait (en) , " Michael Potter, Set Theory and its Philosophy (Book Review) " , History and Philosophy of Logic , vol. 26, n o 22005, p. 162-166 ( citește online ), p. 164 .
(de) Alwin Korselt , " Über einen Beweis des Äquivalenzsatzes " , B. G. Teubner , Leipzig, vol. 70, n o 21911, p. 294–296 ( ISSN 0025-5831 , DOI 10.1007 / bf01461161 , citiți online )
" ... Daß ich Herrn F. Bernstein die Ehre, den G. Cantorschen Satz bewiesen zu haben, allein überlasse, hatte ich einstweilen einem Freunde desselben, Herrn Dr. Max Dehn (jetzt in Münster) schon vorigen Herbst resp. Sommer - natürlich zum Weitergeben - gesagt ” , extras dintr-o scrisoare de la Schröder către Körselt din 23 mai 1902, citată de Korselt 1911 .
(în) Gregory H. Moore , Axioma de alegere a lui Zermelo Origini, dezvoltare și influență Springer al. „Studii de istorie a matematicii și științelor fizice” ( nr . 8),1982( ISBN 978-0-387-90670-6 ) , p. 48.
Hinkis 2013 , p. 87.
Hinkis 2013 , p. 89.
Hinkis 2013 , p. 129.
Hinkis 2013 , p. 196.
J. König, „ Despre teoria seturilor ”, Rapoarte săptămânale ale sesiunilor Academiei de Științe , vol. 143,1906, p. 110-112 ( citiți online ).
De exemplu Garrett Birkhoff și Saunders Mac Lane , A Survey of Modern Algebra , Macmillan ,1977( 1 st ed. 1941) ( ISBN 0-02-310070-2 ) , p. 387-388, Andreï Kolmogorov și Sergei Fomin , Elemente ale teoriei funcțiilor și analizei funcționale , Mir,1977, p. 22(prima ediție în franceză 1974), (ro) John L. Kelley , Topologie generală , Van Nostrand,1955( citiți online ) , p. 28(republicat de Springer-Verlag), René Cori și Daniel Lascar , Mathematical logic II . Funcții recursive, teorema lui Gödel, teoria mulțimilor, teoria modelelor [ detaliul edițiilor ], 1993.
Această demonstrație urmează îndeaproape Kolmogorov și Fomine 1977 , p. 22 și Cori și Lascar 1993 , p. 148-149, care simplifică ușor König 1906 și explică utilizarea definiției prin inducție și, prin urmare, a numerelor întregi. Dovada lui Kelley 1955 care nu explicită definiția secvențelor recurente este incorectă, deoarece partiționarea este definită în funcție de caracterul finit și de paritatea numărului de elemente ale setului de imagini al secvențelor și . Acum acest set poate fi finit, dacă secvența corespunzătoare este infinită, dar are un ciclu. Acest lucru a fost remarcat de Leslie Lamport , How to Write a Proof , 1993, p. 8, care ia această dovadă ca exemplu de falsă dovadă informală, a cărei eroare apare atunci când încearcă să o prezinte într-un mod structurat, dar care altfel este dificil de detectat. $(x_ {n})$ $(y_ {n})$
(în) Stan Wagon , Paradoxul Banach-Tarski , UPC ,1993, 253 p. ( ISBN 978-0-521-45704-0 , citit online ) .

Vezi și tu

Articole similare

Teorema comparabilității cardinale
Imobiliar Cantor-Bernstein (ro)

Bibliografie

(ro) Marcel Crabbé, „ Teorema lui Cantor-Bernstein într-un semiring ” , The Mathematical Intelligencer , vol. 33, n o 3,2011, p. 80 ( citește online )
(ro) Arie Hinkis , Dovezi ale teoremei Cantor-Bernstein, o excursie matematică , Birkhäuser,2013, 456 p. ( ISBN 978-3-0348-0788-3 , DOI 10.1007 / 978-3-0348-0224-6 )