Algebry a grafy - Základní pojmy a definice

I.   BINÁRNÍ RELACE

1.1   (POJEM) MNOŽINA
Množina  (intuitivně) = souhrn objektů takových, že o každém (dalším) objektu lze říci, zda do tohoto souhrnu patří či nikoliv.

1.2   VELIKOST A SROVNÁNÍ MNOŽIN
Definice 1.2.1: Buď A konečná množina. Říkáme, že A je spočetná, jestliže existuje vzájemně jednoznačné zobrazení f: N -> A a píšeme:   |A|=|N|=X₀ (hebrejské písmeno alef s indexem 0). V opačném případě se A nazývá nespočetná a píšeme:   |A|>|N|=X₀.
Příklad 1.2.1: |N| = |S| = |Z| = |Q| = X₀ < |R| = |C| = |P(N)| = |2^N| = c (c...tzv. mohutnost kontinua)
Poznámka 1.2.1.1: |N| < |2^N| < |2^2N| < |2^22N| < ... Existuje více mohutností a je jich tolik, že se nevlezou do žádné množiny tzn. neexistuje množina všech množin.

1.3   OPERACE S MNOŽINAMI (viz cvičení:-)

1.4   BINÁRNÍ RELACE
Definice 1.4.1: Jsou-li X,Y množiny, pak jejich kartézským součinem rozumíme množinu
X × Y = {(x,y)|x patří do X, y patří do Y}.
Definice 1.4.2: Buďte X,Y dvě množiny. Binární relací mezi X,Y rozumíme libovolnou podmnožinu R podmnožina X×Y. Je-li X=Y, hovoříme o binární relaci na množině X.
Poznámka 1.4.2.1: Je-li R podmnožina X×Y relace, píšeme alternativně místo (x,y) patří do R také xRy (což je jiný možný zápis relace).
Definice 1.4.3: Buď R podmnožina X×Y relace. Klademe Dom R = {x|existuje y patřící do Y, že (x,y) patří do R} (tzv. domain, definiční obor relace). Im R =  {y|existuje x patřící do X, že (x,y) patří do R} (tzv. image, obor hodnot relace R).
Definice 1.4.4: Buď f podmnožina X×Y relace mezi X,Y taková, že ke každému x patřícímu do Dom f je podmnožina X existuje právě jedno y patřící do Y, že (x,y) patří do f. Pak říkáme, že f je zobrazení (množiny Dom f do Y, resp. z X do Y (jestliže nechceme blíže specifikovat Dom f) případně X do Y (pokud Dom f = X)) a píšeme:  f(x) = y   místo (x,y) patří do f a   f: X -> Y   místo   f je podmnožina X×Y.
Zobrazeníf: X->Y se nazývá:
   a) prosté (injektivní, injekce), jestliže platí pro každé x₁,x₂ patřící do X:  f(x₁) = f(x₂)   =>  x₁ = x₂  (Každý prvek z X má v Y nejvýše jeden vzor).
   b) na (surjektivní, surjekce), jestliže pro každé y patřící do Y existuje x patřící do X, že  f(x) = y.   (Každý prvek v Y má nějaký vzor v X).
   c) vzájemně jednoznačné (1-1značné, bijektivní, bijekce), jestliže je zobrazení prosté i na. (Prvky množin X,Y si jednoznačně odpovídají).
Definice 1.4.5: Buď R podmnožina X×Y relace. Inverzní relace k relaci R nazýváme relaci R^-1={(y,x)|(x,y) patří do R}. Zřejmě R^-1 je podmnožina Y×X. Jsou-li navíc R, R^-1 zobrazení, nazývá se R^-1 inverzním zobrazením k zobrazení R.
Definice 1.4.6: Buď R podmnožina X×Y a S podmnožina Y×Z relace. Složením (kompozicí) relací R,S rozumíme relaci SoR podmnožina X×Z takovou, že SoR = {(x,z)|existuje y patřící do Y, že (x,y) patří do R a (y,z) patří do S}. Tuto relaci čteme "S po R".
Příklad 1.4.6.1:    X = {1, 2, 3}, Y = {2, 4, 6, 8, 10}, Z = {r, s, t, u}
   R₁ = {(1,2), (1,6), (2,4), (3,4), (3,6), (3,8)}
   R₂ = {(2,u), (4,s), (4,t), (6,t), (8,u)}
   R₁oR₂ = {(1,u), (1,t), (2,s), (2,t), (3,s), (3,t), (3,u)}
