Partiție (teoria seturilor)

În matematică, o partiție a unui set X este o împărțire a lui X în subseturi, numite părți , clase sau blocuri ale partiției, care „acoperă” X fără suprapunere.

Mai formal, o partiție a lui X este o colecție P de subseturi de X astfel încât:

subseturile nu sunt goale;
unirea tuturor subseturilor este mulțimea X în sine ( P este o copertă a lui X );
având în vedere două subseturi (distincte) de X , acestea sunt disjuncte .

O partiție din două părți se numește o bipartiție , o partiție din trei părți; cu sens similar, uneori se folosesc termeni precum tetrapartition sau mai general k -partition.

Exemple

Pentru orice set X , partiția trivială P = {X} .
Pentru orice X , partiția formată din toate singletele elementelor lui X.
Dat fiind un subset A de X , partiția formată din A și complementul său în X.
În setul numerelor naturale , partiția formată din numere pare și numere impare.
În setul de numere întregi , partiția formată din restul claselor modulează orice număr n .

Partiții și relații de echivalență

Fiecărei partiții P a unei mulțimi X i se poate asocia, în mod natural, o relație de echivalență ρ pe același X : două elemente sunt în relație în funcție de ρ dacă și numai dacă aparțin aceluiași element al partiției P. Viceversa, fiecărei echivalențe este posibil să se asocieze în mod natural o partiție, cea constituită din clasele relative de echivalență .

Această relație este importantă , deoarece definește un unu-la-unu funcție între setul de partiții și a relațiilor de echivalență; în plus, „revenirea înapoi” revine la început, adică având în vedere o relație ρ și partiția R asociată cu ea, relația asociată cu partiția nu este altceva decât ρ.

Pentru aceste situații, se folosesc termeni precum echivalența canonică a unei partiții și partiția asociată canonic cu o echivalență.

Proiecția canonică

Având în vedere o partiție P , se poate construi o funcție surjectivă $\pi :X\to P$ ${\ displaystyle \ pi: X \ to P}$ $\ pi: X \ to P$ care se asociază cu fiecare element $x\in X$ ${\ displaystyle x \ în X}$ $x \ în X$ subsetul $\pi (x)\in P$ ${\ displaystyle \ pi (x) \ în P}$ $\ pi (x) \ în P$ astfel încât $x\in \pi (x)$ ${\ displaystyle x \ in \ pi (x)}$ $x \ in \ pi (x)$ . Această funcție se numește proiecție canonică .

Această funcție este utilizată, de exemplu, în construirea, pornind de la orice funcție , a unei funcții one-to-one. Data $f:X\to Y$ ${\ displaystyle f: X \ to Y}$ $f: X \ to Y$ , construim o partiție în X astfel încât două elemente ale aceluiași subset să aibă aceeași imagine conform f ; funcția definită de partiția din imaginea lui X va fi deci o funcție one-to-one. Acest proces se numește descompunerea unei aplicații .

De exemplu, funcția de parte întreagă definită pe set $\mathbb {R} ^{+}$ ${\ displaystyle \ mathbb {R} ^ {+}}$ $\ mathbb {R} ^ {+}$ a realelor non-negative are ca partiție canonică asociată partiția constând din intervale închise din stânga și deschise în dreapta $[n,n+1)$ ${\ displaystyle [n, n + 1)}$ ${\ displaystyle [n, n + 1)}$ pentru mai mulți n numere întregi non-negative; în funcție de echivalența asociată canonic cu această partiție, sau asociată canonic cu funcția de parte întreagă, sunt echivalente două reale pozitive care au aceeași parte întreagă. Apoi, restrângând gama funcției la setul de numere naturale, obținem o funcție one-to-one de la P la $\mathbb {N}$ ${\ displaystyle \ mathbb {N}}$ $\ mathbb {N}$ .

Alte domenii

O ordine parțială importantă este definită între partițiile unui set prin stabilirea unei partiții $LA$ ${\ displaystyle A}$ $LA$ este mai fin decât o secundă $B.$ ${\ displaystyle B}$ $B.$ dacă fiecare parte a $LA$ ${\ displaystyle A}$ $LA$ este conținută într-o singură (o) parte din B. Echipată cu acest aranjament, colecția de partiții ale unui set constituie o rețea numită rețea de partiții ale unui set , foarte importantă de exemplu în combinatorică și, de asemenea, în mecanica statistică .

