text ke studiu matematiky v oboru učitelství pro první stupeň základní školy zejména jako opora pro kombinované studium

UNIVERZITA JANA EVANGELISTY PURKYNĚ Pedagogická fakulta

Binární relace text ke studiu matematiky v oboru učitelství pro první stupeň základní školy zejména jako opora pro kombinované studium Doc. Paed Dr. Miroslav Bělík, CSc.

2005

2

Obsah : 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12.

Kartézský součin . . . . . Binární relace . . . . . Grafické znázornění binárních relací Inverzní relace . . . . . . Vlastnosti binárních relací . . . Relace typu ekvivalence . . . Rozklad množiny . . . . . Relace typu uspořádání . . . Speciální typy uspořádání . . . Uspořádaná množina . . . . Relace typu zobrazení . . . . Speciální typy zobrazení . . .

Literatura

.

.

.

.

.

.

.

. . . . . . . . . . . .

. . . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

. . . . . . . . . . . .

2 3 5 8 9 14 16 20 21 24 27 30

.

.

.

36

1. Kartézský součin množin Uspořádaná dvojice prvků a , b se obvykle zapisuje [ a , b ] , a je první složkou, b druhou složkou této uspořádané dvojice. [a,b]

uspořádaná dvojice prvků a , b

druhá složka uspořádané dvojice první složka uspořádané dvojice Pro zjednodušení zápisu budeme často místo [ a , b ] používat stručnějšího zápisu ab , pokud nebude hrozit nebezpečí nesprávného chápání zápisu.

1.1. Zapište množinu všech uspořádaných dvojic, jejichž první složkou je prvek množiny { b , c , d } a druhou složkou prvek množiny { a , o } . Výsledek : { [ b , a ] , [ b , o ] , [ c , a ] , [ c , o ] , [ d , a ] , [ d , o ] }. Množina všech uspořádaných dvojic, jejichž první složkou je prvek množiny A a druhou složkou prvek množiny B , se nazývá kartézský součin množin A , B a zapisuje se A × B . Řešení přípravné úlohy nám pomohlo vytvořit si představu a formulovat definici pojmu kartézský součin dvou množin :

A × B = { [x,y]: x∈ ∈ A ∧ y∈ ∈B } Uvedený symbolický zápis definice kartézského součinu čteme takto: Kartézský součin množin A , B je množina všech uspořádaných dvojic [ x, y ] , pro které platí, že x je prvkem množiny A a y je prvkem množiny B .

1.2.

Zapište výčtem prvků, tj. výčtem uspořádaných dvojic kartézský součin množin C , D , jestliže

3

a) C = { 1; 2; 3; 4 }, D = { 2; 3 } b) C = { a } , D = { 7; 8; 9 } c) C = ∅ , D = { 3 } d) C = { a, b } , D = C Řešení : a) C × D = { [1;2], [1;3], [2;2], [2;3], [3;2], [3;3], [4;2], [4;3] } b) C × D = { [a,7], [a,8], [a,9] }, stručnější zápis: { a7, a8, a9 } c) C × D = ∅ , nelze utvořit ani jednu dvojici d) C × D = { aa, ab, ba, bb }

1.3. Zapište výčtem prvků kartézský součin M × M , jestliže M je a) tříprvková množina, b) dvouprvková množina, c) jednoprvková množina. Prvky množiny M volte v jednotlivých případech sami. Výsledky : a) Nechť M = { a , b, c } , pak M × M = { aa , ab, ac, ba, bb, bc, ca, cb, cc } b) Nechť M = { a , b } , pak M × M = { [a,a], [a,b], [b,a], [b,b] } c) Nechť M = { a } , pak M × M = { [a,a] } d) Nechť M = { a , b, c, d } , pak M × M = { aa , ab, ac, ad, ba, bb, bc, bd, ca, cb, cc, cd, da,db,dc,dd }

1.4. Rozhodněte a zdůvodněte, která z uspořádaných dvojic [a,e], [a,f], [b,b], [c,c], [d,d], [a,a], [g,h], [e,a], [e,c], [c,e] do kartézského součinu A × B patří a která do něho nepatří, jestliže A = { a, b, c } , B = { b, c, d, e }. Řešení : Podle definice kartézského součinu platí, že [a,e] ∈ A × B , protože a∈ ∈A a e∈ ∈B , dále platí, že [a,f] ∉ A × B, protože f ∉ B , [b,b] ∈ A × B, protože b∈ ∈A i b∈ ∈B a z podobných důvodů platí, že [c,c] ∈ A × B , [d,d] ∉ A × B , [a,a] ∉ A × B , [g,h] ∉ A × B , [e,a] ∉ A × B , [e,c] ∉ A × B , [c,e] ∈ A × B Určete, kolik prvků (uspořádaných dvojic) má kartézský součin A × B , jestliže a) A má 4 prvky, B má 5 prvků, b) A má 8 prvků, B má 7 prvků, c) A má r prvků, B má s prvků, ( r, s jsou libovolná přirozená čísla ).

1.5.

Výsledky : a) 20 b) 56

c) r ⋅ s

2. Binární relace Přípravná úloha :

2.1. Uveďme případ rodiny s těmito členy: matka, otec, syn Pavel, syn David, dcera Helena. Pro naše účely je označíme malými písmeny: matka ... m , otec ... o , Pavel ... p , David ... d , Helena ... h . Budeme tedy pracovat s množinou { m, o, p, d, h }, označme ji M . Uveďte všechny uspořádané dvojice [ x , y ] prvků x, y množiny M, pro které platí, že x je synem y .

4

Řešení : Zřejmě se jedná o tyto uspořádané dvojice: [ p , m ] , protože „ p je synem m “ tj. Pavel je synem matky , [ p , o ] , protože „ p je synem o “ tj. Pavel je synem otce, [ d , m ] , protože „ d je synem m “ tj. David je synem matky, [ d , o ] , protože „ d je bratrem o “ tj. David je synem otce , Vztah „být synem“ je zde „reprezentován“ právě uvedenými čtyřmi uspořádanými dvojicemi. Množina { [ p , m ] , [ p , o ] , [ d , m ] , [ d , o ] } tedy v našem případě představuje příbuzenský vztah „být synem“ v množině M . Pro vztah použijeme cizí slovo relace. Protože se jedná o množinu uspořádaných dvojic, budeme užívat název binární relace. Množinu { [ p , m ] , [ p , o ] , [ d , m ] , [ d , o ] } budeme nazývat binární relace v množině M . Podle uvedeného případu z přípravné úlohy je zřejmé: binární relace v množině M je množinou některých uspořádaných dvojic, které patří kartézskému součinu M × M a v důsledku toho je podmnožinou kartézského součinu M × M . Definice pojmu „binární relace v množině“ tedy zní: Binární relace v množině M je množina, která je podmnožinou kartézského součinu M × M. Množinu dětí v přípravné úloze označme A , tedy A = { p , d , h } a množinu rodičů označme B , tedy B = { o , m } . Potom relace „být synem“ je podmnožinou kartézského součinu A × B . Podle toho lze vyslovit definici binární relace z množiny A do množiny B : Binární relace z množiny A do množiny B je množina, která je podmnožinou kartézského součinu A × B.

2.2. V předcházející úloze (2.1.) je dána množina M = { m, o, p, d, h } . Zapište výčtem uspořádaných dvojic tuto binární relaci v množině M : a) být bratrem b) být otcem c) být sourozencem d) být sestrou e) být manželem f) být manželkou g) být manželem nebo manželkou h) být otcem nebo matkou i) být vnukem j) být příbuzným Výsledky : a) { [ p , d ] , [ p , h ] , [ d , p ] , [ d , h ] } stručný zápis: { pd , ph , dp , dh } b) { op , od , oh } c) { pd , ph , dp , dh , hp , hd } d) { hp , hd } e) { om } f) { mo } g) { om, mo } h) { op , od , oh , mp , md , mh } i) { } , tato binární relace neobsahuje žádnou uspořádanou dvojici, žádný člen dané rodiny není vnukem jiného z uvedených členů rodiny, množina těchto uspořádaných dvojic je prázdná, tato binární relace se nazývá prázdná relace . j) tato relace obsahuje všechny uspořádané dvojice kartézského součinu M× ×M, nazývá se úplná relace .

5

2.3.

Zapište binární relace z předcházející úlohy ( z úlohy 2.2. ) jako obory pravdivosti predikátů (výrokových forem). Řešení : a) { [x,y]∈M×M: x je bratrem y } b) { [x,y]∈M×M: x je otcem y } a podobně v ostatních případech.

Úmluva : V této kapitole se nebudeme setkávat s jinými relacemi než binárními, proto místo názvu binární relace můžeme použít stručného názvu relace.

2.4. Množinu všech přirozených čísel menších než 5 označme P . Zapište výčtem prvků, (tj. výčtem uspořádaných dvojic) relaci: a) { [x,y]∈P×P: x< y } b) { [x,y]∈P×P: x< y ∨ x = y } c) { [x,y]∈P×P: x>y } d) { [x,y]∈P×P: x | y } e) { [x,y]∈P×P: x | y ∧ x ≠ y } Výsledky : a) { [1,2], [1,3], [1,4], [2,3], [2,4], [3,4] } b) { [1,1], [1,2], [1,3], [1,4], [2,2], [2,3], [2,4], [3,3], [3,4], [4,4] } c) { [2,1], [3,1], [4,1], [3,2], [4,2], [4,3] } d) { [1,1], [1,2], [1,3], [1,4], [2,2], [2,4], [3,3], [4,4] } e) { [1,2], [1,3], [1,4], [2,4] }

2.5. Určete, zda množina R = { bc, ac, ca, bb, ed } je nebo není relací v množině a) A = { a, b, c } b) B = { a, b, c, d } c) C = { a, b, c, d, e } d) D = { a, b, c, d, e, f } Řešení : a) ed ∉ A× ×A, protože d∉ ∉A a tedy R není relace v množině A b) ed ∉ B× ×B, protože e∉ ∉B a tedy R není relace v množině B c) R je podmnožinou kartézského součinu C× ×C a tedy R je relace v množině C d) R je podmnožinou kartézského součinu D× ×D a tedy R je relace v množině D 2.6. Zjistěte, zda a) M × M b) prázdná množina je nebo není relací v dané neprázdné množině M . Řešení : a) Kartézský součin je jako každá množina podmnožinou sama sebe a tedy kartézský součin M× ×M je podle definice binární relace binární relací v množině M , říkáme jí úplná relace. b) Prázdná množina je, jak víme, podmnožinou každé množiny a tedy je i podmnožinou kartézského součinu M× ×M , tedy je to relace v množině M , říkáme jí prázdná relace.

3. Grafické znázornění binární relace Zavedeme dva způsoby grafického znázornění binární relace : uzlový graf neboli šipkový diagram a síťový graf neboli kartézský graf .

6

Zavedení uzlového grafu (šipkového diagramu) : Znázorníme relaci R = {ac,bb,cd,dc} v množině M = { a, b, c, d, e } uzlovým grafem (viz Obr. 1 ) : a

e

b d

c Obr.21

Prvky množiny M znázorníme body, říkáme jim uzl y ( uzly zakreslíme „prázdnými kroužky“ ). Uspořádané dvojice množiny R znázorníme šipkami , např. šipka, která „vychází z uzlu a “ a „přichází k uzlu c “ , znázorňuje uspořádanou dvojici [ a, c ] . Šipka, která „přichází k témuž uzlu, z něhož vychází“, má speciální název: smyčka , smyčkou je např. znázorněna uspořádaná dvojice [b,b] . Zavedení síťového grafu (kartézského grafu) : Znázorníme relaci R = { gp , hh , js , mp } z množiny A do množiny B v případě, že A = { g , h , j , k , m , n } , B = { f , h , p , s } síťovým neboli kartézským grafem (viz Obr. 2 ) : Prvky množiny A , tj. prvky g , h , j , k , m , n znázorníme (viz Obr. 2 ) přímkami navzájem rovnoběžnými. Prvky množiny B , tj. prvky f , h , p , s znázorníme přímkami k nim kolmými. Uspořádané dvojice relace R znázorníme zvýrazněním průsečíků příslušných dvou na sebe kolmých přímek, např. uspořádanou dvojici [ g, p ] znázorníme zvýrazněním průsečíku přímek g , p . s p h