Poznámka 1.4.6.1: Jsou-li f,g zobrazení f:X->Y, g:Y->Z, složená relace gof je opět zobrazení a nazývá se složené zobrazení. Místo pojmu zobrazení užíváme někdy ekvivalentní pojem funkce.
Poznámka 1.4.6.2: Je-li f:X->Y prosté zobrazení na Y (tedy bijekce), je f ^-1 o f = id_x a  f o f ^-1 = id_y, kde id_x je vlastně diagonální relace na X a id_y, diagonální relace na Y. Pro obecnou relaci toto neplatí: tzn. R^-1oR, RoR^-1 nemusí být vždy diagonální relace id_x resp. id_y.

Topologie a spojitost zobrazení
Definice 1.4.7: Buď X množina, ? (řecké tau) podmnožina 2^X systém jistých podmnožin množiny X. Řekneme, že ? je topologie na X, jestliže platí:
   1) O,X patří do ?  (neboli prázdná množina a množina X patří do tau)
   2) Jsou-li U_v patřící do ? pro každé v patřící do I (kde I je nějaká indexová množina), pak sjednocení (přes v patřícího do I) U_v patří do ?. (Pokud vezmeme jakékoliv množiny z ? a sjednotím je, tak výsledek zase patří do systému ?)
   3) Jsou-li u,v patřící do ?, pak u průnik v patří také do ?.
Množiny ze systému ? nazýváme otevřenými množinami a dvojici (X,?) říkáme topologický prostor. Množinám tvaru X-U, kde u patří do ? říkáme uzavřené množiny.
Příklady topologických prostorů:
   1) X, ? = {O, X} ... tzv. triviální topologie (nejhrubší ze všech topologií na X).
   2) X, ? = 2^X = P(X) ... tzv. diskrétní topologie (nejjemnější ze všech topologií na X).
   3) X patřící do R, ? = {u|u je sjednocením otevřených intervalů v R}...tzv. Eukleidova topologie na R.
   4) X patřící do Rⁿ, (n patří do N), ? = {u|u je sjednocením otevřených koulí v Rⁿ} (otevřený čtverec bez hranice je dán sjednocením otevřených kruhů).
   5) X = {0,1}, ? = {O, X, {0}} ... tzv. Serjviňského topologický prostor.
   6) X = N, ? = {u|u podmnožina X, X-u je konečná množina} sjednoceno {O} ... tzv. topologie konečných doplňků neboli ko-fintiní topologie.
Definice 1.4.8: Buď (X, ?) topologický prostor a ?₀ podmnožina ?, říkáme že ?₀ je bází topologie jestliže každou množinu U patřící do ? lze vyjádřit jako sjednocení jistých množin z ?₀. Tedy existuje nějaké SIGMA podmnožinou ?₀, že U = sjednocení všech V (kde V patří do SIGMA).
Příklady bází topologií:
   1) Každá topologie je svou vlastní bází.
   2) Otevřené intervaly v R tvoří bázi Eukleidovy topologie (pozor: množina bodů není otevřený interval !)
   3) Otevřené koule (nebo také kvádry nebo krychle) tvoří bázi Eukleidovy topologie na Rⁿ.
   4)
   5)
   6)
   7)
Věta 1.4.1: (Rozpoznání systému tvořícího bázi) Buď X množina a ?₀ podmnožina 2^X systém jistých podmnožin množiny X. Pak ?₀ je bází nějaké topologie na X, právě když platí:
   1) X = sjednocení U (kde U patří do ?₀)
   2) Je-li U,V patřící do ?₀ a x patřící do průniku U a V, pak existuje W podmnožina ?₀ , že (x patří do W) podmnožina (průnik U a V).