Fiecărei partiții a unui set finit i se asociază, de asemenea, o partiție a întregului furnizat de cardinalitatea sa.

Noțiunea de partiție este, de asemenea, utilizată pentru calcularea integralei .

Numărul de partiții ale unui set finit

Numărul de partiții dintr-un set de $n$ ${\ displaystyle n}$ $n$ elemente este numărul Bell $B_{n}$ ${\ displaystyle B_ {n}}$ $B_ {n}$ . Primele numere ale lui Bell sunt: $B_{0}=1,B_{1}=1B_{2}=2,B_{3}=5,B_{4}=15,B_{5}=52,B_{6}=203$ ${\ displaystyle B_ {0} = 1, B_ {1} = 1B_ {2} = 2, B_ {3} = 5, B_ {4} = 15, B_ {5} = 52, B_ {6} = 203}$ ${\ displaystyle B_ {0} = 1, B_ {1} = 1B_ {2} = 2, B_ {3} = 5, B_ {4} = 15, B_ {5} = 52, B_ {6} = 203}$ ^[1] . Numerele clopotelor satisfac recursiunea:

B_{n+1}=\sum _{k=0}^{n}{n \choose k}B_{k}

{\ displaystyle B_ {n + 1} = \ sum _ {k = 0} ^ {n} {n \ alege k} B_ {k}}

{\ displaystyle B_ {n + 1} = \ sum _ {k = 0} ^ {n} {n \ alege k} B_ {k}}

și au o funcție de generare exponențială

\sum _{n=0}^{\infty }{\frac {B_{n}}{n!}}z^{n}=e^{e^{z}-1}.

{\ displaystyle \ sum _ {n = 0} ^ {\ infty} {\ frac {B_ {n}} {n!}} z ^ {n} = e ^ {e ^ {z} -1}.}

{\ displaystyle \ sum _ {n = 0} ^ {\ infty} {\ frac {B_ {n}} {n!}} z ^ {n} = e ^ {e ^ {z} -1}.}

Construcția triunghiului Bell

Numerele clopotelor pot fi calculate folosind triunghiul lui Bell, unde prima valoare din fiecare rând coincide cu ultima din rândul anterior, iar valorile ulterioare sunt calculate prin adăugarea a două numere: numărul din stânga și numărul din stânga sus al poziție luată în considerare. Numerele clopotelor sunt imprimate de-a lungul ambelor fețe ale acestui triunghi. În general numărul $A_{n,k}$ ${\ displaystyle A_ {n, k}}$ ${\ displaystyle A_ {n, k}}$ a rândului $n$ ${\ displaystyle n}$ $n$ și coloană $k$ ${\ displaystyle k}$ $k$ al triunghiului numără numărul de partiții ale unui set cu $n+1$ ${\ displaystyle n + 1}$ $n + 1$ elemente în care singletul este prezent $\{k+1\}$ ${\ displaystyle \ {k + 1 \}}$ ${\ displaystyle \ {k + 1 \}}$ și toate singletele din partiție conțin elemente mai mici decât $k+1$ ${\ displaystyle k + 1}$ $k + 1$ . De exemplu $A_{3,2}=3$ ${\ displaystyle A_ {3,2} = 3}$ ${\ displaystyle A_ {3,2} = 3}$ numără partițiile colecției $\{1,2,3,4\}$ ${\ displaystyle \ {1,2,3,4 \}}$ ${\ displaystyle \ {1,2,3,4 \}}$ care au singletul $\{3\}$ ${\ displaystyle \ {3 \}}$ ${\ displaystyle \ {3 \}}$ dar nu singletul $\{4\}$ ${\ displaystyle \ {4 \}}$ $\ {4 \}$ , care sunt:

{1}, {2, 4}, {3}

{1, 4}, {2}, {3}

{1, 2, 4}, {3}.

Numărul de partiții dintr-un set de $n$ ${\ displaystyle n}$ $n$ elemente exact $k$ ${\ displaystyle k}$ $k$ piesele ne-goale este al doilea număr Stirling $S(n,k).$ ${\ displaystyle S (n, k).}$ ${\ displaystyle S (n, k).}$