Obr. 2

f g

h

j

k

m

n

Binární relaci { ms , sm , ns , sn , np , pp } v množině {m, n, s, p } znázorněte uzlovým i kartézským grafem . Řešení : m n p s n m s p m n s p Obr. 3 3.2. Binární relaci { ba, bi, bu, de } z množiny { b, c, d } do množiny { a, e, i, u } znázorněte uzlovým i kartézským grafem .

3.1.

7

Řešení : b

a

u

c

e

i

d

i

e

u

a

Obr. 4

b

c

d

3.3. Zakreslete uzlový i kartézský graf kartézského součinu M × M v případě, že M = { a , b , c } . Řešení : a

c b a

b

c

a

b

c

Obr. 5 3.4. Zapište výčtem prvků (tj. výčtem uspořádaných dvojic) relaci, která má následující grafické znázornění a) b) a d k m b

b

m

p

s

t

c Obr. 6

Řešení : Uzlovým grafem (šipkovým diagramem) je na Obr.6 a) znázorněna binární relace { ab, ac, ba, cc, cd, db } v množině { a, b, c, d } . Síťovým grafem (kartézským grafem) je na Obr.6 b) znázorněna binární relace { bk, mm, mk, sk, tm } z množiny { b, m, p, s, t } do množiny { m, k } .

3.5. Vyhledejte v učebnicích matematiky pro první stupeň základní školy úlohy a obrázky, které jsou modifikacemi uzlového nebo kartézského grafu. Mějme dánu relaci R v množině M . Zápis [ a, b ] ∈ R budeme velmi často nahrazovat stručnějším zápisem a R b a budeme jej číst: a je v relaci R s b nebo též (pokud je jasné, o kterou relaci jde) a je v relaci s b.

3.6. Nechť M = { b, c, d } . Zapište výčtem prvků (tj. výčtem uspořádaných dvojic) relaci R v množině M , jestliže c R d , b R c , c R b , d R d a zároveň ¬ b R d , ¬ b R b , ¬ c R c , ¬ d R b , ¬ d R c . Výsledek : R = { [ c, d ], [ b, c ], [ c, b ], [ d, d ] } 3.7. V množině { j , k } je dána relace S = { [ j , j ], [ j , k ] } . Určete pravdivost výroků k S j , j S k , k S k , j S j . Výsledek : Výrok k S j není pravdivý, protože [ k, j ] ∉ S , Výrok j S k je pravdivý, protože [ j, k ] ∈ S , Výrok k S k není pravdivý, protože [ k, k ] ∉ S ,

8

Výrok j S j je pravdivý, protože [ j, j ] ∈ S .

4. Inverzní relace Přípravná úloha :

4.1. Je dána binární relace R = { dc , mc , sd , mm , sp } z množiny A do množiny B , kde A = { d , m , s } , B = { c , d , m , p } . Utvořte množinu všech uspořádaných dvojic z kartézského součinu B × A , které jsou „obrácené“ vzhledem k uspořádaným dvojicím relace R . (K dané uspořádané dvojici utvoříme obrácenou uspořádanou dvojici vzájemnou záměnou jejích složek .) Řešení : K uspořádané dvojici [ d , c ] utvoříme obrácenou dvojici [ c , d ] , k dalším dvojicím dané relace R vezmeme jako obrácené dvojice postupně dvojice cm , ds , mm , ps a tedy množina všech obrácených uspořádaných dvojic k dvojicím relace R je { cd , cm , ds , mm , ps } . Je zřejmé, že tato množina je podmnožina kartézského součinu B × A a tedy je to binární relace z množiny B do množiny A . Nazývá se inverzní relace -1 k relaci R a označuje se znakem R . Definice inverzní relace : Nechť R je binární relace z A do B .

R = { [ x , y ] ∈ B × A: [ y , x ] ∈ R } Slovní vyjádření definice inverzní relace: Nechť R je binární relace z množiny A do množiny B . -1 Inverzní relace R k relaci R je množina všech uspořádaných dvojic [x,y] kartézského součinu B × A , pro které platí, že [y,x] je prvkem relace R . -1

Důsledek definice inverzní relace: (∀x∈B)(∀y∈A) x R-1 y ⇔ y R x

4.2. Je dána relace R = { [a,b], [c,d], [b,d], [d,b], [a,a] } v množině -1 M = { a, b, c, d, e }. Zapište výčtem prvků R . Řešení : -1 Pro inverzní relaci R k relaci R v množině M platí podle definice inverzní -1 relace, že R = { [x,y]∈M×M: [y,x]∈R } . -1 To znamená, že uspořádaná dvojice [x,y] náleží relaci R , právě když obrácená uspořádaná dvojice [y,x] náleží relaci R . Pro utvoření inverzní relace k relaci R postačí všechny uspořádané dvojice relace R „obrátit“ . -1 Protože [a,b]∈R , proto inverzní relaci R náleží [b,a],. -1 [c,d] náleží relaci R a proto [d,c] náleží inverzní relaci R . Zcela obdobně lze zdůvodnit, proč inverzní relaci náleží také uspořádané dvojice [b,d] , [d,b] a [a,a] . -1 Proto R = { [b,a], [d,c], [d,b], [b,d], [a,a] }.

9

4.3. Zapište inverzní relaci R-1 k relaci R : a) R={[x,y]∈N×N:xy}

b) R={[x,y]∈N×N:x≤y} . -1

b) R = {[x,y]∈N×N:x≥y} .

5 . Vlastnosti binárních relací Přípravná úloha: 5.1. Nechť je dána relace R = { [a,b], [b,c], [c,c] } v množině M = { a, b, c, d } . Zjistěte, zda je pravdivý výrok a) (∀x∈M) x R x b) (∀x∈M) ¬ x R x c) (∀x∈M)(∀y∈M) x R y ⇒ y R x d) (∀x∈M)(∀y∈M) x ≠ y ∧ x R y ⇒ ¬ y R x e) (∀x∈M)(∀y∈M)(∀z∈M) x R y ∧ y R z ⇒ x R z f) (∀x∈M)(∀y∈M) x ≠ y ⇒ x R y ∨ y R x Řešení : a) Výrok (∀x∈M) x R x není pravdivý, protože x R x neplatí např. pro x = a , neboť [a,a] ∉ R . Lze též říci, že obecný výrok (∀x∈M) x R x není pravdivý proto, že je pravdivá jeho negace, tj.existenční výrok (∃x∈M) ¬ x R x . Skutečně existuje aspoň jeden prvek množiny M , je to např. prvek a , že není v relaci R sám se sebou. b) Tento výrok rovněž není pravdivý. Je tomu tak proto, že např. c R c , čili [c,c]∈R . V tomto případě totiž žádný prvek množiny M nemá být v relaci R sám se sebou . Při ověřování můžete postupovat též tak, že utvoříte negaci daného výroku a určíte, zda je pravdivá nebo ne : Negací daného obecného výroku (∀x∈M) ¬ x R x je výrok (∃x∈M) x R x a ten je pravdivý, protože takový prvek skutečně existuje, je to c . Protože negace je pravdivá, je původní výrok nepravdivý. c) Platí, že [a,b]∈R , tedy a R b . Jestliže a R b , pak by mělo platit b R a , tj. [b,a]∈R . Avšak v dané relaci R = { ab, bc, cc } se dvojice ba nevyskytuje. Proto uvedený výrok není pravdivý. Můžete se o tom přesvědčit také pomocí vyšetření negace zkoumaného výroku, která zní : (∃x∈M)(∃y∈M) x R y ∧ ¬ y R x Tato negace původního výroku je pravdivá, takové prvky skutečně existují, jsou to např. prvky a, b, platí totiž, že aRb ∧¬bRa . Protože negace původního výroku je pravdivá, je původní výrok nepravdivý. (Poznámka – odkaz na poznatky z výrokového počtu: při negování implikace jsme využili tautologie ¬(p⇒q) ⇔ p∧¬q , která nám dovoluje „nahradit“ negaci implikace ¬(p⇒q) konjunkcí p∧¬q .) d) Protože pro dva různé prvky a , b platí, že aRb , pak by mělo platit ¬bRa . Nahlédnutím do zadání relace zjistíme, že to pravda je, uspořádaná dvojice [b,a] se v naší relaci R opravdu nevyskytuje. Podobně je tomu i s prvky b , c. Jiné dva navzájem různé prvky spolu v relaci nejsou. Výrok je tedy pravdivý.

10

e) Protože platí, že a R b a také b R c , bylo by k tomu, aby byl uvedený výrok pravdivý, nezbytně třeba, aby platilo, že a R c, tj. aby a byl v relaci s c . To však není pravda, dvojice [a,c] se v relaci R nevyskytuje. Uvedený výrok je tedy nepravdivý. Jiný způsob důkazu: Dosaďme do příslušného predikátu x R y ∧ y R z ⇒ x R z x = a , y = b , z = c a proveďme hodnocení výroku vzniklého po dosazení: x y z xRy ∧ yRz ⇒ xRz a b c aRb ∧ bRc ⇒ aRc 1

1

1

0

0

Z tabulky pravdivostních hodnot je zřejmé, že zkoumaná implikace je nepravdivá. Zjistili jsme tedy, že existují prvky x = a , y = b , z = c , že implikace x R y ∧ y R z ⇒ x R z je pro ně nepravdivá. Proto obecný výrok uvedený v zadání úlohy (v případu e) je nepravdivý . f) Dosadíme-li do predikátu x ≠ y ⇒ x R y ∨ y R x za proměnnou x prvek a , za proměnnou y prvek b , dostaneme výrok a≠b ⇒ aRb ∨ bRa 1 1 1 1 0 a ten je pravdivý, jak ukazuje pravdivostní hodnocení zapsané pod ním. K tomu, abychom byli oprávněni tvrdit, že zadaný obecný výrok je pravdivý, museli bychom ověřit všechny možné případy. Vyzkoušejme další případ: do predikátu x ≠ y ⇒ x R y ∨ y R x dosaďme tentokrát takto: x = a , y = c a≠c ⇒ aRc ∨ cRa 1 0 0 0 0 Zkoumaná implikace je nepravdivá. Obecný výrok (∀x∈M)(∀y∈M) x ≠ y ⇒ x R y ∨ y R x je proto nepravdivý. Můžeme též postupovat tak, že budeme zkoumat, zda je pravdivá negace našeho obecného výroku, tj. výrok (∃x∈M)(∃y∈M) x ≠ y ∧ (¬ x R y ∧ ¬ y R x ) . Ten pravdivý je, protože skutečně existuje aspoň jeden prvek x (je to např. a ) a aspoň jeden prvek y (je to třeba prvek c ), že jsou to, jak je zřejmé, dva navzájem různé prvky a [a,c]∉R ani [c,a]∉R . Negace je pravdivá a tedy původní výrok je nepravdivý. Obecné výroky z přípravné úlohy vyslovují velmi důležité vlastnosti binárních relací. Konkrétní relace, která je v přípravné úloze zkoumána, má z uvedených vlastností pouze jednu, tj. vlastnost vyjádřenou obecným výrokem v případě d). Doporučení : Zaveďme zestručnění zápisů výroků z předcházející úlohy. Např. místo zápisu (∀x∈M)(∀y∈M) použijeme zápis (∀ ∀x,y∈ ∈M) . Můžeme jej číst např. „pro každé x a y množiny M platí, že ...“ . Zápis (∀x,y,z∈M), který čteme „pro každé x, y a z množiny M platí, že ...“ je zestručněním zápisu (∀x∈M)(∀y∈M)(∀z∈M) . Zápis (∃x,y∈M), který čteme „existuje x, y množiny M, že platí ...“ je zestručněním zápisu (∃x∈M)(∃y∈M) apod.