Definice 1.4.9: Buďte (X,?) a (Y, SIGMA) topologické prostory, f:X->Y zobrazení. Říkáme, že f je spojité jestliže pro každou otevřenou množinu V patřící do SIGMA je množina f ^-1(V) = {x|x patří do X, f(x) patří do V} otevřená množina v (X,?). (Tedy f ^-1(V) patří do ?).
Poznámka 1.4.9.1: Je-li X = Rⁿ, Y = R^m, je tato definice ekvivalentní klasické epsilon-delta definici spojitosti (pro Eukleidovy topologie).
Definice 1.4.10: Buď f:X->Y vzájemně jednoznačné zobrazení mezi topologickými prostory (X,?), (Y, SIGMA), které je oboustranně spojité (tj. f i  f^-1jsou spojitá). Říkáme, že prostory (X,?) příp. (Y, SIGMA) jsou homeomorfní a zobrazení f nazýváme homeomorfismus. (Homeomorfní prostory jsou z topologického hlediska "stejné").
Definice 1.4.11: Buď (X,?) topologický prostor. Říkáme, že (X,?) je kompaktní, jestliže z každého jeho pokrytí otevřenými množinami lze vybrat podpokrytí (kompaktní topologický prostor). (Každý konečný prostor je kompaktní).
Věta 1.4.2: Spojitý obraz kompaktního topologického prostoru je kompaktní topologický prostor.
Poznámka 1.4.2.1: Je-li (X,?) topologický prostor a Y podmnožina X, pak systém SIGMA = {u průnik Y|u patří do ?} je topologie na Y, které říkáme indukovaná topologie (z prostoru X) a (Y,SIGMA) nazýváme topologickým podprostorem prostoru (X,?). Množinová indukce i = id X/Y: Y~>X je vůči topologii spojité zobrazení. V této souvislosti o libovolné množině K podmnožina X říkáme, že je kompaktní, jestliže je kompaktní jako topologický podprostor prostoru X.
Věta 1.4.3: Množina K podmnožina Rⁿ (v Eukleidově topologii) je kompaktní právě, když je omezená a uzavřená.
Důsledek 1.4.3.1: Řada tvrzení matematické analýzy o spojitých funkcích.

1.5   RELACE NA MNOŽINĚ
Definice 1.5.1: Buď R podmnožina X×X relace na X. Řekneme, že R je
   a) reflexivní, když   (x,x) patří do R pro každé x patřící do X
   b) symetrická, když   (x,y) patří do R => (y,x) patří do R
   c) antisymetrická, když   [(x,y) patří do R a zároveň (y,x) patří do R] => x=y
   d) tranzitivní, když   [(x,y) patří do R a zároveň (y,z) patří do R] => (x,z) patří do R.
Dále relace R se nazývá ekvivalencí na X, je-li R reflexivní, symetrická a tranzitivní.
Podobně R se nazývá (částečným) uspořádáním na X, je-li reflexivní, antisymetrická a tranzitivní.
Poznámka 1.5.1.1: Relace, která je reflexivní a symetrická (ne nutně tranzitivní) se nazývá tolerancí. Podobně, je-li relace reflexivní a tranzitivní (ale ne nutně antisymetrická), nazývá se kvaziuspořádání.

1.6   RELACE A ROZKLADY
Definice 1.6.1: Buď X množina, S soubor podmnožin množiny X. Jestliže sjednocení S = X a soubor S je po dvou disjunktní (tedy každé U,V patřící do S, U různé od V => U průnik V = O), nazývá se S rozkladem množiny X.
Věta 1.6.1: Buď S rozklad množiny X. Definujeme xRy pro všechna taková x,y patřící do X, že x,y patří do S pro nějakou množinu M patřící do S. Potom relace R je relací ekvivalence na X. Relace R se nazývá ekvivalencí určenou rozkladem S.
Věta 1.6.2: Buď R ekvivalence na množině X. Pro každé a patřící do X klademe [a]:={x|x patří do X, xRa}, S = {[a]|a patří do X}. Potom S je rozkladem na X.
Poznámka 1.6.2.1: Množiny [a]={x|x patří do X, xRa} se nazývají třídy rozkladu příslušného ekvivalenci R (zkráceně ekvivalenční třídy, třídy ekvivalence).
Poznámka 1.6.2.2: Platí: Rozklad --(Věta 1.6.1)--> ekvivalence --(V.1.6.2)--> původní rozklad ekvivalence --(V.1.6.2)--> rozklad --(V.1.6.1)--> původní ekvivalence

