Rozdělení sady - Partition of a set

Sada razítek 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.

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

Tradiční japonské symboly pro 54 kapitol Příběhu 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).

V matematice je rozdělení množiny seskupením jejích prvků do neprázdných podmnožin takovým způsobem, že každý prvek je obsažen přesně v jedné podmnožině.

Každý vztah ekvivalence na sadě definuje oddíl této sady a každý oddíl definuje vztah ekvivalence. Sada vybavená vztahem ekvivalence nebo přepážkou se někdy nazývá setoid , typicky v teorii typů a teorii důkazů .

Definice a zápis

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 podmnožin (tj. X je disjunktní spojení podmnožin).

Ekvivalentně je rodina sad P oddílem X právě tehdy, pokud platí všechny následující podmínky:

• Rodina P neobsahuje prázdnou množinu (to znamená ).${\ Displaystyle \ emptyset \ notin P}$
• Unie ze souborů v P je rovna X (tj ). Soupravy v P se říká, výfuku nebo krycí X . Viz také souhrnně vyčerpávající události a obálka (topologie) .${\ Displaystyle \ textstyle \ bigcup _ {A \ in P} A = X}$
• Průnik jakýchkoliv dvou rozdílných sad v P je prázdný (tj ). O prvcích P se říká, že jsou párově disjunktní .${\ Displaystyle (\ forall A, B \ in P) \; A \ neq B \ implikuje A \ cap B = \ emptyset}$

Sady v P se nazývají bloky , části nebo buňky oddílu. Pokud pak představují buňku obsahující na By . To znamená, že je notace pro buňku v P, která obsahuje a . ${\ displaystyle a \ in X}$${\ displaystyle [a]}$${\ displaystyle [a]}$

Každý oddíl, P , může být identifikován vztahem ekvivalence na X , a to vztahem takovým, že pro jakýkoli máme právě tehdy a jen tehdy (ekvivalentně, pokud a pouze pokud ). Zápis evokuje myšlenku, že vztah ekvivalence může být vytvořen z oddílu. Naopak každý vztah ekvivalence může být identifikován s oddílem. Proto se někdy neformálně říká, že „vztah ekvivalence je stejný jako oddíl“. Pokud P je oddíl identifikovaný s daným vztahem ekvivalence , pak někteří autoři píší . Tento zápis naznačuje myšlenku, že oddíl je množina X rozdělena do buněk. Zápis také evokuje myšlenku, že z vztahu ekvivalence lze sestrojit oddíl. ${\ displaystyle \ sim _ {P}}$${\ displaystyle a, b \ v X}$${\ displaystyle a \ sim _ {P} b}$${\ Displaystyle a \ in [b]}$${\ Displaystyle b \ v [a]}$${\ displaystyle \ sim _ {P}}$${\ displaystyle \ sim}$${\ displaystyle P = X/\ sim}$

Hodnost of P je | X | - | P | Pokud X je konečný .

Příklady

• Prázdná sada má přesně jeden oddíl, a to . (Poznámka: toto je oddíl, nikoli člen oddílu.)${\ displaystyle \ emptyset}$${\ displaystyle \ emptyset}$
• Pro každou neprázdnou množinu X je P = { X } oddíl X , nazývaný triviální oddíl .
  • Zejména každá sada singletonů { x } má přesně jeden oddíl, konkrétně {{ x }}.