11

Vlastnosti binárních relací, které jsou vysloveny pomocí obecných výroků v úloze 5.1. budou dále pro nás velmi důležité, proto je označme speciálními názvy: reflexivnost, antireflexivnost, symetričnost, antisymetričnost, tranzitivnost, konektivnost. Definice reflexivnosti relace: Binární relace R v množině M je reflexivní, právě když (∀ ∀x∈ ∈M) x R x . Definice antireflexivnosti relace: Binární relace R v množině M je antireflexivní, právě když (∀ ∀x∈ ∈M) ¬x R x . Definice symetričnosti relace: Binární relace R v množině M je symetrická, právě když (∀ ∀x,y∈ ∈M) x R y ⇒ y R x . Definice antisymetričnosti relace: Binární relace R v množině M je antisymetrická, právě když (∀ ∀x,y∈ ∈M) x ≠ y ∧ x R y ⇒ ¬ y R x . Definice tranzitivnosti relace: Binární relace R v množině M je tranzitivní, právě když (∀ ∀x,y,z∈ ∈M) x R y ∧ y R z ⇒ x R z . Definice konektivnosti relace: Binární relace R v množině M je konektivní, právě když (∀ ∀x,y∈ ∈M) x ≠ y ⇒ x R y ∨ y R x .

5.2. Sestrojte binární relaci v množině M = { a, b, c, d } tak, aby byla a) reflexivní, b) antireflexivní, c) symetrická, d) antisymetrická, e) tranzitivní, f) konektivní. Řešení : a) K tomu, aby relace byla v množině { a, b, c, d } reflexivní, musí podle definice reflexivnosti obsahovat přinejmenším všechny uspořádané dvojice [a,a], [b,b], [c,c], [d,d] . Kromě nich může obsahovat kterékoliv další uspořádané dvojice kartézského součinu M × M . Jsou to např. tyto relace: {aa,bb,cc,dd}, {aa,bb,cc,dd,ab}, {aa,bb,cc,dd,ab,ca} apod. b) K tomu, aby relace byla v množině M = { a, b, c, d } antireflexivní, nesmí podle definice antireflexivnosti obsahovat žádnou uspořádanou dvojici stejných prvků. Uspořádané dvojice, jejichž složky se sobě nerovnají, obsahovat může. Antireflexivní jsou např. tyto relace v množině M : { da } , prázdná relace, {bc,ad,ba}, {ab,ba, ac,ca,db,dc} apod. c) K tomu, aby relace byla v množině { a, b, c, d } symetrická, musí podle definice symetričnosti platit: pokud je prvkem relace určitá uspořádaná dvojice, musí této relaci patřit i dvojice k ní „obrácená“ tj. taková, která se liší od dané dvojice záměnou složek. Jsou to např. tyto relace:

12

{ab,ad,cc,ba,da}, {bb,cc}, prázdná relace, {bd,db}, úplná relace, {aa,bb,cd,dc} apod. d) Má-li být relace antisymetrická, pak nesmí k žádné uspořádané dvojici různých prvků, kterou obsahuje, obsahovat uspořádanou dvojici obrácenou. Příklady antisymetrických relací v množině {a,b,c,d}: {ab,dc,bc}, {db,ac,bb,dd}, {bd} apod. e) Má-li být relace tranzitivní, pak pokud obsahuje takové uspořádané dvojice, že druhá složka jedné z nich je první složkou druhé, pak musí též obsahovat takovou uspořádanou dvojici, že její první složkou je první složka první uspořádané dvojice a druhou složkou druhá složka druhé. Příklady tranzitivních relací v množině { a, b, c, d }: {ba,ad,bd,cb,ca,cd}, {cd,cb,ab}, {cb}, prázdná relace, úplná relace, kartézský součin M×M, { dc, ca, cd, da, dd, cc } apod. f) Relace má být konektivní. To podle definice konektivnosti znamená, že ať si vybereme kterékoliv dva různé prvky množiny M, musí relace obsahovat aspoň jednu z uspořádaných dvojic, které z těchto dvou prvků lze utvořit. Má-li být relace konektivní v množině { a, b, c, d }, musí obsahovat uspořádané dvojice ab nebo ba, ac nebo ca, ad nebo da, bc nebo cb, bd nebo db a ještě cd nebo dc. V množině { a, b, c, d } jsou tedy konektivní např. relace : { ba, ac, ad, da, bb, bc, db, cd }, { ab, ac, da, bc, db, cd } apod. Je zřejmé, že např. konektivní relace v čtyřprvkové množině nemá méně než šest uspořádaných dvojic.

5.3. Určete vlastnosti relace R = { [a,b], [a,a] } v množině K = { a, b } . Řešení : Relace R v množině K není reflexivní, protože ¬ b R b . Není ani antireflexivní, protože a R a . Rovněž není symetrická, neboť a R b ∧ ¬ b R a . Antisymetrická však tato relace je, protože obsahuje jedinou dvojici navzájem různých prvků, tj. uspořádanou dvojici [a,b] a neobsahuje uspořádanou dvojici [b,a] . Zkoumání tranzitivnosti proveďme podrobněji: podle definice je R v množině K tranzitivní, právě když (∀x,y,z∈K) x R y ∧ y R z ⇒ x R z . Pravdivost tohoto výroku zjišťujeme dosazením každého z obou prvků postupně za proměnnou x, y, z do příslušného predikátu xRy ∧ yRz ⇒ xRz . Z tabulky, v níž hodnotíme pravdivost vzniklých výroků, je zřejmé, že všechny vzniklé implikace jsou pravdivé. Uvedená relace je tedy tranzitivní. Relace R v množině K je konektivní, neboť K má pouze dva prvky a , b a jedna z uspořádaných dvojic utvořená z těchto prvků, tj. uspořádaná dvojice [a,b] relaci R náleží.

5.4. Určete vlastnosti relace, a) b) c) d)

„větší než“ v množině N , tj. relace { [x,y]∈N×N: x > y } „shodnost úseček“ v množině U všech úseček v prostoru „rovnoběžnost přímek“ v množině všech přímek v prostoru (označme tuto množinu T ), tedy relace { [x,y]∈T×T: x || y } „kolmost přímek“ v T (v prostoru), tedy relace { [x,y]∈T×T: x ⊥ y }

13

„kolmost přímek“ v množině D všech přímek v rovině (v dvojrozměrném prostoru), tedy relace { [u,v]∈D×D: u ⊥v } f) „menší nebo rovno“ v množině R všech reálných čísel, tedy relace { [x,y]∈R×R: x ≤ y } g) „je dělitelem“ v množině N, tj. relace { [x,y]∈N×N: x | y } h) „je dělitelem“ v množině C, tj. relace { [x,y]∈C×C: x | y }, kde C je množina všech celých čísel Výsledky : a) antireflexivní, antisymetrická, tranzitivní, konektivní b) reflexivní, symetrická, tranzitivní c) reflexivní, symetrická, tranzitivní d) antireflexivní, symetrická e) antireflexivní, symetrická f) reflexivní, antisymetrická, tranzitivní, konektivní g) reflexivní, antisymetrická, tranzitivní h) reflexivní, tranzitivní e)

5.5.

Sestrojte všechny takové relace v dvouprvkové množině, aby každá z nich byla : a) symetrická i antisymetrická b) reflexivní i antireflexivní c) tranzitivní a konektivní d) antireflexivní a antisymetrická Výsledky : Zvolme dvouprvkovou množinu, např. {r,s} , pak a) {}, {[r,r]}, {[s,s]}, {[r,r],[s,s]} b) taková relace neexistuje c) {rs},{sr},{rr,rs},{rr,sr},{ss,rs},{ss,sr},{rr,ss,rs}, {rr,ss,sr},{rr,ss,rs,sr} d) {rs},{sr}

5.6. Určete vlastnosti relace a) { [x,y]∈N×N: x + y = 12 }, b) { [x,y]∈C×C: |x| = |y| }, c) { [x,y]∈R×R: y = 3x + 1 }, d) { [x,y]∈N×N: y = 2x ∨ x = y }, e) { [x,y]∈N×N: x > 3 ∧ y > 5 }. Výsledky : Uvedená relace je v dané množině a) symetrická b) reflexivní, symetrická, tranzitivní c) antisymetrická d) reflexivní, antisymetrická e) tranzitivní

5.7.

Vyzkoumejte a vysvětlete, jak se dají zjistit jednotlivé vlastnosti relací pomocí uzlového grafu a jak podle kartézského grafu .

5.8. Zjišťujte vlastnosti různých příbuzenských relací v množině všech žijících lidí.

5.9. Je dána relace R = { [r,s], [s,m], [m,m], [m,r] } v množině M = { r, s, m }. Určete, zda R je nebo není a) reflexivní b) antireflexivní d) antisymetrická e) tranzitivní

c) symetrická f) konektivní

14

g) zda je nebo není pravdivý výrok (∀x,y∈M) x R y ⇒ ¬ y R x Svá zjištění zdůvodněte . Výsledky : a) není reflexivní, protože neobsahuje např. [r,r] b) není antireflexivní, protože obsahuje [m,m] c) není symetrická, protože obsahuje [r,s] a neobsahuje [s,r] d) je antisymetrická, protože - obsahuje [r,s] a neobsahuje [s,r] - obsahuje [s,m] a neobsahuje [m,s] - obsahuje [m,r] a neobsahuje [r,m] e) není tranzitivní, protože obsahuje [r,s] a obsahuje [s,m] a neobsahuje [r,m] f) je konektivní, protože obsahuje - aspoň jednu uspořádanou dvojici se složkami r , s . . . [r,s] - aspoň jednu uspořádanou dvojici se složkami m , s . . . [s,m] - aspoň jednu uspořádanou dvojici se složkami m , r . . . [m,r] g) uvedený výrok není pravdivý, což snadno zjistíme, dosadíme-li x = m a y = m do predikátu x R y ⇒ ¬ y R x . Po dosazení obdržíme výrok m R m ⇒ ¬ m R m , který je nepravdivý : 1 0 0 1

6 . Ekvivalence v množině Definice relace typu ekvivalence : Ekvivalence v množině M je relace, která je v množině M reflexivní, symetrická a tranzitivní.

6.1. Rozhodněte, zda daná relace R v množině M = { a, b, c, d } je nebo není ekvivalence, jestliže a) R = { aa, bb, cc, dd, bc, cb } b) R = { a, b, c } × { a, b, c } ∪ { [d,d] } c) R = { [x,y]∈M×M: x = y } d) R = { [x,y]∈M×M: x = y } ∪ { bc, cb, ad, da } e) R = M × M − { ad, da } f) R = M × M g) R = { aa, bb, cc, dd } Své rozhodnutí zdůvodněte. Řešení : Ve všech případech a)-d), f), g) jsou relace v možině M reflexivní, symetrické a tranzitivní, jsou to tedy relace typu ekvivalence. Jedinou výjimkou je relace v případu e). Tato relace je sice v množině M reflexivní a symetrická, ale není v této množině tranzitivní . Zdůvodnění: u relace R v případě e) např. [a,b]∈R a [b,d]∈R a tedy by mělo být [a,d]∈R . Podle předpisu v zadání úlohy však [a,d] relaci R nepatří .

6.2. Určete, která z relací uvedených v úloze 5.4. (na str.13) je a která není relací typu ekvivalence v příslušné uvedené množině. Výsledky : Z relací uvedených v úloze 5.4. (na str.13) pouze relace v případech b) a c) jsou ekvivalence, protože pouze ony dvě jsou v dané množině reflexivní, symetrické i tranzitivní .