1.7   USPOŘÁDANÉ MNOŽINY
Definice 1.7.1: Buď X množina, R podmnožina X×X relace uspořádání na X. Pak dvojicí (X,R) či méně přesně množinu X, nazýváme uspořádanou množinou. Pro relaci R pak často užíváme symbol <=, kde klademe x<=y <=> (x,y) patří do R. Je-li x<=y a x různo y, píšeme x<y.
Definice 1.7.2: Buď (X,<=) uspořádaná množina. Říkáme, že uspořádání <= je lineární (neboli úplné), jestliže pro každé x,y patřící do X je buď x<=y, nebo y<=x.
Definice 1.7.3: Buď X uspořádaná množina. Nechť a,b patří do X. Řekneme, že b pokrývá a, jestliže a<b a neexistuje x patřící do X takové, že a<x<b.
Poznámka 1.7.3.1: Je-li X konečná množina, lze prvky X reprezentovat uzly v rovině a to tak, že menší prvky jsou zakresleny níže než prvky větší, přičemž pokrývaný prvek je s pokrývajícím spojen úsečkou. Vzniká tzv. Hasseův diagram.
Definice 1.7.4: Buď X uspořádaná množina, A podmnožina X. Říkáme, že a patřící do X je horní závora (resp. dolní) množiny A, jestliže pro všechna x patřící do A je x<=a (resp. a<=x). Existuje-li mezi všemi horními závorami množiny A nejmenší, označujeme ji sup A a nazýváme suprémem množiny A. Naopak, existuje-li největší dolní závora množiny A, označujeme ji inf A a nazýváme infimem množiny A.
Poznámka 1.7.4.1: Buď (X,<=) uspořádaná množina, A podmnožina X. Má-li A největší prvek, je to zároveň suprémum množiny A. Opak obecně neplatí. Podobně má-li A nejmenší prvek, je to infimum množiny A. Opak však obecně neplatí.
Definice 1.7.5: Buď (X,<=) uspořádaná množina. Prvek m patřící do X se nazývá maximálním (resp. minimálním) prvekem množiny X, jestliže v X neexistuje prvek větší (resp. menší) než m. (Maximálních prvků může být více).
Věta 1.7.1: Buď R podmnožina X×X relace uspořádaná na X. Pak také relace S=R^-1 je uspořádaná na X. (Toto uspořádání se nazývá inverzní nebo také duální k uspořádání R. Značíme-li R symbolem "<=", pak S značíme symbolem ">=").
Definice 1.7.6: Buď (X,<=) uspořádaná množina. Řekneme, že (X,<=) je svazně uspořádaná (krátce svaz), jestliže každá dvouprvková podmnožina množiny X má v X suprémum i infimum.

II. MATEMATICKÉ STRUKTURY A ALGEBRY

2.1   KATEGORIE
Definice 2.1.1: Kategorií nazýváme uspořádanou pětici K = (O,M,Dom,Im,o), kde O,M jsou nějaké třídy, Dom a Im jsou závazně definované na M s hodnotami v O, o je operace, která libovolným dvěma f,g patřících do M takovým, že Dom(g) = Im(f) přiřazuje prvek gof patřící do M. Prvky třídy O se nazývají objekty kategorie K, prvky třídy M se nazývají morfismy kategorie K. Je-li f patřící do M, pak Dom(f) patří do O se nazývá oborem morfismu f, Im(f) patří do O se nazývá kooborem morfismu f. Operace o je operací skládání morfismů.
Příklady kategorií:
   1) objekty ... množiny; morfismy ... zobrazení; o ... skládání zobrazení; vzniká kategorie Set (kategorie množin).
   2) objekty ... topologické prostory; morfismy ... spojitá zobrazení; o ... skládání zobrazení; vzniká kategorie Top (kategorie topologických prostorů).
   3) objekty ... vektorové prostory; morfismy ... lineární zobrazení; o ... skládání zobrazení; vzniká kategorie Vect (kategorie vektorových prostorů).
   Další např.: Grp, Gra, ...
Definice 2.1.2: Množina D objektů a morfismů z kategorie K nazýváme diagramem v K, jestliže s každým morfismem f:A->B z D také objekty A,B a identické morfismy id_A a id_B patří do D. Diagram D nazýváme komutativní, jestliže pro libovolné dvě posloupnosti morfismů A -(f₁)-> A₁-(f₂)-> ... -(f_n-1)-> A_n-1 -(f_n)->B a A -(g₁)-> B₁-(g₂)-> ... -(g_n-1)-> B_n-1 -(g_n)->A   platí f_nof_n-1o...of₂of₁=g_nog_n-1o...og₂og₁.

