1 Relace a mohutnost
Pˇr´ıklad 1.1 Minule jsme si uk´azali, ˇze bin´arn´ı relaceR⊆Z×Zdefinovan´a x R ypr´avˇe tehdy, kdyˇz existujek∈Ztakov´e, ˇzex−y= 3k ,
je ekvivalence na mnoˇzinˇe cel´ych ˇc´ıselZ. Popiˇste tˇr´ıdy ekvivalenceR[2], R[−2], R[11] odpov´ıdaj´ıc´ı ˇc´ıslu 2.
Podle definice tˇr´ıdy ekvivalence m´ame:
R[2] ={x∈Z|x R2}={x∈Z| ∃k∈Zt.ˇz.x−2 = 3k}={x∈Z| ∃k∈Zt.ˇz.x= 2 + 3k}, R[2] ={. . . ,−10,−7,−4,−1,2,5,8,11,14,17,20, . . .}.
Podobnˇe
R[−2] ={x∈Z|x R−2}={x∈Z| ∃k∈Zt.ˇz.x−(−2) = 3k}={x∈Z| ∃k∈Zt.ˇz.x=−2+3k}, R[−2] ={. . . ,−14,−11,−8,−5,−2,1,4,7,10,13, . . .}.
Podobnˇe bychom mohli popsat iR[11]. Nicm´enˇe tady m˚uˇzeme dostat v´ysledek okamˇzitˇe. Vˇsimˇete si, ˇze 11∈R[2]. Z toho plyne, ˇzeR[2]∩R[11]6=∅. Protoˇze v´ıme, ˇze tˇr´ıdy ekvivalence jsou po dvou disjuktn´ı, mus´ı nutnˇe platit, ˇzeR[2] =R[11].
Pˇr´ıklad 1.2 Zjistˇete, jestli je n´asleduj´ıc´ı bin´arn´ı relaceR ⊆R2×R2 ekvivalence. Popiˇste tˇr´ıdu ekvivalenceR[(1,1)].
(x, y)R(u, v) pr´avˇe tehdy, kdyˇzx+y−u−v= 0. Ovˇeˇr´ıme, reflexivitu, symetrii a tranzitivitu.
1. Reflexivita: Mˇejme libovoln´y prvek (x, y)∈R2. Protoˇzex+y−x−y= 0, plat´ı (x, y)R(x, y).
Relace je tud´ıˇz reflexivn´ı.
2. Symetrie: Mˇejme dva prvky (x, y),(u, v)∈R2takov´e, ˇze (x, y)R(u, v). Z definice relaceRto znamen´a, ˇzex+y−u−v= 0. Pokud tuto rovnici vyn´asob´ıme−1, dostanemeu+v−x−y= 0.
Tud´ıˇz m´ame (u, v)R(x, y) a relace je tedy symetrick´a.
3. Tranzitivita: Mˇejme tˇri prvky (x, y),(u, v),(a, b) ∈R2 takov´e, ˇze (x, y) R (u, v) a (u, v)R (a, b). Z definice R dostaneme, ˇze plat´ı rovnosti x+y−u−v = 0 a u+v−a−b = 0.
Seˇcten´ım tˇechto rovnost´ı z´ısk´amex+y−a−b= 0. Tud´ıˇz m´ame (x, y)R (a, b) a relace je tedy tranzitivn´ı.
Podle definice tˇr´ıdy ekvivalence m´ame:
R[(1,1)] ={(x, y)∈R2|(x, y)R(1,1)}={(x, y)∈R2|x+y−1−1 = 0}={(x, y)∈R2|y= 2−x}. Vid´ıme tedy, ˇze tˇr´ıda ekvivalenceR[(1,1)] je tvoˇrena body (x, y), kter´e splˇnuj´ı rovnici y= 2−x.
Jedn´a se tedy o pˇr´ımku, kter´a proch´az´ı body (0,2) a (2,0).
Pˇr´ıklad 1.3 Ovˇeˇrte, ˇze n´asleduj´ıc´ı bin´arn´ı relaceRna mnoˇzineA={1,2,3,4,5,6,7,8,9,10,11}
je uspoˇr´ad´an´ı. Nakreslete Hasse˚uv diagram a najdˇete nejvˇetˇs´ı, maxim´aln´ı, nejmenˇs´ı a minim´aln´ı prvky.
x R ypr´avˇe tehdy, kdyˇzx|y , kdex|yvyjadˇruje “xdˇel´ıy”, tj. ˇze existujek∈Ntakov´e, ˇzey=kx.
Ovˇeˇr´ıme, reflexivitu, antisymetrii a tranzitivitu.
1. Reflexivita: Mˇejme libovoln´y prvek x∈ A. Protoˇze x= 1·x (tj. x dˇel´ı samo sebe), plat´ı x R x. Relace je tud´ıˇz reflexivn´ı.
1
2. Antisymetrie: Mˇejme dva prvky x, y ∈A takov´e, ˇze x R y a y R x. Z definice relace R to znamen´a, ˇze x|y a y|x. Existuj´ı tedy pˇrirozen´a ˇc´ısla k, l ∈ N takov´a, ˇze y = kxa x= ly.
Dosazen´ım druh´e rovnice do prvn´ı dostaneme y =kly, z ˇcehoˇz plyne, ˇze kl = 1. Protoˇze k a l jsou pˇrirozen´a ˇc´ısla, mus´ı platit, ˇze k = l = 1. Tud´ıˇzy = 1·x= x. Relace je tedy antisymetrick´a.
3. Tranzitivita: Mˇejme tˇri prvky x, y, z∈Atakov´e, ˇzex R y ay R z. Z definiceRdostaneme, ˇze x|y a y|z. Existuj´ı tedy k, l ∈ N takov´e, ˇze y =kx a z = ly. Dosazen´ım prvn´ı rovnice do druh´e dostaneme z = (lk)x. Protoˇze lk ∈ N, m´ame x|z. Takˇze x R z a relace je tedy tranzitivn´ı.
Z Hasseova diagramu by mˇelo b´yt patrn´e, ˇze ˇz´adn´y nejvˇetˇs´ı prvek neexistuje. Naopak existuje nejmenˇs´ı a to je prvek 1, protoˇze 1 dˇel´ı kaˇzd´e ˇc´ıslo z mnoˇziny A. Tento prvek je zaroveˇn tak´e jedin´y minim´aln´ı prvek. Maxim´aln´ıch prvk˚u m´ame nˇekolik. Jsou to prvky 6,7,8,9,10,11.
8
4 6 9 10
3
2 5 7 11
1
Obr´azek 1: Hasse˚uv diagram
Pˇr´ıklad 1.4 Ovˇeˇrte, ˇze n´asleduj´ıc´ı bin´arn´ı relaceRna mnoˇzineN2je uspoˇr´ad´an´ı.
(x, y)R(u, v) pr´avˇe tehdy, kdyˇz plat´ı jedna z n´asleduj´ıc´ıch podm´ınek: 1.x < u, 2.x=uay≤v.
Vˇsimˇete si, ˇze pokud plat´ı podm´ınka 1 nebo 2 v definici relaceR, tak mus´ı platitx≤u. Jedn´a se o takzvan´e lexicografick´e uspoˇr´ad´an´ı, kter´e zn´ate ze slovn´ık˚u.
Ovˇeˇr´ıme, reflexivitu, antisymetrii a tranzitivitu.
1. Reflexivita: Mˇejme libovoln´y prvek (x, y)∈N2. Protoˇzex=xa y≤y, plat´ı (x, y)R(x, y).
Relace je tud´ıˇz reflexivn´ı.
2. Antisymetrie: Mˇejme dva prvky (x, y),(u, v)∈N2takov´e, ˇze (x, y)R(u, v) a (u, v)R(x, y).
Podle pozn´amky pod definic´ı mus´ı platitx≤uau≤x. To ale znamen´a, ˇzex=u. Zx=ua naˇsich pˇredpoklad˚u tedy plyne, ˇzey≤vav≤y. Tud´ıˇzy=va relace je tedy antisymetrick´a.
3. Tranzitivita: Mˇejme tˇri prvky (x, y),(u, v),(a, b) ∈N2 takov´e, ˇze (x, y) R (u, v) a (u, v)R (a, b). Z toho podobnˇe jako pˇredt´ım plyne, ˇzex≤ua u≤a. Pokud alespoˇn jedna z tˇechto nerovnost´ı je ostr´a (napˇr.x < u), pakx < a, z ˇcehoˇz potom plyne, ˇze (u, v)R(a, b). Pokud ne, pak x=u=a. To ale znamen´a, ˇze mus´ı platity ≤v a v ≤b. Tud´ıˇz mus´ı tak´e platit y≤b. Takˇze i v tomto pˇr´ıpadˇe (x, y)R(a, b) a relace je tedy tranzitivn´ı.
Vˇsimˇete si tak´e, ˇze vzhledem k relaci R nejsou ˇz´adn´e maxim´aln´ı prvky a tud´ıˇz tak´e ˇz´adn´y nejvˇetˇs´ı. Naopak existuje nejmˇenˇs´ı prvek a to je (0,0).
Pˇr´ıklad 1.5 Ukaˇzte, ˇze mnoˇzina N×N je spoˇcetn´a, tj. |N×N| = |N|. Zˇrejmˇe |N| ≤ |N×N|, protoˇze zobrazen´ıf: N →N×N definovan´e vztahem f(x) = (x,0) je prost´e (kdyˇzx6= y, pak (x,0)6= (y,0)). D´ıky Cantor-Bersteinovˇe vˇetˇe staˇc´ı tedy nal´ezt prost´e zobrazen´ıg :N×N→N. Jedno takov´e zobrazen´ı je definov´ano vztahem g(x, y) = 2x3y. Proˇc je toto zobrazen´ı prost´e.
Pˇredpokl´adejme, ˇzeg(x, y) =g(u, v). To znamen´a, ˇze 2x3y = 2u3v. Pˇripomeˇnme z aritmetiky, ˇze
2
kaˇzd´e pˇrirozen´e ˇc´ıslo lze rozloˇzit na souˇcin prvoˇc´ısel a nav´ıc pr´avˇe jedn´ım zp˚usobem. ˇC´ıslo 2x3y je konkr´etnˇe souˇcin xdvojek ay trojek. Podobnˇe 2u3v. Protoˇze 2x3y = 2u3v, mus´ı b´yt na obou stran´ach t´eto rovnice souˇcin stejn´ych prvoˇc´ısel. Toho lze dos´ahnout, ale jen kdyˇzx=ua y=v.
Zobrazen´ıg je tedy prost´e.
Pˇr´ıklad 1.6 Necht’ a, b ∈R takov´a, ˇze a < b. Ukaˇzte, ˇze |ha, bi|= |h0,1i|. Staˇc´ı naj´ıt bijekci z jedn´e z mnoˇzinha, bi,h0,1ido druh´e. Pˇrirozen´a volba jak zobrazit intervalh0,1inaha, bije pomoc´ı funkcef :h0,1i → ha, bijej´ıˇz grafem je useˇcka spojuj´ıc´ı body (0, a) a (1, b). Jedn´a se o ´useˇcku se smˇernic´ıb−aa posunema. Nakreslete si obr´azek. Analytick´y z´apisf vypad´a takto:
f(x) =a+ (b−a)x .
Toto zobrazen´ı je prost´e, protoˇze zf(x1) =f(x2) plynea+ (b−a)x1=a+ (b−a)x2, tj.x1=x2. Nav´ıc je i na. Mˇejmey∈ ha, bi. Hled´amex∈ h0,1itakov´e, ˇzef(x) =y. Naˇsey tedy mus´ı splˇnovat rovnicia+ (b−a)x=y. ˇReˇsen´ım t´eto rovnice dostaneme hledan´ex= (y−a)/(b−a).
Pˇr´ıklad 1.7 Necht’ a, b ∈ R takov´a, ˇze a < b. Ukaˇzte, ˇze |ha, bi| = |R|. Zˇrejmˇe |ha, bi| ≤ |R|, protoˇze ha, bi ⊆ R. D´ıky Cantor-Bersteinovˇe vˇetˇe staˇc´ı naj´ıt prost´e zobrazen´ıf: R→ ha, bi(t´ım uk´aˇzeme, ˇze|R| ≤ |ha, bi|). Uk´aˇzeme to nejprve pro speci´aln´ı pˇr´ıpad, kdy a=−1 a b= 1. Necht’
f:R→ h−1,1ije zobrazen´ı definov´an´e takto:
f(x) = ( x
1+x prox≥0,
x
1−x prox <0.
Ujasnˇete si, proˇcf(x)∈ h−1,1inebo si nakreslete graf. Uk´aˇzeme, ˇzef je prost´e. Pˇredpokl´adejme, ˇze f(x) = f(y). Vˇsimˇete si, ˇze z t´eto rovnosti plyne, ˇze bud’ x, y ≥ 0 nebo x, y ≤ 0, protoˇze x <0< y implikujef(x)<0< f(y). Pokud tedy x, y≥0, pakf(x) =f(y) pˇrejde na rovnici:
x
1 +x= y 1 +y. Vyn´asobn´ım jmenovateli dostaneme:
x+xy=x(1 +y) =y(1 +x) =y+xy .
Vid´ıme tedy, ˇze mus´ı platitx=y. Podobnˇe postupujeme i v pˇr´ıpadˇex, y≤0.
Uk´azali jsme tedy, ˇze |R| = |h−1,1i|. Z pˇredchoz´ıho pˇr´ıkladu v´ıme, ˇze |h−1,1i| = |h0,1i| =
|ha, bi|. Tud´ıˇz|R|=|ha, bi|.
3
