1361

Lema lui Zorn Liviu P˘aunescu September 27, 2007 Lema 0.1. (Zorn) Orice mult¸ime inductiv ordonat˘a are cel put¸in un element maximal. Demonstrat¸ia poate fi formalizat˘a ˆın interiorul logicii de ordinul ˆıntˆai folosind axiomele ZF , cadrul acceptat pentru toata matematica, plus celebra axiom˘a a alegerii. Desigur la o prim˘a citire sau pentru matematicianul neinteresat de logic˘a sau teoria mult¸imilor utilitatea demonstrat¸iei const˘a ˆın urm˘arirea pa¸silor decisivi. Sunt propriet˘a¸ti ale mult¸imilor pe care le accept˘am intuitiv f˘ar˘a dificultate (de fapt le cerem mult¸imilor din start) ¸si care oblig˘a acest enunt¸ de loc evident sau chiar contrar intuit¸iei naive. Din punctul meu de vedere axioma alegerii nu este un pasul decisiv din demonstrat¸ie, este doar o proprietate, aparent banal˘a, a mult¸milor, dar pe care axiomele ZF o scap˘a. Demonstrat¸ie. Fie (M, ≤) o mult¸ime inductiv ordonat˘a. Presupunem prin absurd c˘a M nu are nici un element maximal. Ideea este s˘a construim ˆın interiorul mult¸imii M tot¸i oridinali. Ace¸stia nu formeaz˘a o mult¸ime, ci o clas˘a ¸si de aici contradict¸ia. Oridinalii sunt generat¸i de trei operat¸ii. Mai ˆıntˆai clasa lor are un prim element: mult¸imea vid˘a. A dou˘a operat¸ie este succesorul, fiecare ordinal are un succesor, adic˘a un ordinal cu un element mai mult. Pan˘a aici totul seam˘an˘a cu mult¸imea numerelor naturale. Ceea ce diferent¸iaz˘a este c˘a pentru fiecare mult¸ime de ordinali, ¸si cuvˆantul esent¸ial aici este mult¸ime, avem un ordinal mai mare. ˆIn particular exist˘a un ordinal mai mare decˆat toate numerele naturale. Mult¸imea numerelor naturale se opre¸ste odat˘a cu epuizarea numerelor finite, iar clasa ordinalilor continu˘a. Ordinalii reprezint˘a contextul natural pentru procedeul matematic numit induct¸ie ¸si de fapt lema lui Zorn este un fel de induct¸ie.

1