15

6.3. Zjistěte, zda rovnost v množině všech zlomků, jejichž čitatelem je kterékoliv celé číslo a jmenovatelem kterékoliv nenulové celé číslo, je relace typu ekvivalence. Výsledek : Ze zkušenosti s počítáním se zlomky víte zcela samozřejmě, že každý zlomek je roven sám sobě, to znamená, že rovnost zlomků je reflexivní relace. Dále rovněž znáte, že pro každé dva zlomky platí: je-li jeden z nich roven druhému, je samozřejmě i druhý z nich roven prvnímu (např. jsou-li dvě třetiny rovny šesti devítinám, je určitě šest devítin rovno dvěma třetinám) , tedy tato relace je zřejmě symetrická . Naše představy a zkušenost nám také napovídají, že pro každé tři zlomky platí: je-li první z nich roven druhému a druhý třetímu, můžeme se spolehnout, že i první z nich se rovná třetímu (můžete si to vyzkoušet na libovolném množství konkrétních případů), čili rovnost zlomků je zřejmě relace tranzitivní. Rovnost zlomků jako relace reflexivní, symetrická a tranzitivní je tedy (alespoň podle našich představ) relace typu ekvivalence. Prozatím se musíme spoléhat jen na představy a zkušenost, teprve při systematickém studiu aritmetiky jako odborné disciplíny, kdy budou pojmy jako zlomek, rovnost zlomků a další pojmy této teorie definovány, budete si moci uvedené vlastnosti relace rovnost zlomků přesně dokázat.

6.4. Vezměme množinu všech přirozených čísel menších než např. třicet dva. Sledujme v této množině vlastnosti binární relace „ x dává při dělení sedmi stejný zbytek jako y " . Zjistěte, zda uvedená relace je nebo není ekvivalence v množině zvolených přirozených čísel . Řešení : Omezíme se opět na zkušenost, kterou si můžete bez potřebné teorie spolehlivě ověřit pouze na určitém množství konkrétních případů. Proto jsme určitým způsobem omezili počet uvažovaných přirozených čísel a nebereme v úvahu nekonečnou množinu všech přirozených čísel. Snad ani nemusíme ověřovat, že relace ze zadání této úlohy je reflexivní. Je přece zcela samozřejmé, že každé přirozené číslo dává při dělení sedmi stejný zbytek jako ono samo. Podobně je snadno pochopitelné, že dává-li jedno číslo při dělení např. sedmi stejný zbytek jako druhé, je tomu i obráceně. Naše relace je tedy zřejmě symetrická . Také tranzitivnost je možno snadno ověřit : vybereme-li tři čísla z naší množiny taková, že první z nich dává stejný zbytek jako druhé a druhé dává stejný zbytek jako třetí, pak určitě i první dává stejný zbytek jako třetí (na ukázku aspoň jeden konkrétní případ vyšetřování: „číslo 10 dává při dělení sedmi stejný zbytek jako 17 “(tím zbytkem je totiž číslo 3) , „číslo 17 dává při dělení sedmi stejný zbytek jako 31“ (tím zbytkem je opět číslo 3). Také při dělení čísla 10 sedmi dostáváme stejný zbytek, jako když vydělíme číslo 31 sedmi) . Naše relace je podle toho patrně i tranzitivní a tedy je to relace typu ekvivalence .

7 . Rozklad množiny Přípravná úloha :

7.1.

Je dána množina M = { a, b, c, d, e, f, g } . Sestrojte takové množiny, aby byly neprázdnými podmnožinami množiny M a aby každý prvek množiny M náležel právě jedné z nich.

16

Řešení : Úloha má více než jedno řešení, uveďme na ukázku několik možností: 1. { a }, { b }, { c }, { d }, { e }, { f }, { g } 2. { a, b, c, d }, { e, f }, { g } 3. { a, f }, { c, g }, { e }, { b, d } 4. { a, b, c, d, e, f, g } apod. Uvedené podmnožiny množiny M se v jednotlivých případech nazývají třídy rozkladu množiny M a množina všech těchto tříd se nazývá rozklad množiny M . Je zřejmé, že může existovat více různých rozkladů jedné množiny.

7.2. Zapište všechny rozklady tříprvkové množiny. Řešení : Zvolme tříprvkovou množinu, např. { a, b, c } = M . Máme sestrojit všechny rozklady množiny M , tj. (podle přípravné úlohy) sestrojíme nejprve takové množiny, aby byly neprázdnými podmnožinami množiny M a aby každý prvek množiny M náležel právě jedné z nich . Vezměme tedy např. dva prvky množiny M , třeba a , c , utvořme z nich jednu podmnožinu množiny M , tj. { a , c } . Máme tedy už jednu třídu připravovaného rozkladu . Každý prvek množiny M má patřit do právě jedné třídy, to znamená, že má současně splňovat dva požadavky: má patřit do nejvýše jedné třídy a současně do aspoň jedné třídy . Prvek a i prvek c množiny M už do jedné třídy patří, proto tedy nesmějí podle jednoho z požadavků být zařazeny do další třídy. Prvek b množiny M zatím zařazen není, ale měl by podle druhého požadavku do nějaké třídy zařazen být. Založme tedy pro něj další třídu. V této nové třídě ale už v tomto případě nebude kromě něj zařazen žádný další prvek, protože daná množina M už další prvek nemá. Vytvořili jsme tedy dvě třídy rozkladu množiny M , jsou to tyto dvě podmnožiny množiny M : { a , c } , { b } . Množina těchto tříd je jedním z rozkladů množiny M : { { a , c }, { b } } . Výsledky : Utvořme a vypišme všechny rozklady množiny M = { a, b, c } . { { a }, { b }, { c } } je jeden rozklad množiny { a, b, c } , třídami tohoto rozkladu jsou množiny { a }, { b }, { c } . Uveďme další rozklady množiny { a, b, c } : { { a, b }, { c } }, { { a, b, c } }, { { a }, { b, c } }, { { b }, { a, c } } . Tříprvková množina má tedy celkem pět navzájem různých rozkladů. Uveďme jeden způsob grafického znázornění rozkladů tříprvkové množiny: °a °b °c

°a °b

°c

°a °b

°c

°a °b

°a °c

°b °c

Obr.7

{{a},{b},{c}} {{a},{b,c}} {{b},{a ,c}}

{{a ,b},{c}}

{{a , b, c}}

17

Definice rozkladu množiny: Rozklad neprázdné množiny M je množina takových neprázdných podmnožin množiny M, že každý prvek množiny M náleží právě jedné z nich. Podmnožiny množiny M , uvedené v definici rozkladu množiny se nazývají třídy rozkladu množiny M. Z definice rozkladu vyplývá, že (pokud má rozklad množiny M aspoň dvě třídy), pak - průnikem každých dvou tříd rozkladu je prázdná množina, tj. žádné dvě třídy rozkladu nemají společný prvek a - sjednocením všech tříd rozkladu je množina M .

7.3. Zjistěte, která z množin E , F , G , H je a která není rozkladem množiny M = { a, b, c, d, e, f }, jestliže E = { { a, d }, { c, e, f }, { b } } F = { { a, b, c }, { d, f } } G = { { a, b }, { c, d, e }, { a, f } } H = { M } = { { a, b, c, d, e, f } } Řešení : Množina E je rozkladem množiny M , protože v tomto případě jsou splněny podmínky definice rozkladu: každý ze šesti prvků množiny M patří aspoň do jedné a současně nejvýše do jedné, tedy právě do jedné z množin { a, d }, { c, e, f }, { b } . Množina F není rozkladem množiny M , protože např. e nenáleží žádné z množin, které jsou prvky množiny F . Je též možno argumentovat tím, že { a, b, c } ∪ { d, f } ≠ M . Množina G není rozkladem množiny M , protože a patří zároveň do dvou uvedených podmnožin množiny M , neboli { a , b } ∩ { a , f } ≠ ∅ . Množina H je rozkladem množiny M podle definice rozkladu. Existuje velmi důležitá souvislost mezi rozkladem množiny M a relací typu ekvivalence v množině M : - ke každé ekvivalenci E v množině M existuje právě jeden rozklad množiny M a - ke každému rozkladu množiny M existuje právě jedna ekvivalence E v množině M tak, že pro každé dva prvky x , y množiny M platí : x E y ⇔ x je prvkem téže třídy rozkladu množiny M jako y . Říkáme, že každá ekvivalence v množině M indukuje právě jeden rozklad množiny M a že naopak každý rozklad množiny M je indukován právě jednou ekvivalencí v množině M .

7.4. Zapište ekvivalenci, která indukuje rozklad a) b) c) d) e)

{{p,q},{r,s}} {{1;2;3},{4},{5;6}} {{a,b,c,d,e}} { { 14 } , { 15 } , { 16 } } {{1;3;5},{0;2;4}}

18

Výsledky : Daný rozklad je indukován ekvivalencí a) { pp , qq , rr , ss , pq , qp , rs , sr } v množině { p , q , r , s } b) { [1;1] , [2;2] , [3;3] , [4;4] , [5;5] , [6;6] , [1;2] , [1;3] , [2;3] , [2;1] , [3;1] , [3;2] , [5;6] , [6;5] } v množině { 1 ; 2 ; 3 ; 4 ; 5 ; 6 } c) M × M v množině M = { a , b , c , d , e } d) { [ 14 ;14 ] , [ 15 ;15 ] , [ 16 ; 16 ] } v množině { 14 ; 15 ;16 } e) {[0;0], [1;1], [2;2], [3;3], [4;4], [5;5], [1;3], [3;1], [1;5], [5;1], [3;5], [5;3], [0;2], [2;0], [0;4], [4;0], [2;4], [4;2] } v množině { 0 ; 1 ; 2 ; 3 ; 4 ; 5 }

7.5. Zapište rozklad množiny M , který je indukován ekvivalencí E v množině M , jestliže a) E = { aa, bb, cc, dd, bc, cb, dc, cd, bd, db } , M = { a, b, c, d } b) E = { [x,y]∈M×M: | x | = | y | } , M = { x∈C: | x | < 4 } c) E = { [x,y]∈M×M: x dává při dělení čtyřmi stejný zbytek jako y } , M = {x∈N: x < 21} d) E = { [x,y]∈M×M: x dává při dělení čtyřmi stejný zbytek jako y } , M = { x∈C: x > -5 ∧ x < 0 } e) E = { [x,y]∈M×M: x dává při dělení sedmi stejný zbytek jako y } , M = {x∈N: x < 32} f) E = { [x,y]∈M×M: x dává při dělení dvěma stejný zbytek jako y } , M je množina C všech celých čísel g) E = { [x,y]∈M×M: x dává při dělení třemi stejný zbytek jako y } , M je množina N0 , N0 = N ∪ { 0 } Řešení : Ekvivalence E indukuje v množině M tyto rozklady : a) { { a } , { b , c , d } } b) { { 0 } , { 1 , -1 } , { 2 , -2 } , { 3 , -3 } } c) { {1;5;9;13;17} , {2;6;10,14,18} , {3;7;11;15;19} , {4;8;12;16;20} } d) { {-1} , {-2} , {-3} , {-4} } e) rozklad má těchto sedm tříd: {1;8;15;22;29}, {2;9;16;23;30}, {3;10;17;24;31}, {4;11;18;25}, {5;12;19;26}, {6;13;20;27}, {7;14;21;28} f) rozklad má pouze dvě třídy: jednou je množina všech sudých celých čísel, (označme ji S) a druhou je množina všech lichých celých čísel (označme ji L), těmto třídám říkáme zbytkové třídy podle modulu 2, rozklad se dá zapsat { S , L } . g) rozklad má tři třídy: množinu všech čísel z množiny N0 dělitelných třemi, množinu všech čísel z množiny N0, která při dělení třemi dávají zbytek jedna, množinu všech čísel z množiny N0, která při dělení třemi dávají zbytek dvě, (těmto třídám se říká zbytkové třídy podle modulu tři) , rozklad se dá zapsat takto: { {0;3;6;…} , {1;4;7;…} , {2;5;8;…} , . . . }