2.2   ALGEBRY
Definice 2.2.1: Buď A množina a w (řecké písmeno omega):
Aⁿ=A×A×...×A --> A zobrazení. Pak w nazýváme n-ární operací na A. Číslo n nazýváme četností (aritou) operace w.
Definice 2.2.2: Buď A množina, w₁,w₂,...w_k oprace na A s četnostmi n₁,n₂,...n_k. Pak k+1-tici (A,w₁,w₂,...w_k) nazýváme algebrou, zkráceně označujeme algebru (A,w₁,w₂,...w_k) stejným symbolem jako její nosnou množinu, tj. písmenem A a hovoříme pak o algebře A.
Definice 2.2.3: Buďte (A,a₁,a₂,...a_k) a (B,b₁,b₂,...b_k) dvě algebry se stejnými četnostmi n_i, operací a_i,b_i pro i=1,2,...k a x₁,x₂,...x_ni patří do A. Nechť platí h(a_i(x₁,x₂,...x_ni)) = b_i(h(x₁),h(x₂),...h(x_ni)). Pak h se nazývá morfismem algebry A do algebry B.
Poznámka 2.2.3.1: (Názvosloví morfismů)
   monomorfismus := injektivní morfismus
   epimorfismus := surjektivní morfismus
   izomorfismus := bijektivní morfismus
   endomorfismus := morfismus algebry A do A
   automorfismus := izomorfismus A do A
Definice 2.2.4: Buď (A,w₁,w₂,...w_k) algebra a nechť B podmnožina A je taková podmnožina, že pro libovolné i=1,2,...k a x₁,x₂,...x_n patří do B je w_i.(x₁,x₂,...x_ni) patří do B (kde n_i je četnost operace w_i). Pak algebru   (B,w₁,w₂,...w_k) nazýváme podalgebrou algebry (A,w₁,w₂,...w_k).

2.3   FAKTOROVÉ ALGEBRY
Definice 2.3.1: Buďte X,Y množiny, f:X->Y zobrazení. Relaci k f:=f^-1of nazýváme jádrem zobrazení f.
Věta 2.3.1: Nechť f:X->Y je zobrazení. Pak Ker f je ekvivalence.
Poznámka 2.3.1.1: Dva prvky x,y patřící do X jsou v relaci ker f na X, právě když mají stejný obraz, tj. když f(x) = f(y).
Poznámka 2.3.1.2: Rozkladu S = X/_R se často říká faktorová množina příslušná ekvivalenci R.
Definice 2.3.2: Buď R podmnožina X×X ekvivalence na X. Zobrazení g:X->X/_R přiřazující prvku x patřící do X třídu ekvivalence [x]_R patří do X/_R tj. g(x)=[x]_R, říkáme přirozené či kanonické zobrazení.
Věta 2.3.2: Buď f:X->Y libovolné zobrazení (X do Y), g:X->X/_kerf kanonické zobrazení. Pak existuje jediné zobrazení h:X/_kerf->Y, že diagram
   X --(g)--> X/_kerf --(h)--> Y
    '----------------(f)-------------/\
komutuje, tj. že f =hog, přičemž h je injektivní (a má stejný obor hodnot jako f). Speciálně, je-li f surjekce, je h bijektivní.
Definice 2.3.3: Buď R ekvivalence na A, (A,w₁,w₂,...w_k) algebra nad operacemi w₁,w₂,...w_k s četností n₁,n₂,...n_k. Řekneme, že R je kongruence na A, jestliže pro každé i=1,2,...k a x₁,x₂,...x_ni, y₁,y₂,...y_ni platí indikace: x₁Ry₁ a zároveň x₂Ry₂ a ... a zároveň x_niRy_ni => w_i(x₁,x₂,...x_ni)Rw_i(y₁,y₂,...y_ni).
Věta 2.3.3: Buď f morfismus algebry (A,a₁,a₂,...a_k) do algebry (B,b₁,b₂,...b_k). Pak je relace R=ker f kongruencí na A.
Definice 2.3.4: Buď (A,w₁,w₂,...w_k) algebra a R kongruence na A. Pro libovolné i=1,2,...k a x₁,x₂,...x_ni patřící do A klademe w_i([x₁]_R,[x₂]_R,...[x_ni]_R):=[w_i(x₁,x₂,...x_ni)]_R. Jelikož R je kongruencí, je konkrétně definovaná nová algebra s nosnou množinou A/_R a operacemi w₁,w₂,...w_k. Tuto algebru (A/_R,w₁,w₂,...w_k) nazýváme faktorovou algebrou původní algebry A, příslušnou kongruenci R.
Věta 2.3.4: Buď f epimorfismus algebry (A,a₁,a₂,...a_k) na algebru (B,b₁,b₂,...b_k). Pak je faktorová algebra (A/_{ker f},a₁,a₂,...a_k) izomorfní s algebrou (B,b₁,b₂,...b_k).

