Specii (matematică)

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare

În matematică, speciile sunt o noțiune care poate fi poziționată între logică și aritmetică.

  • Aspect aritmetic : specia extinde, la același nivel de înțelegere, noțiunile fundamentale de număr ordinal/cardinal, către alte tipuri de numere, cum ar fi numere ciclice, numere poligonale, numere partiționale, numere arborescente etc. Astfel de noțiuni se învață pe dinafară (en: by heart, fr: par coeur), în clasele primare.
  • Aspect logic : definițiile și identitățile combinatorice pot fi privite ca propoziții a căror valoare de adevăr nu este 0 sau 1 (fals sau adevărat, nici-unul sau unul-sau-mai-multe) dar a căror valoare arată exact numărul de realizări ( via coeficienții funcției generatoare exponențiale ) ale obiectului (structurii) descrise în propoziție.
  • Aspect combinatoric : În combinatorică, specia descrie o clasă de structuri combinatorice, care pot fi puse în corespondeță biunivocă printr-o bijecție având o proprietate de functorialitate, adică copiază nu numai cardinalitatea unei mulțimi, dar și structura combinatorică asociată.
  • Aspect informatic : În informatică, speciile se manifestă ca suporturi (containere) pentru diferite tipuri abstracte de date, cum ar fi liste, arbori, etc.
  • Aspect geometric : Noțiuni elementare cum ar fi linia și transformările ei, planul și transformările lui, linia proiectivă, etc. au (cel puțin în geometriile finite) descrieri în termeni de specii și operații cu specii.
  • Aspect algebric : Noțiuni fundamentale cum ar fi grupul sau corpul au descrieri în termeni de specii și operații cu specii. Specia poate fi privită ca o structură ce nu a fost coordonatizată încă; totuși anumite operații elementare rămân posibile și în absența reperelor și a coordonatelor.

Datorită adâncimii conceptului, este nevoie de un metalimbaj pentru a putea defini speciile și operațiile cu specii. De aceea expunerile despre specii conțin termeni din teoria categoriilor, diagrame, pasaje de text special marcate sau texte scrise în diverse limbaje de programare.

Istoric[modificare | modificare sursă]

Se spune că primul exemplu de calcul cu specii a fost dat la concursul de matematică nord-american Putnam, la o problemă legată de numărul de partiții.

Une partition est un ensemble d'ensembles non-vides.” ( O partiție este o mulțime de mulțimi nevide. )

În termeni de teoria speciilor, aceasta se scrie :

Part = Ens ( Ens+ )

Funcția generatoare exponențială asociată este :

part (x) = exp (exp (x) - 1)

Coeficienții funcției generatoare exponențiale part (x) sunt

1, 1, 2, 5, 15, 52, 203, 877, 4140,... (șirul A000110 în OEIS)

adică numărul de partiționari ale unei mulțimi de n elemente distincte.

Exemple[modificare | modificare sursă]

Exemple de specii concentrate pe cardinalitatea cinci[modificare | modificare sursă]

Sunt 5.4.3.1 moduri de a eticheta unul din grafurile descrise ; chiar dacă cele două grafuri sunt diferite, etichetarea lor este în esență aceeași
OOOOO este descrisă ca X.Ens2 (X.X)
X.X.X.X.X reprezintă un ”șir” de cinci sloturi cu poziții bine determinate (numărul ordinal cinci), în care pot fi puse obiecte distincte,
iar Ens5 reprezintă un sac în care pot fi puse cinci obiecte distincte, (numărul cardinal cinci) fără ca acestea să poată avea poziții precizate.

Exemplu de număr ciclic cinci[modificare | modificare sursă]

五行 sau Wu Xing : cele cinci transformări,
(foc) → 土 (pământ) → 金 (metal) → 水 (apă) → 木 (lemn) → 火 ( și din nou, foc)

Exemple de specii concentrate pe optsprezece, douăzeci și cinci și respectiv, cinci[modificare | modificare sursă]