19

7.6. Narýsujte čtyři přímky a , b , c , d tak, aby žádné dvě z nich nebyly navzájem rovnoběžné. Dále narýsujte přímky e , f tak, aby každá z nich byla rovnoběžná s přímkou a , potom ještě přímku g rovnoběžnou s přímkou c . Dokažte, že rovnoběžnost přímek v množině všech přímek, které jste narýsovali, je relace typu ekvivalence. Zapište rozklad množiny všech narýsovaných přímek na třídy indukovaný ekvivalencí „rovnoběžnost přímek“ . Výsledek : Množinu všech sedmi přímek, o které se v úloze jedná označme P = { a, b, c, d, e, f, g }, relaci rovnoběžnost přímek lze zapsat: {[x,y]∈P×P: xy } , označme ji R . R = { ae, af, ea, ef, fa, fe, cg, gc, aa, bb, cc, dd, ee, ff, gg } . R je reflexivní, symetrická a tranzitivní, proto je to relace typu ekvivalence. Ekvivalence R v množině P indukuje tento rozklad množiny P : { { a, e, f } , { b } , { d } , { c , g } } .

7.7. Narýsujte čtyři úsečky AB, CD, EF, GH tak, aby žádné dvě z nich nebyly navzájem shodné. Dále narýsujte další dvě úsečky IJ, KL tak, aby každá z nich byla shodná s úsečkou AB , dále úsečku MN tak, aby byla shodná s úsečkou EF . Vysvětlete, že shodnost úseček v množině všech úseček, které jste narýsovali, je relace typu ekvivalence. Zapište rozklad množiny všech narýsovaných úseček indukovaný ekvivalencí „shodnost úseček“. Řešení : Každá úsečka je shodná sama se sebou - shodnost úseček je reflexivní relace. Pro každé dvě úsečky platí: je-li jedna shodná s druhou, pak je i druhá shodná s první – shodnost úseček je symetrická relace. Pro každé tři úsečky platí: je-li jedna shodná s druhou a druhá shodná s třetí, pak i první z nich je shodná s třetí – shodnost úseček je tranzitivní relace. Proto je shodnost úseček relace typu ekvivalence a indukuje rozklad uvažované množiny úseček na třídy navzájem shodných úseček. V našem případě je dána množina úseček { AB , CD , EF , GH , IJ , KL , MN } a relace shodnost úseček, která indukuje její rozklad { { AB, IJ, KL } , { CD } , { MN, EF } , { GH } } .

7.8. Vezměte v úvahu množinu všech žáků jedné určité základní školy, označte tuto množinu A a uvažujte o relaci S : S = { [x,y]∈ A×A: x je žákem téže třídy jako žák y }. Dokažte, že relace S v množině A je ekvivalence (relace typu ekvivalence). Uveďte rozklad množiny A indukovaný ekvivalencí S . Výsledek : Relace S je reflexivní (každý žák chodí „sám se sebou“ do téže třídy), symetrická i tranzitivní (způsob ověřování lze převzít z předcházejících úloh). Třídy rozkladu se nazývají běžně i ve škole „třídy“.

20

8 . Uspořádání Podle běžných představ o uspořádání prvků množiny budete zajisté ochotni přijmout zásadní požadavky: - je-li např. z libovolných prvků a , b dané množiny prvek a před prvkem b , pak nesmí být obráceně prvek b před prvkem a , - je-li z libovolných prvků a, b, c dané množiny a před b a zároveň b před c , pak musí být a před c . Tyto představy o uspořádání jsou ve shodě s definicí pojmu uspořádání: Uspořádání v množině M je relace, která je v množině M antisymetrická a tranzitivní.

8.1. Zapište alespoň tři různá uspořádání ve čtyřprvkové množině . Řešení : Uveďme alespoň některé případy uspořádání v množině M = {a,b,c,d} : { dc, cb, db }, { cb, ba, ca, bd, cd, ad }, { da, cb, cc }, { ab,dc }, ∅ , { cc, bb, dd }, { ad, bd, cd }, { bc, bd, ba } apod. Všechny tyto relace v množině M jsou antisymetrické a tranzitivní a proto podle definice jsou to uspořádání v množině M .

8.2. Zapište alespoň dvě relace v M , které v M uspořádáním nejsou . M = { p, g, r } . Řešení : Příklady relací, které nejsou uspořádání v množině M : { pg, rr, gp }, protože není antisymetrická, { gr, rp } , protože není tranzitivní.

8.3. Určete, zda relace S je uspořádáním v množině G , jestliže a) S = { [x,y]∈G×G: xy ∨ y>x }, G je množina všech přirozených čísel g) S = { [x,y]∈G×G: x>y ∨ x = y }, G je množina všech přirozených čísel h) S = { fg, fe, ge }, G = { e, f, g } i) S = { [x,y]∈G×G: x || y }, G je množina všech přímek v rovině j) S = { [x,y]∈G×G: x ⊥ y } , G je množina všech přímek v rovině k) S = ∅ , G je množina všech přirozených čísel Řešení : Relace S je v dané množině M uspořádáním právě v těchto případech : a), b), d), e), g), h), k) . V každém z těchto případů má totiž daná relace

21

S v dané množině M obě požadované vlastnosti: je antisymetrická i tranzitivní . Zcela neočekávaný je pravděpodobně výsledek v případě k) . Prázdná relace je opravdu antisymetrická, dokonce v kterékoliv množině (tedy nejen v množině všech přirozených čísel). Je tomu tak proto, že po dosazení kterýchkoliv prvků dané množiny za x a za y je xRy nepravdivý výrok (protože R je prázdná relace) a tedy i konjunkce x≠y ∧ xRy je nepravdivý výrok a tudíž implikace x≠y ∧ xRy ⇒ ¬yRx je pravdivá . Prázdná relace je tranzitivní proto, že po dosazení kterýchkoliv prvků dané množiny za x a za y je xRy nepravdivý výrok (protože R je prázdná relace) a tedy i konjunkce xRy ∧ yRz je nepravdivý výrok a tudíž implikace xRy ∧ yRz ⇒ xRz je pravdivá. Relace S není v množině M uspořádáním v těchto případech : c) protože S není v množině všech celých čísel antisymetrická, existují totiž celá čísla, např. 2 , -2 , že (-2)2 a také 2(-2) f) protože S není v množině přirozených čísel antisymetrická , existují přirozená čísla, např. 4 , 7 , že 4 S 7 , ale také 7 S 4 i) protože rovnoběžnost přímek není v množině všech přímek antisymetrická, protože existují dvě přímky, označme je např. p, q , že platí p  q , ale též q p j) protože kolmost přímek není v množině všech přímek tranzitivní, neboť existují přímky a, b, c, že a ⊥ b a b ⊥ c , ale a není kolmá na c

9. Speciální typy uspořádání Tím, že budeme požadovat, aby relace uspořádání měla některé další vlastnosti, vytvoříme speciální typy uspořádání: Tak např. přidáme-li k dvěma „nejpodstatnějším“ vlastnostem uspořádání (tj. k antisymetričnosti a tranzitivnosti) konektivnost, vznikne speciální uspořádání, které budeme nazývat lineární . Lineární uspořádání v množině M je uspořádání, které je v M konektivní . Je zřejmé, že definici lineárního uspořádání můžeme formulovat též takto : Lineární uspořádání v množině M je binární relace, která je v antisymetrická, tranzitivní a konektivní . S příklady se seznámíme při řešení úloh :

9.1.

M

Určete, zda relace R je v množině M antisymetrická, tranzitivní a konektivní, jestliže a) R = { km, kh, kg, mh, mg, hg } , M = { g, m, k, h } b) R = { ca, ad, cd, cs } , M = { a, c, d, s, v } Pokud relace R je uspořádání v množině M , určete, je-li toto uspořádání lineární. Řešení : a) Daná relace R je v M antisymetrická, protože k žádné uspořádané dvojici různých prvků, kterou obsahuje, neobsahuje uspořádanou dvojici obrácenou . R je v M tranzitivní , protože pro každé tři prvky x , y , z množiny M platí implikace xRy ∧ yRz ⇒ xRz .

22

R je tedy uspořádání v M . R je navíc konektivní v M , protože pro každé dva různé prvky x , y množiny M platí, že se v relaci R vyskytuje alespoň jedna uspořádaná dvojice z nich utvořená, tj. xRy nebo yRx . Relace R v množině M je tedy lineární uspořádání . b) V tomto případě je relace R v množině M antisymetrická i tranzitivní, tedy je to uspořádání . Protože se v tomto případě v relaci R nevyskytuje ani jedna uspořádaná dvojice utvořená např. z prvků d , s množiny M , relace R není konektivní. Relace R v množině M je tedy uspořádání, ale není to uspořádání lineární . Znáte ze školy symboly < > ≤ ≥ . Čteme je takto : „menší než“ „větší než“ „menší nebo rovno než“ „větší nebo rovno než“. Jsou to znaky pro zapisování nerovností reálných, racionálních, celých nebo přirozených čísel. Symboly < , > označují tzv. ostré nerovnosti, Symboly ≤ , ≥ označují tzv. neostré nerovnosti, Přípravná úloha :

9.2. Určete vlastnosti relace a) { [x,y]∈R×R: x < y } b) { [x,y]∈R×R: x > y } c) { [x,y]∈R×R: x ≤ y } d) { [x,y]∈R×R: x ≥ y } Řešení : V případech a) , b) jsou relace antisymetrické, tranzitivní a konektivní a tedy každá z nich je lineární uspořádání. Kromě toho každá z těchto relací, které jsou nazývány „ostré nerovnosti“ je a n t ire f le xivn í . V případech c) , d) jsou relace antisymetrické, tranzitivní a konektivní a tedy každá z nich je lineární uspořádání. Kromě toho každá z těchto relací, které jsou nazývány „neostré nerovnosti“ je re f le xivn í . Z označení „ostrá nerovnost“ použijeme slovo „ostrá“ pro všechna ta uspořádání, která jsou antireflexivní – zavedeme termín ostré uspořádání. Z označení „neostrá nerovnost“ použijeme slovo „neostrá“ pro všechna ta uspořádání, která jsou reflexivní – zavedeme termín neostré uspořádání. Ostré uspořádání v množině M je uspořádání, které je v M antireflexivní . Neostré uspořádání v množině M je uspořádání, které je v M reflexivní .

9.3. V množině {e, f, g, h} je dána relace a) b)

{ ef , hg } { ef , hg , ee , ff , gg , hh }

23

c) { ef , hg , gg } d) { gf, ge, gh, fe, f h, eh } e) { ee, ff, gg , hh , ef , hg } f) { ee, ff, gg , hh , f h , fg , fe , hg , he , ge } g) { ef , fe , fg , hf } Zjistěte, zda je tato relace uspořádání, popř. o který speciální typ uspořádání se jedná . Výsledky jsou uvedeny v tabulce : případ

a) b) c) d) e) f) g)

uspořádání ostré

uspořádání neostré

uspořádání lineární

je není není není je není není není není je není je není je není není je je tato relace není uspořádání

Je možné, že poněkud překvapí případ c) a to tím, že relace v něm uvedená je uspořádání, které není ani ostré ani neostré. Některá uspořádání v jedné a téže množině mohou být ostrá, jiná neostrá (to jsou extrémní případy), ale může existovat i řada případů uspořádání, která nejsou ani ostrá ani neostrá .

9.4. Uveďte vlastnosti binární relace, jestliže se jedná o relaci tohoto typu : lineární uspořádání, ostré uspořádání, neostré uspořádání, lineární ostré uspořádání, lineární neostré uspořádání . Výsledky : typ relace

