Functii Möbius

=== 1 ===

Capitolul 1

Latici și mulțimi parțial ordonate

§1. Definiții, exemple și teoreme ale multimilor parțial ordonate și laticilor

Cel mai general concept pe care îl vom considera de acum încolo este acela de muțime parțial ordoantă.

Ne reamintim că o relație binară pe o mulțime S este o submulțime R din mulțtimea produselor . Spunem că a se află în relația R cu b și scriem aRb dacă și numai dacă (a,b)R.

Definiție.O mulțime parțial ordonată este o mulțime S impreuna cu o reație binară a b satisfacând următoarele condiții:

PO1 a a (reflexivitate).

PO2 Dacă a b și b a , atunci a = b (anti-simetrie).

PO3 Dacă a b și b c , atunci a c (tranzitivitate).

Dacă a b și a b, atunci vom scrie a > b. Altfel vom scrie a b ca o alternativă pentru b a și a < b pentru b > a. În general nu vom putea avea nici a b și nici b a pentru o perche de elemente a,b S.Dacă vom avea a b sau ba pentru fiecare pereche (a,b), atunci spunem că S este total ordonată (sau lanț).

Ne-am întâlnit până acum cu câteva exemple de mulțimi parțial ordonate: mulțimea P (S) din submulțimile unei mulțimi S unde pentru mulțimile și înseamnă ,mulțimea subinelelor, și tot așa – toate mulțimile parțial ordonate cu incluziunea definite ca pentru submulțimi.

În general, dacă S , este o mulțime parțial ordonată, atunci orice submulțime T a lui S este parțial ordonată prin relația din S restricționat la T.

Alte exemple interesante au luat naștere din inelele parțial ordonate luând în discuție divizibilitatea în monoide și inele.

De exemplu, în monoidele multiplicative ale întregilor pozitivi putem defini ab asemănător cu a|b (a este divizor al lui b). Atunci PO1 și PO2 au loc. Mai general, fie S un monoid comutativ care satisface principiul reducerii. Spunem că acest S este redus dacă 1 este singurul element inversabil în S. În acest caz a|b și b|a implică a = b.

Atunci S este parțial ordonată dacă deefinim ab prin a|b. Dacă S nu este redus obținem relație de congruență netrivială în S definind a ~ b dacă a = bu, cu u inversabil. Coeficientul monoidal relativ la această relație de congruență este redus și poate fi parțial ordonat prin relația de divizibilitate.

Într-o mulțime parțial ordonată finită dată prin relatia „>” poat fi explicitată în termenii unei relații de acoperire.

Spunem că >dacă nu există u astfel încât >u>.

Este clar că > intr-o mulțime parțial ordonată finită dacă și numai dacă există =,,…,= astfel încât fiecare este o acoperire a lui .

Noțiunea de acoperire sugerează o cale de reprezentare a unei mulțimi parțial ordonate finite S printr-o diagramă.

Reprezentăm elementele lui S prin puncte.

Dacă este o acoperire a lui atunci vom pune deasupra lui și conectăm două puncte printr-o linie dreaptă.

Atunci a < b dacă și numai dacă este o linie frâtă care conecteză a la b.

Dacă nu există nici o linie care sa conecteze a și ba, atunci a și b nu sunt comparabile, deci nu avem nici a b și nici b a.

Câteva exemple de diagrame cu mulțimi parțial ordonate sunt :

Observație! Cea de-a treia figură este chiar o mulțime total ordonată.

Un element u dintr-o mulțime parțial ordonată S este un majorant al submulțimii A din S dacă u a pentru fiecare aA.

Elementul u este cel mai mic majorant sau supremum pentru A dacă u este majorant al lui A si u v pentru fiecare majorant v al lui A.

Este clar din PO2 că dacă există un supremum pentru A atunci el este unic.

Într-o formă similară se definește minorantul și cel mai mare minorant sau infimumul lui A. De asemenea dacă există inf A, atunci el este unic.

Definiție. O latice este o mulțime parțial ordonată în care orice două elemente au superior și inferior.

Notăm cel mai mic majorant al lui a și b prin (“a sau b ” sau “a reunit cu b”) și cell ma mare minorant prin (“a și b” sau “a intersectat cu b”). Dacă a,b,c sunt elementele unei latice L, atunci ()a,b,c și dacă v a,b,c, atunci v ,

c în felul acesta v .

Așadar este superiorul lui a,b și c .

Prin inducție, putem atăta că orice mulțime finită de elemnte ale unei latici are un supremum.

Similar, orice submulțime finită are un inferior (infimum).Notăm supremumul si infimumul lui ,,…, prin

, respectiv .

Orice mulțime total ordonată este o latice. Dacă a și b sunt două elemente ale aceleiași mulțimi avem fie a b sau b a. În primul caz , =a și =b. Dacă b a atunci =b și =a.

O mulțime parțial ordonată se numește latice completă dacă orice submulțime A={} are un superior și un inferior. Notăm acestea prin V și respectiv Λ .

Dacă mulțimea {} coincide cu mulțimea subiacentă laticii L atunci 0Λ este cel mai mic element al lui L și 1V este cel mai mare element al lui L : 0≤a≤1 pentru orice aL.

Următoarea teoremă este un criteriu foarte util pentru a recunoaște că dată o mulțime parțial ordonată ea este o latice completă.

Teoremă 1.1. O mulțime parțial ordonată cu cel mai mare element 1 astfel încât orice submulțime nevidă {} are un cel mai mare minorant este o latice completă. Dual, o mulțime parțial ordonată cu cel mai mic element 0 astfel încât orice submulțime nevidă are un cel mai mic majorant este o latice completă.

Demonstrație.

Presupunând prima propoziție din teoremă adevărată , trebuie să arătăm că fiecare A={ } are un superior.

Cum 1 mulțimea B a majoranților lui A este nevidă.

Să luăm b = inf B. Atunci este clar că b = sup A. Cea de-a doua afirmație rezultă prin simetrie.

Exemple:

Pentru orice mulțime S, P (S) este o latice completă. Aici 1 = S și 0 = Ø.

Mulțimea subgrupurilor unui grup ordonat cu incluziunea. Deoarece G este un subgrup și intersecția oricărei mulțimi de subgrupuri este subgrup, mulțimea subgrupurilor este o latice completă. Demonstația teoremei de mai sus arată că superiorul unei mulțimi de subgrupuri este intersecția tuturor subgrupurilor care conțin mulțimea dată {}.Evident acesta este un subgrup generat de toți .

Următoarele exemple sunt similare cu exemplul 2. Ele sunt latici complete cu relația “≥” care inseamnă incluziune.

Mulțimea subgrupurilor normale ale unui grup. Superiorul mulțimii subgrupurilor normale este subgrupul pe care îl generează acestea.

Mulțimea subspațiilor unui spațiu vectorial ordonat cu incluziunea. Minimul (Inferiorul ) este mulțimea intersecțiilor și superiorul(maximul) este subspațiul cheie dat de mulțimea subspațiilor.

Mulțimea idealelor unui inel R. Infimumul este mulțimea intersecțiilor și supremumul este idealul generat. Pentru două ideale , aceasta este +, mulțimea sumelor ,.

Mulțimea idealelor stângi(drepte) ale unui inel.

Mulțimea întregilor pozitivi parțial ordonați prin relația de divizibilitate: a ≥ b a|b. Aici a b este cel mai mare divizor comun al lui a și b și ab este cel mai mic multiplu comun al lui a și b. Aceasta este o latice dar care nu este și completă.

Toate diagramele de deasupra cu excepția ultimei reprezintă latici (în mod necesar complete deoarece sunt finite).

Mulțimea q a numerelor raționale cu a ≥ b având semnificația uzuală. Aceasta este o mulțime total ordonată și prin urmare q este latice. Oricum q nu este completă.

Chiar și submulțimea raționalilor între 0 și 1 nu este completă. Pe de altă parte intervalul real [0,1] (cu ordinea uzuală) este o latice completă.

Este folositor să alegem proprietățile de bază ale legilor de compoziție binare ab și ab în laticea L.

Aceasta ne va conduce la o definiție alternativă a unei latici în termenii de la condițiile a două legi de compopziție binare pe o mulțime.

Să notăm mai întâi că urmând definițiile observăm ca ab și ab sunt simetrice în cele două argumente.

Prin urmare avem o lege comutativă ab = ba și ab = ba.

Altfel am văzut că (ab) c este supremum din a,b și c.

Cum supremumul este funcție simetrică în a,b și c rezultă că (ab) c=a(b c) și similar (ab)c=a (bc).

Este clar că fiecare a este idempotent relativ la relația și : aa=a, aa=a. De altfel este clar că dacă a≥b, atunci ab= a și ab=b. Deci pentru orice a și b avem (ab) a = a și (ab) a = a.

În schimb, fie L orice mulțime in care sunt definite două legi de compoziție binare și satisfacând condițiile urmatoare:

L1 ab = ba , ab=b a.

L2 (ab)c = a (b c), (a b) c = a (b c).

L3 aa = a, aa = a.

L4 (ab) a = a, (ab) a = a.

Arătăm că dacă L este o latice, relativ la o definiție convenabilă cu relația de ordine ≥ și în care ab și ab sunt supremumul și infimumul lui a și b în această latice.

Înaintea demonstrației să observăm că am făcut în mod precis aceeași presupunere la cele două legi de compoziție și . Deci, avem importantul principiu al dualității care spune că , dacă S este o expunere ce poate fi dedusă din axiomele noastre, atunci expunerea duală S’ obținută prin interschimbarea dintre și oriunde S poate fi dedus.

Vom scrie de acum încolo că dacă a,bL(satisfacând L1-L4), atunci condițiile

ab = a și ab = b sunt echivalente. Vom arăta că definind relația ≥ în L specificând că a ≥ b înseamnă că a b = a, deci ab = b. Evident, dualizând expunerea a ≥ b a fost înlocuită cu b ≥a.

Verificăm acum că relția ≥ pe care am introdus-o satisface relațiile PO1—PO3.

Cum aa = a avem a ≥ a deci PO1 are loc. Dacă a ≥ b și b ≥ a, atunci avem

a b = a și b a = b. Cum a b = b a rezultă că a = b, ceea ce demonstrează PO2. Apoi admitem că a ≥ b și b ≥ c, atunci a b = a și b c = b.