Trei zaruri = Ens3 ( X.Ens5 )
Cub' = X. [ Cyc2 ( Lin12 ) + Cyc3 ( Lin8 ) + Cyc4 ( Lin6 ) ]
Planul lui Fano" = X.Grupul lui Klein

Exemplu de primitivă[modificare | modificare sursă]

Primitiva unui număr ciclic, în cazul în care există, este un corp finit
Fieldr' = Cycr-1
unde r este o putere a unui număr prim.

Specii moleculare[modificare | modificare sursă]

„Arbore (etichetat) cu două, trei sau 4 noduri” este o specie care nu este moleculară. Există 1 + 3 + 12 + 4 = 20 de moduri de a eticheta un arbore cu două, trei sau patru noduri
O specie moleculară este o specie care nu poate fi scrisă ca sumă de alte specii. O componentă moleculară a unei specii este în întregime descrisă de acțiunea lui SA restrânsă la o singură orbită, care este asociată în mod unic unui subgrup de permutări (subgrupul stabilizator al unei realizări). Însă din puzderia de grupuri de permutări numai o parte infimă deține o exprimare în termeni simpli de teoria speciilor și o interpretare combinatorică inteligibilă.
Numărul de realizări ale unei specii moleculare este n!/m, unde n este gradul grupului de permutări asociat, iar m este ordinul acestui grup. Astfel, spectrul speciilor moleculare este cuprins între Ens și Lin având un număr de realizări cuprins între 1 și n!.

Exemple și contra-exemple[modificare | modificare sursă]

  • Ens3 - cu trei elemente poate fi formată o singură mulțime ( această mulțime poate fi scrisă în șase moduri distincte : { a, b, c } = { b, a, c } =...= { c, a, b} ). Specia „mulțime” sau „număr cardinal” are o singură realizare, și nu este o sumă de alte specii.
  • Cyc3 - cu trei elemente pot fi formate două cicluri de lungime trei, ( a b c ) și ( a c b ). Fiecare din cicluri are câte trei scrieri echivalente ; spre exemplu, ( a b c ) = ( b c a ) = ( c b a ). Să notăm aceste cicluri C1(a, b, c) și C2(a, b, c). Se poate scrie :
C1( a, b, c ) = C2( b, a, c )
adică prin transpunerea a doi simboli, unul din cicluri se tranformă în celălalt. Dacă realizările unei specii sunt transformabile din una în alta prin astfel de operații, specia este moleculară.
  • Sunt două tipuri de arbori cu 4 noduri. Un lanț O-O-O-O are 12 realizări (există 12 moduri distincte de a eticheta/colora un lanț cu patru culori), în timp ce o stea are numai 4 realizări ( dată de alegerea unei culori din patru pentru centru ). Prin permutarea a două culori, o realizare de tip lanț este transportată tot într-un lanț, iar o stea merge tot într-o stea. În acest caz, specia arbore cu 4 noduri nu este moleculară, ci este suma a două specii moleculare.

Specii atomice[modificare | modificare sursă]

O specie care nu poate fi scrisă ca produs de alte două specii este numită atomică.

Exemple și contraexemple[modificare | modificare sursă]

  • Cilindrii, de forma Cyc(Lin), sunt specii atomice.
  • Grupurile combinatorice, sau specia grup, sunt date de către grupurile (finite) exact tranzitive.
  • Corpurile combinatorice sunt date de către grupurile (finite) exact dublu tranzitive.
  • Liniile proiective sunt date de către grupurile (finite) exact triplu tranzitive.
  • Cele cinci fețe ale unei prisme triunghiulare drepte împreună cu cele șase rotații sunt o specie atomică.
A B C d e
A C B e d
B A C e d
B C A d e
C A B d e
C B A e d

Cele șase linii ale tabelului de deasupra arată reetichetări echivalente ale prismei. Atunci numărul de reectichetări esențial distincte va fi de 5! / 6 = 20. Una dintre reetichetările esențial distincte ar putea fi, de pildă, A d B C e.

  • Speciile partiționale (produse de mulțimi) sunt moleculare dar nu și atomice.