vlastnosti

lineární uspořádání ostré uspořádání neostré uspořádání ostré lineární uspořádání neostré lineární uspořádání

antisym., tranz., konekt. antisym., tranz., antirefl. antisym., tranz., refl. antisym., tranz., konekt., antirefl. antisym., tranz., konekt., refl.

9.5. Rozhodněte, zda relace S v množině G z úlohy 8.3. je nebo není lineární uspořádání, ostré uspořádání, neostré uspořádání, lineární ostré uspořádání, lineární neostré uspořádání v množině G . Řešení : relace uvedená v úloze 8.3. je a) ostré lineární uspořádání v množině všech reálných čísel b) neostré uspořádání v množině všech přirozených čísel, není to však uspořádání lineární, protože to není konektivní relace (např. pro dva různé prvky 5, 7 neplatí ani 5|7, ani 7|5) c) není vůbec uspořádání v dané množině, protože v množině všech celých čísel není antisymetrická (např. 2 |-2 a též -2|2) d) je uspořádání v množině G, toto uspořádání však není v G ani lineární (není totiž v G konektivní, neboť neobsahuje např. ani [r,u] ani [u,r]),ani ostré (není v G antireflexivní, protože obsahuje [s,s]),

24

e) f) g) h) i) j) k)

ani neostré (není v G reflexivní, protože neobsahuje např. [r,r] je ostré uspořádání v množině všech přirozených čísel ( relace antisymetrická, tranzitivní a antireflexivní v množině G ) není uspořádání v množině všech přirozených čísel, protože není antisymetrická (nebo např. proto, že není tranzitivní ) je neostré lineární uspořádání v množině všech přirozených čísel je ostré lineární uspořádání v množině G = {e,f,g} není uspořádání není uspořádání prázdná relace v množině všech přirozených čísel je uspořádání a je to uspořádání ostré (neobsahuje žádnou uspořádanou dvojici a tudíž ani žádnou uspořádanou dvojici stejných prvků), ale není lineární

9.6.

Vyhledejte a prostudujte v učebnicích matematiky pro první ročník (případně pro další ročníky prvního stupně ZŠ) učivo, v němž se uplatňuje pojem uspořádání. Zhodnoťte, o jaké typy uspořádání se jedná. Je uspořádáním relace „hned před“ ?

10 . Uspořádaná množina Připojme k dané množině M její uspořádání U tím, že utvoříme uspořádanou dvojici [ M , U ] . Tato uspořádaná dvojice udává nejen danou množinu M , ale zároveň vypovídá, jak je množina M uspořádána. Jsou-li např. U , V dvě různá uspořádání v téže množině M , pak [M,U] a [M,V] jsou dvě navzájem různé uspořádané množiny. Definice uspořádané množiny : Uspořádaná dvojice [ M , U ] se nazývá uspořádaná množina, právě když U je uspořádáním v množině M .

10.1.

Vyšetřete, zda následující uspořádaná dvojice množin je nebo není uspořádaná množina a) [ { m, p, k } , { km, mp, kp } ] b) [ N, < ] , kde N je množina všech přirozených čísel a znakem < zde označujeme stručně relaci { [x,y]∈ ∈N× ×N: x < y } c) [ N, > ] , kde znakem > je označena relace { [x,y]∈ ∈N× ×N: x > y } d) [ { a, b, c, d } , { ab, ba, cd } ] Řešení : a) Druhá složka uvedené uspořádané dvojice, tj. množina { km, mp, kp } je uspořádání, dokonce ostré lineární uspořádání v množině { m, p, k } , proto [ { m, p, k } , { km, mp, kp }] je uspořádaná množina (ostře lineárně uspořádaná množina) . b) [ N, < ] je rovněž ostře lineárně uspořádaná množina. Uspořádání < v množině N se často nazývá přirozené uspořádání množiny všech přirozených čísel, při vyučování na prvním stupni ZŠ je právě toto uspořádání zvláště důležité. c) Rovněž uspořádaná dvojice [ N , > ] je ostře lineárně uspořádaná množina, protože > je ostré lineární uspořádání v množině všech přirozených čísel .

25

d) Uvedená uspořádaná dvojice není uspořádanou množinou, protože { ab, ba, cd } není uspořádáním v množině { a, b, c, d } , není např. v této množině tranzitivní.

První prvek, poslední prvek uspořádané množiny V pracovním sešitu matematiky pro první ročník byla zakreslena ilustrace k vyprávění O veliké řepě. Množina všech bytostí, které se podílely na vytahování veliké řepy, je uspořádána podle toho, kdo přišel k řepě dříve. Žáci uváděli toto uspořádání slovy „je před“, např. dědeček je před babičkou, dědeček je před vnučkou, dědeček je před myškou, vnučka je před pejskem ale i před kočičkou atd. a též hovořili o inverzní relaci k tomuto uspořádání (aniž by ovšem používali tohoto termínu) a vyjadřovali ji slovy „je za“, např. kočička je za babičkou atd. Docházeli zcela přirozeně a samozřejmě k závěru, že „dědeček je první“ a zdůvodňovali jej takto: „protože před dědečkem nikdo není“ (velká řepa nepatří mezi bytosti, které ji vytahují) nebo takto „všichni ostatní jsou za ním“. Podobně hodnotili, že „myška je poslední, protože za ní nikdo není“ nebo „myška je poslední, protože všichni ostatní jsou před ní“. Tyto úvahy mohou být pro nás východiskem při vytváření definice prvního a posledního prvku (ostře lineárně) uspořádané množiny: Definice prvního prvku uspořádané množiny: Nechť U je ostré lineární uspořádání v množině M. Prvek a množiny M je první prvek uspořádané množiny [ M , U ] , právě když pro každý prvek x množiny M platí, že x není před a v uspořádání U . Definice posledního prvku uspořádané množiny: Nechť U je ostré lineární uspořádání v množině M. Prvek b množiny M je poslední prvek uspořádané množiny [ M , U ] , právě když pro každý prvek x množiny M platí, že b není před x v uspořádání U . Pokud U je ostré uspořádání, čteme zápis r U s obvykle takto: „ r je (v uspořádání U) před s “, můžeme též říci, že „ s je (v uspořádání U) za r “. Je zřejmé, že uspořádání „ je před “ a „ je za “ jsou navzájem inverzní relace.

10.2. Určete první a poslední prvek uspořádané množiny a) [ { a , b , c } , { ca , ab , cb } ] b) [ { a , b , c } , { bc , ba , ca } ] c) [ N , < ] d) [ N , > ] e) [ N , U ] , kde U = { [x,y]∈N×N: (x je sudé a y je liché) ∨ (x,y jsou sudá ∧ x < y) ∨ (x,y jsou lichá ∧ x > y ) }. Řešení : a) Podle definice prvního prvku je prvním prvkem této uspořádané množiny c , protože žádný z prvků dané množiny není před ním. Podle definice posledního prvku je b posledním prvkem této uspořádané množiny, protože b není před žádným prvkem dané množiny. b) Daná množina je stejná, uspořádání je jiné než v případě a). Prvním prvkem je b, posledním prvkem je a .

26

Důkaz lze provést obdobně jako v případě a). c) Prvním prvkem je číslo jedna, protože žádné přirozené číslo není menší než jedna, čili číslo jedna je menší než každé jiné přirozené číslo. Poslední prvek neexistuje, neexistuje totiž největší přirozené číslo: zvolíme-li kterékoliv přirozené číslo, existuje vždy přirozené číslo, které je větší. d) První prvek neexistuje, protože neexistuje největší přirozené číslo, posledním prvkem je číslo jedna. e) Uspořádání množiny N je tentokrát dáno tak, že nejprve jsou zařazena sudá a pak lichá čísla, tj. kterékoliv sudé číslo je před kterýmkoliv lichým číslem, samotná sudá čísla jsou uspořádána tak, že vždy menší číslo je před větším číslem a lichá čísla jsou uspořádána tak, že vždy větší je před menším. Danou uspořádanou množinu zapišme názorně takto: { 2 , 4 , 6 , 8 , 10 , ......,....., 5 , 3 , 1 } Šipka nad zápisem výrazně naznačuje dané uspořádání (tento způsob názorného naznačení uspořádání je možno použít i ve vyučování matematice od prvního ročníku ZŠ). Z definice prvního a posledního prvku vyplývá, že prvním prvkem takto uspořádané množiny všech přirozených čísel je číslo dvě a posledním prvkem je číslo jedna. Názorně je to zřejmé podle zápisu se šipkou.

Uspořádání a jeho grafické znázorňování Uspořádání lze graficky znázorňovat jako kteroukoliv binární relaci uzlovým nebo síťovým grafem.

10.3. Zvolte z předcházejících úloh některá uspořádání a znázorněte je uzlovým i síťovým grafem. Zkoumejte, jak je možno podle těchto grafů poznat vlastnosti relací. Kromě uzlového nebo síťového grafu zavedeme jeden speciální způsob grafického znázornění, který je určen pouze pro uspořádání. Je to tzv. Hasse-ův diagram. Vytvoření Hasseova diagramu si ukážeme na příkladu . Příklad : V množině A = { 1 , 2 , 3 , 4 , 5 , 6 } je dána binární relace {[x,y]∈A× ×A : x | y } . Tato relace „x je dělitelem y“ je v množině A antireflexivní a tranzitivní a tedy je to uspořádání . Kromě toho je reflexivní a tedy je to neostré uspořádání. Zapišme ji výčtem uspořádaných dvojic: {[1;1],[1;2],[1;3],[1;4],[1;5],[1;6],[2;2],[2;4],[2;6],[3;3],[3;6],[4;4],[5;5],[6;6]} . Vytvoříme Hasse-ův diagram (Obr.8): Prvky množiny A znázorníme body. 4 6 Uspořádanou dvojici zaznamenáme v diagramu tím, že příslušné body spojíme úsečkou (nikoliv šipkou), 2 3 5 můžeme si to dovolit, uspořádání je antisymetrická relace (úsečka znamená uspořádanou dvojici „odzdola nahoru“). 1 Obr.8

27

Nepotřebujeme zde také zaznamenávat uspořádané dvojice, jejichž existence vyplývá z tranzitivnosti (každé uspořádání je přece tranzitivní). Nebudeme zaznamenávat ani uspořádané dvojice, jejichž složky se sobě rovnají (to je určitá nevýhoda Hasseova diagramu: podle něho nepoznáme, zda uspořádání je nebo není reflexivní nebo antireflexivní, čili zda je to uspořádání ostré či neostré).

10.4. Znázorněte Hasse-ovými diagramy aspoň tři různá lineární uspořádání v množině K = { a , b , c , d } . Tato uspořádání zapište výčtem uspořádaných dvojic. Určete v každém tomto uspořádání první prvek a poslední prvek. Řešení : Zvolíme diagramy (Obr. 9) a podle diagramů zapíšeme uspořádání: b a c U1 = { ca , cd , cb , ad , ab , db } d c a Obr. 9 U2 = { bd , bc , ba , dc , da , ca } a d b U3 = { db , da , dc , ba , bc , ac } c U1 b U2 d U3 První prvek množiny K v určitém uspořádání určíme - buď podle Hasse-ova diagramu ( je to prvek znázorněný v diagramu „nejníže“ ze všech ) - anebo ze zápisu uspořádání jako množiny uspořádaných dvojic ( je přede všemi ostatními prvky , žádný není před ním ): v uspořádání U1 je prvním prvkem c , v uspořádání U2 je prvním prvkem b , v uspořádání U3 je prvním prvkem d . Poslední prvek množiny K v určitém uspořádání určíme rovněž - buď podle Hasse-ova diagramu ( je to prvek znázorněný v diagramu „nejvýše“ ze všech ) - anebo ze zápisu uspořádání jako množiny uspořádaných dvojic ( je za všemi ostatními prvky , žádný není za ním ): v uspořádání U1 je posledním prvkem b , v uspořádání U2 je posledním prvkem a , v uspořádání U3 je posledním prvkem c .