Deci

a c = (a b) c =a (b c) = a b = a.

ceea ce înseamnă că a ≥ c. Deci PO3 este validă.

Cum (a b) a = a, din L4, ab ≥ b. Acum fie c un element astfel încât c ≥ a și c ≥ b. Atunci a c = c și b c = c.

Cum

(a b) c = a ( bc) = a c = c.

deci c ≥ a b. Astfel a b este supremumul lui a și b în L.

Prin dualitate a b este infimumul lui a și b. Aceasta completează verificarea că mulțimea L cu legile binare de compoziție satisfăcând relațiile L1 – L4 este o latice și a b și a b sunt supremumul sau infimumul în această latice.

O submulțime M a laticii L este numită sublatice daca este închisă la relațiile de compoziție date de și .

Este evident că această sublatice este o latice relativ la relațiile de compoziție induse.

Pe de altă parte, o submulțime a laticii poate fi o latice relativ la ordinea parțială ≥ definită în L fără să fie însă sublatice.

De exemplu, laticea subgrupurilor unui grup G nu este sublatice a mulțimii P (G) deci nu este în general subgrup.

Dacă a este un element fixat al laticei L, atunci submulțimea elementelor x pentru care x ≥ a (x ≤ a) este evident sublatice. Dacă a ≤ b, submulțimea elementelor xL pentru care a ≤ x ≤ b este sublatice. Numim sublatice un interval notat I[a,b].

Definiția unei latici dată prin axiomele L1-L4 face naturală definirea unui homomorfism de la o latice L la o latice L’ să fie o funcție a→a’ astfel încât

(a b)’ = a’ b’ și a b = a’ b’. În acest caz dacă a ≥ b atunci avem ab = a; deci a’ b’ = a’ și a’ ≥ b’.

O funcție între mulțimi parțial ordonate are proprietatea de ordine invariantă.

Astfel am arătat că un homomorfism laticial este o ordine invariantă. Oricum reciproca nu are loc.

Un homomorfism bijectiv de latici este numit izomorfism. Acesta poate fi caracteizat prin proprietățile ordinii invariante, așa cum vedem în teorema următoare.

Teoremă 1.2. O funcție bijectivă de la o latice L la o latice L’ este un izomorfism laticial dacă și numai dacă inversa sa este o ordine invariantă.

Demonstrație.

Observăm că dacă a→a’ este un izomorfism laticial, atunci această funcție este o ordine invariantă.

Este clar că funcția inversă este un izomorfism de la L’ la L deci este ordine invariantă.

Reciproc, presupunând că a → a’ este bijectivă atunci ea și inversa sa sunt ordini invariante.

Asta înseamnă că a ≥ b în L dacă și numai dacă a’ ≥ b’ în L’ .

Fie d = a b.

Atunci d ≥ a,b, deci d’ ≥ a’,b’. Fie e’ ≥ a’,b’ și fie e preimaginea lui e’. Atunci e ≥ a,b. Deci e ≥ d și e’ ≥ d’. Astfel am arătat că d = a’ b’.

Prin același raționament putem arăta că (a b)’ = a’ b’.

§2.Distributivitatea și modularitatea laticilor

Una din legile de compoziție ale unei latice poate fi vazută ca analoga aditivității dintr-un inel, iar cealaltă poate fi luată ca analoga multiplicității.

Depinzând de cea care o vom folosi pentru aditivitate sau pentru multiplicitate putem formula următoarele două legi distributive:

D a (b c) = (a b) (a c)

și duala sa

D’ a (b c) = (a b) (a c).

Este puțin surprinzător – precum vom arăta – aceste două condiții sunt echivalente. Presupunem că are loc D. Atunci

(a b) (a c) = ((a b) a) ((a b) c)

= a (a b ) c)

= a ((a c) (b c))

= (a (a c)) (b c)

= a (b c)

care este D’. Prin dualitate D’ implică D. O latice în care această lege distributivă are loc este numită distributivitate. Mai intâi am folosit mai devreme că laticea P (S) a submulțimilor unei mulțimi S este distributivă. În al doilea rând avem următoarea lemă.

Lemă 1.3. Orice mulțime total ordonată este latice distributivă.

Demonstrație.

Vrem să arătăm că are loc D pentru orice trei elemente a,b,c și putem distinge două cazuri (1) a ≥ b,a ≥ c; (2) a ≤ b sau a ≤ c. În (1) avem a (b c) = b c și

(a b) (a c) = b c. În (2) avem a (b c) = a și (a b) (a c) = a. Deci în ambele cazuri D are loc.

Această lemă poate fi folosită ca să arătăm că mulțimea intregilor pozitivi ordonați prin divizibilitate este latice distributivă.

În acest exemplu, a b = (a,b) este cel mai mare divizor comun pentru a și b, și a b = [a,b] este cel mai mic multiplu comun pentru a și b.

De asemenea, dacă scriem a = , b = unde sunt numere prime distincte și și sunt intregi nenegative, atunci (a,b) = ,

[a,b] = . Deci dacă c = , nenegative, atunci

[a,(b,c)] =

și

([a,b],[a,c]) = .

Acum mulțimea întregilor nenegativi cu ordinea naturală este total ordonată și

, în această latice.

Deci, legea distributivă D’ din această latice dă următoarea relație

Atunci avem

[a,(b,c)] = ([a,b],[a,c])

care este proprietatea D pentru laticile de întregi pozitivi ordonati cu divizibilitatea.

Același raționament aplicat oricăror monoizi factoriali reduși (în care au loc reducerea).

Altă observație mai importantă în distributivitate este că în orice latice avem

a (bc) ≥ a b și a (bc) ≥ a c. Deci

a (b c) ≥ (a b)(ac).

Astfel în ordinea stabilirii distributivității este suficient să arătăm inegalitatea inversă

(1) a (b c) ≤ (a b)(ac).

Cele mai importante latice care apar în algebră (de ex. laticea submodulelor unui modul, laticea subgrupurilor normale ale unui grup) nu sunt distributive.

Pentru început, fie L(V) laticea subspațiilor unui spațiu vectorial V peste un domeniu.

Presupunem dim V ≥ 2 și fie x și y vectori linear independenți.

Atunci F(x+y)(Fx+Fy) = F(x+y) dar F(x+y) Fx = 0 și F(x+y) Fy = 0 deci F(x+y)(Fx+Fy)≠( F(x+y) Fx)+( F(x+y) Fy). După cum vedem în acest moment laticea L(V) satisface o condiție de distributivitate mai slabă, care a fost fomulată pentru prima dată de Dedekind.

Iată condiția:

M Dacă a ≥ b, a (b c) = b (ac).

Cum b = ab partea dreaptă a egalității poate fi înlocuită prin

(a b) (ac).

Deci condiția M este echivalentă cu D în cazul special în care a ≥ b (a ≥ c). Condiția M este numită modularitate și laticea care satisface această relație se numește modulară. Condiția duală M’ este: Dacă a ≤ b atunci a (bc) = b (a c). Desigur că este același lucru cu M. Presupunând acestea pentru laticele distributive, principiul dualității are loc și pentru latici modulare.

Importanța laticelor modulare în algebră are la bază următoarea teoremă.

Teoremă 1.4. Laticea subgrupurilor normale ale unui grup este modulară. Laticea submodulelor unui modul este modulară.

Demonstrație.

Subgrupul normal generat de două subgrupuri normale și ale unui grup G este =.

Deci avem de arătat că dacă ,i=1,2,3, sunt subgrupuri normale astfel încât , atunci () = ().

Observația de mai sus despre legea distributivă arată că este suficient să demonstrăm că

() ().

Presupunând că a(). Atunci a = ( ), .

= -1 ,

deci .

Astfel și a = ( ).

Aceasta demonstrează incluziunea cerută.

Argumentul pentru module este similar.

O definiție alternativă pentru modularitate care ne este folositoare poate fi extrasă din urmatoarea teoremă.

Teoremă 1.5. O latice L este modualră, dacă și numai dacă, atunci

când a ≥ b și ac = bc și ac = bc

pentru un c in L,

atunci a = b.

Demonstrație.

Fie L o latice modulară și fie a,b,c elemente din L astfel încât a ≥ b, ac = bc, și ac = bc. Atunci

a = a(ac) = a(bc) = b(ac) = b(bc) =b.

Reciproc, presupunem că L este o latice care satisface condițiile din teoremă. Fie a,b,c L și a ≥ b. Știm că a(bc) ≥ b(ac).

De asemenea

(a(bc))c = a((bc)c) = ac

și

ac = (ac)c ≤ (b(ac)) c ≤ ac.

Deci

(b(ac)) c = ac.

Cum b ≤ a duala primei relații este

(b(ac)) c = bc

și duala celei de-a doua relații este

(a(bc)) c) = bc.

Astfel avem

(a(bc)) c) = (b(ac)) c

(a(bc)) c) = b(ac)) c.

Deci proprietatea de mai sus implică a(bc) = b(ac), care este chiar axioma modulară.

Vom demonstra o teoremă analogă cu a doua teoremă de izomorfism pentru grupuri în cazul laticilor modulare.

Teoremă 1.6. Dacă a și b sunt elementele unei latici modulare, atunci aplicația x → xb este un izomorfism pe intervalul I[a,ab] spre I[ab,b]. Izomorfismul invers este dat de aplicația y → y a.

Demonstrație.

Să arătăm mai întâi că în orice latice aplicațiile x → xa și x → xa sunt ordine invariantă.

Deci avem x ≥ y dacă și numai dacă xy = x și dacă și numai dacă xy =y.

Atunci xy = x implică

(xa)(ya) = (xy)(aa) = (xy)a = xa.

Deci x ≥ y implică xa = ya.

Similar avem xa ≥ ya.

Acum dacă a ≤ x ≤ ab, atunci a b ≤ x b ≤ b = (ab)b,

și dacă ab ≤ y ≤ b,

atunci a = a(ab) ≤ ya ≤ ab.

Deci x →xb și y →ya aplică I[a,ab] în I[ab,b] și respectiv I[ab,b] în I[a,ab].

Deoarece aceste aplicații sunt ordini invariante teorema va folosi Teorema 1.2, dacă arătam că aceste aplicații sunt inverse una celeilalte.