Cele patru operații de bază[modificare | modificare sursă]

Notațiile pentru cele patru operații de bază au fost alese asfel ca forma ecuațiilor să permită extragerea directă a funcției generatoare exponențiale (f.g.e.). Cele patru operații combinatorice extind calculele cu funcții generatoare în sensul că mai multe specii distincte pot avea aceeași f.g.e.. Dacă singurele specii considerate ar fi de tip Ensn, (numere cardinale) informația despre oricare specie construită din acestea ar fi conținută exhaustiv în f.g.e..

Adunarea[modificare | modificare sursă]

O specie poate fi înțeleasă ca o multimulțime de specii moleculare.
Spre exemplu, multimulțimea {{ 2, 2, 2, 3, 5 }} capătă în teoria speciilor aspectul :
F = Ens2 + Ens2 + Ens2 + Ens3 + Ens5
În exemplul de mai jos, permutarea a două etichete A și B lasă pe loc două copii ale mulțimii formate din A și B, și comută între ele cele două realizări AB și BA - perechi formate din A și B.
permutările de etichete A B
A B
B A

acționează asupra

{ A, B }
{ A, B }
{ {A}, {B} }
{ {A}, {B} }
AB BA
BA AB
În total, specia Ens2 + Ens2 + Lin2 are 1+1+2 = 4 realizări.

Produsul[modificare | modificare sursă]

Produsul a două specii F × G este produsul a două multimulțimi, adică multimulțimea produselor de specii moleculare {{ F.G }} unde F este în F și G în G.
La rândul lui, produsul a două specii moleculare poate fi definit cu ajutorul grupurilor stabilizatoare asociate.
Spre exemplu, produsul Ens3.Ens2 va avea următorul grup de permutări asociat:
A B C
A C B
B A C
B C A
C A B
C B A

×

D E
E D

=

A B C D E
A B C E D
A C B D E
A C B E D
B A C D E
B A C E D
B C A D E
B C A E D
C A B D E
C A B E D
C B A D E
C B A E D
Exemplul de mai sus se referă la partiționarea unei mulțimi cu 5 elemente în două clase a câte 3, respectiv 2 elemente. Funcțiile generatoare exponențiale ale speciilor Ens3 .și Ens2 sunt
1.{x^3 \over 3!} și respectiv 1.{x^2 \over 2!}
Produsul funcțiilor generatoare exponențiale este
1.1.{x^3 \over 3!}.{x^2 \over 2!} = {5! \over 2!.3!} .{x^5 \over 5!} = 10.{x^5 \over 5!}
așadar există 10 moduri de a partiționa cinci obiecte în două clase a câte 3, respectiv 2 obiecte.
Produsul a două specii moleculare poate fi privit în mod natural ca o specie multisort, ceea ce este o reflectare a principiului multiplicativ :
F[ X ] . G[ X ] = F[ X ] . G[ Y ]    / X = Y

Derivarea[modificare | modificare sursă]

Triangular prism.svg

Prin „derivarea” unei specii se obține o altă specie.

Exemplu[modificare | modificare sursă]

Prismă triunghiulară ===== derivare ====> X.Cyc3 + Cyc2(X.X)
Să presupunem că cele cinci fețe ale unei prisme triunghulare dreapte trebuie etichetate cu cinci etichete diferite. După aplicarea unei prime etichete, pe un triunghi sau pe un pătrat, ceea ce rămâne de etichetat este specia derivată.
Astfel, în cazul în care prima etichetă a fost aplicată pe un triunghi, al doilea triunghi este unic determinat, în timp ce pentru cele trei pătrate rămase, libertatea de reetichetare (nedeterminarea) este descrisă de un ciclu de lungime 3, ceea ce se formulează ca X.Cyc3 .
În cazul în care prima etichetă a fost aplicată pe un pătrat, libertatea de reetichetare este descrisă de un cilindru solid Cyc2(X.X).
Funcția generatoare exponențială pentru specia derivată este :
 x \cdot 2.{x^3 \over 3!} +  1.{x^2 \over 2!} \circ ( x \cdot x ) = 
 {x^4 \over 3} + {x^4 \over 2}  = 20.{x^4 \over 4!}