2.4   ALGEBRY S JEDNOU BINÁRNÍ OPERACÍ
Definice 2.4.1: Nechť (A,*) je algebra s binární operací *. Pak (A,*) se nazývá grupoid. Řekneme, že (A,*) je pologrupa, jestliže operace splňuje asociativní zákon, tj.: pro každé a,b,c patřící do A platí: (a*b)*c=a*(b*c). Dále řekneme, že (A,*) je grupa, jestliže A obsahuje tzv. jednotkový prvek e patřící do A, s vlastností: pro každé a patřící do A platí: a*e=a=e*a, a jestliže A obsahuje s každým a patřící do A tzv. inverzní prvek k a, značený a^-1 a mající vlastnost: a*a^-1=e=a^-1*a. Dále řekneme, že (A,*) je komutativní grupa (neboli abelovská) jestliže operace * splňuje navíc tzv. komutativní zákon, tj.: pro každé a,b patřící do A platí:   a*b=b*a.
Poznámka 2.4.1.1: Pologrupa s jednotkovým prvkem se nazývá monoid.
Věta 2.4.1: a) v grupoidu existuje nejvýš jeden jednotkový prvek
                 b) v monoidu existuje ke každému prvku nejvýš 1 prvek inverzní.
Poznámka 2.4.1.2: Každý monoid (M,*) lze chápat jako algebru (M,*,e) s binární operací hvězdička * a nulární operací e. Každou grupu (G,*) lze chápat jako algebru (G,*,e,^-1) s binární operací *, nulární operací e a unární operací inverze ^-1.
Poznámka 2.4.1.3: U algeber s jednou binární operací často užíváme tzv. multiplikativní symboliky (místo * píšeme .), pak značíme jednotkový prvek jako 1 a inverzní prvek k a jako a^-1. Nebo také používáme tzv. aditivní symboliku (místo * píšeme +) a pak jednotkovému prvku říkáme neutrální prvek a značíme ho 0. Inverznímu prvku k a říkáme opačný prvek a značíme ho -a.
Poznámka 2.4.1.4: Pologrupový epimorfismus zobrazí jednotku na jednotku a inverzní prvek na inverzní prvek (dokonce vynutí existenci). Je-li f:A->B epimorfismus pologrup (A,o) a (B,*) a má-li A jednotku e_A, pak f(e_A) je jednotka pologrupy B. Jsou-li a,b patřící do A navzájem inverzní prvky, pak f(a), f(b) jsou navzájem inverzní v B.
Definice 2.4.2: Buď (G, .) grupa, H podmnožina G její podgrupa. Řekneme, že podgrupa H je normální podgrupou grupy G, jestliže pro libovolné a patřící do G, h patřící do H platí: a.h.a^-1 patří do H.
Příklad 2.4.2.1: V komutativní grupě je každá podgrupa normální.
V nekomutativních grupách (např. S₃) obecně existují i nenormální podgrupy.
Věta 2.4.2: Buď (G,o) grupa, R kongruence na G. Nechť 1 patřící do G je jednotkový prvek v G. Pak H=[1]_R je normální podgrupou v G.
Věta 2.4.3: Buď (G,o) grupa a H podmnožina G její normální podgrupa. Pak relace R={(x,y)|x,y patřící do G, y^-1ox patří do H} je kongruence na G.
Poznámka 2.4.3.1: Faktorové třídy podle R mají tvar [x]_R = {y|y patří do G, yRx} = {y|y patří do G, x^-1.y patří do H} = {y|y=x.h, h patří do H} = {x.h|h patří do H}, což zjednodušeně značíme [x]_R=x.H a těmto třídám říkáme levé třídy podle H. Vzniklému rozkladu G/_R říkáme levý rozklad podle H.
Poznámka 2.4.3.2: Analogicky bychom mohli definovat tzv. pravý rozklad podle H na třídy H.x:={h.x|h patří do H}. Obecně se tento rozklad může lišit od levého rozkladu (pro nekomutativní grupy). Je-li H normální podgrupa G, jsou oba rozklady stejné.
Věta 2.4.4: (Lagrangeova) Řád podgrupy je dělitelem řádu grupy.
Definice 2.4.3: Buď (G,o) grupa a H její normální podgrupa. Nechť R={(x,y)|x,y patří do G, y^-1.x patří do H} je kongruenční relace příslušna podgrupě H. Pak faktorovou grupu G/_R (je to grupa vzhledem k existenci přirozeného epimorfismu G->G/_R) nazýváme faktorovou grupu grupy G podle H a značíme G/_H.
Poznámka 2.4.4.1: Buď f:G->F morfismus grup (G,o) a (F,*). Označme R=ker f. Podle věty 2.3.3 je R kongruencí na G, takže třída J(f):=[1_G]_{ker f}   je normální podgrupou G podle věty 2.4.2. Přitom
...
... Existuje tedy vzájemně jednoznačná korespondence mezi jádrem ker f  a normální podgrupou J(f) (jíž se také říká v důsledku toho jádro morfismu f).
Věta 2.4.5: BuĎ f:G->F epimorfismus grup (G,o) a (F,*). Pak grupy (G/_J(f),o) a (F,*) jsou izomorfní.