11. Zobrazení Úvodní příklad : Jsou dány množiny A , B , R tak, že A = { -1 ; 0 ; 1 ; 2 ; 3 } , B = { 1 ; 2 ; 3 ; 4 } , R = { [x,y]∈A×B: y = x2 } . Je zřejmé, že R je binární relace z množiny A do množiny B . Zapišme relaci R výčtem uspořádaných dvojic: R = { [-1 ; 1 ] , [ 1 ; 1 ] , [ 2 ; 4 ] } . Zaměřme pozornost na zvláštní vlastnost této relace: - každé z čísel -1 , 1 , 2 z množiny A je první složkou jen jedné a žádné jiné uspořádané dvojice relace R - čísla 0 a 3 z množiny A nejsou první složkou žádné uspořádané dvojice relace R To znamená: každý prvek množiny A je první složkou nejvýše jedné uspořádané dvojice relace R .

28

Relace, která má tuto vlastnost, se nazývá zobrazení . Definice zobrazení : Relace R z A do B se nazývá zobrazení z A do B, právě když

každý prvek množiny A je první složkou nejvýše jedné uspořádané dvojice relace R. 11.1. Znázorněte zobrazení R = { [x,y]∈A×B: y = x2 } , A = { -1 ; 0 ; 1 ; 2 ; 3 } , B = { 1; 2; 3; 4 } z úvodního příkladu a) uzlovým grafem b) kartézským grafem. Popište, jak se projeví v uzlovém grafu a jak v kartézském grafu charakteristická vlastnost zobrazení . Výsledek : Na uzlovém grafu (šipkovém diagramu) se uvedená vlastnost našeho zobrazení projevuje tak, že „z každého uzlu vychází nejvýše jedna šipka“. Na kartézském (síťovém) grafu se skutečnost, že uvedená relace je zobrazením projevuje tak, že „na každé přímce, která znázorňuje prvek množiny A , se vyskytuje nejvýše jeden zvýrazněný průsečík“.

11.2. Ověřte, zda relace R z A do B je nebo není zobrazením, jestliže a) R = { [x,y]∈A×B: x je manželem y } , kde A je množina všech mužů, B množina všech žen v našem státě b) R = { [x,y]∈A×B: x je vlastníkem automobilu y } , jestliže A je množina všech žijících lidí, B je množina všech automobilů schopných jízdy c) R = { [x,y]∈A×B: x má rodné číslo y } , A je množina všech občanů českého státu, B je množina všech rodných čísel, která jsou registrována v našem státě d) R = { [x,y]∈A×B: x = y } , A = N , B = N e) R = { [x,y]∈A×B: x < y } , A = B = N f) R = { [x,y]∈A×B: x || y } , A i B je množina všech přímek v rovině Řešení : a) R je zobrazením, protože každý muž v našem státě může být podle zákona manželem nejvýše jedné ženy. b) R není zobrazením, protože v množině všech lidí existuje aspoň jeden člověk, který vlastní více než jeden automobil. c) R je zobrazením, protože každý občan českého státu nemá více než jedno rodné číslo. d) R je zobrazením, protože každé přirozené číslo se rovná pouze samo sobě, tedy každé přirozené číslo se rovná nejvýše jednomu přirozenému číslu. e) R není zobrazením, protože např. 3 < 4 , ale také 3 < 5 a tedy není pravda, že přirozené číslo 3 je menší než nejvýše jedno přirozené číslo. f) R není zobrazením, protože ke každé přímce v rovině existuje mnoho přímek, které jsou s ní rovnoběžné a tedy není pravda, že určitá přímka je rovnoběžná nejvýše s jednou přímkou.

11.3. Určete, zda relace S je zobrazením z C do D , když a) S = { [m,n], [o,p], [p,p] }, C = { m, n, o, p }, D = { p, n } b) S = { [a,b], [b,a] }, C = { a, b }, D = C c) S = { [f,g], [g,h], [h,f], [f,h] }, C = { f, g, h, j }, C = D

29

d) S = { [f,g], [g,h], [h,f] }, C = { f, g }, D = { f, g, h } e) S = { [f,g], [g,g], [h,g] }, C = { f, g, h }, D = C Řešení : a) Každý prvek množiny C je první složkou nejvýše jedné uspořádané dvojice relace S : m je první složkou jen jedné uspořádané dvojice [m,n] , n není první složkou žádné uspořádané dvojice , je první složkou jen jedné uspořádané dvojice [o,p] , p je první složkou jen jedné uspořádané dvojice [p,p] . Proto relace S je zobrazení . b) Každý prvek množiny C je první složkou nejvýše jedné uspořádané dvojice relace S : a je první složkou jen jedné uspořádané dvojice [a,b] , b je první složkou jen jedné uspořádané dvojice [b,a] a tedy relace S je zobrazení . c) f je první složkou dvou uspořádaných dvojic [f,g] a [f,h] . Není tedy pravda, že každý prvek množiny C je první složkou nejvýše jedné uspořádané dvojice relace S a tedy v případě c) relace S není zobrazení . d) Každý prvek množiny C je první složkou nejvýše jedné uspořádané dvojice relace S : f je první složkou jen jedné uspořádané dvojice [f,g] , g je první složkou jen jedné uspořádané dvojice [g,g] , h je první složkou jen jedné uspořádané dvojice [h,g] , proto v tomto případě relace S je zobrazení . e) Každý prvek množiny C je první složkou nejvýše jedné uspořádané dvojice relace S : f je první složkou jen jedné uspořádané dvojice [f,g] , g je první složkou jen jedné uspořádané dvojice [g,g] , h je první složkou jen jedné uspořádané dvojice [h,g] , proto v tomto případě relace S je zobrazení .

11.4. Zvolte tříprvkovou množinu A a sestrojte relaci v A tak, aby byla a) zobrazením z A do A a současně relací typu ekvivalence v A b) zobrazením z A do A a uspořádáním v množině A Řešení : Volme např. A = { a, b, c } a a) R = { aa, bb, cc } b) R = { ab, cb }

11.5. Zapište všechna zobrazení v dvouprvkové množině. Řešení : Zvolme dvouprvkovou množinu, např. K = { a , b } . Máme sestrojit všechna zobrazení z množiny K do množiny K , jsou to tato zobrazení : { aa } , { ab } , { ba } , { bb } , { aa, bb } , { bb, ab } , { aa, ba } , { ab, ba } .

30

12. Speciální typy zobrazení Prosté zobrazení Úvodní příklad : Jsou dány dvě množiny K = { a , b , c , d }, L = { c , d , e , f , g } a binární relace P = { ad , bc , cg } z K do L . Protože každý prvek množiny K je první složkou nejvýše jedné uspořádané dvojice, která je prvkem relace P , znamená to, že relace P je zobrazením z K do L . V našem případě ale také obráceně „každý prvek množiny L je druhou složkou nejvýše jedné uspořádané dvojice relace P “ . Zobrazení, které má tuto vlastnost se nazývá prosté . Podle úvah z úvodního příkladu vyslovíme definici pojmu prosté zobrazení : Zobrazení Z z A do B se nazývá prosté zobrazení z A do B, právě když každý prvek množiny B je druhou složkou nejvýše jedné uspořádané dvojice zobrazení Z.

12.1. Rozhodněte, zda binární relace a) {ma,bu} z množiny {m,b,g} do množiny {a,e,u} b) {ma,ba} z množiny {m,b,g} do množiny {a,e,u} je nebo není prosté zobrazení. Řešení : Relace v případě a) i v případě b) je zobrazení, neboť každý prvek množiny {m,b,g} je první složkou nejvýše jedné uspořádané dvojice dané relace. Relace v případě a) je prosté zobrazení , protože každý prvek množiny { a , e , u } je druhou složkou nejvýše jedné uspořádané dvojice dané relace. Relace v případě b) ne ní prosté zobrazení , protože prvek a množiny { a , e , u } je druhou složkou dvou uspořádaných dvojic (tj. více než jedné uspořádané dvojice) dané relace.

12.2. Znázorněte uzlovým grafem a) zobrazení { ma , bu } z množiny { m , b , g } do množiny { a , e , u } b) zobrazení { ma , ba } z množiny { m , b , g } do množiny { a , e , u } Popište, jak se v uzlovém grafu projevuje, zda uvedené zobrazení je nebo není prosté,. Řešení : a) m a b) m a b

e

b

e

g

u

g

u

Obr. 10 Obr. 11 V obou grafech jsou skutečně znázorněna zobrazení, což podle grafů poznáme snadno:

31

u obou grafů totiž platí, že „z každého uzlu vychází nejvýše jedna šipka“. a) O grafu prostého zobrazení v případě a) (na Obr.10) platí, že „ke každému uzlu směřuje nejvýše jedna šipka“ , b) O grafu zobrazení, které není prosté v případě b) (na Obr.11) platí negace předcházejícího výroku : „není pravda, že ke každému uzlu směřuje nejvýše jedna šipka“ čili platí, že „existuje aspoň jeden uzel, ke kterému směřuje více šipek než jedna“.

12.3. Znázorněte síťovým (kartézským) grafem a) zobrazení { ma , bu } z množiny { m , b , g } do množiny { a , e , u } b) zobrazení { ma , ba } z množiny { m , b , g } do množiny { a , e , u } Popište, jak se v síťovém grafu projevuje, zda uvedené zobrazení je nebo není prosté. Řešení : u b) u a) e a

e a m

b

g

Obr. 12

m

b

g

Obr. 13

V případě a), tj. na Obr.12 vidíme, že na každé přímce, která znázorňuje prvek množiny B , se vyskytuje nejvýše jeden zvýrazněný průsečík , proto jde o prosté zobrazení . V případě b), tj. na Obr.13 pozorujeme, že na přímce, která znázorňuje prvek a množiny B , se vyskytuje více než jeden zvýrazněný průsečík, proto jde o zobrazení, které není prosté .

12.4. Rozhodněte, která zobrazení jsou a která nejsou prostá R = { [m,n], [o,p], [p,p] } z A = { m, n, o, p } do B = { p, n } Z = { [a,b], [b,a] } z C = { a, b } do C T = { [f,g], [g,h], [h,f], [f,h] } z K do K , K = { f, g, h, j } S = { [f,g], [g,g], [h,g] } z P do P , P = { f, g, h } Q = { [x,y]∈A×B: x je manželem y } , kde A je množina všech mužů, B množina všech žen v našem státě f) R = { [x,y]∈N×N: x = y } z N do N g) Z = { [x,y]∈R×R: y = 3x+5 } z R do R , kde R je množina všech reálných čísel Výsledky : a) zobrazení R z A do B není prosté (prvek p množiny B je druhou složkou dvou uspořádaných dvojic relace R ) b) zobrazení Z z C do C je prosté (každý prvek množiny C je druhou složkou nejvýše jedné uspořádané dvojice ) c) relace T v množině K není zobrazení ! ! d) zobrazení S z P do P není prosté ( g je druhou složkou tří uspořádaných dvojic zobrazení S ) e) zobrazení Q z A do B je prosté (podle zákona o monogamii každá občanka našeho státu smí být manželkou nejvýše jednoho muže) a) b) c) d) e)

32

f) zobrazení R v množině N (rovnost přirozených čísel) je prosté (každé přirozené číslo je rovno pouze samo sobě) g) zobrazení Z z R do R je prosté (každé reálné číslo je druhou složkou jediné uspořádané dvojice zobrazení Z ) Poznámka : Toto zobrazení je tzv. lineární funkce – zobrazení v číselných množinách se zpravidla nazývají funkce.

12.5. K danému zobrazení Z z A do B utvořte inverzní relaci.