Prin integrare se obține funcția generatoare a prismei de la care s-a pornit :
 20.{x^5 \over 5!}
În concluzie, există 20 de moduri de a colora cele cinci fețe ale unei prisme cu cinci culori diferite.
Calculul „clasic” presupune să se partiționeze 5 culori în 2 + 3 (sunt 10 variante) ; după aplicarea a două culori pe fețele triunghiulare, prisma capătă o orientare, ceea ce dă două moduri de a aplica cele trei culori rămase pe fețele pătrate : 10 × 2 = 20.

Cazul (F+G)'[modificare | modificare sursă]

Prin derivarea unei sume de specii moleculare se obține suma derivatelor.
(F+G)' = F'+G'

Derivarea unei specii moleculare[modificare | modificare sursă]

În cazul în care stabilizatorul are o singură orbită, stabilizatorul speciei derivate este Fix(a), stabilizatorul unei singur simbol.

În cazul mai multor orbite, prin derivarea unei specii moleculare se obține o sumă de specii moleculare, fiecare componentă corespunzând unei orbite a stabilizatorului. Deoarece o specie moleculară cu mai multe orbite este în mod natural o specie multi-sort, spre exemnplu Cub(F,M,V), componentele derivatei corespund sorturilor de etichete (trei, pentru un cub).

Prisma triunghiulară din exemplul de mai sus, având două triunghiuri T și trei pătrate P se derivează ca specie multi-sort astfel :

Prismă triunghiulară (T,P) ===== derivare ====> T.Cyc3(P) + Cyc2(T.P)

Astfel, derivata este suma derivatelor parțiale în raport cu fiecare sort.

Compunerea[modificare | modificare sursă]

Speciile pot fi exprimate ca sume (multimulțimi) de specii moleculare, așadar pentru exemplificarea compunerii trebuie considerate trei cazuri. F ,F1 , F2 , G , G1 și G2 sunt, în cele ce urmează, specii moleculare.

Cazul F(G)[modificare | modificare sursă]

În teoria grupurilor, operația corespunzătoare se numeste produs în coroană (en: wreath product).
Compunerea a două specii moleculare poate fi definită în felul următor. Spre exemplu (fără a pierde din generalitate) grupul de permutări asociat speciei Cyc3(Ens2) este :
1 2 3
2 3 1
3 1 2
°
a b
b a
=
a1 b1 a2 b2 a3 b3
b1 a1 b2 a2 b3 a3
a2 b2 a3 b3 a1 b1
b2 a2 b3 a3 b1 a1
a3 b3 a1 b1 a2 b2
b3 a3 b1 a1 b2 a2
Ca și în cazul produsului a două specii moleculare, specia obținută prin compunere este tot moleculară, însă cardinalitatea pentru care este definită ( gradul grupului de permutări asociat) nu mai este grad1 + grad2 ci grad1 × grad2.

Cazul (F1+F2)(G)[modificare | modificare sursă]

În acest caz, specia compusă este multimulțimea a două specii moleculare, F1(G) + F2(G)

Cazul F(G1+G2)[modificare | modificare sursă]