Fie x I[a,ab] .

Atunci, cum x ≥ a, prin modularitate avem :

(xb)a = x(ab)

și cum x ≤ ab, găsim (xb)a = x.

Dual, avem că dacă yI[ab,b], atunci (ya)b = y.

Acesta demonstrează că cele două aplicații sunt inverse una celeilalte.

Acestă teoremă conduce la introducerea noțiunii de echivalență pentru intervalele care în laticile modulare sunt mai tari ca izomorfismele.

Mai întâi să definim intervalele I[u,v] și I[w,t] transpuse dacă există a și b în latice astfel încât unul dintre acestea coincide cu I[a,ab] și celălalt cu I[ab,b].

Intervalele I[u,v] și I[w,t] sunt proiective dacă există un șir finit

I[u,v]=I[,] , I[ ,],…,I[,]=I[w,t]

astfel încât perechile consecutive I[,],I[,] sunt transpuse. Se observă imediat că aceasta este o relație de echivalență.

Deci este clar din Teorema 1.6 că într-o latice modulară intervalele proiective sunt izomorfe.

Facem aici o prezentare a teoremei celor patru funcții extinsă, ca o consecință a funcțiilor date peste laticele distributive.

§3.Preliminarii teorema celor patru funcții

Teoremă 1.7. Dacă M este o latice și X o mulțime parțial ordonată atunci MX (mulțimea aplicațiilor de la X la M ) este o latice. Dacă M este modulară sau distributivă atunci MX este de asemenea modulară respectiv distributivă.

Demonstrație. Fie y=f(x) și y=g(x) două funcții izotone cu o singură valoare, de la X la M , atunci pentru orice x se definește h(x)= f(x) g(x) M, obținem funcția h(x) izotonă, cu o singură valoare și cu cel mai mic majorant (supremum) al lui f și g în MX.

În mod dual h*(x)=f(x)g(x) este cel mai mare minorant și deci prima afirmație este demonstrată.

Pentru cea de-a doua parte a demonsrtației ramâne să arătăm că identitatea de mai sus este bine definită pentru fiecare x.

În acest sens o aplicație importantă a puterilor cardinale este construcția lui 2X,unde X este o mulțime parțial ordonată.

Definiție. O submulțime A a lui X se numește J-închisă (sau semi-ideal dual) când conține pentru orice a toți x≥a.

Ea se numește semi-ideal sau M-închisă când conține pentru fiecare a toți x≤a.

Observație. Dacă X este latice, atunci orice ideal al lui X este M-închis, iar orice ideal dual este J-închis.

Lema 1.8. Laticea distributivă 2X este izomorfă cu inelul tuturor submulțimilor J-închise ale lui X, ordonate prin incluziune.

Demonstrație. Fie A o submulțime J-închisă a lui X ce corespund funcției caracteristice : X → 2, definită prin

=,

Această este evident corespondență unu la unu ; deasemenea valabilă pe 2X ,

deoarece orice f 2X corespunde mulțimii = {x X | f(x)=1}.

Cu alte cuvinte =f.

Mai mult este J-închisă în X datorită izotoniei lui f; dacă a și x≥a atunci f(x)≥f(a)=1 și deci x conform cu definiția lui .

Mai mult, corespondența A → este un izomorfism , deoarece B A implică (x)≤(x), pentru orice x X.

Corolar 1.9. În mod dual este izomorf cu inelul tutror submulțimilor M-închise ale lui X.

Capitolul 2

Algebre booleene

§1. Definiții, exemple și proprietăți importante

Asociată cu o mulțime S care are un agregat P(S),mulțimea submultimilor sale,si algebra (in sens non tehnic) din P (S) bazată pe intersecție si .Când una din incercările de a pune bazele structurii P (S),, aceasta duce la un concept abstarct despre algebra Booleană.

George Boole a fost primul carea a realizat că acest tip de algebră poate fi folosită pentru a analiza calulul propozițiilor din logica matematică și joacă un rol de bază în teoria probablităților.

Un concept mult mai general deacât algebra booleană este acela de latice, noțiune introdusă de Dedekind studiind divizibilitatea în inele comutative și proprietățile combinatoriale ale idealelor care respectau intersecția și suma

Definiție. O algebră booleană este latice cu cel mai mare element 1 și cel mai mic element 0 care este distributivă și completă.

Cel mai important exemplu de algebră booleană este laticea submulțimilor unei mulțimi S.

Mai general orice corp de submulțimi ale lui S – care este o mulțime de mulțimi ale lui S care este închisă la reuniune și intersecție – conține S și mulțimea vidă și complementara oricărei astfel de mulțimi este alegebră booleană.

Următoarea teoremă demonstrează cea mai elementară proprietate a complemenților într-o algebră booleană.

Teoremă 2.1. Complementul a’ al oricărui element a al unei algebre booleene B este unic determinat. Funcția a → a‘ este un anti-automorfism de perioada ≤ 2 : a → a’ satisface

(2) (ab)’ = a’ b’ , (a b)’ = a’b’

(3) a’’ = a.

Demonstrație.

Fie a D , fie a’ și satisfacând a a’ = 1, a a’ = 0.

Atunci =1=(aa’)= a‘.

Deci, dacă în a =1 și a a’=0,

atunci a’ = a , și avem prin urmare a’=.

Aceasta dovedește unicitatea complementului.

Este clar că acest a este complementul lui a’.

Deci

a’’ = (a’)’ = a și a → a’ este cu perioadă unu sau doi; deci bijectivă.

Acum fie a’ b’≤ bb’ = 0.

Deci

b’ = b’1 = b’(a a’) = (b’ a)( b’a’) = b’a’.

Deci, b’ ≤ a’.

De la a → a’ avem inersiunnea canonică care este și ordine inversă ,asta avem din Teorema 1.2 și aplicația a → a’ este un anti-izomorfism laticial.

Din punct de vedere istoric,laticele au fost studiate pentru prioma dată algebre booleene.

Ele au fost introduse de Boole pentru formularea calcului propozitional.

De mult timp a fost presupus că tipurile de algebre reprezentate prin acest sistem au un caracter diferit față de complicatele sisteme de numere și generalizările lor (algebre in sens tehnic și inele).

Oricum, mai devreme sau mai târziu a fost descoperită într-o zi de M.H.Stone dar nu înaceste cazuri.

De fapt, orice algebră booleană,dacă este văzută cum se cuvine, devine un tip special de inel.

Să facem un inel în afara unei algebre booleene B introducem o nouă lege de compoziție:

a+b = (a b’)(a b’)

care este numită diferența simetrică dintre a și b. Avem

(ab)(a b)’ = (ab)(a’b’)

=((ab)a’)((ab)b’)

(4) =((aa’)(b a’))((ab’)(b b’))

=(ba’)(ab’)

=a+b.

Prima formulă arată că într-o algebră booleană de submulțimi ale unei mulțimi, U+V este mulțimea elementelor conținute în U și V dar nu în amândouă:

Vom arăta acum că acest B este un inel cu legea “+” definită mai sus, produsul ab = a b, iar 1 este unitatea lui B.

În mod evident “+” este comutativă. Pentru a demonstra asociativitatea scriem în baza relației (4) urmatoarele:

(a+b)’ = (ab)’(ab) = (ab)(a’ b’).

Deci

(a+b)+c=[ ((a b’)(a’b))c’][((ab)(a’b’))c]

=[(ab’c’)(a’ b c’)][(a b c)(a’ b’ c)]

=( ab’c’)( a’ b c’)( a b c)( a’ b’ c).

Aceasta este simetrică în a, b și c. În particular, (a+b)+c=(c+b)+a.

Comutativitatea implică așadar și legea asociativă pentru “+”. În mod evident,

a+0 = (a 1)(a’ 0) = a

și

a+a = (a a’)(a’ a) = 0.

Deci (B,+,0) este grup comutativ.

De asemenea aּ1 = 1ּa = a 1 = a pentru toți a din B.

Mai ramâne de arătat una din legile distributivității.

Acum avem

(a+b)c = ((a b’)(a’ b)) c

= (a b’ c)(a’ b c)

ac+bc = ((a c)(b c)’)((a c)’(b c))

= ((a c)(b’ c’))((a’ c’)(b c))

= (a c b’)(a’ b c).

Am arătat că (a+b)c = ac+bc.

Deci (B,+,ּ,0,1) este inel.

Am văzut de asemenea că acest inel este comutativ și fiecare element al său are ordinul ≤ 2 în grupul aditiv.

De asemenea fiecare element estre idempotent: a2 = a a = a.

Aceste proprietăți ale inelului nu sunt independente;după cum vom arăta, că dacă orice element al unui inel este idempotent, atunci inelul este comutativ și 2a=0 pentru orice a.

Pentru a demonstra asta, să observăm mai întâi că:

a + b + ab + ba = a2 + b2 + ab + ba = (a + b)2 = a + b.

Deci ab + ba = 0. Atunci 2a = 2a2 = aa + aa = 0 și avem a =–a . Atunci ab = -ba = ba. Aceste considerații ne conduc să untroducem următoarea definiție.

Definiție. Un inel este numit boolean dacă toate elemntele sale sunt idempotente.

Am văzut că un astfel de inel este de caracteristică doi.

Vom arăta că orice inel boolean B definește o algebră booleană și, mai mult, aceste două concepte sunt echivalente.

Presupunem că (B,+,∙,0,1) este inel boolean. Contrar odinii procesului, ca să mergem de la o algebră booleană la un inel boolean definim ab = a+b – ab = 1 – (1 – a)(1 – b).

A doua expresie pentru ab arată că dacă introducem aplicația σ : x → 1-x în B, atunci

ab = σ-1(σ(a)σ(b)),

de asemenea σ2 = 1.

Este clar din aceasta și din legea asociativă a inmulțirii din B că este asociativă și, desigur, compunerea sa este comutativă.

Deci aa = 2a – a2 = –a2=a.

Acum definim ab = ab.

Atunci asociativitatea și comutativitatea sunt evidente, și aa = a orice element din B este idempotent.

De asemenea avem :

(ab)a = (a + b – ab)a = a și (a b)a = ab + a – a2b = a.