Vyšetřete, zda Z-1 ( tj. inverzní relace k zobrazení Z ) je nebo není zobrazení, popřípadě jestli je to prosté zobrazení a) Z = { ad, bf, cc, de } , A = { a, b, c, d } , B = { b, c, d, e, f } b) Z = { ae, be, cf, dd } , A = { a, b, c, d } , B = { b, c, d, e, f } Řešení : -1 -1 a) Z = { da, fb, cc, ed }. Z je prosté zobrazení z B do A . Podle toho, jak -1 tvoříme inverzní relaci, je zřejmé, že Z je zobrazením, právě když Z je prosté zobrazení . -1 -1 b) Z = { ea, eb, fc, dd }. Relace Z není zobrazením. Je tomu tak proto, že zobrazení Z není prosté . Poznámka : Zkušenost z řešení úlohy 12.5. nás vede k tomuto zobecnění : Inverzní relace Z-1 k zobrazení Z je zobrazení z B do A , právě když zobrazení Z z A do B je zobrazení prosté.

První a druhý obor relace Přípravná úloha: 12.6. Jsou dány množiny A = { k, l, m, n }, B = { a, o, u } a relace R z A do B, R = { ka, ko, lo, na }. Vypište všechny prvky množiny A, z nichž každý je první složkou aspoň jedné uspořádané dvojice R. Výsledek : Jsou to prvky k, l, n. Množinu { k, l, n } budeme nazývat první obor relace R a zavedeme pro něj označení O1(R) . Definice prvního oboru relace: První obor relace R z množiny A do množiny B je množina všech prvních složek všech uspořádaných dvojic relace R Definici prvního oboru relace R z A do B lze zapsat stručně pomocí symbolů takto: O1(R) = { x∈A: (∃y∈B) x R y }. Z definice vyplývá, že pro každou relaci R z A do B platí, že O1(R) ⊂ A . Přípravná úloha : 12.7. Jsou dány množiny A = { k, l, m, n }, B = { a, o, u } a relace R z A do B, R = { ka, ko, lo, na }.

33

Vypište všechny prvky množiny B, z nichž každý je druhou složkou aspoň jedné uspořádané dvojice R . Řešení : Jsou to prvky a, o . Množinu { a, o } budeme nazývat druhý obor relace R a zavedeme pro něj označení O2(R). Definice druhého oboru relace : Druhý obor relace R z množiny A do množiny B je množina všech prvních složek všech uspořádaných dvojic relace R . Definici druhého oboru relace R z A do B lze zapsat stručně pomocí symbolů takto: O2(R) = { y∈B: (∃x∈A) x R y } . Z definice vyplývá, že pro každou relaci R z A do B platí, že O2(R)⊂B .

12.8. Zjistěte O1(S) a O2(S), jestliže S je relace z množiny E do množiny F a jestliže a) E = { k, l, m, n, o, p }, F = { n, o, p, r }, S = { nn, oo, kr, pr, or } b) E = { a, b, c, d }, F = {x∈N: x < 50 }, S = { [c,17], [d,1], [c,1] } c) E = N, F = C, S = { [x,y]∈E×F: y = 2x – 1 } d) E = F = { a, b, c }, S = { ab, ac, ba, cb, cc, ca } Výsledky : a) O1(S) = { k, n, o, p } , O2(S) = { n, o, r } b) O1(S) = { c, d } , O2(S) = { 1 ; 17 } c) O1(S) = N , druhým oborem relace S je množina všech lichých přirozených čísel d) O1(S) = O2(S) = { a, b, c }

12.9. Určete první a druhý obor zobrazení Z z A do B, když A = { 1; 2; 3; 5 }, B = { 2; 3; 4; 5; 6; 7 }, Z = { [x,y]∈A×B: x + y = 8 } b) A = { m, r, v, u }, B = { s, t }, Z = { mt, vs } c) A = { a, b, c, d }, B = { c, d, e }, Z = { ad, be, cc, de } d) A = N, B je množina všech sudých přirozených čísel Z = { [x,y]∈A×B: y = 2x } Řešení : a) Z = { [1;7], [2;6], [3;5], [5;3] } O1(Z) = { 1, 2, 3, 5 } , O2(Z) = { 3, 5, 6, 7 } b) O1(Z) = { m, v } , O2(Z) = { s, t } c) O1(Z) = { a, b, c, d } = A , O2(Z) = { c, d, e } = B d) O1(Z) = N , O2(Z) je množina všech sudých přirozených čísel a)

Zobrazení množiny do množiny Zobrazení z množiny na množinu Zobrazení množiny na množinu Přípravná úloha:

12.10. Nechť jsou dány množiny A, B tak, že A = { a, b, c, d }, B = { f, e, d }. Sestrojte aspoň jedno takové zobrazení Z z A do B , aby platilo, že

34

a) O1(Z) = A b) O2(Z) = B c) O1(Z) = A ∧ O2(Z) = B d) O1(Z) ≠ A ∧ O2(Z) ≠ B Výsledky : Uveďme od každého případu alespoň jedno zobrazení, které splňuje dané podmínky: a) { af, be, cf, de }, { ad, bd, cd, dd }, { ae, bd, ce, df } apod. b) { af, be, cd }, { bd, cf, de }, { af, be, cd }, { bd, cf, de } apod. c) {af,be,cd,dd}, {ae,be,cf,dd}, {ad,bf,ce,de}, {af,bd,ce,df} apod. d) {af,be}, {ae,cf,df}, {ae}, {ad,dd}, {bf,ce,de} apod. V předcházející přípravné úloze jsme studiem různých případů zobrazení z A do B poznali různé speciální typy zobrazení, které se vzájemně liší podle toho, zda a) O1(Z) = A b) O2(Z) = B c) O1(Z) = A ∧ O2(Z) = B Názvy uvedených speciálních typů zobrazení jsou uvedeny v tabulce: vlastnost zobrazení O1(Z) = A O2(Z) = B O1(Z) = A ∧ O2(Z) = B

název zobrazení zobrazení množiny A do množiny B zobrazení z množiny A na množinu B zobrazení množiny A na množinu B

Na základě řešení přípravné úlohy a zavedení názvů v uvedené tabulce formulujme definice speciálních typů zobrazení : Zobrazení Z z A do B se nazývá zobrazení A do B , právě když O1(Z) = A . Zobrazení Z z A do B se nazývá zobrazení z A na B , právě když O2(Z) = B . Zobrazení Z z A do B se nazývá zobrazení A na B , právě když O1(Z) = A ∧ O2(Z) = B . Příklady : Zobrazení z A do B z úlohy 12.10. označme speciálními názvy : v případě a) zobrazení množiny A do množiny B , v případě b) zobrazení z množiny A na množinu B , v případě c) zobrazení množiny A na množinu B , v případě d) zobrazení z množiny A do množiny B, (není to žádný z uvedených tří speciálních typů).

12.11. Určete co nejvýstižněji, o který typ zobrazení se jedná: a) { [x,y]∈C×N: x + 5 = y } b) { [x,y]∈N×N: x2 = y }

35 2

c) { [u,v]∈C×N0: u = v } d) {[x,y]∈G×L: x je manželem y }, jestliže G je množina všech mužů občanů našeho státu a L je množina všech žen občanek našeho státu e) {[x,y]∈G×L: x je manželem y }, jestliže G je množina všech mužů a L je množina všech žen žijících v současné době na světě f) { [x,y]∈N×S: 2 x = y }, kde S je množina všech sudých přirozených čísel g) { [x,y]∈A×B: 2 x -1 = y }, A = { x∈R: x < 1000 }, B = { y∈R: y > -√5 } h) { [x,y]∈A×B: student x má řidičský průkaz y } A je množina všech studentů vaší skupiny B je množina řidičských průkazů všech studentů vaší skupiny i) { [x,y]∈A×B: student x má občanský průkaz y } A je množina všech studentů vaší skupiny, B je množina občanských průkazů všech studentů vaší skupiny, Výsledky : a) prosté zobrazení z C na N, b) prosté zobrazení N do N, c) zobrazení C do N, ale není prosté, d) prosté zobrazení z L do L, e) není zobrazení - např. v arabských zemích není uplatňován zákon o monogamii, f) prosté zobrazení N na S, g) prosté zobrazení z A do B .

12.12. Utvořte alespoň jedno prosté zobrazení A na B , jestliže a) A = { r, k, t, e }, B = { 9; 1; 5; 4 } b) A = { r, k, t, e }, B = { 9; 1; 5 } c) A = { r, k, t }, B = { 9; 1; 5; 4 } d) A = { r, k, t }, B = { 9; 1; 5 } e) A = { x∈N: x < 10 }, B = { y∈C: 284 < y < 294 } f) A = { x∈N: x < 6 }, B = { 17 ; 24 ; 39 ; 1 ; 8 } Výsledky : jsou to např. tato prostá zobrazení A na B a) { r 9 , k 1 , t 5 , e 4 } , { r 1 , k 4 , t 5 , e 9 } , { r 5 , k 9 , t 4 , e 1 } apod., b) neexistuje zobrazení požadovaných vlastností c) neexistuje zobrazení požadovaných vlastností d) { r 1 , k 5 , t 9 } , { r 1 , k 9 , t 5 } , { r 5 , k 1 , t 9 } , { r 5 , k 9 , t 1 } , { r9, k1, t5 }, { r9, k5, t1 } e) např. { [ 1 ; 285 ] , [ 2 ; 286 ] , [ 3 ; 287 ] , [ 4 ; 288 ] , … , [ 9 ; 293 ] }, { [ 1 ; 286 ] , [ 2 ; 287 ] , [ 3 ; 288 ] , [ 4 ; 289 ] , … , [ 9 ; 285 ] }, ⋅ ⋅ ⋅ { [ 1 ; 293 ] , [ 2 ; 285 ] , [ 3 ; 289 ] , [ 4 ; 291 ] , … , [ 9 ; 292 ] } apod. f) např. { [ 1 ; 17 ] , [ 2 ; 24 ] , [ 3 ; 39 ] , [ 4 ; 1 ] , [ 5 ; 8 ] }, { [ 1 ; 17 ] , [ 2 ; 8] , [ 3 ; 1 ] , [ 4 ; 24 ] , [ 5 ; 39 ] }, ⋅ ⋅ ⋅ { [ 1 ; 24 ] , [ 2 ; 1 ] , [ 3 ; 8 ] , [ 4 ; 39 ] , [ 5 ; 17 ] } atd.

36

12.13. Utvořte všechna prostá zobrazení a) { a , b , c } na { d , e , f } b) { a , b , c } na { b , c , d } c) { a , b , c } na { a , b , c } Výsledky : a) { ad , be , cf } , { ad , bf , ce } , { ae , bd , cf } , { ae , bf , cd }, { af , bd , ce } , { af , be , cd } , takových zobrazení je šest b) { ab , bc , cd } , { ab , bd , cc } , { ac , bb , cd }, { ac , bd , cb } , { ad , bb , cc } , { ad , bc , cb } c) { aa , bb , cc } , { aa , bc , cb } , { ab , ba , cc } , { ab , bc , ca } , { ac , ba , cb } , { ac , bb , ca }

Literatura [1] Bělík M. a kol.: Matematika pro studium učitelství 1. st. ZŠ PF UJEP Ústí n.Lab., 1996, 2000, 2002 [2] Blažek J. a kol.: Algebra a teoretická aritmetika, I. díl SPN Praha, 1983 [3] Drábek J. a kol.: Základy elementární aritmetiky SPN Praha, 1985 [4] Hruša K.: Základy moderní matematiky pro učitele 1.-5.ročníku ZDŠ, I. a II. díl SPN Praha, 1975 [5] Sciacovelli G.: Nová matematika SPN Praha, 1978 [6] Šedivý J.: O modernizaci školské matematiky SPN Praha, 1969