Exemplu : Specia Cyc3(Ens2 + Lin2), un ciclu ale cărui elemente pot fi mulțimi cu două elemente sau perechi de două elemente. Această specie are patru componente moleculare.
tip matematic tip de specie ordin GP # realizări
( { x, y } { z, t } { u, v } ) Cyc3(Ens2) 24 30
( { x, y } { z, t } uv ) Ens2.Ens2.Lin2 4 180
( { x, y } zt uv ) Ens2.Lin2.Lin2 2 360
( xy zt uv ) Cyc3(Lin2) 3 240
Cyc3(Ens2 + Lin2) 810
Scoțând din context o linie a tabelului, spre exemplu linia a doua (cea cu 180 de realizări), numărarea se poate face așa : sunt 6 variante pentru alegerea lui u, 5 variante pentru alegerea lui v, 3 variante pentru alegerea perechii lui x și încă două variante pentru stabilirea ordinii celor două mulțimi ; în total 6×5×3×2 = 180.
  • O altă specie, definită pentru aceleași cardinalități, poate avea însă o altă compoțiție moleculară. Spre exemplu, specia Lin3(Ens2 + Lin2) are opt componente moleculare.
  • Definiția formală a unei specii poate fi urmărită astfel pentru exemplul considerat :
(F \circ G)[A] = \sum_{\pi \in P[A]} (F[\pi] \times \Pi_{B \in \pi} G[B]).
Mulțimea suport A are șase etichete : a, b, c, d, e și f care pot fi partiționate corespunzător (2+2+2) în 15 moduri iar suma se face pentru 15 termeni. Pentru fiecare partiție există exact 2 cicluri care pot fi definite. Pentru fiecare parte B, există 3 realizări ale lui G, de pildă { a, b } , ab și ba. În total sunt deci 15×2×3×3×3 = 810 realizări. Una din realizări ar putea fi :
( { a, b } { c, d } { e, f } ). { { a, b }, { c, d }, ef }
Etichetele e și f nu pot fi permutate cu alte etichete, deci nici { e, f } cu alte părți. Singura libertate de reetichetare rămâne a ↔ b și c ↔ d, corespunătoare permutărilor XIIII și IIXII, care generează un grup cu 4 elemente.
  • Cele două semne  \times și \Pi \, trebuiesc înțelese mai degrabă ca un unic semn \times \Pi desemnând un „produs ghidat” de către specia F\,. Definiția formală a compunerii speciilor este posibilă datorită echivalenței între diferite scrieri ale unor obiecte matematice. Spre exemplu, se poate scrie :
( 1 2 3 )( 4 5 ) ≈ ( 1 2 3 )( 4 5 ) . { { 1, 2, 3 }, { 4, 5 } } ≈ ( 1 2 3 )( 4 5 ) . { 1, 2, 3 } . { 4, 5 }
deoarece, ca specie, cele trei mulțimi de mai sus sunt echivalente.
  • Apelând la specii multisort, F(G1+G2) = F(X+Y) / X=G1, Y=G2.
  • În general, F(X+Y)= F(X) + F'(X).Y + ... + X.F'(Y) + F(Y).

Specii Multisort[modificare | modificare sursă]

Ecuația combinatorică descrie ceea ce rămâne după etichetarea unui nod, adică a unui singur nod de tip X sau nod de tip Y.

Un exemplu de specie multisort poate fi un cub, care are 26 de elemente : 8 vîrfuri, 12 muchii și 6 fețe. Sunt 24 de rotații care transportă vârfuri în vârfuri, muchii în muchii și fețe în fețe. Avem așadar trei sorturi de obiecte permutate de un același grup abstract. Văzut ca grup de permutări, avem un grup de grad 26 = 8+12+6 și ordin 24, care însă nu permută ”tranzitiv” obiectele : spre exemplu, un vârf nu va fi transportat într-o muchie (sau într-o față).

Cub'(V, M, F) = V. Cyc3 ( V2.M4.F2 ) + M. Cyc2 ( V4.M5.F3 ) + F. Cyc4 ( V2.M3.F )

Această ecuație poate fi citită astfel :