Astfel condițiile definite la L1 – L4 prin și ramân valabile pentru latice.

Este imediat faptul că acest inel cu 1 și 0 cel mai mare și cel mai mic element, respectiv, ale laticii (B,,) și 1 – a complementul lui a,chiar dacă a(1 – a) =1 și a(1 – a) = 0.

Laticea este distributivă

(ab)c =(a + b – ab) = ac + bc – acbc = (a c) (b c).

Astfel (B,,,0,1,’) este algebră booleană.

Mai ramâne de arătat că acest proces de trecere de la o algebră booleană la un inel și procesul de trecere de la un inel la o algebră boolenă este invers.

Astfel spus începem cu algebra booleană (B,,,0,1,’).

Apoi obținem inelul (B,,,0,1,’) în care :

a + b =(ab’) (a’b)

și

ab = a b.

Aplicația celui de-al doilea proces al acestui inel dă o algebră booleană în care 1 = 1, 0 = 0, a’ = 1 – a și noii și pe care îi vom nota prin și respectiv sunt:

ab = a+ b – ab = 1 – (1 – a)(1 – b) = (a’b’)’ = ab

și

a b = ab = a b.

Deci = , = și obținem algebra booleană originală.

Pe de altă parte, presupunem că începem cu cu inelul boolean (B,,,0,1) și obținem algebra booleană (B,,,0,1,’) în care a b = a + b – ab, a b = ab, 0 = 0, 1 = 1, a’=1 – a.

Atunci aplicând procedeul am dat inelului structura unui corp în care noua adunare și înmulțire sunt definite astfel:

a b = (a (1 – b)) ((1 – a) b)

= a(1 – b)(1 – a)b

= a – ab + b – ab – (a – ab)(b – ab)

= a – ab + b – ab – ab + ab + ab – ab

= a + b.

a b = a b = ab.

De asemenea 1 = 1, 0 = 0 și obținem inelul original. Așadar avem de demonstrat următoarea teoremă a lui Stone.

Teoremă 2.2. Următoarele două tipuri de sisteme abstracte sunt echivalente: algebra booleană și inelul boolean.

O remarcă care merită facută. Prin procesul de trecere de la o algebră booleană la un inel boolean am putut folosi pentru , pentru , 1 penrtu 0 și 0 pentru 1 în construicție.

Acestea sunt urmări ale principiului dualității care sunt aplicabile și în algebrele booleene.

Procedeul nostru ne-a condus la un inel B’ cu aceeași mulțime subiacentă B în care avem următoarea lege aditivă

a +’ b = (a b’)(a’ b)

și multipicativă

a ∙’ b = a b.

De asemenea noul 0 și 1 sunt 0’ = 1 și 1’ = 0. În condițiile inelului B avem:

a +’ b = (a + (1 – b) – a + ab)(b + (1 – a) – b + ab)

= (1 – b + ab)(1 – a + ab)

= 1 – (a + b)

a ∙’ b = a + b – ab.

Definim idealul algebrei booleene B să fie idealul asociat inelului boolean (B,,,0,1). Condițiile pentru ca submulțimea I să fie ideal sunt :

dacă u,v I , atunci u + v I

dacă a este arbitrar din B, atunci ua I.

Cum ua = u a și ua = a dacă și numai dacă a ≤ u, a doua condiție este echivalentă cu:

Dacă u I, atunci b I pentru fiecare b ≤ u.

Deoarece u v = u + v + uv, u v I pentru fiecare u,v I. În schimb, fie I o submulțime a lui B astfel încât dacă u,v I atunci u v I și dacă u I, atunci fiecare b ≤ u este în I.

Atunci u v’ și v u’ I (u’,v’ fiind complemnții lui u și v,respectiv).

Prin urmare u + v = (u v’)(v u’) I și deci I este un ideal.

Astfel o submulțime I a unei algebre booleene este ideal dacă și numai dacă este închisă la și conține fiecare b ≤ u pentru orice u I.

Un ideal este numit propriu dacă I ≠ B. Este clar că I este ideal propriu dacă și numai dacă 1 I.

Dacă u B atunci (u) = { x B | x ≤ u} este ideal numit idealul principal generat de u. Un ideal I este maximal dacă I este propriu și nu mai sunt alte ideale proprii care să conțină pe I (I).

Observăm că acest ideal I este maximal dacă și numai dacă I este propriu pentru fiecare a B și orice a sau a’ I.

Mai întâi presupunem că I este maximal și fie a I.

Considerăm mulțimea cu elemente de forma u + b unde u I și b ≤ a.

Acesta este un ideal care conține exact pe I, deci, prin maximalitatea lui I, el coincide cu B. Astfel 1 = b + u unde b ≤ a și u I.

Prin urmare b’ = 1 + b = u I.

Cum a’ ≤ b’ este de asemenea adevărat că a’ I. În schimb, fie I un ideal propriu astfel încât pentru fiecare a B și orice a sau a’ I.

Fie orice ideal care îl conține exact pe I și fie a ,I. Atunci a’ I, și deci a’ și 1 = a + a’ .

Astfel = B

și

I este maximal.

Toate acestea pot fi dualizate aplicând aceleași considerații ca la al doilea inel B’ = (B,+’,∙’, 0’,1’) asociat algebrei booleene B.

Prin urmare, definim ca filtru (idealul dual) al lui B să fie idealul B’.

Deci rezultatele anterioare pot fi dualizate.

Mai întâi, notăm prin dualitate, conform criteriului nostru pentru ca o submulțime să fie un ideal, o submulțime F a algebrei booleene B este filtru dacă și numai dacă este închisă la și conține fiecare b ≥ u pentru orice u F.

Cum (a b)’ = a’ b’ și (a b)’ = a’ b’ este clar că F este filtru dacă și numai dacă mulțimea F’ a complemenților a’,a F, este ideal.

Condiția (1) este echivalentă cu o intersecție finită, mai exact : F este închisă la intersecții finite.

Un filtru este propriu în sensul că F ≠ B dacă și numai dacă 0 F.

Un ideal maximal al lui B’ este numit ultrafiltru al algebrei booleene B. Un filtru F este ultrafiltru dacă și numai dacă

0 F,

Pentru orice a B oricare ar fi a sau a’ F.

Dacă a B, submulțimea elementelor x ≥ a este filtru numit filtru principal generat de a.

EXEMPLE

Fie r dreapta reală înzestrată cu topologia uzuală și fie S notația pentru o familie de submulțimi deschise ale lui r. Aceasta are proprietatea intersecțiilor finite. Mulțimea a submulțimilor care conțin submulțimile deschise ale lui r este filtru.

Fie S o mulțime oarecare, B = P (S) mulțimea submulțimilor lui S. Fie I mulțimea submulțimlor finite ale lui S. Acesta este ideal în B; prin urmare mulțimea F a complemenților a submulțimilor finite este filtru.

§2.Extindere a teoremei celor patru funcții

§§2.1. Maxime și minime slabe

Este bine cunoscut de mai sus și din [3] că orice algebră booleană finită = (X,0,1,¯,,) este izomorfă cu algebra booleană (2N,Ø,N,–,, ) a submulțimii N={,,…,}, mulțimea atomilor lui .

Incluziunea între submulțmile lui N transformă 2N într-o mulțime partial ordonată.

În cele ce urmează vom considera funcțiile reale definite pe 2N care sunt compatibile cu această ordine parțială și vom explora această structură.

Definiție. O funcție reală : 2N → R+ este numită izotonică dacă satisface condiția următoare:

(ISO) Dacă M P N, atunci (M) ≤ (P).

Notată prin Iso(N) mulțimea funcțiilor izotonice : 2N → R+.

Desigur , structura algebrică a lui R+ (semigrup aditiv, grup multiplicativ) este transferată pe Iso(N) în mod evident.

În cele ce urmează vom urmări transferul structurii ordinii naturale a lui R+,care pare puțin mai interesantă.

Date , Iso(N), ≤ înseamnă (M) ≤(M) pentru orice M N. Desigur, putem defini =max(,) și = min(,) prin

(M)=max((M),(M))

(M)=min((M),(M)) pentru M N.

Dar, pentru că ținta este să extindem teorema Ahlswede-Daykin (i.e. teorema celor patru funcții), operațiile max-slab și min-slab pe Iso(N) nu vor fi definite prea clar.

Definiție. Date , : 2N→ R+ , funcția : 2N → R+ este definită recursiv astfel:

(1) ()(Ø)=max{(Ø),(Ø)},

(2) pentru M N , M≠Ø

()(Ø)=

Dual , funcția : 2N → R+ este definită recursiv astfel:

(1) ()(Ø)=min{(Ø),(Ø)},

(2) pentru M N , M≠Ø

()(Ø)=

În particular, pentru N={1} avem:

()(N)=max{(Ø),(Ø)} ∙ ,

()(N)=min{(Ø),(Ø)} ∙ ,

Propoziția 2.3. Dacă , Iso(N), atunci , Iso(N).

Demonstrație.

Să considerăm M P N . Luând în considerare definiția recursiva a lui , avem

() (P) ≥ ()(M) .

Deoarece M K, L P, avem (M) ≤ (P) și (M) ≤ (L), astfel factorul max este ≥1. Deci ()(M) ≤ () (P).

Dual, luând în considerare definiția recursivă a lui , avem:

()(P) ≥ ()(M) .

De această dată factorul min este >1, pentru că (P) ≥ (K) și (P)≥(L), deci

()(M) ≤()(P).

q.e.d.

Propoziția 2.4. Dacă , Iso(N), atunci:

(1) pentru orice M,P N avem

(M)∙(P) ≤ ()(M P)∙()(M P)

Și în particular

(2) pentru orice M N avem

(M)∙(M) ≤ ()(M)∙()(M).

Demonstrație.

Să începem cu demonstrarea punctului (2). Pentru M = Ø avem, prin definiție

()(Ø)∙()(Ø) = (Ø)∙(Ø).

Presupunem M ≠ Ø. Atunci există J* M și K*,L* astfel încât K* L* =J*, K*L*=M și

()(M)=( )(J*)∙.

Prin inducție știm că ()(J*)∙()(J*) ≥ (J*)∙(J*). De aici, luând în considerare definiția recursivă a lui , avem :

()(M)∙()(M)=

=( )(J*)∙∙≥

≥ ( )(J*)∙∙()(J*)∙≥ (M)∙(M).

Să demonstrăm acum (1). Fie M,P N.

Dacă M P = Ø, atunci evident avem egalitatea

(M)∙(P)=()(M P)∙()(M P)

pentru că M = N = M P = Ø.

Dacă M P ≠ Ø, atunci M P M P și avem

()(M P) ≥ ( )(M P) ∙ ≥

≥ ()(M P) ∙ .

Acum putem valorifica (recursiv) inegalitatea

()(M P)∙()(M P) ≥ (M P)∙(M P).

și propoziția este demonstrată.

Operațiile max-slab și min-slab nu sunt veritabilele operații max/min. de exemplu, în general ≠ ≠ , tot ceea ce putem stabili este

≤ ,≥.

Dar proprietățile acestor operații sunt bine inzestrate pentru extinderea teoremei Ahlswede-Daykin.

§§ 2.2. Teorema celor patru funcții

Enunțul calsic al teoremei celor patru funcții este următorul:

Teoremă 2.5. (Ahlswede—Daykin ). Dacă =(L,,) este o latice distributivă și ,,, : L → [0,] sunt în așa fel încât

(x)(y)≤(x y)(x y)

Pentru fiecare x,y L, atunci

(X)(Y)≤(X Y)(X Y) pentru fiecare X,Y L.

Aici extinderea a funcției : L → [0, ] este definită prin

(Z) = pentru Z L,

unde este funcția caracteristică a lui Z (ca o submulțime a lui L).

Mai mult , X Y și X Y sunt definite astfel:

dacă X=Ø sau Y=Ø, atunci X Y = X Y = Ø;

dacă X,Y≠Ø, atunci X Y = {x y | a X, y Y } și X Y={x y | x X , y Y}.

Demonstrația nu a o dăm aici ea poate fi gasită în [6] sau [7].

Considerăm acum algebra booleană = (2N,Ø,N,–,,) și presupunem că

: 2N → [0, ] este o funcție . Înseamnă că : Iso(N) → [0,] extinderea lui este definită prin

()= .

Propoziția 2.6. Presupunem ,,, : 2N → [0,] sunt patru funcții care satisfac condiția

(M)∙(P) ≤ (M P)∙(M P)

pentru toți M,P N.

Atunci

()∙() ≤ ()∙() pentru orice , Iso(N).

Unde este minimul slab și este maximul slab al funcțiilor izotonice.

Demonstrație.

Presupunem că , ,, satisfac condiția:

(M)∙(P) ≤ (M P)∙(M P) pentru M,N N

și , sunt funcțiile izotonice definite pe 2N. Atunci , din propoziția 2 (1) de mai sus aveam

(M)∙(P)=()(M P)∙()(M P)

Dacă aratăm că :

’(X)=(X)∙(X), ’(X)=(X)∙(X), ’(X)=(X)∙()(X),

’(X=(X)∙()(X) pentru X N,

atunci este evident că:

’(M)∙’(P) ≤ ’(M P)∙’(M P) pentru M,N N

Aplicând teorema de mai sus (unde L este algebra boolean canonică peste 2N).

Am obținut

’(2N)∙’(2N)≤ ’(2N)∙’(2N).

Acum

’(2N)= ===(),

Similar avem:

’(2N)=(), ’(2N)≤(), ’(2N)≤( ) și propoziția 2.6 este demonstrată.

=== FUNCTI~1 ===

Capitolul 3

Funcția Möbius

În acest capitol, vom da o aplicație a mulțimilor parțial ordonate la probleme de numărare. Tipul problemei pe care o vom considera, implică o sumare după o mulțime parțial ordonată, a cărei inversiune dă formula de numărare. Următoarea problemă este din această categorie.

§1. Problema 1

Numărul deranjamentelor unei mulțimi finite (pentru mulțimi parțial odonate).

Presupunem că S este o mulțime finită. Numim deranjament al lui S orice permutare a lui S fară puncte fixe. Notăm prin

Der S = { :S→S | bijectivă, Fix =Ø}

mulțimea deranjamentelor lui S.

Fie T S.

f(T)=numărul permutărilor lui S care fixează toate elementele lui T, dar nu fixează nici un element din T’ = S–T.

f(T)=|{ | Fix =T}|

g(T)=numărul permutărilor lui S care fixează toate elementele lui T și poate și alte elemente în plus.

g(T)=|{ | T Fix }.

Notăm: ={ | Fix T}

{ | T Fix }, T S

Lema 3.1. = .

Demonstrație.

Vom demonstra prin dublă incluziune.

„” Fie Fix T. Notăm U=Fix .

Prin urmare: (1’)

„” Fie () T astfel încât Fix =

T Fix T

Deci : (2’)

Din (1’) și (2’) rezultă :

=

Demonstrăm că reuniunea este disjunctă.

Presupunem că () și Fix = U’ U=U’.

Prin urmare : =.

Lema este complet demonstrată.

Conform lemei 3.1, trecând la cardinali, rezultă :

||= g(T)=

Deci am obținut :

||=, U P (S) (1)

Obiectivul este de a inversa relația (1), adică de a obține o formulă pentru f(U) în termenii lui g(T).

Der S=FØ, |Der S|=| FØ |=f(Ø)

G(T)=numărul permutărilor lui T’=(|T’|)!.

În general, fie S o mulțime parțial ordonată (S,≤) și f,g : S → A, unde A este un grup comutativ. Avem :

g(Y)=, y S. (2)

Din nou, vrem să exprimăm f în termenii lui g.

Lema 3.2.(Szpilrajn – Marczewski)

S poate fi total ordonată. Există o numerotare S = {,,.., } a mulțimii S astfel încât din < rezultă i<j.

Demonstrație.

Numerotarea mulțimii S o facem astfel : deoarece S este finită, putem alege S astfel încât să fie element minimal; alegem S astfel încât să fie element minimal în S\{}; alegem astfel încât să fie element minimal în S\{,}. Continuăm acest procedeu alegând inductiv astfel încât să fie element minimal în mulțimea S\{,,…, } ș.a.m.d.

Atunci S={,,…,} satiface proprietățile cerute.

Presupunem prin absurd că (< j≥i) , S\{,,….,} dar este element minimal în S\{,,….,} și <, contradicție.

Deci < rex i<j.

Lema este complet demonstrată.

Fie (S,≥) o mulțime parțial ordonată.

Definim aplicația : S×S → Z

(x,y)= (3)

Utilizând total ordonarea dată în lemă, vedem că relația (2) poate fi scrisă ca un sistem de ecuații :

g() = (i=1,2,…,n)

sau în formă matriceală:

(4)

f,g : S → A x S, f(x),g(x) A.

Deoarece A este grup abelian, A poate fi privit în mod natural ca Z–modul.

(Pentru n Z, n>0 și x A, definim nx=x+x+…+x (n termeni),0∙x=0 și pentru n<0,

(–n)x=–((–n)x); Z×A → A, (k,x) → kx legea de compoziție externă. Deci orice grup abelian poate fi conceput ca Z–modul).

Avem :

(,)=1

Dacă i>j nu putem avea ≤ (x,x)=0.

Deci matricea Z=()1≤i≤n,1≤j≤n este superior triunghiulară ci unu de-a lungul diagonalei principale , une =(,). Este evident că Z (Z) și Z=I–N, unde N=()1≤i≤n,1≤j≤n cu N=

Deoarece det Z =1≠0, rezultă că Z este inversabilă în (Z).

Notăm cu M=()1≤i≤n,1≤j≤n inversa sa. Din calculul inversei unei matrici avem :

=1 dacă 1≤i≤n

=0 dacă i>j

Matricea M=()1≤i≤n,1≤j≤n definește funcția Möbius a mulțimii parțial ordonate S prin :

: S×S → Z (,)= , , S.

Ecuația (4) are forma prescurtată :

G = Z∙F, unde :

G=; F= (A).

Putem înmulți relația de mai sus la stânga cu inversa lui Z și obținem :

F=M∙G.

Avem :

f()== (6)

Renunțând la renumerotarea mulțimii S, putem rescrie (6) astfel :

f(y)= , y S.

Teorema 3.3. Pentru orice mulțime finită, parțial ordonată (S,≥), există o unică funcție : S×S → Z astfel încât, dacă A este un grup comutativ și f,g : S → A astfel încât

g(y)= , y S

atunci

f(y)= , y S.

Această egalitate se numește inversiunea lui Möbius.

Demonstrație.

Existența lui a fost arătată în cele precedente teoremei.

Să arătăm unicitatea lui .

Fară a restrânge generalitatea, putem presupune că sunt ordonate ca în lema Szpilrajn–Marczewski. Luăm A=(Z,+) și considerăm aplicația :

: S → A=Z.

()==

Fie corespondența funcțiilor de la S la Z definită prin relația (2) sau echivalent, prin (4).

()==(,).

=()==

Avem ecuația matriceală :

M∙Z=1, unde M=() 1≤i≤n,1≤j≤n, Z =((,)).

Deci M este unic determiantă M = Z-1 și, în consecințîă, funcția este unic determiantă.

Teorema este complet demonstrată.

În mod similar putem rezolva sistemul de ecuații de forma :

g(y) = , y S (7)

Dacă definim Z=()1≤i≤n,1≤j≤n, ca mai înainte (utilizând ordonarea din lemă), atunci (7) este echivalentă cu ecuația matriceală :

(g(),g(),….,g()) = (f(),f(),….,f())∙Z

Atunci :

(f(),f(),….,f()) = (g(),g(),….,g()) ∙M,

unde M=Z-1.

Corolar 3.4. Fie f,g : S → A, A grup abelian, satisfăcând :

g(y) = , y S.

Atunci :

f(y) = .

Funcția Möbius poate fi determinată printr-o formulă de recurență.

Corolar 3.5. Funcția Möbius este unica funcție de la S×S la Z, satisfăcând (x,y)=0, dacă x≤y și formula de recurență :

=(x,z). (8)

unde funcția delta(x,z)=

altenativ, (8) poate fi înlocuită prin :

=(x,z).

Demonstrație.

Relațiile din enunț sunt echivalente cu ecuațiile matriceale M∙Z=,respectiv Z∙M=.

Într-adevăr, să demonstrăm =(x,z),

Z∙M= = .

Avem :

(,)=1 dacă ≤

(,)=0 în caz contrar.

=. (*)

Cum din ≤ rezultă j<k și în acest caz avem (,)=0, obținem egalitatea :

=.

Să dovedim mai întâi că dacă ≤ este falsă, atunci (,)=0.

Demonstrăm prin reducere la absurd.

Presupunem prin absurd că (,)≠0 este falsă și relația ≤ nu are loc deloc.

Considerăm mulțimea ={ P | & (,)≠0}.

Fie element maximal în (căci este finită).

Egalitatea (*) scrisă pentru și se reduce la (,)==0 (deoarece ≠j), contradicție cu definiția lui .

Dacă avem ≤ și ținând cont de rezultatul pe care l-am demonstrat, egalitatea (*) se scrie :

=

sau renunțând la renumerotarea mulțimii S obținem : (x,y)=0 dacă xy și în cazul x≤y avem :

=(x,z)= .

Analog, din egalitatea M∙Z=, obținem egalitatea :

=(x,z).

§2. Problema 2

Problema colorării hărților.

O hartă este definită ca un plan divizat într-un număr finit de regiuni nesuprapuse, numite țări, conectate printr-un număr finit de arce care se intersectează doar nu la capete (deci intersecția a două arce este fie zero, fie un singur punct).

Putem scrie : =((,…,),(,…,),(m,n))

Unde : T : → P (R2)

T(j)= tara, j .

A : → A i , A(i) = arc

Două țări și sunt adiacente dacă au o frontieră comună care este unul dintre arce, adică dacă (() a A) ={a}

Fie C={,…, } o mulțime de culori.

Definiție. O funcție c : {,…,} → C se numește funcție de colorare dacă este definită prin condiția următoare:

C()= dacă este colorata cu culoarea .

Definiție. O funcție de colorare c : {,…,} → C se numește colorare proprie dacă este îndeplinită condiția următoare:

(,) adiacente c()≠c().

(adică orice două țări am considera, ele sunt colorate cu aceeași culoare).

Problemele care se pun sunt :

(Numărul colorării proprii ale unei harți)

Se dau : a) o hartă

