Rozdělení sady - Partition of a set

Sada známek rozdělených do svazků: ​​Žádné razítko není ve dvou svazcích, žádný svazek není prázdný a každé razítko je ve svazku.

The 52 oddíly sady s 5 prvky. Barevná oblast označuje podmnožinu X, tvořící člen uzavírajícího oddílu. Nezbarvené tečky označují podmnožiny s jedním prvkem. První zobrazený oddíl obsahuje pět jednoprvkových podmnožin; poslední oddíl obsahuje jednu podmnožinu s pěti prvky.

Tradiční japonské symboly pro 54 kapitol Příběh Genji jsou založeny na 52 způsobech rozdělení pěti prvků (dva červené symboly představují stejný oddíl a zelený symbol je přidán pro dosažení 54).^[1]

v matematika, a oddíl sady je seskupení jeho prvků do neprázdný podmnožiny, takovým způsobem, že každý prvek je zahrnut právě v jedné podmnožině.

Každý vztah ekvivalence na soubor definuje oddíl této sady a každý oddíl definuje relaci ekvivalence. Soubor vybavený relací ekvivalence nebo přepážkou se někdy nazývá a setoid, obvykle v teorie typů a teorie důkazů.

Definice

Oddíl sady X je sada neprázdných podmnožin X tak, že každý prvek X v X je přesně v jedné z těchto podskupin^[2] (tj., X je disjunktní unie podmnožin).

Ekvivalentně, a rodina sad P je oddíl X pouze tehdy, pokud platí všechny následující podmínky:^[3]

• Rodina P neobsahuje prázdná sada (to je ${ displaystyle emptyset notin P}$).
• The svaz sad P je rovný X (to je ${ displaystyle textstyle bigcup _ {A v P} A = X}$). Sady v P jsou prý Pokrýt X.
• The průsečík ze dvou odlišných sad P je prázdný (tj ${ displaystyle ( forall A, B in P) ; A neq B implikuje A cap B = emptyset}$). Prvky P se říká, že jsou párově disjunktní.

Sady v P se nazývají bloky, části nebo buňky oddílu.^[4]

The hodnost z P je |X| − |P|, pokud X je konečný.

Příklady

• Prázdná sada ${ displaystyle emptyset}$ má přesně jeden oddíl, jmenovitě ${ displaystyle emptyset}$. (Poznámka: toto je oddíl, nikoli člen oddílu.)
• Pro jakoukoli neprázdnou sadu X, P = {X} je oddíl X, nazvaný triviální oddíl.
  • Obzvláště každý singletonová sada {X} má přesně jeden oddíl, konkrétně {{X} }.
• Pro všechny neprázdné správná podmnožina A sady U, sada A společně s jeho doplněk tvoří oddíl U, jmenovitě {A, U \ A}.
• Sada {1, 2, 3} má těchto pět oddílů (jeden oddíl na položku):
  • {{1}, {2}, {3}}, někdy psáno 1 | 2 | 3.
  • {{1, 2}, {3}} nebo 12 | 3.
  • {{1, 3}, {2}} nebo 13 | 2.
  • {{1}, {2, 3}} nebo 1 | 23.
  • {{1, 2, 3}} nebo 123 (v kontextech, kde nedojde k záměně s číslem).
• Toto nejsou oddíly {1, 2, 3}:
  • {{}, {1, 3}, {2}} není oddíl (jakékoli sady), protože jedním z jeho prvků je prázdná sada.
  • {{1, 2}, {2, 3}} není oddíl (jakékoli sady), protože prvek 2 je obsažen ve více než jednom bloku.
  • {{1}, {2}} není oddílem {1, 2, 3}, protože žádný z jeho bloků neobsahuje 3; jedná se však o oddíl {1, 2}.

Rozdělení a ekvivalenční vztahy

Pro všechny vztah ekvivalence na setu X, sada jeho třídy ekvivalence je oddíl X. Naopak z libovolného oddílu P z X, můžeme definovat vztah ekvivalence na X nastavením X ~ y přesně kdy X a y jsou ve stejné části v P. Pojmy vztah ekvivalence a rozdělení jsou tedy v zásadě rovnocenné.^[5]

The axiom volby záruky za jakékoli rozdělení sady X existence podmnožiny X obsahující přesně jeden prvek z každé části oddílu. To znamená, že vzhledem k relaci ekvivalence na množině lze vybrat kanonický reprezentativní prvek z každé třídy ekvivalence.

Upřesnění oddílů

Oddíly 4-sady seřazené podle upřesnění

Oddíl α sady X je upřesnění oddílu ρ z X—A my to říkáme α je jemnější než ρ a to ρ je hrubší než α—Pokud každý prvek α je podmnožina nějakého prvku ρ. Neformálně to znamená α je další fragmentace ρ. V tom případě je psáno, že α ≤ ρ.

