— — Množiny

Množiny

Množina: soubor prvků.

Zápis:

• výčtem prvků: X = {a, b, c}
• vlastností: X = {i ∈ ℕ : ∃ j ∈ ℕ, i = j}

X = Y ⇔ (x ∈ X ⇔ x ∈ Y) ∀x

Je-li X konečná, |X| ⇔ len(X) (velikost, mohutnost).

X ⊆ Y ⇔ (x ∈ X ⇒ x ∈ Y) ∀x

P (X): Potenční množina množiny X — množina všech podmnožin množiny X (včetně ∅ a X). Je-li X konečná, |P (X)| = 2^{|X|}.

Symbolika: |X| ∩ |Y |, |X| ∪ |Y |, |X| \ |Y |, …

Relace

Neuspořádaná dvojice: {x, y} Uspořádaná dvojice: (x, y): (x, y) = (x′, y′) ⇔ (x = x′ ∧ y = y′); např. {{x}, {x, y}} Kartézský součin: X × Y = {(x, y) : x ∈ X, Y ∈ Y } Relace R mezi X, Y: R ⊆ X × Y Relace R na X: R ⊆ X × X Značení: (x, y) ∈ ℝ: xRy (jde-li o binární relaci)

Definice:

Relace R na množině X je:

• reflexivní: xRx ∀x ∈ X : xRx

• symetrická: xRy ⇒ yRx ∀x, y ∈ X

• tranzitivní: (xRy ∧ yRz) ⇒ xRz ∀x, y, z ∈ X • ekvivalence: reflexivní, symetrická, tranzitivní

Třídy ekvivalence

Určené prvkem x:

R[x] = {y ∈ X, xRy}

(díky symetrii platí i yRx).

Příklad:

X = {1, 2, 3, 4}

R = {(1, 1), (2, 2), (3, 3), (4, 4), (2, 4), (4, 2)}

\begin{aligned}R[1] & = \{1\} \\ R[2] = R[4] & = \{2, 4\} \end{aligned}

Tvrzení:

(i) x ∈ R[x] ∀x ∈ X
(ii) R[x] = R[y] ∨ R[x] ∩ R[y] = ∅ ∀x, y ∈ X

— — Uspořádání

DŮKAZ:

(i) Z reflexivity. (ii) Nechť x, y ∈ X:

(1) Předpokládejme xRy:

R[x] ⊆ R[y]: Mějme libovolné z ∈ R[x], tedy zRx →^{tranz.} zRy, to znamená z ∈ R[y]. Q.E.D.

R[y] ⊆ R[x] obdobně (symetrie).

R[x] = R[y]

(2) Předpokládejme, že neplatí xRy:

Pro spor nechť R[x] ∩ R[y] ≠ ∅. Mějme libovolné z ∈ R[x] ∩ R[y]. Pak jistě

xRz ∧ zRy ⇒^{tranz.} xRy. ♯̸ Spor

R[x] ∩ R[y] = ∅

Důsledek:

Množina (systém množin) {R[x] : x ∈ X} tvoří tzv. rozklad množiny X. ∀x ∈ X pak patří do právě jedné množiny z rozkladu.

Uspořádání

(Částečné) uspořádání: Relace na X, která je reflexivní, tranzitivní a antisymetrická (xRy ∧ yRx ⇒ x = y ∀x, y ∈ X).

Značení: ≤ či ⪯ Příklady: (ℕ, ⪯), (ℕ, |) (dělí), (P (X), ⪯) Lineární uspořádání: Takové uspořádání, že xRy ∨ yRx ∀x, y ∈ X. Pozn.: (P (X), ⪯) je lineární, pokud |X| ≤ 1.

Zobrazení

Definice:

Máme-li množiny X, Y, zobrazení z X do Y definujeme jako libovolnou relaci f ⊆ X × Y, která splňuje předpoklad, že ∀x ∈ X ∃! y ∈ Y takové, že xfy.

Značení: f: X → Y, f: x ↦ y, f(x) = y

Definice:

Máme-li f: X → Y a g: Y → Z, složené zobrazení g ∘ f značí zobrazení X → Z, definované předpisem:

(g ∘ f)(x) = g(f(x)) ∀x ∈ X

Poznámka:

g ∘ f je skutečné zobrazení z X do Z:

(g ∘ f)(x) = g(\underbrace{f(x)}_{∃! y}) = \underbrace{g(y)}_{∃! z} = z

— — Zobrazení

Definice:

Říkáme, že zobrazení f: X → Y je: • prosté (injekce f: X ↔ Y), pokud x ≠ y ⇒ f(x) ≠ f(y) ∀x, y ∈ X.

• na (z X na Y) (surjekce f: X →> Y), pokud ∀y ∈ Y ∃ x ∈ X takové, že f(x) = y.

• vzájemně jednoznačné (bijekce f: X ↔> Y či f: X ⟷^{1–1} Y), pokud je prosté a na. Pro konečné množiny platí:

• prosté: |X| ≤ |Y |

• na: |X| ≥ |Y |

• bijekce: |X| = |Y |

Pozn.: Pojem funkce se používá ve významu “zobrazení” či “zobrazení do ℝ”.