b) k culori

Se cere : să se determine numărul de funcții de colorare proprie.

(De Morgan 1850) (problema celor 4 culori). Să se stabilească dacă numărul colorării ale oricărei hărți cu 4 culori este strict pozitiv.

Reformulare. Să se stabilească adevărul sau falsul următorului enunț:

„Pentru orice hartă, există cel puțin o colorare proprie cu k = 4 culori ”.

Răspunsul la problema (2) este afirmativ: pentru orice hartă, numărul colorărilor proprii cu k=4 culori este pozitiv. Problema a fost rezolvată în 1985 utilizând 1200 ore de calculator.

Scopul urmărit în continuare: Se cere ca pentru orice hartă H există un polinom cu coeficienți intregi Z[X] astfel încât (4) reprezintă numărul colorării ale lui H de ordin k (adică cu k culori).

(k) se numește polinomul cromatic asociat hărții H. Prin polinomul cromatic asociat hărții H este furnizată o soluție la problema (1).

În limbajul polinomului cromatic, problema celor 4 culori are urmatorul enunț.

Să se stabilească calitatea logică a următoarei propoziții:

„Pentru orice hartă H, (4)>0, unde (4) este polinomul cromaticasociat hărții H”.

Cu alte cuvinte, să se stabilească care dintre următoarele enunțuri este adevărat:

(1) ( H hartă ) (4)>0.

(2) (() H hartă) (4)=0.

După cum am precizat anterior, enunțul (1) este adevărat.

Definim o subhartă a hărții ca fiind harta obținută din ștergând anumite arce.

Mulțimea subhărților lui o notăm cu s().

Definim pe s() o relație de ordine „≤” astfel:

( (E,) s2()) E≤ E este o subhartă a lui .

( s()) f()= numărul colorării proprii ale lui cu k culori.

g()=numărul total de colorări.

Notăm cu c()numărul de țări din .

Atunci :

g()=kc()

(numărul aplicațiilor de la mulțimea țărilor la mulțimea culorilor).

Pentru orice colorare E a lui , există o unică subhartă E a lui și o colorare proprie c* a lui E astfel încât este o extensie a lui c*.

Avem :

g()=

avem : f:(s(T),≤) → (Z,+) și g : (s(T),≤) → (Z,+) astfel încât :

g()=

Conform corolarului 3.4, rezultă :

f()=

unde este funcția lui Möbius pe (s(T),≤), deci : s(T)×s(T) → Z verifică condiția corolarului 5. F() este polinomul cromatic al lui .

Teorema 3.6. Fie C={0,1,…,n} cu ordinea naturala. Atunci fucția Möbius a lui C este dată prin :

(i,i)=1, (i-1,i)=-1

(j,i)=0, dacă j≠i,i-1

Demonstrație.

(i,i)=1, i C.

(i,i+1)=–1, deoarece (i,i)+(i,i+1)=0.

(i,j)=0, j≠i,i+1.

Dacă : j<i (i,j)=0.

i<j și j≠i+1 i< i+1,j

j=i+2 =0 (i,i) + (i,i+2)=0 (i,i+2)=0.

Analog (i,i+3)=…=(i,n)=0.

Deci avem :

(i,j)=

Altă demonstrație :

: C×C → Z

g(i)= g(i)= .

Conform corolarului 3.4, rezultă :

f(i)= , (i,i)=1, (j,i-1)=-1, (i,j)=0 pentru j≠i-1,i.

Teorema 3.7. Fie S=× , unde , i=1,2 sunt mulțimi parțial ordonate fie ,, respectiv funcțiile Möbius ale lui S,,. Atunci

((,)∙(,))=(,)(,), , , , .

Demonstrație.

Reamintim că dacă și sunt mulțimi parțial ordonate, atunci și × este parțial ordonată prin:

(,)≤(,) ≤ & ≤ .

Fie :× → Z , :× →Z și : S×S → Z funcțiile Möbius asociate mulțimilor , și respectiv S.

Vom arăta că :

((,),(,))=(,)∙(,)

Fie ’: S×S → Z definită prin egalitatea :

’((,),(,))=(,)(,).

Dacă (,) ך≤ (,), atunci ך≤ sau ך≤ și atunci (,) = 0 sau (,)=0, adică ’((,),(,))=0.

Calculăm

Avem :

== =

=(,)(,)=((,),(,)).

Conform corolarului 3.5, din relația de mai sus

=((,),(,)).

Și unicitatea funcției , rezultă ’ = . Deci teorema 7 este demonstrată.

Putem utiliza aceste rezultate pentru a calcula funcția Möbius a algebrei booleene P (S), S={1,2,…,n}. Rezulatul este următorul :

Corolar 3.8. Fie S={1,2,…,n}. Funcția Möbius a algebrei booleene P (S) este dată de formula :

(U,V)=

Unde V–U = V U’ = {x V | x U }.

Demonstrație.

P (S) C×C×…×C (de n ori), C={0,1}

Fie U S, S={1,2,…,n}. Îi asociem lui U funcția caracteristică :

: S → {0,1}

s S avem (s)=.

Putem reprezenta prin vectorul ((1),…,(n)).

Aplicația P (S) U → ((1),…,(n)) ××…×, unde ={0,1}, este un izomorfism de ordine.

(U,V)=( (1),…,(n)), ((1),…,(n)))=

= ((1),(1)) ((2),(2))… ((n),(n))=

=

Alta demonstrație:

Presupunem U V și m = |V–U|

m=0 U=V (U,U)=1.

Presupunem afirmația adevărată pentru toate mulțimile finite de cardinal mai mic și o demonstrăm pentru mulțimile finite cu m elemente.

Cum =0, această egalitate se mai scrie și astfel:

(U,U)+ ++…++(U,V)=0.

Folosind ipoteza de inducție și faptul că există submulțimi W cu proprietatea că U W V și cu |W-U| = k rezultă:

1+(–1)1+(–1)2+…+(–1)m-1+(U,V)=0.

Cum 1–+–+…+(–1)m=0 obținem că (U,V)=(–1)m.

Utilizarea funcției Möbius a lui P (S) este deseori referită metoda includerii și excuderii.

Soluția problemei 1

Numărul deranjamentelor lui S={1,2,…,n} este :

f(Ø)==== =.

Acesta este asimptotic egal cu .

=.

§3. Problema 3

Tratare a funcției Möbius pe cazul

Fie n și laticea divizorilor întregi ai lui n, ordonați prin divizibilitate (a≥b însemnă a|b), adică :

Pe considerăm relația de ordine divizibilitatea, adică dacă d,d’ , atunci d≤d’ d|d’.

Putem scrie n= , unde ,,…, sunt numere prime distincte și ≥1. Considerăm mulțimile ={0,1,…,}.

Rezultă că este izomorfă ca latice cu mulțimea ordonată ××…×. Acest izomorfism este definit astfel: dacă d , d=, 0≤≤, atunci definim : → ××…× astfel : (d)=(,,…,).

Se vede imediat că este o bijecție.

Conform teoremei 7 rezultă că funcția lui Möbius a lui este egală cu funcția Möbius a mulțimii ordonate produs ××…×. Mai precis, dacă a, b sunt din cu a=, b= și a|b rezultă :

≤ și (a,b)=.

Cum

(,)=–1 dacă =+1,

(,)=1 dacă = și

(,)=0 în rest

Obținem că:

Cum (,)=–1 dacă =+1, (,)=1 dacă = și (,)=0 dacă în rest obținem că:

(a,b) =

Deci, (a,b)=(1,)=() reprezintă funcția Möbius clasică din teoria numerelor.

(n)=.

Fie K un corp finit având q elemente (corpul K este comutativ) și V un K-spațiu vectorial de dimensiune n. Deoarece V≈Kn , atunci V are qn elemente.

Vom nota L(V) laticea tuturor subspațiilor vectoriale ale lui V.

Deoarece corpul K este finit, atunci L(V) est eo latice finită. Dacă 0≤k≤n este un număr natural vom nota numarul de subspații vectoriale ale lui V care au dimensiunea egală cu k.