• Pro jakoukoli neprázdnou správnou podmnožinu A množiny U tvoří množina A společně s jejím doplňkem oddíl U , konkrétně { 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 1 2 | 3.
  • {{1, 3}, {2}} nebo 1 3 | 2.
  • {{1}, {2, 3}} nebo 1 | 2 3.
  • {{1, 2, 3}} nebo 123 (v kontextech, kde nedojde k záměně s číslem).
• Následující oddíly nejsou oddíly {1, 2, 3}:
  • {{}, {1, 3}, {2}} není oddíl (žádné sady), protože jedním z jeho prvků je prázdná sada .
  • {{1, 2}, {2, 3}} není oddíl (žádné 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; je to však oddíl {1, 2}.

Příčky a ekvivalenční vztahy

Pro jakékoliv ekvivalence vzhledem ke stanovenému X , soubor svých tříd ekvivalence je rozdělení X . Naopak, z libovolného oddílu P z X , můžeme definovat vztah rovnocennosti na X nastavením x ~ y právě tehdy, když x a y jsou ve stejné části v P . Pojmy ekvivalenčního vztahu a rozdělení jsou tedy v zásadě ekvivalentní.

Axiom výběru záruk pro jakýkoli Rozklad množiny X existence podmnožiny X , který obsahuje přesně jeden prvek z každé části oddílu. To znamená, že vzhledem k vztahu ekvivalence na množině lze vybrat kanonický reprezentativní prvek z každé třídy ekvivalence.

Upřesnění oddílů

Přepážky seřazené podle upřesnění

Oddíl α z množiny X je zjemnění z oddílů p o X -a my říkáme, že α je jemnější než p a ρ je hrubší než alfa -pokud každý prvek alfa je podmnožina nějakého prvku p . Neformálně to znamená, že α je další fragmentací ρ . V takovém případě je psáno, že α ≤ ρ .

Tento vztah jemnější než na sadě oddílů X je dílčí pořadí (vhodný je tedy zápis „≤“). Každá sada prvků má nejmenší horní hranici a největší dolní hranici , takže tvoří mřížku , a konkrétněji (pro oddíly konečné množiny) je to geometrická mřížka . Oddíl mřížka z 4-prvek nastaven má 15 prvků a je znázorněna v diagramu Hasse vlevo.

Na základě cryptomorphism mezi geometrickými mřížek a matroidy Tento mřížka příček z konečného souboru odpovídá matroid, ve kterém je základní sada na matroid se skládá z atomů v mřížce, a to, že příčky se ojedinělých a jedno dvouprvková soubor. Tyto atomové oddíly odpovídají jeden na jednoho s okraji kompletního grafu . Matroid uzávěr ze sady atomových oddílů je nejlepší společný zhrubnutí z nich; v graficko-teoretických termínech je to rozdělení vrcholů kompletního grafu na spojené složky podgrafu tvořené danou sadou hran. Tímto způsobem mřížka příček odpovídá mřížce ploch grafického matroidu kompletního grafu. ${\ displaystyle n-2}$

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

Nekřížené oddíly

Oddíl množiny N = {1, 2, ..., n } s odpovídajícím vztahem ekvivalence ~ není křížový, pokud má následující vlastnost: Pokud čtyři prvky a , b , c a d z N mají 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 vrcholů pravidelného n -gonu (v pořadí proti směru hodinových ručiček). Oddíl lze poté zobrazit nakreslením každého bloku jako mnohoúhelníku (jehož vrcholy jsou prvky bloku). Oddíl je pak nekřížený právě tehdy, pokud se tyto polygony neprotínají.

Mřížka nekřížících se oddílů konečné sady v poslední době nabyla na důležitosti kvůli své roli v teorii volné pravděpodobnosti . Tito tvoří podmnožinu mřížky všech oddílů, ale ne sublattic, protože operace spojení obou mřížek nesouhlasí.

Počítání oddílů

Celkový počet oddílů sady n -prvků je Bell číslo B _n . Prvních několik Bellových čísel je B ₀ = 1, B ₁ = 1, B ₂ = 2, B ₃ = 5, B ₄ = 15, B ₅ = 52 a B ₆ = 203 (sekvence A000110 v OEIS ). Čísla zvonů uspokojují rekurzi

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

a mají funkci generování exponenciálů

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

Konstrukce Bellova trojúhelníku

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

Počet oddílů n -prvku nastaveného na přesně k neprázdných částí je Stirlingovo číslo druhého druhu S ( n , k ).

Počet nekřížících oddílů sady n -prvků je katalánské číslo C _n , dané

${\ displaystyle C_ {n} = {1 \ over n+1} {2n \ choose n}.}$

Viz také

• Přesné krytí
• Blokový design
• Klastrová analýza
• Slabé uspořádání (seřazený nastavený oddíl)
• Částečný vztah ekvivalence
• Upřesnění oddílu
• Seznam témat oddílů
• Laminace (topologie)
• Rýmovat schémata podle nastaveného oddílu

Poznámky

Reference

• Brualdi, Richard A. (2004). Úvodní kombinatorika (4. vyd.). Sál Pearson Prentice. ISBN 0-13-100119-1.
• Schechter, Eric (1997). Příručka analýzy a jejích základů . Akademický tisk. ISBN 0-12-622760-8.