2.5   ALGEBRY SE DVĚMA BINÁRNÍMI OPERACEMI
Definice 2.5.1: Buď (A,+,.) algebra se dvěmi operacemi +,. taková, že:
   (i)  (A,+) je komutativní grupa
   (ii)  (A,.) je monoid
   (iii)  pro libovolné a,b,c patřící do A platí: a.(b+c)=ab+ac, (b+c).a=ba + ca
Pak (A,+,.) se nazývá okruh. Je-li |A|>1, nazývá se (A,+,.) netriviální okruh. Nechť 0 patří do A je neutrální prvek grupy (A,+). Pak 0 se nazývá nulou okruhu (A,+,.). Nechť 1 patří do A je označení pro jednotkový prvek monoidu (A,.). Pak 1 se nazývá jednotkou (jedničkou) okruhu (A,+,.). Je-li (A-{0},.) komutativní grupa, nazývá se (A,+,.) těleso.
Příklady těles: (R,+,.),  (C,+,.),   (Z_p,+,.) (kde p je prvočíslo, pokud p není prvočíslo tak to není okruh).

2.6   SVAZY
Definice 2.6.1: Buď X množina, spojení (písmeno v) a průsek (stříška) binární operace na X s vlastnostmi:   Pro všechna x,y,z patřící do X:
   (1) x spojení x = x,  x průsek x = x   (idempotence)
   (2) x spojení y = y spojení x,  x průsek y = y průsek x   (komutativita)
   (3) (x spojení y) spojení z = x spojení (y spojení z), (x průsek y) průsek z = x průsek (y průsek z)    (asociativita)
   (4) x průsek (x spojení y) = x,  x spojení (x průsek y) = x (absorbční zákony).
Pak trojici (X, spojení, průsek) nazýváme (algebraicky definovaným) svazem na X.
Poznámka 2.6.1.1: Algebraická definice svazů a svazová uspořádání na množině spolu úzce souvisí. Buď X množina v níž je dáno svazové uspořádání <=. Klademe pro x,y patřící do X:  x spojení y := sup{x,y};  x průsek y:= inf{x,y}
Pak (X, spojení, průsek) je algebraicky definovaný svaz. Naopak, mějme algebraicky definovaný svaz (X, spojení, průsek), klademe pro x,y patřící do X:
   x<=y  <=>  x spojení y = y (nebo alternativně x<=y  <=> x průsek y = x).
Pak (X,<=) je svazově uspořádaná množina. Navíc platí:
   (X,<=) --->  (X, spojení, průsek) ---> (X,<=) ... stejné uspořádání
   (X, spojení, průsek) ---> (X,<=) ---> (X, spojení, průsek) ... tentýž svaz
Z těchto důvodů nerozlišujeme mezi algebraicky definovaným svazem a svazovým uspořádáním na množině a hovoříme pouze o svazu.

2.7   PODSVAZY, IZOMORFISMY SVAZŮ
Definice 2.7.1: Buď (X, spojení, průsek) svaz, Y podmnožina X. Řekneme, že (Y, spojení_Y, průsek_Y) je podsvazem svazu (X, spojení_X, průsek_X) ,jestliže platí:
   1) (Y, spojení_Y, průsek_Y) je svaz
   2) pro každé x,y patřící do Y; x spojení_Y y = sup_Y{x,y} = sup_X{x,y} = x spojení_X y
       x průsek_Y y = inf_Y{x,y} = inf_X{x,y} = x průsek_X y
