Matematick´y ustav Slezske´ univerzity v Opaveˇ ´ ´ sce ALGEBRA I, zimn´ı semestr 2002/2003 Uˇcebn´ı texty k pˇrednaˇ Michal Marvan
0. Mnoˇziny, relace a zobrazen´ı Uk´azuje se, zˇ e pojem ,,mnoˇzina“ nelze jednoduˇse definovat – naivn´ı pokusy vedou ke spor˚um. Pˇresto v dneˇsn´ı dobˇe spoˇc´ıvaj´ı z´aklady matematiky pr´avˇe v teorii mnoˇzin a lepˇs´ı alternativa zat´ım neexistuje. Korektn´ı zaveden´ı pojmu mnoˇzina pˇredstavuje probl´em ˇreˇsen´y v tzv. axiomatick´e teorii mnoˇzin a pˇr´ısluˇsn´y v´yklad je pˇredmˇetem samostatn´e pˇredn´asˇky.
ˇ ık´ame t´ezˇ , zˇ e a patˇr´ı do Bud’ M mnoˇzina. Z´apis a ∈ M oznaˇcuje, zˇ e a je prvek mnoˇziny M. R´ mnoˇziny M. Z´apis a ∈ M oznaˇcuje, zˇ e a nen´ı prvek mnoˇziny M (nepatˇr´ı do mnoˇziny M). Pro libovoln´e a nast´av´a pr´avˇe jedna z moˇznost´ı a ∈ M nebo a ∈ / M. Intuitivn´ı pˇredstava spojen´a s pojmem mnoˇzina je stejn´a jako u slov ,,souhrn“ cˇ i ,,soubor.“ Ale napˇr´ıklad ,,mnoˇzina vˇsech mnoˇzin“ obsahuje sama sebe a vznik´a logick´y kruh, kdy se objekt pod´ıl´ı na sv´e vlastn´ı definici, coˇz otev´ır´a cestu k r˚uzn´ym paradox˚um (viz Russel˚uv paradox n´ızˇ e). Podle axiomatick´e teorie mnoˇzin ,,mnoˇzina vˇsech mnoˇzin“ neexistuje.
0.1. Definice. Mnoˇziny A, B jsou si rovny, maj´ı-li tyt´ezˇ prvky, tj. plat´ı-li ekvivalence x∈A
⇔
x ∈ B.
Zapisujeme A = B. Uveden´a definice odpov´ıd´a na ot´azku: ,,Jak pozn´ame, zˇ e jsou si mnoˇziny rovny?“ Obecnˇe ˇreˇceno, definicemi zav´ad´ıme nov´e pojmy, zde rovnost mnoˇzin. Definice umoˇznˇ uje rozhodnout, zda definovan´a situace (rovnost mnoˇzin) nastala cˇ i nenastala. Existuje pr´avˇe jedna mnoˇzina, kter´a neobsahuje zˇ a´ dn´y prvek. Naz´yv´a se pr´azdn´a mnoˇzina a oznaˇcuje se ∅. Jednoznaˇcnost pr´azdn´e mnoˇziny lze dok´azat: kaˇzd´a jin´a mnoˇzina, kter´a tak´e neobsahuje zˇ a´ dn´e prvky, je rovna mnoˇzinˇe ∅ podle pr´avˇe uveden´e definice rovnosti mnoˇzin. Koneˇcnou mnoˇzinu (mnoˇzinu s koneˇcn´ym poˇctem prvk˚u) lze zadat v´ycˇ tem prvk˚u, napˇr´ıklad A = { ♥, ♠, ♦, ♣ }. Nˇekter´e nekoneˇcn´e mnoˇziny lze zadat ne´upln´ym v´ycˇ tem, napˇr´ıklad N = {1, 2, 3, 4, 5, . . .} je mnoˇzina vˇsech pˇrirozen´ych cˇ´ısel. Pˇr´ıklad. Plat´ı { ♣ } = { ♣, ♣ }, protoˇze mnoˇziny na lev´e a prav´e stranˇe shodnˇe obsahuj´ı prvek ♣ a zˇ a´ dn´y jin´y.
ˇ 0.2. Definice. Rekneme, zˇ e mnoˇzina B je podmnoˇzinou mnoˇziny A, jestliˇze kaˇzd´y prvek z mnoˇziny B n´aleˇz´ı i mnoˇzinˇe A, tj. kdyˇz plat´ı implikace x∈B
⇒
x ∈ A.
Zapisujeme B ⊆ A. Vztah ‘⊆’ se naz´yv´a inkluze. Pˇr´ıklad. Plat´ı { ♥, ♣ } ⊆ { ♥, ♠, ♦, ♣ }. Vskutku, vˇsechny prvky leˇz´ıc´ı v mnoˇzinˇe { ♥, ♣ }, coˇz jsou prvky ♥ a ♣, leˇz´ı i v mnoˇzinˇe { ♥, ♠, ♦, ♣ }.
Z´apis B ⊂ A znamen´a, zˇ e B ⊆ A a z´aroveˇn B = A. Napˇr´ıklad, { ♥, ♣ } ⊂ { ♥, ♠, ♦, ♣ }. Cviˇcen´ı. Rozhodnˇete, zda plat´ı a) { ♣ } ∈ {{ ♣ }}; b) { ♣ } ⊂ {{ ♣ }}; c) ∅ ∈ { ∅ }; d) ∅ ⊂ { ∅ }. N´avod: V pˇr´ıpadech a) a c) se pt´ame, zda prvek leˇz´ıc´ı po lev´e stranˇe symbolu ,∈‘ n´aleˇz´ı mnoˇzinˇe uveden´e po prav´e stranˇe symbolu ,∈‘. V pˇr´ıpadech b) a d) se pt´ame, zda vˇsechny prvky leˇz´ıc´ı v mnoˇzinˇe uveden´e po lev´e stranˇe symbolu ,⊆‘ leˇz´ı i v mnoˇzinˇe uveden´e po prav´e stranˇe symbolu ,⊆‘.
0. Mnoˇziny, relace a zobrazen´ı
Cviˇcen´ı. 1. Negujte v´yrok ∀x∈A x ∈ B. Jak se pozn´a, zˇ e neplat´ı A ⊆ B? 2. Jak se pozn´a, zˇ e neplat´ı A ⊂ B?
0.3. Tvrzen´ı. Pro libovoln´e dvˇe mnoˇziny A, B jsou n´asleduj´ıc´ı v´yroky ekvivalentn´ı: (1) A = B; (2) (A ⊆ B) ∧ (B ⊆ A). ˚ Dukaz. Ekvivalenci ,⇔‘ dok´azˇ eme tak, zˇ e zvl´asˇt’dok´azˇ eme implikaci ,⇒‘ a zvl´asˇt’implikaci ,⇐‘. ,⇒‘: Plat´ı-li (1), maj´ı obˇe mnoˇziny tyt´ezˇ prvky, a pak kaˇzd´y prvek mnoˇziny A leˇz´ı v mnoˇzinˇe B a naopak, kaˇzd´y prvek mnoˇziny B leˇz´ı v mnoˇzinˇe A. Plat´ı tedy oba v´yroky A ⊆ B a B ⊆ A. ,⇐‘: Plat´ı-li (2), pak kaˇzd´y prvek mnoˇziny A leˇz´ı v mnoˇzinˇe B a kaˇzd´y prvek mnoˇziny B leˇz´ı v mnoˇzinˇe A. Tud´ızˇ , mnoˇziny A, B maj´ı stejn´e prvky. Jin´y d˚ukaz implikace ,⇐‘ (sporem): Pˇripust’me, zˇ e A, B nemaj´ı stejn´e prvky, pak existuje prvek x leˇz´ıc´ı jen v jedn´e z nich. Rozezn´avejme dva pˇr´ıpady. V pˇr´ıpadˇe, zˇ e x leˇz´ı v A a ne v B, neplat´ı A ⊆ B, v pˇr´ıpadˇe, zˇ e x leˇz´ı v B a ne v A, neplat´ı B ⊆ A. V obou pˇr´ıpadech (2) neplat´ı.) ˚ Jin´y dukaz. V´yrok α ⇔ β je logicky ekvivalentn´ı s v´yrokem (α ⇒ β) ∧ (β ⇒ α). Dosad´ıme-li za α v´yrok ,,x ∈ A“ a za β v´yrok ,,x ∈ B“, dost´av´ame, zˇ e v´yrok x ∈ A ⇔ x ∈ B je ekvivalentn´ı s v´yrokem (x ∈ A ⇒ x ∈ B) ∧ (x ∈ B ⇒ x ∈ A), coˇz bylo tˇreba dok´azat. Bud’ A mnoˇzina. Bud’ ψ nˇejak´a vlastnost, kterou prvek a ∈ A bud’ m´a, coˇz zapisujeme ψ(a), cˇ i nem´a, coˇz zapisujeme ψ(a). Podmnoˇzina mnoˇziny A tvoˇren´a vˇsemi prvky a ∈ A s vlastnost´ı ψ se oznaˇcuje a ∈ Aψ(a) . Zapamatujte si: x ∈ a ∈ Aψ(a)
⇔
x ∈ A ∧ ψ(a).
Pˇr´ıklad. Je-li A = { ♥, ♠, ♦, ♣ }, pak { a ∈ A | a je cˇ ern´e barvy } = { ♠, ♣ }. Z´apis { a | ψ(a) } (chyb´ı ,,∈ A“, kde A je mnoˇzina) je v principu tak´e moˇzn´y, ale nemus´ı oznaˇcovat mnoˇzinu. Pˇr´ıklad (Russel˚uv paradox): Necht’ N = { x | x je mnoˇzina a x ∈ / x } (souhrn vˇsech mnoˇzin, kter´e nejsou samy sv´ym prvkem). Pˇripust´ıme-li, zˇ e N je mnoˇzina, pak mohou nastat dvˇe moˇznosti: Bud’ N ∈ / N , ale pak N ∈ N podle sv´e vlastn´ı definice, spor; anebo N ∈ N , ale pak N ∈ / N podle definice, opˇet spor. Tud´ızˇ , N nen´ı mnoˇzina.
Bud’n pˇrirozen´e cˇ´ıslo, bud’te A1 , . . . , An nˇejak´e mnoˇziny. Sjednocen´ı mnoˇzin A1 , . . . , An oznaˇc´ıme A1 ∪· · ·∪ An ; je to mnoˇzina tvoˇren´a pr´avˇe tˇemi prvky a, kter´e leˇz´ı v alespoˇn jedn´e z mnoˇzin A1 , . . . , An . Napˇr´ıklad, { ♥ } ∪ { ♥, ♠ } ∪ { ♠, ♣ } = { ♥, ♠, ♣ }. Plat´ı ekvivalence a ∈ A ∪ B ⇔ a ∈ A ∨ a ∈ B. Pr˚unik mnoˇzin A1 , . . . , An oznaˇc´ıme A1 ∩ · · · ∩ An ; je to mnoˇzina tvoˇren´a pr´avˇe tˇemi prvky a, kter´e leˇz´ı v kaˇzd´e z mnoˇzin A1 , . . . , An . Napˇr´ıklad, { ♥, ♠, ♣ } ∩ { ♥, ♦, ♣ } = { ♥, ♣ }. Zˇrejmˇe A ∩ B = { x ∈ A | x ∈ B } = { x ∈ B | x ∈ A }. Plat´ı a ∈ A ∩ B ⇔ a ∈ A ∧ a ∈ B. Rozd´ıl mnoˇzin A, B je A \ B = { a ∈ A | a ∈ B }. Napˇr´ıklad: { ♥, ♠, ♣ } \ { ♥, ♦ } = { ♠, ♣ }. Sjednocen´ı, pr˚unik i rozd´ıl mnoˇzin jsou vˇzdy opˇet mnoˇziny. Plat´ı rovnosti A ∪ B = B ∪ A, A ∪ (B ∪ C)= (A ∪ B) ∪ C = A ∪ B ∪ C, A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C), A \ (B ∩ C) = (A \ B) ∪ (A \ C),
A ∩ B = B ∩ A, A ∩ (B ∩ C)= (A ∩ B) ∩ C = A ∩ B ∩ C, A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C), A \ (B ∪ C) = (A \ B) ∩ (A \ C).
Cviˇcen´ı. Dokaˇzte pˇredchoz´ı rovnosti dosazen´ım do vhodn´ych logick´ych ekvivalenc´ı.
2
0. Mnoˇziny, relace a zobrazen´ı
1. Kart´ezsk´y souˇcin ˇ Rekneme, zˇ e je zad´ana uspoˇra´ dan´a dvojice (a, b) prvk˚u mnoˇzin A, B, je-li zad´ana jej´ı prvn´ı sloˇzka a ∈ A a druh´a sloˇzka b ∈ B. Uspoˇra´ dan´e dvojice (a, b) a (a , b ) jsou si rovny, pr´avˇe kdyˇz plat´ı a = a a z´aroveˇn b = b . Zapisujeme (a, b) = (a , b ). Vid´ıme, zˇ e uspoˇra´ dan´a dvojice (a, b) je jednoznaˇcnˇe urˇcena zad´an´ım dvou prvk˚u a jejich poˇrad´ım, na rozd´ıl od mnoˇziny { a, b }, kter´a je urˇcena zad´an´ım dvou prvk˚u bez ohledu na poˇrad´ı. Shora uveden´e vymezen´ı pojmu uspoˇra´ dan´a dvojice lze v jist´e rozumn´e m´ırˇe povaˇzovat za definici. Alternativnˇe m˚uzˇ eme uspoˇra´ danou dvojici (a, b) definovat pˇredpisem (a, b) = {{ a }, { a, b }}. Skuteˇcnˇe, {{ a }, { a, b }} = {{ a }, { a , b }} pr´avˇe tehdy, kdyˇz a = b ∧ a = b (pokuste se dok´azat).
Mnoˇzinu vˇsech uspoˇra´ dan´ych dvojic (a, b) prvk˚u mnoˇzin A, B naz´yv´ame kart´ezsk´y souˇcin mnoˇzin A, B a oznaˇcujeme A × B. Pˇr´ıklad. { ♥, ♦ } × { ♠, ♣ } = {(♥, ♠), (♥, ♣), (♦, ♠), (♦, ♣)}. Pˇr´ıklad. Bud’te A, B libovoln´e mnoˇziny, bud’te A ⊆ A, B ⊆ B jejich podmnoˇziny. Pak plat´ı A × B = ( A × B ) ∩ ( A × B ). Proved’me d˚ukaz tohoto tvrzen´ı. Jde o rovnost mnoˇzin; dokaˇzme inkluze ,,⊆“ a ,,⊇“ zvl´asˇt’. ,,⊆“: Bud’ (a, b) ∈ A × B libovoln´y prvek. To znamen´a, zˇ e a ∈ A a b ∈ B jsou dva libovoln´e prvky. Protoˇze A ⊆ A, je tak´e a ∈ A, naˇceˇz (a, b) ∈ A × B . Protoˇze B ⊆ B, m´ame podobnˇe b ∈ B, naˇceˇz (a, b) ∈ A × B. Tud´ızˇ , (a, b) ∈ (A × B ) ∩ (A × B). Pˇr´ısluˇsn´a inkluze je dok´az´ana. ,,⊇“: Bud’ (a, b) libovoln´y prvek pr˚uniku (A × B ) ∩ (A × B). Pak speci´alnˇe (a, b) ∈ A × B , naˇceˇz a ∈ A, b ∈ B . Podobnˇe (a, b) ∈ A × B, naˇceˇz a ∈ A , b ∈ B. Z a ∈ A , b ∈ B vypl´yv´a (a, b) ∈ A × B . T´ım je dok´az´ana i opaˇcn´a inkluze. Cviˇcen´ı. Bud’te A, B libovoln´e mnoˇziny, bud’te A , A ⊆ A podmnoˇziny. Dokaˇzte, zˇ e plat´ı 1. (A ∩ A ) × B = (A × B) ∩ (A × B); 2. (A ∪ A ) × B = (A × B) ∪ (A × B).
Podobnˇe jako uspaˇra´ dan´e dvojice lze zav´est i uspoˇra´ dan´e trojice, cˇ tveˇrice, atd., obecnˇe ntice pro libovoln´e pˇrirozen´e cˇ´ıslo n. Dvˇe ntice (a1 , . . . , an ) a (b1 , . . . , bn ) jsou si rovny, jestliˇze ai = bi pro kaˇzd´e i = 1, . . . , n. Cviˇcen´ı. Zaved’me uspoˇra´ dan´e trojice pˇredpisem (a1 , a2 , a3 ) := (a1 , (a2 , a3 )), kde symbol ,:=‘ znamen´a, zˇ e objekt na jeho lev´e stranˇe je definov´an formul´ı uvedenou na jeho prav´e stranˇe. Vˇsimnˇete si, zˇ e na prav´e stranˇe stoj´ı dvˇe uspoˇra´ dan´e dvojice, coˇz jsou pojmy jiˇz zn´am´e. Ukaˇzte, zˇ e (a1 , a2 , a3 ) = (b1 , b2 , b3 ) pr´avˇe tehdy, kdyˇz a1 = b1 , a2 = b2 a a3 = b3 .
2. Relace 2.1. Definice. Bud’te A, B libovoln´e mnoˇziny. Relace (neboli korespondence) mezi mnoˇzinami A, B je libovoln´a podmnoˇzina kart´ezsk´eho souˇcinu A × B. Je-li ρ ⊆ A × B relace a jsou-li a ∈ A, b ∈ B prvky takov´e, zˇ e (a, b) ∈ ρ, pak ˇr´ık´ame, zˇ e prvek a je v relaci ρ s prvkem b a struˇcnˇe zapisujeme aρb. Relace na mnoˇzinˇe A je zvl´asˇtn´ı pˇr´ıpad, kdy A = B. Zadat relaci mezi mnoˇzinami A, B je tedy tot´ezˇ , co vybrat urˇcitou mnoˇzinu dvojic (a, b), kde a ∈ A a b ∈ B. Zapamatujte si: aρb
⇔
(a, b) ∈ ρ.
Relace mezi mnoˇzinami, zejm´ena koneˇcn´ymi, m˚uzˇ eme zn´azorˇnovat grafem. Prvky mnoˇzin A, B zn´azorn´ıme body v rovinˇe, body a a b zn´azorˇnuj´ıc´ı prvky jednotliv´ych mnoˇzin spoj´ıme sˇipkou tehdy a jen tehdy, jsou-li v relaci. 3
0. Mnoˇziny, relace a zobrazen´ı
Pˇr´ıklady. 1. Necht’ A = { ♥, ♦ }, B = { ♠, ♣ }. Podmnoˇzina ρ = {(♥, ♠), (♥, ♣)} je relace mezi mnoˇzinami A, B. Plat´ı ♥ρ♠ a ♥ρ♣. Neplat´ı napˇr´ıklad ♦ρ♣. Graficky: A
♦ ♥
✿♣ ✘✘ ✘✘ ✲ ♠ B
ˇ adn´e dva prvky a ∈ A, b ∈ B nejsou v 2. Pr´azdn´a podmnoˇzina ∅ ⊆ A × B je relace mezi mnoˇzinami A, B. Z´ t´eto relaci. Graf takov´e relace neobsahuje zˇ a´ dnou sˇipku. 3. Podmnoˇzina A × B ⊆ A × B je relace mezi mnoˇzinami A, B. Kaˇzd´e dva prvky a ∈ A, b ∈ B jsou v t´eto relaci. Graf takov´e relace obsahuje po jedn´e sˇipce z kaˇzd´eho prvku a ∈ A do kaˇzd´eho prvku b ∈ B. 4. Identick´a relace na mnoˇzinˇe A je podmnoˇzina id A = { (a, a) | a ∈ A }. Prvky a, b ∈ A jsou v t´eto relaci pr´avˇe tehdy, kdyˇz a = b. 5. Relace ostr´eho uspoˇra´ d´an´ı podle velikosti ,,<“ na mnoˇzinˇe R re´aln´ych cˇ´ısel. 6. Relace neostr´eho uspoˇra´ d´an´ı podle velikosti ,,≤“ na mnoˇzinˇe R re´aln´ych cˇ´ısel. 7. Relace ,, “ sousedstv´ı zleva mezi cel´ymi cˇ´ısly – ˇrekneme, zˇ e cˇ´ıslo a soused´ı zleva s cˇ´ıslem b, jestliˇze b = a + 1. Cviˇcen´ı. Nakreslete grafy relac´ı 2, 3, 4 a 7.
ˇ 2.2. Definice. Bud’ ρ relace mezi mnoˇzinami A, B, bud’ σ relace mezi mnoˇzinami C, D. Rekneme, zˇ e relace ρ a σ jsou si rovny, jestliˇze A = C, B = D a ρ = σ . Poˇzadavek rovnosti mnoˇzin ρ = σ vypl´yv´a z definice relace jako jist´e mnoˇziny. Poˇzadavek rovnosti mnoˇzin A = C a B = D je nav´ıc a jen ,,pro poˇra´ dek,“ aby jedna a tat´azˇ relace nemohla b´yt mezi r˚uzn´ymi mnoˇzinami. Kdybychom relaci definovali jako uspoˇra´ danou trojici (A, B, ρ), pak by rovnost mnoˇzin byla pˇr´ım´ym d˚usledkem definice relace. 2.3. Definice. Relace ρ −1 mezi mnoˇzinami B, A definovan´a pˇredpisem ρ −1 := (b, a)aρb se naz´yv´a opaˇcn´a relace k relaci ρ. Zapamatujte si: aρb ⇔ bρ −1 a. V grafu relace ρ −1 vede sˇipka b − → a pr´avˇe tehdy, kdyˇz v grafu relace ρ vede sˇipka a − → b. Vid´ıme, zˇ e graf opaˇcn´e relace vznikne obr´acen´ım vˇsech sˇipek grafu p˚uvodn´ı relace. Pˇr´ıklady. 1. Relace ρ −1 mezi mnoˇzinami B = { ♠, ♣ } a A = { ♥, ♦ }, opaˇcn´a k relaci zaveden´e v pˇredchoz´ım pˇr´ıkladu cˇ . 1, je podmnoˇzina ρ −1 = {(♠, ♥), (♣, ♥)}. Graf: A
♦
✘♣ B ✾✘✘ ✘ ✛ ♥ ♠
2. Relace opaˇcn´a k relaci ,,<“ uspoˇra´ d´an´ı re´aln´ych cˇ´ısel podle velikosti je relace ,,>“ opaˇcn´eho uspoˇra´ d´an´ı podle velikosti. 3. Bud’ H = { h 1 , h 2 } nˇejak´a mnoˇzina hoch˚u, D = { d1 , d2 } nˇejak´a mnoˇzina d´ıvek. Nˇekteˇr´ı hoˇsi chod´ı s d´ıvkou; fakt, zˇ e hoch h ∈ H chod´ı s d´ıvkou d ∈ D zap´ısˇeme hχ d. Vznik´a tak relace χ ⊆ H × D. Relace χ −1 pak popisuje, kter´a d´ıvka chod´ı se kter´ym hochem.
2.4. Definice. Bud’ ρ relace mezi mnoˇzinami A, B, bud’ σ relace mezi mnoˇzinami B, C. Relace σ ◦ ρ (ˇcti ,,σ po ρ“) mezi mnoˇzinami A, C definovan´a pˇredpisem σ ◦ ρ = (a, c) ∃ (aρb ∧ bσ c) b∈B
se naz´yv´a sloˇzen´ı relac´ı ρ a σ . Zapamatujte si: aρc ⇔ ∃b∈B (aρb ∧ bσ c). V grafu relace σ ◦ ρ vede sˇipka mezi prvky a ∈ A a c ∈ C pr´avˇe tehdy, kdyˇz v grafu relace ρ vede sˇipka a − → b do alespoˇn jednoho prvku b ∈ B, na niˇz v grafu relace σ navazuje sˇipka b − → c. 4
0. Mnoˇziny, relace a zobrazen´ı
Pˇr´ıklady. 1. Pokraˇcujme v pˇredchoz´ım pˇr´ıkladu cˇ . 3. Nˇekter´e d´ıvky nav´ıc chod´ı se sv´ym psem; mnoˇzinu vˇsech takov´ych ps˚u oznaˇcme P. Fakt, zˇ e d´ıvka d ∈ D chod´ı se psem p ∈ P zap´ısˇeme dπ p. Vznik´a tak relace π ⊆ D × P. Pak π ◦ χ je relace, kter´a vyjadˇruje, kter´y hoch chod´ı se kter´ym psem. Vskutku, hoch h chod´ı se psem p pr´avˇe tehdy, kdyˇz existuje d´ıvka d, se kterou chod´ı jak hoch h, tak pes p. Napˇr´ıklad, necht’ H = { h 1 , h 2 }, D = { d1 , d2 }, P = { p1 , p2 }. Necht’ hoch h 1 chod´ı s d´ıvkou d2 , hoch h 2 nechod´ı s nik´ym a kaˇzd´a d´ıvka di chod´ı se sv´ym psem pi , i = 1, 2. M´ame H
h1 h2
d
1 D zd 2 χ
π
✲ p1 ✲ p2 P
a tedy π ◦ χ = {(h 1 , p2 )}. 2. Uvaˇzujme o relaci ,, “ sousedstv´ı zleva mezi cel´ymi cˇ´ısly z pˇr´ıkladu cˇ . 7. Pak a( ◦ )c pr´avˇe tehdy, kdyˇz c = a + 2.
2.5. Tvrzen´ı. Bud’ ρ relace mezi mnoˇzinami A, B. Pak plat´ı 1◦ . ρ ◦ id A = ρ; 1 . id B ◦ ρ = ρ. Bud’ nav´ıc σ relace mezi mnoˇzinami B, C. Pak plat´ı 2. (σ ◦ ρ)−1 = ρ −1 ◦ σ −1 . ˚ Dukaz. 1◦ a 1 jsou snadn´a; dok´azˇ eme tvrzen´ı 2. Jde o rovnost mnoˇzin, dokazujme kaˇzdou inkluzi zvl´asˇt’. ,,⊆“: Necht’ (c, a) ∈ (σ ◦ ρ)−1 . Pak (a, c) ∈ σ ◦ ρ, naˇceˇz existuje prvek b ∈ B takov´y, zˇ e aρb a bσ c. Potom ale cσ −1 b a bρ −1 a, takˇze (c, a) ∈ ρ −1 ◦ σ −1 . ,,⊇“: Cviˇcen´ı (staˇc´ı postupovat obr´acenˇe). Cviˇcen´ı. 1. Ukaˇzte, zˇ e (ρ −1 )−1 = ρ. 2. Necht’ρ ⊆ ρ , σ ⊆ σ . Dokaˇzte, zˇ e pak ρ ◦ σ ⊆ ρ ◦ σ .
3. Zobrazen´ı Velmi d˚uleˇzit´y je pojem zobrazen´ı mezi mnoˇzinami. Zde pojedn´ame jen o nˇekter´ych nejd˚uleˇzitˇejˇs´ıch vlastnostech. Dalˇs´ı uˇziteˇcn´e definice a tvrzen´ı jsou uvedeny v pˇredn´asˇce z matematick´e anal´yzy. Intuitivnˇe jde o pˇriˇrazen´ı hodnoty: kaˇzd´emu prvku z jedn´e mnoˇziny A se pˇriˇrad´ı pr´avˇe jedna ,,hodnota“ z druh´e mnoˇziny. Zobrazen´ı lze definovat jako speci´aln´ı pˇr´ıpad relace: Definice. Bud’te A, B mnoˇziny. Zobrazen´ı f z mnoˇziny A do mnoˇziny B je relace f ⊆ A × B, kter´a splˇnuje podm´ınku: Pro kaˇzd´y prvek a ∈ A existuje pr´avˇe jeden prvek b ∈ B takov´y, zˇ e plat´ı (a, b) ∈ f . Prvek b se pak obvykle oznaˇcuje f (a), nˇekdy tak´e f a . Naz´yv´a se hodnota zobrazen´ı f v prvku a nebo tak´e obraz prvku a pˇri zobrazen´ı f . Z´apisem f : A − → B vyjadˇrujeme, zˇ e f je zobrazen´ı z mnoˇziny A do mnoˇziny B. Jin´y z´apis: f f a −−→ b. M´ısto b = f (a) cˇ asto p´ısˇeme f : a #− → b nebo a #−−→ b. Zobrazen´ı f : A − → B je jednoznaˇcnˇe urˇceno zad´an´ım mnoˇzin A, B a hodnot f (a) pro kaˇzd´e a ∈ A. Zobrazen´ı f : A − → B, g : C − → D jsou si rovna pr´avˇe tehdy, kdyˇz A = C, B = D a pro kaˇzd´e a ∈ A plat´ı f (a) = g(a). Existuje zvl´asˇtn´ı kvantifik´ator ∃! s v´yznamem ,,existuje pr´avˇe jeden.“ Jinak rˇeˇceno: ,,existuje, a pokud existuj´ı dva, pak jsou stejn´e.“ Negac´ı je: ,,Neexistuje zˇ a´ dn´y nebo existuj´ı alespoˇn dva r˚uzn´e.“ Podm´ınku z definice zobrazen´ı pak m˚uzˇ eme zapsat jako
∀ ∃! (a, b) ∈
f.
(*)
a∈A b∈B
5
0. Mnoˇziny, relace a zobrazen´ı
Pˇr´ıklady. 1. Necht’ A = { ♥, ♠, ♦, ♣ }, B = { , }. Pak n´asleduj´ıc´ı pˇredpisy zad´avaj´ı jedno a to sam´e zobrazen´ı f : A − → B: (1) f = {(♥, ), (♠, ), (♦, ), (♣, )} ⊂ A × B. (2) f (♥) = , f (♠) = , f (♦) = , f (♣) = . (3) f : ♥ #− → , ♠ #− → , ♦ #− → , ♣ #− → . 2. Relace, kter´a vejci pˇriˇrazuje slepici, kter´a je snesla, je zobrazen´ı z mnoˇziny vˇsech slepiˇc´ıch vajec do mnoˇziny vˇsech slepic.
Identick´a relace na mnoˇzinˇe A je zobrazen´ı (identick´e zobrazen´ı) z mnoˇziny A do n´ı sam´e a znaˇc´ı → A. Plat´ı id A (a) = a pro kaˇzd´e a ∈ A. se id A : A − 3.1. Tvrzen´ı. Bud’te f : A − → B, g : B − → C dvˇe zobrazen´ı. Pak je relace g ◦ f zobrazen´ı A − →Ca (g ◦ f )(a) = g f (a) pro kaˇzd´e a ∈ A. (**) ˚ Dukaz. Bud’ a ∈ A libovoln´y prvek. Dokaˇzme existenci obrazu. Oznaˇcme c := g( f (a)) ∈ C. Pak plat´ı (a, c) ∈ g ◦ f , protoˇze prvek b := f (a) ∈ B splˇnuje (a, b) ∈ f a (b, c) ∈ g (proˇc?). Dokaˇzme jednoznaˇcnost obrazu. Je-li c ∈ C prvek takov´y, zˇ e (a, c) ∈ g ◦ f , pak podle definice existuje prvek b ∈ B takov´y, zˇ e (a, b) ∈ f a (b, c) ∈ g. Ale f je zobrazen´ı, a proto prvek b ∈ B takov´y, zˇ e (a, b) ∈ f existuje pr´avˇe jeden. Podobnˇe g je zobrazen´ı, a proto prvek c ∈ C takov´y, zˇ e (b, c) ∈ g existuje pr´avˇe jeden. Zobrazen´ı g ◦ f se naz´yv´a kompozice zobrazen´ı f, g. 3.2. Tvrzen´ı. (1) Budiˇz f : A − → B zobrazen´ı. Pak f ◦ id A = id B ◦ f = f. (2) Bud’te f : A − → B, g : B − → C, h : C − → D zobrazen´ı. Pak h ◦ (g ◦ f ) = (h ◦ g) ◦ f. Jak vypl´yv´a z (2), v´yraz h ◦ g ◦ f je jednoznaˇcn´y i pˇri vynechan´ych z´avork´ach. ˚ Dukaz. (1) Jak f ◦ id A , tak id B ◦ f jsou zobrazen´ı A − → B. Ukaˇzme, zˇ e pro kaˇzd´e a ∈ A nab´yvaj´ı stejn´ych hodnot. Pro libovoln´e a ∈ A ale m´ame ( f ◦ id A )(a) = f (id A (a)) = f (a) a podobnˇe (id B ◦ f )(a) = id B ( f (a)) = f (a). (2) Jak h ◦ (g ◦ f ), tak (h ◦ g) ◦ f jsou zobrazen´ → D.Ukaˇzme, zˇ e nab´yvaj´ ı A − ı stejn´ych hodnot pro kaˇzd´e a ∈ A. Pro libovoln´ y prvek a ∈ A m´ a me h ◦ ◦ f = h ◦ f = h(g( f (a))) = (g ) (a) (g )(a) (h ◦ g) f (a) = (h ◦ g) ◦ f (a). Cviˇcen´ı. Proˇc plat´ı kaˇ zd´a z rovnost´ ı uveden´ ych v d˚ukazu? Napˇr´ıklad rovnost h ◦ (g ◦ f ) (a) = h (g ◦ f )(a) je v´ysledkem dosazen´ı h za g, g ◦ f za f a a za a do formule (∗∗) definuj´ıc´ı skl´ad´an´ı ,,◦.“ Vysvˇetlete zb´yvaj´ıc´ı rovnosti.
Bud’ d´ano zobrazen´ı f : A − → B. Je-li prvek b ∈ B obrazem prvku a ∈ A, pak se prvek a naz´yv´a vzor prvku b pˇri zobrazen´ı f . Mnoˇzina vˇsech vzor˚u prvku b ∈ B pˇri zobrazen´ı f se znaˇc´ı f −1 {b}. Zapamatujte si formuli: f (a) = b ⇔ a ∈ f −1 (b). Zat´ımco obraz obecn´eho prvku a ∈ A vˇzdy existuje a je jedin´y, vzor prvku b ∈ B obecnˇe existovat nemus´ı a nemus´ı b´yt ani jedin´y. V souvislosti s t´ım uved’me dalˇs´ı definice. 6
0. Mnoˇziny, relace a zobrazen´ı
3.3. Definice. Zobrazen´ı f : A − → B se naz´yv´a surjektivn´ı (ˇcili surjekce), jestliˇze m´a kaˇzd´y prvek b ∈ B alespoˇn jeden vzor v A:
∀ ∃
b = f (a).
b∈B a∈A
Zobrazen´ı f : A − → B se naz´yv´a injektivn´ı (ˇcili injekce) neboli prost´e, jestliˇze m´a kaˇzd´y prvek b ∈ B nejv´ysˇe jeden vzor v A: ∀ f (a1 ) = f (a2 ) ⇒ a1 = a2 . a1 ,a2 ∈A
Tud´ızˇ , zobrazen´ı f je surjektivn´ı pr´avˇe tehdy, kdyˇz je pro kaˇzd´e b ∈ B mnoˇzina f −1 {b} nepr´azdn´a. Hovoˇr´ıme t´ezˇ o zobrazen´ı mnoˇziny A na mnoˇzinu B. Zobrazen´ı f je injektivn´ı pr´avˇe tehdy, kdyˇz je pro kaˇzd´e b ∈ B mnoˇzina f −1 {b} nejv´ysˇe jednoprvkov´a. Pˇr´ıklady. 1. { ♥, ♠, ♦, ♣ } − → { , }, f (♥) = , f (♠) = , f (♦) = , f (♣) = . Zobrazen´ı f je surjektivn´ı (oba prvky , ∈ B maj´ı vzor), ale nen´ı injektivn´ı (napˇr. m´a dva vzory: ♠ a ♣). 2. Vrat’me se k relaci χ mezi mnoˇzinou H hoch˚u a mnoˇzinou D d´ıvek. Tato relace je zobrazen´ım, pokud kaˇzd´y hoch h ∈ H chod´ı s pr´avˇe jednou d´ıvkou d ∈ D. Toto zobrazen´ı je injektivn´ı, pokud kaˇzd´a d´ıvka chod´ı s nejv´ysˇe jedn´ım hochem a je surjektivn´ı, pokud kaˇzd´a d´ıvka chod´ı s alespoˇn jedn´ım hochem. Cviˇcen´ı. Bud’te f : A − → B, g : B − → C dvˇe zobrazen´ı. (1) Je-li zobrazen´ı g ◦ f injektivn´ı, pak je i zobrazen´ı f injektivn´ı. (2) Je-li zobrazen´ı g ◦ f surjektivn´ı, pak je i zobrazen´ı g surjektivn´ı. Dokaˇzte. Cviˇcen´ı. Bud’te f : A − → B, g : A − → B dvˇe zobrazen´ı. Dokaˇzte, zˇ e plat´ı: (1) Bud’ h : B − → C injektivn´ı zobrazen´ı takov´e, zˇ e h ◦ f = h ◦ g. Pak f = g. Jin´ymi slovy, injektivn´ım zobrazen´ım lze kr´atit zleva. (2) Bud’ h : D − → A surjektivn´ı zobrazen´ı takov´e, zˇ e f ◦ h = g ◦ h. Pak f = g. Jin´ymi slovy, surjektivn´ım zobrazen´ım lze kr´atit zprava.
Je-li A ⊆ X podmnoˇzina, pak je ι A = {(a, a) | a ∈ A} zobrazen´ı, kter´e prvku a ∈ A pˇriˇrad´ı t´yzˇ prvek a ∈ X : ι AX (a) = a. Zobrazen´ı ι AX je injektivn´ı (dokaˇzte) a naz´yv´a se vloˇzen´ı podmnoˇziny. Je-li f :X− → Y nˇejak´e zobrazen´ı, pak kompozice f ◦ ι AX pˇredstavuje zobrazen´ı A − → Y , kter´e se naz´yv´a restrinkce zobrazen´ı f na podmnoˇzinu A a znaˇc´ı se f | A : ι
f
f | A : A −−AX −→ X −−→ Y. Vˇsimnˇete si, zˇ e restrinkce je d´ana t´ymˇz pˇredpisem a #− → f (a) jako f . Je-li mnoˇzina Y obsaˇzena v jin´e mnoˇzinˇe Z , pak existuje i kompozice ιY Z ◦ f : X − → Z . V tomto pˇr´ıpadˇe ˇr´ık´ame, zˇ e f vznik´a rozˇs´ıˇren´ım oboru hodnot, ale zvl´asˇtn´ı dohodnut´e oznaˇcen´ı neexistuje, naopak, b´yv´a zvykem rozd´ıl v oborech hodnot ignorovat. Kaˇzd´e zobrazen´ı f : X − → Y vznik´a rozˇs´ıˇren´ım oboru hodnot nˇekter´eho surjektivn´ıho zobrazen´ı. Vskutku, oznaˇcme f X = { f (x) | x ∈ X } mnoˇzinu vˇsech hodnot zobrazen´ı f . Pak je f¯ : X − → f X, x #− → f (x) surjektivn´ı zobrazen´ı a plat´ı f = ι f X,X ◦ f¯ . Pro koneˇcn´e mnoˇziny plat´ı tzv. Dirichlet˚uv z´asuvkov´y princip: Um´ıst´ıme-li n pˇredmˇet˚u do m z´asuvek, pˇriˇcemˇz m < n, pak existuje z´asuvka, kter´a obsahuje alespoˇn dva pˇredmˇety. Matematicky lze tento princip zformulovat jako n´asleduj´ıc´ı tvrzen´ı: 3.4. Tvrzen´ı. Bud’ f : A − → B zobrazen´ı mezi koneˇcn´ymi mnoˇzinami. Bud’ m poˇcet prvk˚u mnoˇziny A a n poˇcet prvk˚u mnoˇziny B. Je-li m > n, pak f nen´ı injektivn´ı. 7
0. Mnoˇziny, relace a zobrazen´ı
D˚ukaz povedeme matematickou indukc´ı. Jde o zn´am´y trik, umoˇznˇ uj´ıc´ı dokazovat tvrzen´ı (n) z´avisl´e na nˇejak´em pˇrirozen´em cˇ´ısle n. Dok´azˇ eme-li (1) platnost (1), (2) indukˇcn´ı krok: z platnosti (i) pro vˇsechna i < n plyne platnost (n), lze tvrzen´ı (n) povaˇzovat za dok´azan´e pro vˇsechna n. Vskutku, pˇripust’me, zˇ e existuje m takov´e, zˇ e (m) neplat´ı. Pak existuje nejmenˇs´ı pˇrirozen´e cˇ´ıslo m takov´e, zˇ e (m) neplat´ı. (Existence takov´eho m je intuitivnˇe zˇrejm´a, ale d˚ukaz nepod´av´ame; v pˇredn´asˇce z teorie mnoˇzin bude platnost podobn´eho tvrzen´ı jednou z podm´ınek definuj´ıc´ıch mnoˇzinu pˇrirozen´ych cˇ´ısel.) Je-li m = 1, pak dost´av´ame spor s tvrzen´ım (1). Je-li m > 1, pro vˇsechna i splˇnuj´ıc´ı 1 ≤ i < m tvrzen´ı plat´ı (m bylo minim´aln´ı pro nˇezˇ neplat´ı), a proto podle (2) plat´ı i pro m, opˇet spor.
˚ Dukaz. Dokazujme matematickou indukc´ı vzhledem k cˇ´ıslu n. Je-li n = 1, m´ame v mnoˇzinˇe B jedin´y prvek, na kter´y se mus´ı zobrazit vˇsech m > 1 prvk˚u mnoˇziny A, tvrzen´ı tedy plat´ı. Indukˇcn´ı krok: Necht’tvrzen´ı plat´ı pro vˇsechna i < n. Ukaˇzme, zˇ e pak plat´ı i pro n. Uvaˇzujme tedy o zobrazen´ı f z m-prvkov´e mnoˇziny A do n-prvkov´e mnoˇziny B. Vyberme libovoln´y prvek b ∈ B. Prvek b m´a vzor f −1 {b}. Rozliˇsujme tˇri pˇr´ıpady: a) M´a-li vzor f −1 {b} v´ıce neˇz jeden prvek, nen´ı zobrazen´ı f injektivn´ı a jsme hotovi. b) Nem´a-li f −1 {b} zˇ a´ dn´y prvek, m˚uzˇ eme f povaˇzovat za zobrazen´ı do mnoˇziny B = B \ {b}, kter´a m´a n − 1 prvek. Pak m > n > n − 1, naˇceˇz podle indukˇcn´ıho pˇredpokladu f nen´ı injektivn´ı jako zobrazen´ı do B , a proto ani jako zobrazen´ı do B. c) Nakonec, necht’ m´a mnoˇzina f −1 {b} pr´avˇe jeden prvek, kter´y oznaˇc´ıme a. Oznaˇcme B = B \ {b}, A = A \ {a}. Zobrazen´ı f zobrazuje prvky podmnoˇziny A do podmnoˇziny B . Skuteˇcnˇe, v opaˇcn´em pˇr´ıpadˇe by existoval prvek a ∈ A takov´y, zˇ e f (a ) ∈ B , ale pak nutnˇe f (a ) = b, pˇriˇcemˇz b m´a jedin´y vzor, a sice a, takˇze a = a, spor. Dost´av´ame tedy zobrazen´ı m − 1-prvkov´e mnoˇziny A do n − 1-prvkov´e mnoˇziny B , vlastnˇe restrinkci f | A . Pˇritom bylo-li m > n, je m − 1 > n − 1, a proto zobrazen´ı f | B nen´ı injektivn´ı podle indukˇcn´ıho pˇredpokladu. To znamen´a, zˇ e ani f nen´ı injektivn´ı. Cviˇcen´ı. Jak´e mus´ı b´yt n, abychom mˇeli jistotu, zˇ e mezi n kˇreˇcky se najdou dva, kteˇr´ı maj´ı narozeniny ve stejn´y den.
4. Bijekce Zobrazen´ı f : A − → B se naz´yv´a bijektivn´ı cˇ ili bijekce, je-li injektivn´ı a surjektivn´ı souˇcasnˇe Tud´ızˇ , zobrazen´ı f je bijektivn´ı tehdy a jen tehdy, m´a-li kaˇzd´y prvek b ∈ B pr´avˇe jeden vzor (je-li pro kaˇzd´e b ∈ B mnoˇzina f −1 {b} jednoprvkov´a). 4.1. Tvrzen´ı. Bud’ f : A − → B zobrazen´ı. N´asleduj´ıc´ı podm´ınky jsou ekvivalentn´ı: (1) f je bijektivn´ı; (2) existuje zobrazen´ı g : B − → A takov´e, zˇ e g ◦ f = id A ,
f ◦ g = id B .
V kladn´em pˇr´ıpadˇe existuje jedin´e zobrazen´ı g s vlastnostmi (2) a je opˇet bijektivn´ı. Zobrazen´ı g z pˇredchoz´ıho tvrzen´ı se naz´yv´a inverzn´ı k f a znaˇc´ı se f −1 . ˚ Dukaz. Dokaˇzme implikaci ,,(1) ⇒ (2).“ Bud’ f bijektivn´ı. Oznaˇcme g = f −1 ⊆ B × A relaci opaˇcnou k relaci f ⊆ A × B. Snadno se vid´ı, zˇ e n´asleduj´ıc´ı v´yroky jsou ekvivalentn´ı: (1) Zobrazen´ı f je bijektivn´ı; (2) Pro kaˇzd´y prvek b ∈ B existuje pr´avˇe jeden prvek a ∈ A takov´y, zˇ e b = f (a); 8
0. Mnoˇziny, relace a zobrazen´ı
(3) Pro kaˇzd´y prvek b ∈ B existuje pr´avˇe jeden prvek a ∈ A takov´y, zˇ e (a, b) ∈ f ; (4) Pro kaˇzd´y prvek b ∈ B existuje pr´avˇe jeden prvek a ∈ A takov´y, zˇ e (b, a) ∈ g; (5) Relace g je zobrazen´ı B − → A. Zobrazen´ı g : B − → A je definov´ano pˇredpisem: g(b) = a ⇔ b = f (a). Ovˇeˇrme rovnost g ◦ f = id A . Zˇrejmˇe jde o dvˇe zobrazen´ı A − → A. Pro kaˇzd´e a ∈ A pak pˇri oznaˇcen´ı b = f (a) m´ame (g ◦ f )(a) = g( f (a)) = g(b) = a = id A (a), coˇz se mˇelo dok´azat. Podobnˇe f ◦ g = id B (proved’te samostatnˇe). Dokaˇzme implikaci ,,(2) ⇒ (1).“ Necht’ existuje zobrazen´ı g : B − → A takov´e, zˇ e g ◦ f = id A a f ◦ g = id B . Ukaˇzme, zˇ e f je surjektivn´ı. Bud’ b ∈ B libovoln´e. Poloˇzme a = g(b), potom f (a) = f (g(b)) = ( f ◦ g)(b) = id B (b) = b, takˇze a je vzor prvku b pˇri zobrazen´ı f a f je surjektivn´ı. Ukaˇzme, zˇ e f je injektivn´ı. Bud’te a1 , a2 ∈ A dva prvky takov´e, zˇ e f (a1 ) = f (a2 ). Potom g( f (a1 )) = g( f (a2 )), ale g( f (a1 )) = (g ◦ f )(a1 ) = id A (a1 ) = a1 a podobnˇe g( f (a2 )) = a2 , naˇceˇz a1 = a2 a f je injektivn´ı. D´ale je tˇreba dok´azat jednoznaˇcnost zobrazen´ı g : B − → A s vlastnostmi g ◦ f = id A a f ◦ g = id B . → A jin´e zobrazen´ı, pro nˇezˇ plat´ı g ◦ f = id A a f ◦ g = id B . Bud’ b ∈ B libovoln´y prvek; Bud’ g : B − ukaˇzme, zˇ e g(b) = g (b). M´ame ovˇsem f (g(b)) = ( f ◦ g)(b) = id B (b) = ( f ◦ g )(b) = f (g (b)). Ale f je injektivn´ı podle jiˇz dok´azan´e implikace ,,(2) ⇒ (1),“ naˇceˇz g(b) = g (b). Vzhledem k libovoln´e volbˇe prvku b dost´av´ame rovnost g = g . Nakonec je tˇreba dok´azat, zˇ e i zobrazen´ı g je bijektivn´ı. To ovˇsem plyne z jiˇz dok´azan´e implikace ,,(2) ⇒ (1),“ zamˇen´ıme-li mezi sebou f ↔ g a A ↔ B. 4.2. Pˇr´ıklad. Zobrazen´ı f : { ♥, ♦ } − → { ♠, ♣ }, ♥ #− → ♠, ♦ #− → ♣, je bijekce. Inverzn´ı je zobrazen´ı g = f −1 : { ♠, ♣ } − → { ♥, ♦ }, ♠ #− → ♥, ♣ #− → ♦. (Invertov´an´ı bijekce spoˇc´ıv´a v obracen´ı sˇipek.)
4.3. Tvrzen´ı. Bud’ f : A − → B bijektivn´ı zobrazen´ı. Pak ( f −1 )−1 = f . ˚ Dukaz. Je potˇreba dok´azat, zˇ e f je inverzn´ı zobrazen´ı k f −1 . K tomu pouˇzijeme pˇredchoz´ı Tvrzen´ı 4.1(2), kam dosad´ıme f za g a f −1 za f a rovnˇezˇ A za B a B za A. Obdrˇz´ıme podm´ınku f −1 ◦ f = id A a f ◦ f −1 = id B , kter´a ovˇsem plat´ı, protoˇze f −1 je inverzn´ı k f . 4.4. Tvrzen´ı. Bud’te f : A − → B, g : B − → C bijekce. Potom (1) g ◦ f : A − → C je bijekce; (2) (g ◦ f )−1 = f −1 ◦ g −1 . ˚ Dukaz. Jsou-li f a g bijekce, pak maj´ı inverze f −1 a g −1 , pro kter´e plat´ı f ◦ f −1 = id B , f −1 ◦ f = id A , −1 g ◦ g = idC , g −1 ◦ g = id B . Dokaˇzme (1). Podle Tvrzen´ı 4.1 staˇc´ı naj´ıt zobrazen´ı inverzn´ı k g ◦ f . Vhodn´ym kandid´atem je zobrazen´ı h = f −1 ◦ g −1 : C − → A. A skuteˇcnˇe, plat´ı h ◦(g ◦ f ) = f −1 ◦ g −1 ◦ g ◦ f = f −1 ◦id B ◦ f = −1 f ◦ f = id A . Podobnˇe (g ◦ f ) ◦ h = g ◦ f ◦ f −1 ◦ g −1 = g ◦ id B ◦ g −1 = g ◦ g −1 = idC . Tud´ızˇ , g ◦ f m´a inverzi, a proto je bijektivn´ı podle Tvrzen´ı 4.1. (2) V´ypoˇcet proveden´y v cˇ a´ sti (1) souˇcasnˇe ukazuje, zˇ e (g ◦ f )−1 = h = f −1 ◦ g −1 . 4.5. Tvrzen´ı. Bud’te A, B libovoln´e koneˇcn´e mnoˇziny maj´ıc´ı shodnˇe po n prvc´ıch. Bud’ f : A − → B injektivn´ı zobrazen´ı. Ukaˇzte, zˇ e f je bijektivn´ı. ˚ Dukaz. Dokazuje se indukc´ı vzhledem k cˇ´ıslu n. Pro n = 1 je tvrzen´ı zˇrejm´e. Indukˇcn´ı krok: vyberme libovolnˇe prvek a ∈ A a oznaˇcme b = f (a). Uvaˇzujme o mnoˇzin´ach A = A \ {a} a B = B \ { f (a)}. Zobrazen´ı f zobrazuje prvky podmnoˇziny A do podmnoˇziny B . Vskutku, pˇripust’me naopak, zˇ e se nˇekter´y prvek a ∈ A zobraz´ı vnˇe B , tedy do prvku b, pak ale f (a ) = b = f (a), naˇceˇz a = a v d˚usledku injektivity zobrazen´ı f , spor. Pˇritom B i A maj´ı shodnˇe n − 1 prvk˚u, zobrazen´ı f | A : → B je injektivn´ı stejnˇe jako f , a proto podle indukˇcn´ıho pˇredpokladu je f | A : A − → B A − 9
0. Mnoˇziny, relace a zobrazen´ı
surjektivn´ı. Vˇsechny prvky z B tedy maj´ı sv´e vzory, zat´ımco prvek b ∈ B \ B m´a za vzor a, tud´ızˇ f :A− → B je surjektivn´ı. 5. Relace ekvivalence 5.1. Definice. Bud’ ρ ⊆ A × A relace na mnoˇzinˇe A. Relace ρ se naz´yv´a – reflexivn´ı, jestliˇze pro kaˇzd´e a ∈ A plat´ı aρa; – symetrick´a, jestliˇze plat´ı implikace aρb ⇒ bρa; – tranzitivn´ı, jestliˇze plat´ı implikace (aρb ∧ bρc) ⇒ aρc. Pˇr´ıklady. 1. Identick´a relace id A je reflexivn´ı, symetrick´a i tranzitivn´ı. 2. Relace ,,≤“ neostr´eho uspoˇra´ d´an´ı re´aln´ych cˇ´ısel je tranzitivn´ı a reflexivn´ı. 3. Relace ,,<“ ostr´eho uspoˇra´ d´an´ı re´aln´ych cˇ´ısel je pouze tranzitivn´ı. Cviˇcen´ı. Graf relace na mnoˇzinˇe m˚uzˇ eme kreslit tak, zˇ e m´ısto dvou kopi´ı mnoˇziny A zobraz´ıme jen jednu a sˇipky vedeme mezi jej´ımi prvky. Jak se pozn´a graf reflexivn´ı resp. symetrick´e resp. tranzitivn´ı relace? Cviˇcen´ı. Najdˇete chybu v n´asleduj´ıc´ım ,,d˚ukazu“ nepravdiv´eho tvrzen´ı, zˇ e kaˇzd´a symetrick´a a tranzitivn´ı relace ρ je reflexivn´ı: ,,Je-li aρb, pak ze symetrie plyne bρa, naˇceˇz z tranzitivity plyne aρa.“
5.2. Definice. Reflexivn´ı, symetrick´a a tranzitivn´ı relace se naz´yv´a relace ekvivalence (nebo prostˇe ekvivalence, pokud nem˚uzˇ e doj´ıt k z´amˇenˇe s logickou ekvivalenc´ı). Pˇr´ıklady. 1. Identick´a relace id A je ekvivalence na mnoˇzinˇe A. 2. Bud’ V nˇejak´a mnoˇzina vajec. Zaved’me relaci ς pˇredpisem: v1 ς v2 pr´avˇe tehdy, kdyˇz vejce v1 a v2 poch´azej´ı od stejn´e slepice. Pak ς je ekvivalence. Probl´em k rˇ eˇsen´ı. Bud’te ρ, σ relace ekvivalence na mnoˇzinˇe A. Dokaˇzte, zˇ e σ ◦ ρ je relace ekvivalence pr´avˇe tehdy, kdyˇz σ ◦ ρ = ρ ◦ σ .
Relace ekvivalence se hojnˇe vyskytuj´ı v matematice i v realitˇe. Jsou vˇzdy spojeny s takzvan´ymi rozklady. 5.3. Definice. Rozklad na mnoˇzinˇe A je syst´em nepr´azdn´ych podmnoˇzin mnoˇziny A, zvan´ych tˇr´ıdy rozkladu, splˇnuj´ıc´ı podm´ınku, zˇ e kaˇzd´y prvek x ∈ A leˇz´ı v pr´avˇe jedn´e z tˇr´ıd. Tˇr´ıda rozkladu R obsahuj´ıc´ı prvek x se obvykle oznaˇcuje [x] R nabo prostˇe R, je-li rozklad zˇrejm´y z kontextu. Pˇr´ıklady. 1. Necht’ A = { ♥, ♠, ♦, ♣ }, U = { ♥, ♦ }, V = { ♠, ♣ }. Pak { U, V } je rozklad na mnoˇzinˇe A, protoˇze kaˇzd´y z prvk˚u ♥, ♠, ♦, ♣ mnoˇziny A leˇz´ı v pr´avˇe jedn´e z mnoˇzin U, V : U
V
♥ ♦
♠ ♣
Pˇritom [♥] = U , [♠] = V , [♦] = U , [♣] = V . ˇ 2. Mnoˇzinu vˇsech obc´ı Cesk´ e republiky lze rozloˇzit na tˇr´ıdy, tvoˇren´e obcemi jednotliv´ych kraj˚u (za ˇ pˇredpokladu, zˇ e kaˇzd´a obec v Cesk´ e republice leˇz´ı v pr´avˇe jednom kraji). Pak [Opava] oznaˇcuje mnoˇzinu vˇsech obc´ı leˇz´ıc´ıch v t´emˇze kraji jako Opava. Pˇritom [Opava] = [V´avrovice], ale [Opava] = [Humpolec]. 3. Populace kura dom´ac´ıho m˚uzˇ e b´yt rozloˇzena na dvˇe tˇr´ıdy: kohouty a slepice. Cviˇcen´ı. 1. Naleznˇete vˇsechny rozklady na mnoˇzinˇe A = { 1, 2, 3 } (je jich pˇet). 2. Dvˇe mnoˇziny A, B se naz´yvaj´ı disjunktn´ı, je-li A ∩ B = ∅. Ukaˇzte, zˇ e kaˇzd´e dvˇe r˚uzn´e tˇr´ıdy rozkladu jsou disjunktn´ı.
10
0. Mnoˇziny, relace a zobrazen´ı
5.4. Tvrzen´ı. Bud’ d´an rozklad na mnoˇzinˇe A na tˇr´ıdy [a], a ∈ A. Bud’ ρ relace na mnoˇzinˇe A zadan´a pˇredpisem xρy ⇔ [x] = [y], tj. xρy pr´avˇe kdyˇz x, y leˇz´ı v jedn´e a t´ezˇ e tˇr´ıdˇe rozkladu. Pak ρ je ekvivalence na A. ˚ Dukaz. Tvrzen´ı je vlastnˇe d˚usledkem toho, zˇ e rovnost ‘=’ je relace ekvivalence. Detailnˇe: Pro kaˇzd´e x ∈ A plat´ı xρx, protoˇze [x] = [x]. Tud´ızˇ , ρ je reflexivn´ı. Pro libovoln´e prvky x, y ∈ A, pro nˇezˇ xρy, m´ame [x] = [y], naˇceˇz [y] = [x], a tedy yρx. Tud´ızˇ , ρ je symetrick´a. Pro libovoln´e prvky x, y, z ∈ A, pro nˇezˇ xρy a yρz m´ame [x] = [y] = [z], a tedy xρz. Tud´ızˇ , ρ je tranzitivn´ı. Pˇr´ıklady. Ve stejnˇe cˇ´ıslovan´ych pˇredchoz´ıch pˇr´ıkladech plat´ı: 1. ♥ρ♦, ♠ρ♣. 2. Obec a je ekvivalentn´ı obci b pr´avˇe tehdy, kdyˇz obˇe leˇz´ı v t´emˇze kraji. 3. Dva exempl´aˇre kura dom´ac´ıho jsou ekvivalentn´ı pr´avˇe tehdy, kdyˇz jsou stejn´eho pohlav´ı.
Kaˇzd´a ekvivalence poch´az´ı z rozkladu. Pˇr´ısluˇsn´y rozklad nen´ı tˇezˇ k´e sestrojit. 5.5. Tvrzen´ı. Bud’ ρ ekvivalence na mnoˇzinˇe A. Oznaˇcme [a]ρ = { x ∈ A|aρx },
a ∈ A,
mnoˇzinu vˇsech prvk˚u ekvivalentn´ıch s prvkem a. Pak je syst´em {[a]ρ | a ∈ A} rozklad na A. ˚ Dukaz. Pro jednoduchost vˇsude vynech´avejme index ρ. Ukaˇzme, zˇ e kaˇzd´y prvek x ∈ A leˇz´ı v pr´avˇe jedn´e tˇr´ıdˇe. Pˇredevˇs´ım kaˇzd´y prvek x leˇz´ı v tˇr´ıdˇe [x]. Skuteˇcnˇe, x ∈ [x], protoˇze xρx (reflexivita ekvivalence). D´ale ukaˇzme, zˇ e kaˇzd´a tˇr´ıda, v n´ızˇ leˇz´ı x, je rovna tˇr´ıdˇe [x]. Pˇredpokl´adejme, zˇ e x ∈ [y] a dokaˇzme, zˇ e pak [y] = [x]. Nejprve dokaˇzme inkluzi [x] ⊆ [y]. Bud’ u ∈ [x] libovoln´e, pak uρx. M´ame ale x ∈ [y], takˇze xρy. Potom z tranzitivity relace ρ plyne, zˇ e uρy, naˇceˇz u ∈ [y]. Tud´ızˇ , [x] ⊆ [y]. Inkluzi [x] ⊇ [y] dokaˇzte jako cviˇcen´ı. Vid´ıme, zˇ e prvky x, y leˇz´ı v jedn´e a t´ezˇ e tˇr´ıdˇe rozkladu pr´avˇe tehdy, kdyˇz xρy. 5.6. Definice. Rozklad z Tvrzen´ı 5.5 se naz´yv´a rozklad podle ekvivalence ρ. Mnoˇzina vˇsech tˇr´ıd tohoto rozkladu se znaˇc´ı A/ρ = {[a] | a ∈ A}. Probl´em k rˇ eˇsen´ı. Bud’ ρ ekvivalence na mnoˇzinˇe A, bud’ σ ekvivalence na mnoˇzinˇe B. Zaved’me relaci τ na mnoˇzinˇe C = A × B pˇredpisem (a1 , b1 )γ (a2 , b2 ) ⇔ a1 ρa2 ∧ b1 σ b2 . Ukaˇzte, zˇ e γ je relace ekvivalence. Ukaˇzte, zˇ e tˇr´ıdy ekvivalence γ jsou pr´avˇe mnoˇziny U × V , kde U je tˇr´ıda ekvivalence ρ a V je tˇr´ıda ekvivalence σ . Cviˇcen´ı. Bud’ ρ relace na mnoˇzinˇe A. 1. Ukaˇzte, zˇ e ρ je reflexivn´ı pr´avˇe tehdy, kdyˇz plat´ı id A ⊆ ρ. 2. Ukaˇzte, zˇ e ρ je symetrick´a pr´avˇe tehdy, kdyˇz plat´ı ρ = ρ −1 . 3. Ukaˇzte, zˇ e ρ je tranzitivn´ı pr´avˇe tehdy, kdyˇz plat´ı ρ ◦ ρ ⊆ ρ.
11
0. Mnoˇziny, relace a zobrazen´ı
Syst´em mnoˇzin obecnˇe je mnoˇzina, jej´ızˇ prvky jsou zase mnoˇziny. Bud’ I nˇejak´a mnoˇzina (naz´yv´a se indexov´a mnoˇzina), pro kaˇ zd´e i ∈ I bud’ Ai zase nˇejak´a mnoˇzina. Pak {Ai | i ∈ I } je syst´em mnoˇzin. Znaˇc´ı se t´ezˇ {Ai }i∈I . Symbolem i∈I Ai oznaˇcujeme mnoˇzinu vˇsech prvk˚u, kter´e leˇz´ı v alespoˇn jedn´e z mnoˇzin Ai . Je to opˇet mnoˇzina a naz´y v´a se sjednocen´ı syst´emu mnoˇzin {Ai }i∈I . Symbolem i∈I Ai oznaˇcujeme mnoˇzinu vˇsech prvk˚u, kter´e leˇz´ı ve vˇsech mnoˇzin´ach Ai . Je to opˇet mnoˇzina a naz´yv´a se pr˚unik syst´emu mnoˇzin {Ai }i∈I . Cviˇcen´ı. Syst´em { Ai | i ∈ I } podmnoˇzin mnoˇziny A je rozklad pr´avˇe tehdy, kdyˇz plat´ı podm´ınky (i) Kaˇzd´ a podmnoˇzina Ai je nepr´azdn´a; (ii) A = i∈I Ai ; (iii) maj´ı-li dvˇe tˇr´ıdy nepr´azdn´y pr˚unik, Ai ∩ A j = ∅, pak se rovnaj´ı, Ai = A j .
12