Numerele , unde k=0,1,…,n se numesc coeficienții lui Gauss sau numerele lui Gauss asociați spațiului vectorial V. Cum avem un singur subspațiu de dimensiune zero și anume spațiul vectorial nul al lui V, atunci =1.

Următoarea teoremă ne precizează mai bine care sunt numerele .

Teoremă 3.9. Cu notațiile de mai sus avem relațiile

i) =

ii) =

iii) = qk + .

Are loc identitatea polinomială (identitatea lui Cauchy)

iv) yn = 1+.

Demonstrație.

i) Vom nota numărul de sisteme ordonate având k vectori liniar independenți. Ca prim element al unui astfel de sistem putem considera pe oricare din cei qn-1 vectori diferiți de zero.

Orice vector v≠0 generează un subspațiu unidimensional conținând q vectori. Deci sunt qn-q vectori liniar independenți față de V și oricare dintre ei poate fi luat ca cea de-a doua componentă.

Fie w una dintre acestea. Perechea {v,w} generează un subspațiu bidimensional conținând q2 vectori.

Deci există qn–q2 vectori liniar independenți față de {v,w} și oricare ar fi dintre ei poate fi luat ca cea de-a treia componentă. Continuând astfel rezultă că

= (qn-1)(qn-q)…(qn-qk-1).

Fiecare k sistem de vectori liniar independenți generează un subspațiu k-dimensional.

Pe de altă parte, orice subspațiu k-dimensional conține baze ordonate care îl generează. Deci

= =

și relația i) se poate obține reducand în mod convenabil puterile lui q.

ii) Egalitatea i) se mai poate scrie și astfel:

(*) = ceea se arată că = adica ii).

Afirmația iii) rezultă direct prin calcul folosind egalitatea (*) de mai sus.

Pentru a demonstra afirmația iv) vom nota cu un spațiu vectorial de dimensiune n peste corpul K, iar cu V un K-spațiu vectorial având y vectori.

Este evident că avem având y vectori. Este evident că avem yn omomorfisme definite pe și cu valoru în V.

Fie f : → V un omomorfism.

Avem Im f ≈/Ker f, unde Ker f este un subspațiu vectorial al lui . Fie acum W un subspațiu vectorial al lui de dimensiune k (0≤k≤n).

Fie ,, … , ,, … , o bază a lui astfel încât ,…, constituie o bază pentru W.

Atunci o aplicație liniară f : → V are Ker f = W dacă și numai dacă ea aplică vectorii ,…, în zero, iar vectorii , ,…, într-o mulțime liniar independentă de vectori din V.

Deoarece f() poate fi oricare din cei y-1 vectori nenuli; f() poate fi oricare dintre cei y-q vectori care nu aparțin subspațiului generat de f(); f(e3) poate fi oricare din cei y-q2 vectori care nu aparțin subspațiului generat de f() și f(). Găsim astfel (y-1)(y-q)…(y-qn-k-1) aplicații liniare f : → V cu proprietatea că Ker f=W. Cum în există subspații vectoriale de dimensiune k și cum pentru k=n avem o singură aplicație liniară definită pe cu valori în V și anume aplicația nulă, rezultă imediat egalitatea iv) când y este dimensiunea unui spațiu vectorial arbitrar.

Cum această egalitate are loc pentru o infinitate de valori, atunci egalitatea IV) este valabilă pentru yR.

Remarcă. Se observă imediat că

= = .

Ne propunem acum să calculăm funcția Möbius a laticei L(V). Fie X,YL(V) astfel încât X Y.

Cum intervalul [X,Y]={Z L(V) | X Z Y} este izomorf cu laticea subspațiilor L(Y/X) aspațiului vectorial Y/X și folosind formulele de recurență rezultă ce (X,Y) deinde numai de

m = (Y/X)= Y – X.

Din aceste motive mai notăm (X,Y)=(m).

Teorema 3.10. Cu notațiile de mai sus avem că

(X,Y)=(–1)m∙q.

Demonstrație.

Din cele de mai sus ne putem reduce la cazul când X=(0) și Y=V, adică să srătăm că

(n)=(–1)nq.

Procedăm prin inducție după n.

Dacă n=0 afirmația este evidentă.

Presupunem afirmația adevărată pentru toate numerele naturale strict mai mici ca n. Din formulele de recurență avem egalitatea

=0

De unde obținem că :

(0,0)++ +…++ (0,V)=0

sau folosind coeficienții lui Gauss obținem:

1+ (1)+ (2)+…+ (n-1) + (n)=0.

Din ipoteza de inducție avem că (m)=(–1)mq oricare ar fi m<n. Deci

1+ (–1)1q0+ (–1)2q1+ (–1)3q3+ … + (–1)n-1+ (n)=0.

Din teorema 3.10 egalitatea iv) rezultă că (n) trebuie să fie egal cu .

§4. Algebra de incidență asociată unei mulțimi finite parțial ordonate

Fie (P,≤) o mulțime finită parțial ordonată și K un corp de caracteristică zero (de exemplu corpul Q al numerelor raționale). Definim

(P)={f : P2 → K | x>y f(x,y)=0}.

Când nu este nici o problemă de confuzie notăm mai simplu A(P)=(P). Mulțimea (P) devine K-spațiu vectorial unde pentru f,g (P) și r K avem operațiile :

(f+g)(x,y)=f(x,y)+g(x,y),

rf(x,y)=rf((x,y).

Definim convoluția f*g lui f,g (P) prin (f*g)(x,y)=în cazul x≤y și (f*g)(x,y)=0 dacă x>y.

Teorema 3.11. Mulțimea (P) cu operațiile de adunare, înmulțire cu scalari și convoluția este o algebră numită algebra de incidență asociată mulțimii (P,≤). Elementele din (P) se vor numi funcții de incidență.

Demonstrație.

Să verificăm mai întâi asocoativitatea operației de convoluție : dacă f,g,h (P) avem pentru

x≤y : (f*(g*h))(x,y)= == ===((f*g)*h)(x,y) și deci f*(g*h)=(f*g)*h.

Se observă imediat că funcția lui Kronecker

:P2 → K, (x,y)=aparține mulțimii (P) și este element neutru față de operația de convoluție.

Celelalte axiome se verifică imediat.

Corolar 3.12. Un element f (P) este inversabil dacă și numai dacă f(x,x)≠0 pentru orice x P.

Demonstrație.

Dacă f este inversabil, există g (P) astfel încât f*g=g*f=.

Atunci pentru orice x P avem 1=(f*g)(x,x)∙g(x,x) și deci f(x,x)≠0.

Invers, presupunem că f(x,x)≠0 pentru x P. Vom defini recursiv funcția f-1:

f-1(x,x)=f(x,x)-1 oricare ar fi x P, dacă x<y, punem f-1(x,y)=

= f(y,y)-1∙(), iar dacă x>y punem f-1(x,y)=0. Să dovedim că

f*f-1=f-1*f=.

Evident, presupunem că x≤y și vom proceda prin inducție după numărul m de elemente din intervalul [x,y]. Dacă m=1, atunci (f*f-1)(x,x)=f(x,x)∙f(x,x)-1=1.

Presupunem deci că m>1; avem în acest caz :

(f*f-1)(x,y)= =+ f(x,y)∙f-1(y,y)=

= f(y,y)-1+ f(x,y)∙f-1(y,y) =

= f(y,y)-1+ f(x,y)∙f-1(y,y) =

= – f(y,y)-1+f(x,y)∙f-1(y,y) =

= – f(y,y)-1+f(x,y)∙f-1(y,y) =

=– f(y,y)-1f(x,y)+f(x,y)∙f-1(y,y)=0.

Deci f*f-1=. Analog se arată și egalitatea f-1*f=.

Exemple de funcții de incidență.

i) Funcția lui Kronecker (sau funcția Delta)

(x,y)=

Am văzut că este elementul unitate în algebra (P).

ii) Funcția Zeta

(x,y)=

iii) Funcția Lambda

(x,y)=

iv) Funcția Lanț = – .

v) Funcția Acoperire K = – .

vi) Funcția Möbius = x-1.

Are sens să vorbim de funcția lui Möbius deoarece este un element inversabil în (P). Din demonstrația corolarului 3.6 funcția are proprietățile :

1) (x,x)=1; 2) dacă x<y, (x,y)= – = –; 3) dacă x>y, (x,y)=0 și astfel regăsim relațiile de recurență din teorema 3.2,

§5. Inversiunea lui Möbius. Aplicații.

Fie din nou (P,≤) o mulțime finită parțial ordonată și G un grup abelian. Fie f : P → G o aplicație oarecare.

Definim funcțiile :

g : P → G , g(x)=

h : P → G , h(x)= .

Am văzut că putem numerota mulțimea P astfel : P={,…,; cu condiția că < i<j }. Folosind funcția Zeta : P2 → Z, (x,y)= , atunci putem scrie

g(x) = sau g() = ,

iar i=1,2,…,n. Aceste egalități le putem scrie sub forma matriceală

.

Înmulțind această egalitate cu A-1=B obținem

=B

de unde rezultă că f()=sau renunțând la numerotarea lui A avem :

f(x)= =.

Un rezultat analog obținem pentru funcția h :

f(x)= .

Deci avem următorul rezultat.

Teorema 3.13. Fie f,g,h : P → G. Atunci au loc relațiile:

i) g(x)= f(x)=

ii) h(x)= f(x)= .

Aceste egalități se numesc inversiunile lui Möbius.

Aplicații.

I) Considerăm mulțimea P={0<1<2<…<n}.

Reamintim că funcția Möbius asociată mulțimii P este :

(i, j) =

Atunci pentru orice f,g,h : P → G avem relațiile :

g(m)= f(m)= g(m)–g(m+1)

h(m)= f(m)= g(m)–g(m–1).

II) Fie X o mulțime finită și P=P (X) cu relația de ordine incluziunea. Am văzut că funcția Möbius asociată lui P (X) este :

(A,B)=(–1)|B–A| pentru A B.

Deci pentru orice f,g,h : P (X) → G au loc relațiile :

g(A)= f(A)=

h(A)= f(A)= .

III) Fie ,…, submulțimi ale unei mulțimi finite A. Fie T={1,2,…,t}; dacă I T este o submulțime a lui T, vom nota f(I) numărul de elemente din A care se găsesc în mulțimile cu i I și nu se găsesc în celelalte.