Definice 2.7.2: Buďte (X, spojení_X, průsek_X) a (Y, spojení_Y, průsek_Y) svazy. Nechť existuje vzájemně jednoznačné zobrazení f:X->Y takové, že pro každé x,y patrící do X platí:
   f(x spojení_X y) = f(x) spojení_Y f(y)
   f(x průsek_X y) = f(x) průsek_Y f(y)
Pak říkáme, že svazy (X, spojení_X, průsek_X) a (Y, spojení_Y, průsek_Y) jsou izomorfní. Zobrazení f nazýváme izomorfismem svazů (X, spojení_X, průsek_X) a (Y, spojení_Y, průsek_Y).

2.8   KLASIFIKACE SVAZŮ
Definice 2.8.1: Buď (X, spojení, průsek) svaz. Řekneme, že (X, spojení, průsek) je:
   (i) modulární, jestliže každé x,y,z patřící do X, (x<=z) => (x spojení (y průsek z) = (x spojení y) průsek z).
   (ii) distributivní, jestliže každé x,y,z patřící do X, (x spojení (y průsek z)) = ((x spojení y) průsek (x spojení z)).
   (iii) komplementární, jestliže v X existuje nejmenší prvek (označíme ho 0 patřící do X), největší prvek (označíme ho 1 patřící do X) a pro každé x patřící do X existuje x s vlastností:
         x průsek x = 0      a      x spojení x = 1; Prvek x se nazývá komplementem (doplňkem) prvku x.
Věta 2.8.1: Každý distributivní svaz je modulární.
Věta 2.8.2: Buď X distributivní svaz. Pak každý prvek x patřící do X má nejvýš jeden komplement v X.
Poznámka 2.8.2.1: Svaz s Hasseovým diagramem (viz. obr. ... čtyřúhelník s jednou úhlopříčkou s uzly ve vrcholech a jedním uzlem uprostřed úhlopříčky) se nazývá diamantový svaz a značí se M₅. Podobně, svaz s diagramem (viz obr. ... pětiúhelník s pěti uzly ve vrcholech) se nazývá pentagonální svaz a značí se N₅.
Věta 2.8.3: Svaz (X, spojení, průsek) je
   1) modulární <=> neobsahuje podsvaz izomorfní s N₅.
   2) distributivní <=> neobsahuje podsvaz izomorfní s M₅ ani s N₅.

2.9   BOOLEOVSKÉ SVAZY
Definice 2.9.1: Buď (X, spojení, průsek) distributivní a komplementární svaz s nejmenším prvkem  0 patřící do X a největším prvkem 1 patřící do X. Pak (X, spojení, průsek) nazýváme Booleovským svazem. Uspořádanou pětici (X, spojení, průsek,-,0,1), kde -:X->X je operace komplementu v X, nazýváme Booleovskou algebrou na X.
Příklad 2.9.1.1: Je-li A množina, pak X=2^A je (X, spojení, průsek) je Booleovský svaz.
Definice 2.9.2: Buď (X, spojení, průsek) Booleovský svaz. Řekneme, že a patřící do X je atom svazu X, jestliže a pokrývá nejmenší prvek 0 patřící do X.
Věta 2.9.1: Buď (X, spojení, průsek) konečný Booleovský svaz. Pak X je izomorfní s Booleovským svazem (2^P, spojení, průsek), kde P je množina všech atomů svazu X.
Důsledek 2.9.1.1: Počet prvků Booleovského svazu je vždy 2^|P|.
Důsledek 2.9.1.2: Každá dvě Booleovsé algebry se stejným počtem prvků jsou si izomorfní.

III.   GRAFY

3.1   ZÁKLADNÍ POJMY

Definice 3.1.1: Neorientovaný graf G se skládá z množiny V vrcholů

Zdroj informací: Přednášky na VUT FEI z předmětu Algebry a grafy pro 1. ročním letní semestr pana profesora Kovára.

 Hot Tip: Podívejte se na stránky humorného školního časopisu PRD (Pravidelný Redakční Drb):
 

Pokud chcete sledovat tyto stránky (kdy budou změněny, tak se zaregistrujte sem: