Množiny Jan Paseka Masarykova univerzita Brno Množiny ­ p.1/23 Abstrakt V této kapitole připomeneme pojem množiny a pojmy s ním spjaté (podmnožina, operace nad množinami, vlastnosti množin). Speciálně zavedeme pojem množiny všech podmnožin. Množiny ­ p.2/23 Obsah přednášky Ú vod Množina, prvek, podmnožina, vztah inkluze. Sjednocení, průnik, rozdíl, disjunktní množiny. Množiny ­ p.3/23 Obsah přednášky Ú vod Množina, prvek, podmnožina, vztah inkluze. Sjednocení, průnik, rozdíl, disjunktní množiny. Základní tvrzení o množinách Komutativita, asociativita, idempotentnost, distributivita, de Morganova pravidla Množina všech podmnožin Množiny ­ p.3/23 Množina, prvek množiny Množinou rozumíme každý soubor určitých objektů shrnutých v jeden celek. Zmíněné objekty pak nazýváme prvky dané množiny. Pojem ,,množina" je tedy synonymem pojmů typu ,,soubor", ,,souhrn", apod. Množiny ­ p.4/23 Množina, prvek množiny Množinou rozumíme každý soubor určitých objektů shrnutých v jeden celek. Zmíněné objekty pak nazýváme prvky dané množiny. Pojem ,,množina" je tedy synonymem pojmů typu ,,soubor", ,,souhrn", apod. Je-li objekt x prvkem množiny A, píšeme x A. Není-li objekt x prvkem množiny A, píšeme x / A. Množina je plně určena svými prvky. Množiny ­ p.4/23 Rovnost množin Pro množiny A, B máme A = B právě když pro každý objekt x platí, že x je prvkem A tehdy a jen tehdy, když x je prvkem B. Množiny ­ p.5/23 Rovnost množin Pro množiny A, B máme A = B právě když pro každý objekt x platí, že x je prvkem A tehdy a jen tehdy, když x je prvkem B. Zapsáno formulí, máme A = B (x)(x A x B). Množiny ­ p.5/23 Podmnožina Ř ekneme, že množina A je podmnožinou množiny B, jestliže každý prvek množiny A je prvkem množiny B. Píšeme A B a mluvíme o inkluzi množin. Množiny ­ p.6/23 Podmnožina Ř ekneme, že množina A je podmnožinou množiny B, jestliže každý prvek množiny A je prvkem množiny B. Píšeme A B a mluvíme o inkluzi množin. To znamená, že A B právě když pro každý objekt x platí, že je-li x prvkem A, pak x je také prvkem B. Množiny ­ p.6/23 Podmnožina Ř ekneme, že množina A je podmnožinou množiny B, jestliže každý prvek množiny A je prvkem množiny B. Píšeme A B a mluvíme o inkluzi množin. To znamená, že A B právě když pro každý objekt x platí, že je-li x prvkem A, pak x je také prvkem B. Zapsáno formulí, máme tedy A B (x)(x A = x B). Množiny ­ p.6/23 Inkluze, rovnost a tranzitivita Máme pak A = B (A B & B A). Množiny ­ p.7/23 Inkluze, rovnost a tranzitivita Máme pak A = B (A B & B A). Pro libovolné množiny A, B, C platí (A B & B C) = A C. Množiny ­ p.7/23 Inkluze, rovnost a tranzitivita Máme pak A = B (A B & B A). Pro libovolné množiny A, B, C platí (A B & B C) = A C. Místo A B se někdy píše také B A. Platí-li současně A B a A = B, bývá to krátce zapisováno ve tvaru A B. Množiny ­ p.7/23 Konečná a nekonečná podmnožina Význačnou množinou je prázdná množina, tedy množina, která neobsahuje žádný prvek. Značíme ji . Pro libovolnou množinu A máme A A a A. Množiny ­ p.8/23 Konečná a nekonečná podmnožina Význačnou množinou je prázdná množina, tedy množina, která neobsahuje žádný prvek. Značíme ji . Pro libovolnou množinu A máme A A a A. Množina A se nazývá konečná, obsahuje-li pouze konečně mnoho různých prvků. Množiny ­ p.8/23 Konečná a nekonečná podmnožina Význačnou množinou je prázdná množina, tedy množina, která neobsahuje žádný prvek. Značíme ji . Pro libovolnou množinu A máme A A a A. Množina A se nazývá konečná, obsahuje-li pouze konečně mnoho různých prvků. V opačném případě je A nekonečná množina. Množiny ­ p.8/23 Sjednocení a průnik množin Pro libovolné dvě množiny A, B definujeme jejich sjednocení A B jako množinu, která je tvořena těmi prvky, které jsou prvky bud' množiny A nebo množiny B, tedy těmi prvky, které jsou prvky alespoň jedné z množin A, B. Množiny ­ p.9/23 Sjednocení a průnik množin Pro libovolné dvě množiny A, B definujeme jejich sjednocení A B jako množinu, která je tvořena těmi prvky, které jsou prvky bud' množiny A nebo množiny B, tedy těmi prvky, které jsou prvky alespoň jedné z množin A, B.Klademe A B = {x | x A x B}. Množiny ­ p.9/23 Sjednocení a průnik množin Pro libovolné dvě množiny A, B definujeme jejich sjednocení A B jako množinu, která je tvořena těmi prvky, které jsou prvky bud' množiny A nebo množiny B, tedy těmi prvky, které jsou prvky alespoň jedné z množin A, B.Klademe A B = {x | x A x B}. Definujeme průnik A B těchto množin jako množinu, která je tvořena těmi prvky, které jsou současně prvky množiny A i množiny B. Množiny ­ p.9/23 Sjednocení a průnik množin Pro libovolné dvě množiny A, B definujeme jejich sjednocení A B jako množinu, která je tvořena těmi prvky, které jsou prvky bud' množiny A nebo množiny B, tedy těmi prvky, které jsou prvky alespoň jedné z množin A, B.Klademe A B = {x | x A x B}. Definujeme průnik A B těchto množin jako množinu, která je tvořena těmi prvky, které jsou současně prvky množiny A i množiny B. Tedy A B = {x | x A & x B}. Množiny ­ p.9/23 Disjunktnost a rozdíl množin Ř íkáme, že množiny A, B jsou disjunktní, je-li A B = . Množiny ­ p.10/23 Disjunktnost a rozdíl množin Ř íkáme, že množiny A, B jsou disjunktní, je-li A B = . Konečně definujeme rozdíl A - B množin A, B jako množinu těch prvků množiny A, které nejsou prvky množiny B. Množiny ­ p.10/23 Disjunktnost a rozdíl množin Ř íkáme, že množiny A, B jsou disjunktní, je-li A B = . Konečně definujeme rozdíl A - B množin A, B jako množinu těch prvků množiny A, které nejsou prvky množiny B. To znamená, že klademe A - B = {x | x A & x / B}. Množiny ­ p.10/23 Základní tvrzení o množinách I Tvrzení. Pro libovolné množiny A, B, C platí A B = B A A B = B A (komutativita) (A B) C = A (B C) (A B) C = A (B C) (asociativita) Množiny ­ p.11/23 Základní tvrzení o množinách II A A = A A A = A A (B C) = (A B) (A C) A (B C) = (A B) (A C) A - (B C) = (A - B) (A - C) A - (B C) = (A - B) (A - C) (idempotence) (distributivita) de Morganova pravidla Množiny ­ p.12/23 Základní tvrzení o množinách III Tvrzení. Pro libovolné množiny A, B, C platí A - B = A - (A B) A - (B C) = (A - B) - C A - (B - C) = (A - B) (A C) A (B - C) = (A B) - C Množiny ­ p.13/23 Sjednocení souboru množin Obecněji bud' I libovolná množina. Dále necht' pro každé i I je Ai nějaká množina. Ř íkáme, že I je indexová množina souboru množin Ai, i I. Množiny ­ p.14/23 Sjednocení souboru množin Obecněji bud' I libovolná množina. Dále necht' pro každé i I je Ai nějaká množina. Ř íkáme, že I je indexová množina souboru množin Ai, i I. Pak sjednocení tohoto souboru množin definujeme jako množinu i I Ai = {x | (i I)(x Ai)}, tedy jako množinu všech těch prvků, které jsou prvky alespoň jedné z množin Ai uvedeného souboru. Množiny ­ p.14/23 Průniky souboru množin I Je-li I = , pak definujeme také průnik tohoto souboru množin jakožto množinu i I Ai = {x | (i I)(x Ai)}, tedy jako množinu všech těch prvků, které jsou prvky každé z množin Ai uvedeného souboru. Pro I = není tento průnik definován. Množiny ­ p.15/23 Průniky souboru množin I Je-li I = , pak definujeme také průnik tohoto souboru množin jakožto množinu i I Ai = {x | (i I)(x Ai)}, tedy jako množinu všech těch prvků, které jsou prvky každé z množin Ai uvedeného souboru. Pro I = není tento průnik definován. V této souvislosti dále říkáme, že množiny zmíněného souboru jsou vzájemně disjunktní, jestliže pro každá i, j I, i = j, platí Ai Aj = . Množiny ­ p.15/23 Základní tvrzení o množinách IV Tvrzení. Pro libovolnou množinu A, pro libovolnou indexovou množinu I = a pro libovolný soubor množin Bi, kde i I, platí A i I Bi = i I A Bi A i I Bi = i I A Bi A - i I Bi = i I A - Bi A - i I Bi = i I A - Bi ( distributivita) de Morganova pravidla Množiny ­ p.16/23 Doplněk množiny Pro libovolnou množinu A M množinu M - A značíme krátce A a nazýváme ji doplněk množiny A v množině M. Pro libovolnou množinu A M platí A A = M, A A = a A = A. Množiny ­ p.17/23 Průniky souboru množin II Je-li I indexová množina a jsou-li Ai M jakékoliv podmnožiny pro všechna i I, pak je možno modifikovat definici průniku souboru množin Ai pro i I předpisem i I Ai = {x M | (i I)(x Ai)}, tedy jako množinu všech těch prvků z M, které jsou prvky každé z množin Ai uvedeného souboru. Množiny ­ p.18/23 Průniky souboru množin II Je-li I indexová množina a jsou-li Ai M jakékoliv podmnožiny pro všechna i I, pak je možno modifikovat definici průniku souboru množin Ai pro i I předpisem i I Ai = {x M | (i I)(x Ai)}, tedy jako množinu všech těch prvků z M, které jsou prvky každé z množin Ai uvedeného souboru. Průnik je definován i tehdy, je-li I = , a v tom případě je roven celé množině M. Pro I = je tato definice shodná s definicí předchozí. Množiny ­ p.18/23 Aplikace de Morganových pravidel Dále z de Morganových pravidel pro libovolný soubor podmnožin Ai M, kde i I, plyne i I Ai = i I Ai i I Ai = i I Ai a tyto rovnosti platí i v případě, že I = . Množiny ­ p.19/23 Množina všech podmnožin K libovolné množině A vytvořme množinu P(A) = {X | X A}, tedy množinu, jejímiž prvky jsou právě všechny ty množiny, které jsou podmnožinami množiny A. Množiny ­ p.20/23 Množina všech podmnožin K libovolné množině A vytvořme množinu P(A) = {X | X A}, tedy množinu, jejímiž prvky jsou právě všechny ty množiny, které jsou podmnožinami množiny A. Tuto množinu nazýváme množinou všech podmnožin množiny A, nebo též potenční množinou množiny A. Množiny ­ p.20/23 Iterace konstrukce potenční množiny Konstrukci potenční množiny lze iterovat. Všimněme si například, že P() = {}, Množiny ­ p.21/23 Iterace konstrukce potenční množiny Konstrukci potenční množiny lze iterovat. Všimněme si například, že P() = {}, P(P()) = {, {}}, Množiny ­ p.21/23 Iterace konstrukce potenční množiny Konstrukci potenční množiny lze iterovat. Všimněme si například, že P() = {}, P(P()) = {, {}}, P(P(P())) = {, {}, {{}}, {, {}}}, atd. Množiny ­ p.21/23 Konstrukce přirozených čísel I Sestrojíme množinu = {0, 1, 2, 3, . . . } všech nezáporných celých čísel. Prvky této množiny mají být zase množiny. Množiny ­ p.22/23 Konstrukce přirozených čísel I Sestrojíme množinu = {0, 1, 2, 3, . . . } všech nezáporných celých čísel. Prvky této množiny mají být zase množiny. Definujeme tedy čísla 0, 1, 2, 3, . . . , n, . . . indukcí jako množiny následovně. Množiny ­ p.22/23 Konstrukce přirozených čísel II Klademe 0 = Množiny ­ p.23/23 Konstrukce přirozených čísel II 0 = , 1 = {} Množiny ­ p.23/23 Konstrukce přirozených čísel II 0 = , 1 = {}, 2 = {, {}}, Množiny ­ p.23/23 Konstrukce přirozených čísel II 0 = , 1 = {}, 2 = {, {}}, 3 = {, {}, {, {}}}, . . . , Množiny ­ p.23/23 Konstrukce přirozených čísel II 0 = , 1 = {}, 2 = {, {}}, 3 = {, {}, {, {}}}, . . . , tedy pro každé n > 1 klademe n = {0, 1, 2, . . . , n - 1}. Množiny ­ p.23/23 Konstrukce přirozených čísel II 0 = , 1 = {}, 2 = {, {}}, 3 = {, {}, {, {}}}, . . . , tedy pro každé n > 1 klademe n = {0, 1, 2, . . . , n - 1}. Pro každá m, n máme m < n právě tehdy, když m n. Množiny ­ p.23/23