Rozbicie zbioru

Z Wikipedii, wolnej encyklopedii
(Przekierowano z Podział zbioru)
Skocz do: nawigacja, szukaj
Podział zbioru na sześć części.

Rozbicie zbioru (inaczej: podział zbioru, partycja zbioru) – dla niepustego zbioru A to taka rodzina \Pi niepustych podzbiorów tego zbioru, że każdy element zbioru A należy do dokładnie jednego podzbioru tej rodziny[1].

Liczba sposobów podziału skończonego zbioru  n-elementowego wyraża się  n-tą liczbą Bella  B_n.

Definicja formalna[edytuj | edytuj kod]

Rodzina \Pi = \{ A_t : t\in T \} podzbiorów zbioru A\neq\empty jest jego rozbiciem wtedy i tylko wtedy, gdy:

  1. \forall_{t\in T} A_t\neq\empty,
  2. A_i\neq A_j \Longrightarrow A_i\cap A_j = \empty,
  3. A = \bigcup_{t\in T} A_t[1].

Podzbiory A_t nazywane są klasami rozbicia[1].

Przykłady[edytuj | edytuj kod]

Istnieją dwa podziały zbioru \{1, 2\}, mianowicie rodzina złożona ze zbioru \{1, 2\} (podział jednoelementowy) oraz rodzina składająca się ze zbiorów \{1\}, \{2\} (podział dwuelementowy).

Trójelementowy zbiór \{a, b, c\} można podzielić na jeden z pięciu sposobów:

  • \bigl\{\{a, b, c\}\bigr\},
  • \bigl\{\{a\}, \{b, c\}\bigr\},
  • \bigl\{\{a, b\}, \{c\}\bigr\},
  • \bigl\{\{a, c\}, \{b\}\bigr\},
  • \bigl\{\{a\}, \{b\}, \{c\}\bigr\}.

Zbiory nieskończone[edytuj | edytuj kod]

Jeśli nieskończony zbiór Z ma \kappa elementów, to istnieją  2^\kappa podziałów zbioru Z. Innymy słowy, zbiór podziałów zbioru Z jest równoliczny ze zbiorem potęgowym zbioru Z.

Zobacz też[edytuj | edytuj kod]

Przypisy

  1. 1,0 1,1 1,2 Bolesław Gleichgewicht, Algebra, Oficyna Wydawnicza GiS, Wrocław 2004, ISBN 978-83-89020-35-2; s.270