Formulă Citire
Cub'(V, M, F) = Fixând un element al unui cub, acesta poate fi un vîrf
V caz în care vîrful opus este determinat
. iar libertatea de mișcare rămasă este descrisă de
Cyc3 ( un cilindru format din
V2.M4.F2 ) componentele rămase
+ sau poate fi o muchie
M caz în care muchia opusă este la rândul ei fixată
. iar libertatea de mișcare rămasă este descrisă de
Cyc2 ( un cilindru format din
V4.M5.F3 ) componentele rămase
+ sau poate fi o față
F caz în care fața opusă este la rândul ei fixată
. iar libertatea de mișcare rămasă este descrisă de
Cyc4 ( un cilindru format din
V2.M3.F ) componentele rămase.

Factorizând prin V = M = F (folosind un singur sort de etichete, în loc de trei) se obține ecuația cubului cum a fost descrisă într-unul din exemplele de mai sus.

Grupul stabilizator al unei specii multisort nu este tranzitiv ci are mai multe orbite - câte una pentru fiecare sort.

Particularizarea definiției functoriale[modificare | modificare sursă]

  • Restrângerea definiției ”telescopice” functoriale la endo-specii. Prin aceasta, bijecțiile devin permutări iar functorialitatea exprimă o colecție (pentru orice mulțime A ) de acțiuni a grupului simetric SA asupra mulțimii realizărilor F[A].
  • Restrângerea la o anumită cardinalitate. În această etapă speciile sunt încă sume de specii moleculare, spre exemplu F[A] + F[A] + G[A] .
  • Molecularizarea (restrângerea la o singură orbită a acțiunii) : o specie care nu se mai descompune în sumă de alte specii este unic asociată unei orbite a acțiunii grupului SA pe mulțimea realizărilor F[A]. Având o singură orbită (a acțiunii), specia este descrisă în mod unic de grupul stabilizator (grup de permutări, subgrup în SA). La acest nivel există, spre exemplu, solidele platonice sau specia Loto 6/49 = Ens6.Ens43.
  • Restrângerea la specii atomice, care nu pot fi exprimate ca produse. Spre exemplu, Ens2(X.X) , desenată ca O-O-O-O, este o specie atomică, are ca grup stabilizator grupul generat de pemutarea (1 4)(2 3), și nu poate fi exprimată ca produs de alte specii. La acest nivel există încă specii multisort, spre exemplu Ens2(X.X) poate fi văzută ca Ens2(X.Y), desenată ca O-o-o-O.
  • Restrângerea la specii nucleare, cum ar fi grupurile, corpurile, liniile proiective, spațiile vectoriale afine sau numerele (unul câte unul, nu toate deodată) poligonale / ciclice/ cardinale a căror stabilizator este un grup tranzitiv de permutări, având o singură orbită. Clasificarea grupurilor tranzitive de permutări este o conseciință a clasificării grupurilor simple finite, rezultat acceptat actualmente, însemnând un secol de matematică în peste 200 de articole și 10.000 de pagini.

Vezi și[modificare | modificare sursă]

Note[modificare | modificare sursă]

Pentru tabele :

  • Jaques Labelle, Quelques espèces sur les ensembles de petite cardinalité, Ann. Sci. Math. Québec 9 (1985), no. 1, 31-58.
  • Yves Chiricota, Classification des espèces moléculaires de degré 6 et 7, Ann. Sci. Math. Québec 17 (1993), no. 1, 11-37.
  • "On Transitive Permutation Groups" by J.H. Conway, A. Hulpke, and J. McKay, LMS J. Comput. Math. 1 (1998), 1-8.
  • Notațiile Maple ale grupurilor tranzitive de grad ≤ 15

Seminarii și cursuri[modificare | modificare sursă]

Bibliografie[modificare | modificare sursă]

  • Dumitriu, Anton (1977), History of logic, Tunbridge Wells, Eng.: Abacus Press 
  • André Joyal, „Une théorie combinatoire des séries formelles”, Advances in Mathematics 42:1-82 (1981).
  • François Bergeron, Gilbert Labelle, Pierre Leroux, Théorie des espèces et combinatoire des structures arborescentes, LaCIM, Montréal (1994). English version: Combinatorial Species and Tree-like Structures, Cambridge University Press (1998).

Legături externe[modificare | modificare sursă]