Rozklad na třídy

Doc. Dr. Vladimír Homola, Ph.D.

Rozklad na třídy

Definice: Nechť je dána neprázdná množina P a neprázdný systém T = { A₁, A₂, ... , A_n }, kde pro každé i je A_iÍ P (T je tedy systémem podmnožin množiny P). Tento systém T nazýváme rozkladem množiny P na třídy, jestliže T je disjunktním systémem a ČT = P. Každá A_i ÎT se nazývá třída v T.

T je tedy rozkladem P na třídy, jestliže průnik libovolných dvou tříd je prázdný a jejich sjednocením je celá P.

Jak bylo shora uvedeno, každé množině přísluší určující pravidlo, podle kterého byla množina vytvořena. Rozklad na třídy T je systémem podmnožin, je tedy sám množinou, existuje tedy i pro něj určující pravidlo. Velmi často mívá toto určující pravidlo matematickou podobu.

Příklad: Barvy {červená, modrá, zelená, žlutá, jiná} rozkládají množinu všech jednobarevných aut na třídy. Tento rozklad B je tvořen pěti třídami (podmnožina červených aut, podmnožina modrých aut, ...). Sjednocení všech těchto tříd je celá množina všech jednobarevných aut, a každé dvě třídy jsou disjunktní (protože jde o jednobarevná auta, není žádné auto např. červené a zelené současně).

Věta: Každý rozklad množiny P na třídy definuje na P relaci ekvivalence. Každá ekvivalence na P definuje rozklad P na třídy.

Důkaz:

A. Mějme rozklad T množiny P na třídy. Definujme relaci » na P takto: a»b ş $ i: A_i ÎT Ů a ÎA_i Ů b ÎA_i (a»b, právě když “patří do stejné třídy”). Relace » je ekvivalence na P: je reflexivní (každé aÎP patří právě do jedné třídy a je tedy a» a), symetrická (je-li a»b, pak a i b patří do stejné třídy, je tedy současně i b»a) a tranzitivní (je-li a»b - a i b patří do stejné třídy - a současně b»c - b i c patří do stejné třídy - pak tedy evidentně a i c patří do téže třídy a je tedy a»c). Relace » je tedy ekvivalence.

B. Nechť naopak je na P definována relace ekvivalence «.

Definujme systém T podmnožin A_iÍP takto: je-li aÎP, bÎP, a«b, pak existuje i tak, že aÎA_iÍP, bÎA_i Í (každá A_i je množina všech prvků z P, které jsou spolu ekvivalentní).

Tento systém je především disjunktní. Mějme totiž dvě různé podmnožiny A_i a A_k a předpokládejme, že nejsou disjunktní (existuje tedy alespoň jeden prvek zÎP takový, že zÎA_i Ů zÎA_k). Protože A_i a A_k jsou podle předpokladu různé, existuje v A_i jeden prvek aÎA_i takový, že aĎA_k; dále existuje v A_k jeden prvek bÎA_k takový, že bĎA_i.

Protože aÎA_i a současně zÎA_i, je a«z. Protože bÎA_k a současně zÎA_k, je b«z. Protože « je ekvivalence a je tedy symetrická, je i z« b; protože dále je « tranzitivní a je a«z a z«b, je tedy a«b. To je však podle definice ve sporu s předpokladem, že podmnožiny A_i a A_k jsou různé - podmnožiny jsou tedy disjunktní.

Tvrzení, že ČT=P, je zřejmé. Kdyby neplatilo, existoval by prvek aÎP takový, že by nebyl prvkem žádné třídy A_i. Protože však « je ekvivalence a tedy je reflexivní, platí pro každý prvek (tedy i pro ono a) z P, že a«a. Musí tedy existovat A_k tak, že aÎA_k (byť by A_k měla být jednoprvková množina). To je ovšem ve sporu s tím, že prvek a v žádné A_k není.

Což bylo dokázat.

 

 

Rev. 10 / 2002