De la ˆınceput ¸si pˆan˘a la final va fi vorba despre lant¸uri (mult¸imi total ordonate). Fie: L = {L ⊂ M : L lant¸}. Acum avem nevoie de cele trei operat¸ii pentru aceste lant¸uri. ˆIn primul rˆand mult¸imea vid˘a este lant¸, adic˘a ∅ ∈ L. Acum pentru fiecare lant¸ avem nevoie de un succesor, un lant¸ cu un element mai mult. Desigur, fiecare lant¸ L are un majorant, dar acel element poate fi deja ˆın L. Avem nevoie de un majorant strict, de un element a lui M cu care sa ˆıl prelungim pe L. Noi ˆıns˘a am presupus prin absurd c˘a ˆın M nu exist˘a elemente maximale. Deci acel elemnt majorant pentru L, chiar dac˘a este ˆın L are un element mai mare, deci g˘asim pentru L un majorant strict. Pentru orice L ∈ L fie: SL = {x ∈ M : x majorant strict pentru L}. Conform celor spuse ˆınainte fiecare mult¸ime SL este nevid˘a (axiomele ZF pentru a vedea c˘a SL este ˆıntr-adev˘ar mult¸ime). Aici intervine pentru prima ¸si ultima oar˘a axioma alegerii. Trebuie pentru fiecare lant¸ s˘a alegem un majorant strict, deoarece pot fi mai mult¸i ¸si avem un num˘ar albitrar de alegeri de f˘acut (num˘ar cardinal, desigur). Din axioma alegerii exit˘a: f : L → M astfel ˆıncˆat f (L) ∈ SL . Definim acum s : L → L prin s(L) = L ∪ f (L). Desigur L ( s(L) ¸si este succesorul de care aveam nevoie. Pentru a treia operat¸ie, un majorant pentru un lant¸ de lant¸uri, avem reuniunea. Putem definii acum not¸iunea de clan (e o definit¸ie adhoc, nu are leg˘atur˘a cu ce numeat¸i clan prin alte p˘art¸i, eg teoria m˘asurii). Definit¸ia 0.2. O mult¸ime C ⊂ L se nume¸ste clan dac˘a: 1. ∅ ∈ C; 2. L ∈ C ⇒ s(L) ∈ C; 3. Pentru un ¸sir {Li }i∈I ⊂ C total ordonat de incluziune avem

S

i∈I

Li ∈ C.

L este un clan, deci exist˘a clanuri. Se observ˘a u¸sor c˘a intersect¸ie albitrar˘a de clanuri este clan. Definim: \ C0 = C. C clan 2

Deci C0 este un clan ¸si este de fapt clasa ordinalilor pe care o aveam de la ˆınceput ˆın minte. Pentru a afirma acest lucru trebuie s˘a ar˘at˘am c˘a C0 este total ordonat˘a de incluziune, ca nu avem ramificat¸ii. Acest lucru ne va tine putin ocupat¸i, deoarece este momentul ˆın care intuit¸ia se opre¸ste. Intuitiv am constrit obiectul C0 , avem in minte faptul c˘a este clasa ordinalilor, dar acum intervine tehnica ¸si trebuie s˘a folosim, cumva ingenios, toate propriet˘a¸tile obiectelor pe care le-am construit pˆan˘a acum. Prima idee este s˘a consider˘am: C1 = {L ∈ C0 : L se compar˘a cu toate lant¸urile din C0 }, adic˘a pentru orice L1 ∈ C1 ¸si orice L0 ∈ C0 L0 este o submult¸ime a lui L1 sau invers sau L0 = L1 . Ca s˘a ar˘at˘am c˘a C1 = C0 vom demonstra c˘a C1 este clan. Propozit¸ia 0.3. C1 este clan. Demonstrat¸ie. Mult¸imea vid˘a este clar ˆın C1 . Probleme mari avem c˘and ar˘at˘am c˘a s(L1 ) ∈ C1 dac˘a L1 ∈ C1 . Fie L0 ∈ C0 . Vreu s˘a ar˘at c˘a L0 se compar˘a cu s(L1 ). Acum L0 se comar˘a cu L1 ¸si dac˘a L0 ⊂ L1 lucrurile sunt ok. Presupunem L1 ( L0 . S˘a presupunem c˘a L0 nu se compar˘a cu s(L1 ). Atunci am avea o ramificat¸ie. L1 ar fi punctul ˆın care arborele se ramific˘a, L0 pe o ramur˘a ¸si cealalt˘a ramur˘a ar ˆıncepe cu s(L1 ). Un desen ar sugera s˘a ”t˘aiem” ramura lui L0 . Definim: C2 = {L ∈ C0 : L ⊂ L1 sau s(L1 ) ⊂ L}. Afirmat¸ia este c˘a C2 este un clan, bineˆınt¸eles. Ca de obicei cu mult¸imea vid˘a nu sunt probleme: ∅ ∈ C2 . Fie un L2 ∈ C2 . Dac˘a s(L1 ) ⊂ L2 totul e ok, s(L2 ) ∈ C2 . Presupunem c˘a L2 ⊂ L1 . Vreau s˘a ar˘at c˘a s(L2 ) ∈ L2 . Acum L1 ∈ C1 ¸si s(L2 ) ∈ C0 , deci L1 se compar˘a cu s(L2 ). Dac˘a s(L2 ) ⊂ L1 lucrurile sunt ok. Presupunem c˘a L1 ( s(L2 ). Avem ¸sirul L2 ⊂ L1 ( s(L2 ), iar mult¸imile L2 ¸si s(L2 ) difer˘a printr-un singur element. Atunci L1 = L2 ¸si rezult˘a s(L1 ) = s(L2 ) ¸si s(L2 ) ∈ C2 . Ar p˘area un pas important demonstrat¸ia faptului c˘a L1 = L2 , dar e un pas doar pentru partea tehnic˘a a demonstraiei, preg˘atit de construct¸iile noastre. Ca s˘a ar˘at˘am c˘a C2 este clan trebuie s˘a vedem c˘a reuniunea unei mult¸imi total ordonate de lant¸unri din C2 este un lant¸ din C2 . Acest lucru este u¸sor, fie toate lant¸urile sunt incluse ˆın L1 ¸si atunci ¸si reuniunea lor, fie exist˘a un lant¸ ce cont¸ine s(L1 ) ¸si atunci ¸si reuniunea lor ˆıl cont¸ine pe s(L1 ). Deci C2 este clan ¸si este inclus ˆın C0 . Din minimalitatea lui C0 avem C0 = C2 . Am definit C2 ¸si am ar˘atat c˘a este clan doar ca s˘a concluzion˘am acum c˘a L0 ∈ C2 . Ipoteza de lucru era L1 ( L0 ¸si vroiam s˘a ar˘at˘am c˘a L0 se compar˘a 3

cu s(L1 ) pentru a concluziona c˘a s(L1 ) ∈ C1 . Acum deoarece L0 ∈ C2 ¸si L1 ( L0 r˘amˆane c˘a s(L1 ) ⊂ L0 , deci L0 se compar˘a cu s(L1 ) ¸si, deoarece L0 era albitrar avem s(L1 ) ∈ C1 . Pentru a ˆıncheia demonstrat¸ia propozit¸iei, a faptului c˘a C1 este clan mai avem nevoie de condit¸ia a treia, cea cu reuniunea. Fie (Li )i∈I un ¸sir de lant¸uri total ordonat din C1 ¸si fie L un lant¸ din C0 . Fiecare Li se compar˘a cu L. Dac˘a L este mai mare decˆat toate lant¸urile Li atunci este mai mare ¸si decˆat runiunea lor. Dac˘a pentru un i ∈ I avem L ⊂ Li atunci L este mai mic decˆat reuniunea Li -urilor. Oricum L se compar˘a cu ∪i∈I Li deci ∪i∈I Li ∈ C1 ¸si asta ˆıncheie demonstrat¸ia faptului c˘a C1 este clan. C1 este clan deci C1 = C0 ¸si atunci C0 este total ordonat. Cel mai mic lant¸ din C0 este mult¸imea vid˘a, exist˘a un singur lant¸ cu un element: s(∅), un singur lant¸ cu dou˘a elemente etc. Pentru fiecare oridinal exist˘a un singur lant¸ din C0 izomorf cu acel ordinal. C0 este o copie a clasei ordinalilor ˆın interiorul mult¸imii M . Cuvˆantul esent¸ial din lema lui Zorn este ”mult¸ime” ¸si aceast˘a lem˘a spune c˘a mult¸imile sunt colect¸ii care se termin˘a. Nu putem num˘ara la infinit (infinitul dat de ordinali) elementele unei mult¸imi. Axioma ZF care implic˘a acest lucru este axioma reuniunii: reuniune de mult¸imi, idexat˘a de o mult¸ime, este o mult¸ime. Ultimul pas este acela¸si cu demonstrat¸ia faptului c˘a ordinalii nu formeaz˘a o mult¸ime ¸si folose¸ste decisiv axioma reuniunii. S C0 este total ordonat˘a ¸si din a treia axiom˘a a clanului L0 = L∈C0 L este un lant¸ din C0 . A contat faptul c˘a C0 este o mult¸ime ¸si atunci L0 este o mult¸ime. L0 este din definit¸ie cel mai mare lant¸ din C0 . Dar L0 ( s(L0 ). Contradict¸ie. Deci orice mult¸ime inductiv ordonat˘a are un element maximal.

4