Množiny

Naivně jde o souhrn jednoznačně určených a rozlišitelných prvků. Nejčastěji se v matematice setkáváme s množinami, jejichž prvky jsou čísla, n-tice, funkce atd. O těchto prvcích hovoříme jako o prvcích (elements) a nezáleží na jejich pořadí a každý prvek je v množině obsažen jen jednou. Počet prvků množiny není omezen a mohou mít konečně i nekonečně mnoho prvků.

Běžně označujeme množiny velkými písmeny abecedy A, B, …, M, N, …, a jejich prvky malými písmeny.

Teorie množin se dělí na naivní teorii množin a axiomatickou teorii množin, která přesně formuluje vlastnosti množin několika axiomy.

Zadání množiny

Množina je dostatečně určena, jestliže jsme o každém prvku schopni říci, zda do dané množiny patří, nebo ne. Tečky označují pokračování výčtu čísel, které pokračují v pozitivním i negativním směru. Množinu můžeme zadat slovně, ale obvykle je definujeme dvěma základními způsoby:

1) Výčet prvků

Výčtem jednotlivých prvků, oddělených čárkami které jsou uzavřeny ve složených závorkách $\{\}$. Často se tento způsob nazývá list comprehance.

• konečné množiny $A := {3, 4, {π,4}}$
• nekonečné množiny $ℕ := {2, 4, 6, …}$

2) Pomocí pravidla (set notation)

Množina může být definována sadou pravidel, kdy z některé univerzální množiny (např. číselné množiny) vybíráme prvky splňující určitou podmínku. První určíme nějakou výchozí množinu $M$ (universum) na jehož prvky aplikujeme pravidlo a následkě určíme pravidlo $P(x)$, tedy výrok o $x ∈ M$.

Tento způsob se nazývá v literatuře set builder, set notation.

Příklady:

• Obecně: $A = \{x ∈ M | P(x)\}$

• Zápis sudých čísel: $\{k ∈ ℕ | (∃j∈ℕ)(k=2j)\} = \{2j | j∈ℕ\}$

Znak | se čte jako takových/splňující. Někdy se místo něj používá : nebo ;.

Podmnožiny

Prvek v množině může být i jiná množina. Množiny do sebe můžeme navzáme vnořovat. Nebo z množiny můžeme taky vyjmout jen určitou část. Vyjádření této akce, máme operator inkluze.

Inkluze ⊆

A nazýváme podmnožinou množiny B.

$A ⊆ B ≝ {∀x ∈ U; x ∈ A ⇒ x ∈ B}$

Ostrá inkluze ⊂

A nazýváme vlastní podmnožinou množiny B.

$A ⊂ B ≝ {∀x ∈ U; A ⊆ B ∧ A ≠ B}$

Vlastnosti podmnožiny: $\{\} ⊆ A$: prázdná množina je podmnožina jakékoliv množiny.

Velikost množin

Jako velikost množiny myslíme počet prvků v množině. V kontextu nekonečných množin mluvíme spíše o mnohutnosti, protože některá nekonečna jsou větší než jiná nekonečna. George Cantor zjistíl, že celých čísel je stejně jako sudých a racionálních, ale méně než reálných, respektive množiny mají příslušné mohutnosti. O celé problematice velikost nekonečen si můžete přečíst.

Nekonečna vedly k zavedení pojmů kardinální číslo nebo ordinální číslo.

Velikost symbolicky vyjadřujeme znaky, tedy velikost množiny A, $|A| = n$.

• Velikost prázdné množiny je nulová $|\{\}|=0$
• Velikost množiny přirozených čísel je nekonečná $|ℕ| = ∞$
• Pro kartézský součin dvou množin platí $|A × B| = |A|·|B|$

Základní množinové operace

Jazyk teorie množin obsahuje jediný binární predikát $∈$. Znak „$∈$ – „náleží" – je odvozen od slova „element" (prvek). Binární množinové operace.

Rovnost množin =

Množiny jsou stejné, tehdy když mají stejné prvky. $A = B ≝ (A ⊆ B ∧ B ⊆ A) = \{∀x ∈ U; x ∈ A ⇔ x ∈ B\}$

Průnik množin ∩

Množina právě všech prvků x, které náleží oběma množinám A i B současně. $A ∩ B ≝ \{x ∈ U; x ∈ A ∧ x ∈ B\}$

Disjunktní množiny A ∩ B = ∅
Ekvivalentní formule: A ∩ B = A - (A - B)

Sjednocení množin ∪

$A ∪ B = A + B ≝ {∀x ∈ U; x ∈ A ∨ x ∈ B}$

Rozdíl množin /

Množina obsahující právě ty prvky x, které leží v množině A a neleží v množině B.

$A - B ≝ \{∀x ∈ U; x ∈ A ∧ x ∉ B\}$

Doplněk množiny vzhledem k univerzu M

$A_M ≝ A' = M - \{A\} = \{∀x ∈ M; x ∉ A\}$.

Jak se liší množiny a relace?

Identitou. V množině může být prvek a pouze jednou. Platí tedy $M = {a, b} = {b, a} = {a, b, a}$.

Všimněte si, že $\{a, b\}$ je množina shodná s $\{b, a\}$, kdežto uspořádané dvojice $(x, y)$ a $(y, x)$ nejsou stejné (obecně). Symbolem $A × B$ označujeme kartézský součin.

Další vlastnosti

Negace inkluze $A - B ≝ ¬(A ⊆ B)$

Symetrická diference $A ⊕ B ≝ (A \ B) ∪ (B \ A)$

Demorganovy zákony $(A ∪ B)' = A' ∩ B'$

$(A ∩ B)' = A' ∪ B'$

Uspořádání

Uspořádaná množina není úplně množinový pojem a bývá zadávána prostřednictvím relací nebo posloupností. Dá se vyjádřit pomocí množin např.

$(a,b) = \{\{a\}, \{a, b\}\}$

Relace je podmnožina kartézského součinu.

Potenční množina

Je množina obsahující všechny podmnožiny množiny (značí se $P(X)$ nebo $2^X$), včetně a celé množiny A.

$P(A) ≝ 2^A ≝ {X ⊆ U; X ⊆ A}$.

Příklad: $A = \{1,2,3\}$

$P(A) = \{∅, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}\}$

Formálně vyplývá existence potenční množiny k libovolné množině z axiomu potenční množiny.

Počet všech podmnožin množiny $\sum_{k=0}^{n} {n \choose k} = 2^n$.

Princip inkluze a exkluze

$|\textstyle\cup_{i=1}^n A_i|$

$= \sum_{i=1}^{n} |A_i| - \sum_{i<j} |A_i \cap A_j| + \sum_{i<j<k} |A_i \cap A_j \cap A_k| - ... + (-1)^{n-1} |\textstyle\cup^n_{i=1}A_i|$

$|A ∪ B| = |A| + |B| − |A ∩ B|$

Rozklad na množině

Splňuje následující dvě podmínky

• $\textstyle\cup_{i \in I}^n A_i = A$ (podmínka pokrytí)
• $A_i \cap A_j = {}$ (podmínka disjunkce)

Je počet reálných čísel „stejný“ jako počet všech podmnožin množiny čísel přirozených? Dnes je známá kladná odpověď na tuto otázku.

Dobrým znázorněním vztahu mezi množinami jsou tzv. Vennovy diagramy. Pro 4 a více množin, ale příliš toto znázornění nefunguje.