Tento jemnější než vztah na množině oddílů X je částečná objednávka (proto je vhodný zápis „≤“). Každá sada prvků má a nejmenší horní mez a a největší dolní mez, takže tvoří a mříž a konkrétněji (pro oddíly konečné množiny) je to geometrická mříž.^[6] The přepážka čtyřprvkové sady má 15 prvků a je zobrazena v Hasseův diagram nalevo.

Založeno na kryptomorfismus mezi geometrickými mřížemi a matroidy, tato mřížka oddílů konečné sady odpovídá matroidu, ve kterém základní sada matroidu sestává z atomy mřížky, jmenovitě přepážek s ${ displaystyle n-2}$ singletonové sady a jedna dvouprvková sada. Tyto atomové oddíly korespondují jedna k jedné s okraji a kompletní graf. The uzavření matroidu sady atomových oddílů je nejlepší společné hrubnutí všech; z teoreticko-grafického hlediska jde o rozdělení vrcholy celého grafu do připojené komponenty podgrafu tvořeného danou sadou hran. Tímto způsobem mřížka příček odpovídá mřížce bytů grafický matroid celého grafu.

Další příklad ilustruje upřesnění oddílů z hlediska vztahů ekvivalence. Li D je sada karet ve standardním balíčku 52 karet, stejná barva jako vztah na D - které lze označit ~_C - má dvě třídy ekvivalence: sady {červené karty} a {černé karty}. Dvoudílný oddíl odpovídající ~_C má vylepšení, které poskytuje stejný oblek jako vztah ~_S, který má čtyři třídy ekvivalence {piky}, {diamanty}, {srdce} a {kluby}.

Noncrossing oddíly

Oddíl sady N = {1, 2, ..., n} s odpovídajícím vztahem ekvivalence ~ is nekřížení pokud má následující vlastnost: Pokud čtyři prvky A, b, C a d z N mít A < b < C < d uspokojit A ~ C a b ~ d, pak A ~ b ~ C ~ d. Název pochází z následující ekvivalentní definice: Představte si prvky 1, 2, ..., n z N nakreslen jako n vrcholy pravidelné n-gon (v pořadí proti směru hodinových ručiček). Oddíl lze poté vizualizovat nakreslením každého bloku jako mnohoúhelníku (jehož vrcholy jsou prvky bloku). Přepážka se poté neprotíná, a to pouze tehdy, pokud se tyto polygony neprotínají.

Mřížka nekřížících se oddílů konečné množiny nedávno získala na důležitosti díky své roli v bezplatná pravděpodobnost teorie. Ty tvoří podmnožinu mřížky všech oddílů, ale nikoli sublattice, protože operace spojení dvou mřížek nesouhlasí.

Počítání oddílů

Celkový počet oddílů souboru n-prvková sada je Bell číslo B_n. Prvních několik čísel Bell je B₀ = 1,B₁ = 1, B₂ = 2, B₃ = 5, B₄ = 15, B₅ = 52, a B₆ = 203 (sekvence A000110 v OEIS ). Čísla zvonků uspokojí rekurze

${ displaystyle B_ {n + 1} = součet _ {k = 0} ^ {n} {n zvolit k} B_ {k}}$

a mít exponenciální generující funkce

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

Stavba Bell trojúhelník

Čísla Bell lze také vypočítat pomocí Bell trojúhelník ve kterém je první hodnota v každém řádku zkopírována z konce předchozího řádku a následující hodnoty jsou vypočítány přidáním dvou čísel, čísla vlevo a čísla vlevo nahoře od pozice. Čísla Bell se opakují po obou stranách tohoto trojúhelníku. Čísla v trojúhelníku počítají oddíly, ve kterých je daný prvek největší jedináček.

Počet oddílů souboru n-prvek nastaven přesně k neprázdné části jsou Stirlingovo číslo druhého druhu S(n, k).

Počet nepřekračujících se oddílů n-prvková sada je Katalánské číslo C_n, dána

${ displaystyle C_ {n} = {1 nad n + 1} {2n vyberte n}.}$

Viz také

• Přesné krytí
• Blokový design
• Shluková analýza
• Slabé objednávání (objednaná množinová příčka)
• Vztah ekvivalence
• Vztah částečné ekvivalence
• Upřesnění oddílů
• Seznam témat oddílu
• Laminování (topologie)
• Schémata rýmů podle nastaveného oddílu

Poznámky

Reference

• Brualdi, Richard A. (2004). Úvodní kombinatorika (4. vydání). Pearson Prentice Hall. ISBN  0-13-100119-1.CS1 maint: ref = harv (odkaz)
• Schechter, Eric (1997). Příručka pro analýzu a její základy. Akademický tisk. ISBN  0-12-622760-8.CS1 maint: ref = harv (odkaz)