Deci

f(I)=||.

Obținem astfel o funcție f : P (A) → Z.

Este clar că funcția g : P (A) → Z, unde g(I)=.

Aplicând exemplul precedent obținem că :

Pentru I=Ø obținem egalitatea

|A–|=|A| –+–…+(–1)t|…| (*)

Am ținut cont că =A când I=Ø, care ne implică egalitatea, numită principiul includerii – excluderii :

|| = – ± … (–1)t|…|.

Este binecunoscut că această ultimă egalitate se demonstrează ușor prin inducție după t.

Ținând cont de egalitatea (*) putem determina numărul de elmente din A care se găsesc în exact p mulțimi . Acest număr este egal cu

=|| = || = ∙||.

Deci am obținut următorul rezultat.

Teorema 3.14. Fie A o mulțime finită , ,…, submulțimi ale lui A și T={1,2,…,t}. Atunci numărul al elementelor din A care se găsesc în exact p submulțimi este

= ||.

Să aplicăm această egalitate la următoarea problemă : Fie grupul permutărilor de gradul n. Vom nota cu (n) numărul permutărilor care au p puncte fixe. Ne propunem să determinăm acest număr. Pentru aceasta vom nota cu ={ | (i)=i}, unde i = 1,2,…,n. Este evident că || = (n–| I |) ! unde I {1,2,…,n}.

Aplicând teorema 3.13 obținem :

(n) =

Dacă p=0, obținem numărul al tuturor permutărilor de gradul n care nu au nnici un punct fix.

Deci = n!

Să observăm că când n→.

IV) (Funcția lui Euler).

Fie n≥1 un număr natural. Vom nota cu (n) nuarul de numere naturale prime cu n i mai mici ca n; (n) se numește indicatorul lui Euler al nunărului n, iar funcția se numește funcția lui Euler.

Presupunem că n=, unde ,,…, sunt numere prime distincte și ≥1. Fie A={1,2,…,n} ={k A | | k } pentru i=1,2,…,t și T={1,…,t}. Este clară egalitatea :

|| =, unde I T.

Aplicând teorema 3.13 avem

(n)==n–=+…+(–1)t=n∙.

Se vede ușor că din ultima egalitate obținem

(n)=,

unde este funcția Möbius asociată mulțimii, ={d | d divide n} unde relația de ordine este divizibilitatea.

Dar această ultimă egalitate este echivalentă cu egalitatea n=, conform teoremei 3.12.

V) Polinomul cromatic asociat unei hărți(Problema celor patru culori).

Numim hartă împărțirea panului în regiuni (numite țări) prin arce. Două țări sunt vecine dacă au frontieră în comun un arc. Fie k culorile fixate. Se numește colorare proprie a hărții dacă oricare două țări vecine nu sunt colorate cu aceeași culoare (folosindu-se de cele k culori).

Fie o hartă. Ne propunem să determinăm numărul de colorări proprii ale acestei hărți folosindu-ne de cele k culori. Acest număr îl notăm (). Dacă k=4, problema celor 4 culori spune că orice hartă se poate colora propriu cu cele 4 culori, adică ()≠0 oricare ar fi hartă.

Acestă problemă a fost enunțată prima dată în anul 1850, de către De Morgan.

este o subhartă a lui , , dacă se obține din ștergând anumite frontiere.

Notăm ={| subhartă a lui }.

(,≤) este o mulțime parțial ordonată.

Dacă , considerăm ()=numărul de colorări proprii ale hărții , folosind cele k culori.

Dacă , definim ()=numărul tuturor colorărilor lui (nu neapărat proprii), este clar că ()=, unde C()=numărul de țări care aparțin hărții.

Avem =(), deci

f()=, g(E)= .

Dacă =, avem

f()=,

formulă care se numește polinomul cromatic asociat hărții.

VI) Numărul de polinoame ireductibile de gradul n (n≥1) peste un corp finit.

Fie K un corp finit având q elemente, adică |K|=q.

Vom nota cu mulțimea polinoamelor ireductibile, monice de gradul n din inelul K[X] (un polinom se zice monic dacă coeficientul termenului de grad maxim este 1) și cu =||. Ne propunem să determinăm acest număr. Pentru aceasta avem nevoie de o serie de rezultate preliminarii.

Fie p= char K; deci p≥2 și p este număr prim. Vom nota cu P subcorpul prim al lui K. Deci P≈și deci |P|=p.

Fie K E o extindere e lui K; Evident E este un K spațiu vectorial; vom nota cu [E:K] dimensiunea lui E considerat ca K spațiu vectorial. Dacă [E:K]=m<; atunci spunem că E este o extindere finită.

În acest caz, deoarece E≈Km, atunci |E|=qm. În particular, dacă [K:P]=n rezultă că |K|=pr adică q=pr.

Mulțimea K este egală cu mulțimea rădăcinilor polinomului Xq–X P[X].

Într-adevăr, fie K. Dacă =0, atunci 0 este evident o rădăcină a polinomului Xq–X.

Dacă ≠0, atunci K*=K\{0}. Cum K* este grup față de operația de înmulțire și |K*|=q–1, atunci conform teoremei lui Lagrange rezultă că q-1=1, de unde rezultă că q=, ceea ce ne arată că este o rădăcină a polinomului Xq–X.

c) Fie f= +X+…+Xn-1+Xn un polinom ireductibil monic dininelul K[X]. Cum este o mulțime finită este bine cunoscut faptul că există o extindere K L care conține rădăcinile polinoamelor din mulțimea . Fie L o rădăcină a lui f. Vom nota cu

E=K[]={++…+n-1 | , ,…, K}.

Deoarece n+n-1+…+=0, atunci este ușor de văzut că E este subinel al corpului L.

Pe de altă parte, elementele 1,,…,n-1 sunt liniar independente peste K.

Într-adevăr, dacă avem o egalitate de forma

+ + … + n-1=0, K.

Atunci notând cu g(X) = +X + … + Xn-1 K[X] avem că g()=0.

Dacă polinomul g(X) nu este zero, atunci rezultă că f ți g sunt prime între ele și deci există polinoamele , K[X] astfel încât 1= f+g de unde înlocuind pe X cu obținem 1=0, contradicție.

Deci g(X)=0 și prin urmare = = … = =0. Prin urmare E=K[] este un K-spațiu vectorial având o bază egală cu {1,,…,n-1}.

În particular, rezultă că E este inel finit. Cum E este un subinel al unui corp rezultă că E este un corp. Deci E este o extindere finită cu [E:K]=n.

d) Cu notațiile de la punctul c) E conține toate rădăcinile polinoamelor care aparțin mulțimii .

Într-adevăr, cum [E:K]=n, atunci E≈Kn ca un K-spațiu vectorial și deci |E|=qn. Conform punctului b), E este egală cu mulțimea rădăcinilor polinomului–X. Cum f este polinom reductibil, iar f()=0, atunci f dinide polinomul –X și deci toate rădăcinile lui f sunt conținute în mulțimea rădăcinilor polinomului –X și deci E conține toate rădăcinile lui f.

Dacă g este un alt polinom, atunci un raționament similar celui dinainte, ne arată că rădăcinile lui g se găsesc în mulțimea E.

În plus, dacă g≠f, atunci mulțimea rădăcinilor lui f este disjunctă de mulțimea rădăcinilor lui g, deoarece dacă f și g au o rădăcină comună, cum f și g sunt ireductibile, rezultă că f|g și g|f adică f=g.

e) Fie E un element oarecare. Atunci există un m|n și un h astfel încât este o rădăcină a polinomului h.

Într-adevăr, cum [E:K]<, atunci sistemul de elemente 1,,2,…,k,… este liniar dependent peste corpul K, înseamnă că există elementele ,,…, K nu toate nule astfel încât + +…+s=0. Dacă notăm cu g(X) polinomul

g(X)=+X+…+Xs,

atunci

g()=0.

Vom nota cu h(X) un polinom monic nenul de gradul cel mai mic astfel încât h()=0.

Este ușor de văzut că h(X) este ireductibil. Să notăm cu m=grad h.

Cum h()=0, atunci corpul F=K[] este o extindere finită a lui K astfel încât [F:K]=m.

Pe de altă parte, avem K F E.

Cum |E| este o putere a lui |F| rezultă, în particular, că m|n.

Din afirmația e) rezultă că :

E={rădăcinile polinomului h}).

Cum mulțimile care apar în această reuniune sunt distincte două câte două și cum un polinom h are m rădăcini, atunci obținem egalitatea

|E|=sau qn=.

Folosind formula de inversiune a lui Möbius obținem că

=

care ne dă numărul polinoamelor monice ireductibile de gradul n peste corpul finit K având q elemente.

De exemplu, dacă K= avem q=2 și avem =2;

=; =;=;=; =.

Dacă K= avem q=3 și deci =3;

=; =;=;=; =.

Bibliografie

[1] Nathan Jacobson – Basic Algebra, vol I, Yale University, San Francisco, 1985;

[2] Niță C., Năstăsescu C., Vraciu C. – Bazele algebrei, vol I , Editura Academiei, 1986;

[3] G.Birkoff – Lattice theory, American Mathematical Society, Rhode Island, 1967;

[4] Rudeanu S. – Curs de bazele informaticii, latici și algebre booleene, Universitatea din Bucuresti ;

[5] T.Spircu – Four Function Theorem, Univ. de Medicină și Farmacie, 2005;

[6] P.C. Fishburn – Correlations in p.o. sets. Discrete Appl. Math. 39(1992),173-191;

[7] B. Bollobás – Combinatorics. Cambrigde Univ. Press, Cambridge UK, 1986;

[8] Purdea I. – Tratat de algebră modernă , vol.I, Editura Academiei, Bucuresti,1982;

[9] Ion D. Ion, Radu N. – Algebra, Editura Didactică și Pedagogică, București, 1991;

[10] P.C. Fishburn – The Ahlswede-Daykin theorem. In:I. Althöfer, N. Cai, G. Dueck, L. Khachatrian, M.S. Pinsker, A. Sárközi, I. Wegener, Z. Zhang (Editors), Numbers, Information and Comlexity. Kluwer Acad. Publ., Boston-Dordrecht-London, 2000.