Rozbicie zbioru

Rozbicie zbioru

Rozbicie, podział lub partycja zbioru to rodzina podzbiorów $\backslash \{A\_t\backslash colon\; t\; \backslash in\; T\backslash \}$, która spełnia trzy podstawowe warunki:

• Niepustość: $\backslash forall\_\{t\; \backslash in\; T\}\; A\_t\; \backslash neq\; \backslash varnothing;$
• Paralelność: $A\_i\; \backslash neq\; A\_j\; \backslash implies\; A\_i\; \backslash cap\; A\_j\; =\; \backslash varnothing;$
• Sumowanie: $A\; =\; \backslash bigcup\_\{t\; \backslash in\; T\}\; A\_t.$

Podzbiory $A\_t$ są nazywane klasami rozbicia.

Liczba sposobów podziału zbioru o $n$ elementach jest wyrażana przez $n$-tą liczbę Bella, $B\_n.$ Dla zbioru z $\backslash kappa$ elementami istnieje $2^\backslash kappa$ możliwych podziałów, co oznacza, że zbiór podziałów $Z$ jest równoliczny ze zbiorem potęgowym $\backslash mathcal\; P(Z).$

Przykłady

Przykłady podziałów zbiorów:

• Dla zbioru pustego jedynym podzbiorem jest zbiór pusty, więc tylko pusta rodzina zbiorów może być jego rozbiciem.
• Podział zbioru jednoelementowego $\backslash \{x\backslash \}$ to sam zbiór $\backslash \{x\backslash \}$.
• Dla zbioru $\backslash \{1,\; 2\backslash \}$ istnieją dwa podziały:
  • Rodzina $\backslash \{\backslash \{1,\; 2\backslash \}\backslash \}$ (podział jednoelementowy).
  • Rodzina $\backslash \{\backslash \{1\backslash \},\; \backslash \{2\backslash \}\backslash \}$ (podział dwuelementowy).
• Trójelementowy zbiór $\backslash \{a,\; b,\; c\backslash \}$ można podzielić na pięć sposobów:
  • $\backslash big\backslash \{\backslash \{a,\; b,\; c\backslash \}\backslash big\backslash \},$
  • $\backslash big\backslash \{\backslash \{a\backslash \},\; \backslash \{b,\; c\backslash \}\backslash big\backslash \},$
  • $\backslash big\backslash \{\backslash \{a,\; b\backslash \},\; \backslash \{c\backslash \}\backslash big\backslash \},$
  • $\backslash big\backslash \{\backslash \{a,\; c\backslash \},\; \backslash \{b\backslash \}\backslash big\backslash \},$
  • $\backslash big\backslash \{\backslash \{a\backslash \},\; \backslash \{b\backslash \},\; \backslash \{c\backslash \}\backslash big\backslash \}.$