ALGEBRA. Zapisky z prednasky. 1 Algebry, homomorsmy a kongruence

ALGEBRA

Z apisky z predn asky

1 Algebry, homomor smy a kongruence de nice Necht' A je mnozina, pak o zobrazen  : AN n-arn operace, n 2 N0

! A rekneme, ze je

terminologicka poznamka

   

0-arn operace: A0 ! A, A0 = fg, je to vlastne vyber prvku 1-arn operace - unarn 2-arn operace - binarn 3-arn operace - ternaln

de nice Necht' A je mnozina, i ; i 2 I a to i nekonecna; jsou (ni -arn) operace. Pak A(i j i 2 I ) nazveme (universaln) algebrou. prklady

    

N (+;
)

Z (+; ;
)

Q n f0g(
; =)

<(+; ;
) <(+;
; p )

de nice Necht' A je mnozina s n-arn operac  a B  A. R ekneme, ze B je uzavrena na operaci , pokud 8b1 ; :::; bn 2 B plat, ze (b1 ; :::; bn ) 2 B . Je-li A(i ; i 2 I ) algebra a B  A, pak rekneme, ze B je podalgebra A(i ; i 2 I ), pokud je B uzavrena na vsechny i ; i 2 I prklady

 N (+;
) - k 2 B , potom kN = fknjn 2 N g jsou podalgebry N (+;
) Overen: Necht' b1 ; b2 2 kN 1. b1 + b2 2 kN 2. b1
b2 2 kN  Z (+; ; 0) ma podalgebry kZ = fk
rjr 2 Z g (a zadne jine). Je dulezite si rozmyslet uzavrenost na nularn operaci 0 1

 Vektorovy prostor U (+;
tjt 2 T; 0) nad telesem T
t : U ! U , u ! u
t W je podprostor U , W je podalgebra U (+;
t; 0)  A(i ji 2 I ) je algebra, potom A je podalgebra A  Pokud zadna operace algebry A nen nularn, potom ; je podalgebrou A skorode nice Je-li A(i ji 2 I ) algebra a B jej podalgebra, pak i = i dB ni : B ni ! B - mame prirozene danou strukturu na B prklady

 Q(+;
), Z  Q je podalgebra algebry Q(+;
) restrikce ! Z (+;
)  Necht' Mn (T ) jsou ctvercove matice radu n nad telesem T . Vezmeme algebru M2 (<)(
), potom diagonaln matice D(<)(
) tvor podalgebru M2 (<)(
). poznamka 1.1

1. Necht' A je mnozina s operac em podmnozin T   a necht' Aj , j 2 J je syst A uzavrenych na . Pak j 2J Aj je opet uzavrena na  T 2. Necht' A(i ji 2 I ) je algebra a Aj ; j 2 J jsou jej podalgebry. Pak j2J Aj je podalgebra d ukaz

1.  je n-arn operace

8j 2 j : (a1 ; a2 ; :::; an ) 2

\

j 2J

Aj  Aj T

Podle predpokladu (a1 ; :::; an ) 2 Aj 8j ) (a1 ; :::; an ) 2 Aj 2. Aj jsou uzav a na i 8i 2 I; j 2 J Tren Podle 1. je j2J Aj uzavrena na i 8i 2TI , tedy je uzavrena na vsechny operace na algebre A(i ji 2 I ), a proto je j2J Aj podalgebra A(i ji 2 I ) QED de nice Necht' A a B jsou mnoziny s n-arn operac  a f : A ! B . R ekneme, ze f je slucitelne s , pokud 8a1 ; a2 ; :::; an 2 A B (f (a1 ); f (a2 ); :::; f (an )) = f (A (a1 ; :::; an )) de nice R ekneme, ze algebra A(i ji 2 I ) a B (i ji pokud i na A i na B jsou stejne arity 8i 2 I

2

2 I ) jsou stejneho typu

de nice Necht' A(i ji 2 I ) a B (i ji 2 I ) jsou algebry stejneho typu. Pak zobrazen f : A ! B je homor smus, pokud je f slucitelna se vsemi i . poznamka 1.2

1. Necht' A, B , C jsou mnoziny s n-arn operac , f : A ! B , g : B ! C jsou zobrazen slucitelna s . Pak g  f : A ! C je slucitelne s . Je-li f bijekce, potom f 1 je opet slucitelne s . 2. Necht' A(i ji 2 I ), B (i ji 2 I ), C (i ji 2 I ) jsou algebry stejneho typu a f : A ! B , g : B ! C jsou homomor smy. Pak g  f : A ! C je opet homomor smus. Je-li navc f bijekce, pak f 1 je take homomor smus. d ukaz

1. Vezmeme a1 ; ::::; an 2 A g(f ((a1 ; :::;n ))) sluc:=f s  g((f (a1 ); :::; f (an ))) = sluc: g s 

= (g(f (a1 )); :::; g(f (an ))) f bijekce ... f 1 je zobrazen B ! A, b1 ; b2 ; :::; bn 2 B a chceme dokazat f 1 (B (b1 ; :::; bn )) =? A (f 1 (b1 ); :::; f 1 (bn ))




= B f f 1 (b1 ) ; :::; f f 1 (bn ) f A f 1 (b1 ); :::; f 1 (bn ) def:

Tedy vezmeme





 f 1 (b1 ); :::; f 1 (bn ) = f 1 f A b1 ; :::; f 1 (bn )

Podle radku pred tm se toto rovna f 1 ((b1 ; :::; bn )) Tedy i inverzn zobrazen je slucitelne s . 2. Podle prvnho bodu je g  f slucitelne s i 8i 2 I , tedy g  f je homomor smus. f 1 je podle bodu 1. slucitelne se vsemi i , a tedy je take homomor smus. QED de nice Jsou-li A(i ji 2 I ) a B (i ji 2 I ) algebry stejneho typu a f : A ! B je bijektivn homomor smus, pak mluvme o isomor smu. A a B jsou isomorfn

algebry, pokud mezi nimi existuje isomor smus.

poznamka Dve isomorfn algebry maj "stejne algebraicke vlastnosti" (tj, logicke operace, mnozinove operace a vlastnosti algeber)

3

poznamka 1.3 1. Necht' A a B jsou mnoziny s operac  a C  A; D  B jsou uzavrene na . Je-li f : A ! B slucitelne s , pak f (C ) je (opet) uzavrene na  v B a f 1 (D) = fa 2 Ajf (a) 2 Dg je uzavrena na  v A 2. Necht' A(i ji 2 I ) a B (i ji 2 I ) jsou algebry stejneho typu a C  A, D  B podalgebry prslusnych algeber. Je-li f : A ! B homomor smus, pak f (C )  B a f 1 (D)  A jsou podalgebry d ukaz 1.  je n-arn operace, je na ni f (C ) uzavrena? b1 ; ::; bn 2 f (C ) 9a1 ; :::; an 2 C : f (ai ) = bi 8i 2 I (b1 ; :::; bn ) =  (f (a1 ); :::; f (an )) = f ((a1 ; :::; an )) Vme, ze C je uzavrena na , tedy (a1 ; :::; an ) 2 C , f ((a1 ; :::; an )) f (C )

2

Dale

a1 ; :::; an 2 f 1 (D) f (ai ) 2 D Lez f ((a1 ; :::; an )) v mnozine D? f ((a1 ; :::; an )) = (f (a1 ); :::; f (an )) | {z } 2D To mus z uzavrenosti D na  lezet v D, tedy (a1 ; :::; an ) 2 f 1 (D) 2. stac aplikovat 1. na i 8i

QED

prklady

1. linearn zobrazen f : U ! V , kde U; V jsou vektorove prostory nad telesem T , jsou homomor smy algebry U (+;
tjt 2 T ) a V (+;
tjt 2 T ) 2. ctvercove matice nad telesem T - Mn (T ). Determinant : Mn (T ) ! T je homomor smus algebry Mn (T )(
) a T (
) 3. n : Z ! Zn : n (k) = k mod n. Pak n je homomor smus algebry Z (+;
) do algebry Zn (+;
)

de nice R ekneme, ze  je relace na mnozine A, pokud   A  A. Necht'  je relace na A, potom   = f(b; a) 2 A  Aj(a; b) 2 g je opacna relace  + = f(a; b) 2 A  Aj9a1 ; :::; an 2 A : a1 = a; an = b; (ai ; ai+1 ) 2  i = 1; :::; n 1g je transitivn obal  id = f(a; a) 2 A  Aja 2 Ag je identita

4

de nice R ekneme, ze relace  je

   

re exivn, pokud id   symetricka, pokud    transitivn, pokud +   ekvivalence, pokud je re exivn, symetricka a transitivn relace.

de nice Necht' A je mnozina a  je ekvivalence na A, pak mnozina A= = f[a] ja 2 Ag, kde [a] = fb 2 Aj(a; b) 2 g, nazyvame faktor A podle  poznamka 1.4 Necht' A je mnozina a  je ekvivalence na A, pak A= tvor

rozklad.

d ukaz

A=

[

f[a] ja 2 Ag

a 2 [a] - re exivita, ale ony se prekryvaj x 2 [a] \[b] ) (a; x) 2 ; (b; x) 2 g ) f(x; a) 2 ; (x; b) 2 g ) (a; b) 2 ; (b; a) 2 

(a; b) 2 , [b] = fy 2 Aj(b; y) 2 g 8y 2 [b] (a; y) 2  ) y 2 [a] tj. [b]  [a] symetricky [a]  [b] , tedy [a] = [b] . Obsahuj-li 2 trdy spolecny prvek, potom splyvaj, jestlize neobsahuj ani jeden prvek, pak jsou disjunkntn QED poznamka 1.5 Necht' fBi ji 2 I g je rozklad mnoziny A. Pak relace na A de novana predpisem (a; b) 2  def  9i 2 I : a; b 2 Bi je ekvivalence a A= = fBi ji 2 I g d ukaz

1.  je ekvivalence

 a 2 Bi pro nejake i 2 I ) (a; a) 2  - re exivita  (a; b) 2  ) 9i a; b 2 Bi ) (b; a) 2  - symetrie  (a; b) 2 &(b; c) 2  ) 9i; j a; b 2 Bi &b; c 2 Bj . Protoze to je disjunktn rozklad, Bi = Bj , a tedy a; c 2 Bj - transitivita 5

2. Dokazeme A  =  fBi ji 2 I g "" [a] a 2 Bi def: , [a] = fb 2 Ajb 2 Bi g = Bi [a]  Bi "" Bi  [a]

vezmu libovolny prvek a zjistm, ze to dela rozkladovou trdu QED de nice Necht' f : A ! B je zobrazen. Pak jadrem f nazveme relaci ker f danou predpisem (a1 ; a2 ) 2 ker f def  f (a1 ) = f (a2 ). Je-li  ekvivalence na mnozine A, pak o zobrazen  : A ! A= dane formul  (a) = [a] rekneme, ze je to prirozena projekce podle  poznamka 1.6 Necht' f : A ! B je zobrazen a  je ekvivalence na A. Pak

plat 1. ker f je ekvivalence 2. f je proste , ker f = id 3. ker  =  4. zobrazen g : A= ! B s vlastnost g = f existuje prave tehdy, kdyz   ker f d ukaz

1.

2.

 re exivita: f (a) = f (a) ) (a; a) 2 ker f  symetrie: f (a1 ) = f (a2 ); f (a2 ) = f (a1 ), tj. (a1 ; a2 ) 2 ker f ) (a2 ; a1 ) 2 ker f  transitivita: (a1 ; a2 ) 2 ker f ) f (a1 ) = f (a2 ) = f (a3 ) ) (a1 ; a3 ) 2 ker f

a1 6= a2 ) f (a1 ) 6= f (a2 ) ) (a1 ; a2 ) 2= ker f

a stejne tak opacne 6

3.

(a1 ; a2 ) 2 ker  , |{z(a1}) = |{z(a2}) , (a1 ; a2 ) 2  [a1 ]

[a2 ]

Predpokladame existenci g : g = f , tj. 8a 2 A g   (a) = f (a) | {z }

) g([a] ) = f (a) Predpokladejme a; b 2  ) [a] = [b] . Pak f (a) = g ([a] ) = g ([b] ) = f (b) Tedy a, b lez v jadru

4. ")"

[a]

"(" Predpokladame   ker f De nujeme

g ([a] ) = f (a)

Je tato de nice korektn [a] = [b] ) (a; b) 2   ker f ...prvky se slepuj podle de nice jadra f (a) = f (b) g ([a] ) = f (a) = f (b) = g ([b] ) Zrejme g = f

QED

prklad Deterministicky algoritmus f , A je mnozina vstupnch hodnot, B je mnozina moznych vystupnch hodnot f : A !f B , Potom ker f je zcela prirozene

de novana ekvivalence: ztotoznuje vstupy, ktera daj stejny vysledek

de nice Necht'  je n-arn operace na A,  je ekvivalence na A. R ekneme, ze  je slucitelna s , pokud (ai ; bi ) 2  i = 1; :::; n ) (a1 ; :::; an )(b1 ; :::; bn )

Je-li A(i ; i 2 I ) algebra a  je ekvivalence na A, pak  je kongruence na A, pokud  je slucitelna s i ; 8i 2 I poznamka 1.7 1. Necht' A; B jsou mnoziny,  je operace na A; B a f je zobrazen A ! B slucitelne s , Pak ker f je slucitelna s  2. Necht' A; B jsou algebry stejneho typu a f je homomor smus A ! B . Potom ker f je kongruence

7

d ukaz

1.

tj.

(ai ; bi ) 2 ker f ) f (ai ) = f (bi ) 8i = 1; :::; n f ((a1 ; :::; an )) =  (f (a1 ; :::; an )) = =  (f (b1 ; :::; bn )) = f ((b1 ; :::; bn ))

((a1 ; :::; an ); (b1 ; :::; bn )) 2 ker f Podle poznamky 1.6(1.) je ker f ekvivalence 2. plyne z 1. QED  TA 1.8 VE

1. Necht'  je ekvivalence na A,  je operace na A. Pak  je slucitelna s  prave kdyz  je slucitelna s  2. Necht'  je ekvivalence na algebre A. Pak  je kongruence ,  je homomor smus de nice k 1.8 Necht' A ke mnozina s ekvivalenc  a relac . De nujeme

operaci  na A=

 ([a1 ] ; :::; [an ] ) = [(a1 ; :::; an )]

Na mnozine A= de nujeme stejnym zpusobem algebru stejneho typu jako na A za predpokladu, ze A je algebra. Koreknost de nice (a1 ; b1 ) .. [a1 ] = [b1 ] ; :::; [an ] = [bn ] ) ! [(a1 ; :::; an )] = [(b1 ; :::; bn )] . (an ; bn ) neboli  je slucitelne s , pro algebry je de nice korektn prave tehdy, kdyz  je kongruence. D ukaz vety 1.8

 je slucitelna s , potom je  dobre de novana na A= . ??? Je  : A ! A= slucitelna s  ???

")"

 ((a1 ; :::; an )) def = [(a1 ; :::; an )] =  ([a1 ] ; :::; [an ] ) =  ( (a1 ); :::;  (an )) tj.  je slucitelne s  8

"(" Je-li  slucitelne s  ... ker   = , potom  je korektne de novano, tedy ker  je slucitelne s  )  je slucitelne s  ... a druhy bod se dokaze pouzitm prvnho bodu na vsechny operace algebry. QED de nice Grupoidem nazveme algebru G(
) s binarn operac
. Prvek e nazveme neutralnm prvkem grupoidu G(
), pokud e
g = g
e = g 8g 2 G R ekneme, ze algebra M (
; e) je monoid, pokud
je asociativn binarn operace a e je neutraln prvek M (
) prklady

 X 6= ;...mnozina znaku, M (X ) mnozina slov na abecede X operace x1 x2 :::xn  y1 :::ym = x1 :::xn y1 :::ym e je prazdne slovo Potom M (X )(; e) je monoid  X 6= ;, T (X ) = ff : X ! X jf zobrazeng, potom T (X )(; idX ) je monoid  T -telesom Mn (T )-ctvercove matice nad T . Mn (T )(
; In ) je monoid  det : Mn (T ) ! T je homomor smus monoidu Mn (T )(
; In ) a T (
; 1) Poznamka 1.9 Necht' G(
) je grupoid. Pak na G existuje nejvyse jeden

neutraln prvek.

D ukaz Pro spor necht' f; g 2 G jsou 2 r uzne neutraln prvky.

Potom

e=e
f =f

QED poznamka 1.10 Necht' M (
; e) je monoid, necht' a; b; c 2 M tak, ze e = a
b = c
a, pak b = c d ukaz

c = c
e = c
(a
b) asoc: = (c
a)b = e
b = b

QED de nice Je-li M (
; 1) monoid, potom prvek m 1 nezveme inverznm prvkem, pokud m
m 1 = m 1
m = 1. Prvek je invertibiln, existuje-li j nemu inverzn

prvek.

9

prklady

 M (X ) obsahuje pouze jeden invertibiln prvek, a to prazdne slovo.  v T (X ) jsou invertibiln prave bijekce X nekonecna... 9f 2 T (X ) pro nej najdeme nejake g 2 T [x] : g  f 2 Id, ale f nen invertibiln naprklad f : N ! N n ! 2n n g:N !N n!d e 2 g(f (x)) = Id, ale f (g(x)) nen na, protoze f nen na. de nice Podmonoidem nazveme podalgebru monoidu M (
; 1) poznamka 1.11 Necht' M (
; 1), pak M  mnozina vsech invertibilnch prvk u

tvor podmonoid, navc kazdy inverzn prvek k nejakemu invertibilnmu prvku je tez invertibiln D ukaz  M  = fm 2 M j9n 2 M : n
m = m
n = 1g

 1
1 = 1, tj. 1 je inverzn sama k sobe ) 1 2 M  (uzavrenost na operaci "1")  Necht' a; b 2 M  , tj. 9c; d 2 M a
c=c
a=1 b
d=d
b=1 Tedy (a
b)
(d
c) asoc: = a
(b
d)
c = |{z} a
1
c = a
c = 1 a

(d
c)
(a
b) = d
(c
a)
b = d
b = 1 Tedy (a
b) 2 M a tm jsme overili uzavrenost na
 m 2 M 9n n
m = m
n = 1 neboli m je inverznm prvkem pro n QED de nice R ekneme, ze G(
; 1 ; 1) je grupa, pokud G(
; 1) je monoid a 1 je

unarn operace inverznho prvku 1 : G ! G 8g 2 G : g
g 1 = g 1
g = 1 10

poznamka 1.12 Necht' M (
; 1) je monoid, M  mnozina vsech invertibilnch

prvku,


dM  : M 
M  ! M  m
dM  n = m
n m; n 2 M  a 1 prirad kazdemu prvku z M inverz. Potom M  (
dM  ; 1 ; 1) je grupa. d ukaz z de nice grupy a poznamky 1.11 prklady

 T (x)(; Id) - monoid, podle 1.12, (T (x)) = S (x) vsechny bijekce, pak S (x)(; 1 ; Id) je grupa, specielne S (f1; :::; ng) jsou permutace na f1; :::; ng  Mn (T )(
; In ) GLn (T )(
; 1 ; In ) je grupa, kde GLn (T ) jsou invertibiln matice nad telesem T

de nice Necht' G(
; 1 ; 1) je grupa. R ekneme, ze H  G je podgrupa grupy G(
; 1 ; 1), pokud H je podalgebra algebry G(
; 1 ; 1) R ekneme, ze podgrupa H je normaln, plat-li 8g 2 G 8h 2 H : g
h
g 1 2 H

R ekneme, ze grupa je komutativn, je-li jej binarn operace komutativn

poznamka 1.13 Vsechny podgrupy komutativn grupy jsou normaln d ukaz Necht' G(
; 1 ; 1) je komutativn grupa, H je podgrupa G, g 2 G, h2H g
h
g 1 komut: = g
g 1
h=1
h=h2H

QED prklad

S (f1; 2; 3g) (
; 1 ; Id) 1 = (23) 2= H , tj. H nen normaln fId; (12)g je podgrupa ... (13)
(12)
|(13) {z } (31)

 TA 1.14 Necht' G(
; 1 ; 1) je grupa. Pak  je kongruence na grupe G(
; 1 ; 1) VE

prave tehdy, kdyz  [1] je normaln podgrupa  (g; h) 2  , g 1
h 2 [1]

11

d ukaz

")"

 [1] je podgrupa { (1; 1) 2  - re exivita ) 1 2 [1] - uzavrenost na 1. { h 2 [1] tzn. (1; h) 2 , a protoze  je slucitelna s 1 0 @

1

1

1

|{z}; h

1

1 A 2  ) h 1 2 [1]

- uzavrenost na 1 { h1 ; h2 2 [1] tzn. (1; h1 ) 2  a (1; h2 ) 2 , a protoze  je slucitelna s
, tedy 0 1 @

1
1

|{z}; h1

1


h2 A 2  ) h1
h2 2 [1]

- uzavrenost na
 [1] je normaln Necht' g 2 G, h 2 [1] , tedy (1; h) 2 .  je ekvivalence, tedy (g; g) 2  a (g 1 ; g 1 ) 2  Vme, ze  je slucitelna s
, takze (g
1; g
h) 2 &(g|
1{z
g }1 ; g
h
g 1 ) 2  1

Tedy

g
h
g 1 2 [1]

 (g; h) 2 , (g1 ; g 1 ). Protoze  je slucitelne s
(|g {z1
g}; g 1
h) 2  ) g 1
h 2 [1] =1

 g 1
h 2 [1] tj. (1; g 1
h) 2 , ale  je kongruence, takze (g; g) 2 , a protoze  je slucitelna s
(g
1; g
g 1
h) = (g; h) 2  "(" H je normaln podgrupa def  : (g; h) 2   g 1
h 2 H , kazda podgrupa je uzavrena na 0-arn operaci, tedy 1 2 H  ? ekvivalevnce? 12

{ (re exivita) g 1
g = 1 2 H ) (g; g) 2  { (symertie) (g; h) 2  def ) g 1
h 2 H , pak (g 1
h) 1 2 H , kvuli uzavrenosti na 1 . (g 1
h) 1 = h 1
(g 1 ) 1 = h 1
g def ) (h; g) 2  def { (transitivita) (g; h) 2 ; (h; r) 2  ) g 1
h 2 H; h 1
r 2 H , a protoze H je uzavrena g 1
r = (g 1
h)
(h 1
r) 2 H def ) (g; r) 2  |

{z

1

}

 ?slucitelnost se vsemi operacemi? { (1; 1) 2 , nebot'  je re exivn { (g; h) 2  def 1 ) g
h 2 H H norm ) aln{ g
(g 1
h)
g 1 = hg 1 = (h 1 ) 1
g 1 2 H ) (h 1 ; g 1 ) 2  ) (g 1 ; h 1 ) 2  Tedy  je slucitelne s 1 { (g1 ; h1 ); (g2 ; h2 ) 2  def 1 ) g1
h1 ; g2 1
h2 2 H H normaln{ ) h 2
g 2 1 = g2
g 2 1
h 2
g 2 1 2 H H normaln{ 1 ) g2
g1 1
h1
h2 g|2 1{z
g}2 2 H 1

 12H

) (g1
g2 ) 1
(h1
h2 ) 2 H ) (g1
g2 ; h1
h2 ) 2  

[1] = h 2 H j(1; h) 2 (tj: h = 1 1
h 2 H )



QED

znacen Necht' G(
; 1 ; 1) je grupa, H je kongruence, H = [1]H (toto jednoznacne de nuje tu kongruenci). G= (
; 1 ; [1]H ) se obvykle znac G=H (
; 1 ; [1]H ) Prklady  Z (+; ; 0) je komutativn grupa. nZ ...nsechny celocselne nasobky n

! podgrupy Z (+; ; 0), ktere jsou podle 1.13 normaln.  Regularn matice GLn (T )(
; 1 ; In ) Normaln podgrupou jsou naprklad konstantne diagonaln matice (vsechny prvky na diagonale jsou stejne) nebo matice se stejnym determinantem  Sn ...permutace na f1; :::; ng An - sude permutace tvor normaln grupu  G(
; 1 ; 1) je grupa, pak [1], G jsou trivialn normaln grupy. 13

2 Uzaverove systemy na algebre

de nice R ekneme, ze C  P (A) je uzaverovy system na mnozine A, pokud

 (1) A 2 C  (2) B  C ) T B = TB2B B 2 C

de nice Je-li C uzaverovy system, pak

clC (B ) =

\

fC 2 CjB  C g

je uzaver mnoziny B  A de nice Zobrazen  : P (A) ! P (A) nazveme uzaverovym operatorem, pokud

 (1) B  (B ) 8B  A  (2)  ((B )) = (B )  (3) B  C  A ! (B )  (C ) (monotonie)

prklad V ...vektorovy prostor, V ...vsechny podprostory V . system: X  V clV (X ) = L

V je uzaverovy

poznamka 2.1

1. Necht' A je mnozina s operac . Pak vsechny podmnoziny uzavrene na  tvor uzaverovy system na A 2. Necht' A(i ji 2 I ) je algebra. Potom vsechny podalgebry tvor uzaverovy system na A. d ukaz

1. viz. poznamka 1.1, (2) z de nice 2. vlastnost (1), A je trivialne uzavrena na  QED  TA 2.2 VE

1. Necht' C je uzaverovy system na A. Pak uzaver clC je uzaverovy operator. 2. Necht'  : P (A) ! P (A) je uzaverovy operator na mnozine A. Potom  C = fC 2 P (A)j(C ) = C g je uzaverovy system a  clC =  14

d ukaz

1. C ...uzaverovy system  Nejdrve overme axiom (1) \

B C fC 2 CjB  C g 8C :) B  clC (B )  (2) prvn inkluze je trivialn

clC (B ) =

clC (clC (B ))

(1)

 clC (B ) 2 C

druha je jiz trosku tezs clC (B ) 2 fC 2 CjclC (B )  C g \ clC (B )  fC 2 CjclC (B )  C g = clC (clC (B ))  B1  B2  A fC 2 CjB1  C g  fC 2 CjB2  C g \ \ clC (B1 ) = fC 2 CjB1  C g  fC 2 CjB2  C g = clC (B2 ) 2. ...uzaverovy operator Je C = fC 2 P (A)j(C ) = C g uzaverovy system?  A   ( A)  A ) A =  ( A) ) A 2 C  Ci 2 C i 2 I  (Ci ) = Ci  \

i2I \

i2I



\

i2I

Ci

 

\

i2I

\

Ci  

i2I

!

Ci

Ci  Cj j 2 I ) !

  (Cj ) = Cj 8 j 2 I

\

i2I !

!

Ci

Ci =

tj. C je uzaverovy system

15



[

i2I

\

j 2I

Cj

\

) Ci 2 C

3.  = clC , dokazeme 8B (B ) = clC (B )  ((B )) = (B ) ) (B ) 2 C B  (B ) ) clC  (B ) 4. ?(B )  clC (B )? clC (B ) =

\

fC 2 PjC = (C ) & B  C g

B  C )  (B )   (C ) = C

) (B )  vsech takovych mnozin, tedy je i v jejich pruniku, a tedy (B )  clC (B ) To jest (B ) = clC (B ) 8B 2 A QED prklad Z (+;
; 0), ni 2 N , ni Z = fni z jz 2 Z g. Potom \

i2Z

ni Z = gcd(n1 ; :::; nk )Z

Neboli lez v uzaverovem systemu vsech podgrup poznamka 2.3 Vsechny uzaverove systemy na A tvor uzaverovy system na

P

d ukaz

 P (A) je trivialne uzaverovy system.  Ci - uzaverove systemy na A, i 2 I B

\

Ci ) B  Ci 8i 2 I Ci uz:)system

\

B 2 Ci 8i 2 I )

\

B2

\

i2I

Ci

QED poznamka 2.4 Necht' A  B jsou uzaverove systemy na A a C  D  A. Pak clB (C )  clA (D)

16

d ukaz





fB 2 BjC  B g  fA 2 AjC  Ag (tato inkluze plyne z velikosti mnozin) \

\

) clB (C ) = fB 2 BjC  B g  fA 2 AjC  Ag = clA (C )

 z de nice a (2.2) )

clA (C )  clA (D) clB (C )  clA (C )  clA (D)

QED

poznamka 2.5 Vsechny re exivn (symetricke, transitivn) relace i ekvivalence na mnozine A tvor uzaverove systemy na A  A d ukaz

      

R... vsechny re exivn relace na A S ... vsechny symetricke relace na A T ... vsechny transitivn relace na A E ... vsechny ekvivalence na A E =R\S \E A  A 2 E (R; S ; T ), tm je overena prvn podmnka uzaveroveho systemu i 2 R \ id  i 8i 2 I ) id  i 2 R i2I

 i 2 S \ \ (a; b) 2 i ) (a; b) 2 i 8i symetrie ) (b; a) 2 i 8i 2 I ) (b; a) 2 i 2 S i2I

 i 2 T (a; b); (b; c) 2

\

i ) (a; b); (b; c)i 8i 2 I ) (a; c) 2 i \

\

) (a; b) 2 i ) i 2 T  E je prunik uzaverovych systemu a vsechny uzaverove systemy na mnozine tvor uzaverovy system. Proto E mus byt tez uzaverovy system. QED 17

poznamka 2.6

1. Necht'  je operace na A. Pak vsechny ekvivalence slucitelne s  tvor uzaverovy system na A  A 2. Necht' A(i ji 2 I ) je algebra. Potom vsechny kongruence na A tvor uzaverovy system na A  A d ukaz

1. A  A je trivialne slucitelne s  T Necht' i je ekvivalence slucitelne s , i 2 I . Potom i je podle poznamky 2.5 tez ekvivalence T Necht' a1 ; :::; an ; b1 ; :::; bn 2 A a (aj ; bj ) 2 i2I i 8j = 1; :::; n ) (aj ; bj ) 2 i 8i 2 I 8j = 1; :::; n ((a1 ; :::; an ); (b1 ; :::; bn )) 2 i 8i 2 I \ ) ((a1 ; :::; an ); (b1 ; :::; bn )) 2 i i2I

neboli  je slusitelna s ekvivelenc vzniklou prunikem ekvivalenc slucitelnych s 2. Ei ...mnozina vsech ekvivalenc slucitelnych s i tvor uzaverovy system. KOngruence Tje podle de nice slucitelna se vsemi operacemi kongruence= i2I Ei - tedy dle poznamky 2.3 uzaverovy system QED poznamka 2.7 Necht'  je relace na A. Pokud  je re exivn (resp. symetricka), tak  [  , + je opet re exivn (resp. symetricka) d ukaz

 Necht'  je re exivn

id     [  id    + = f(a; b) 2 AAja0 ; :::; an 2 A; a0 = a; an = b; (ai 1 ; ai ) 2 8i 2 1; :::; ng

 Necht'  je symetricka

=[ 1 (a; b) 2 + z de nice a0 ; :::; an 2 A tz. a0 = a, an = b, (ai 1 ; ai ) )

) (ai ; ai 1 ) 2  ) (an ; a0 ) 2 + QED 18

 TA 2.8 Necht'  je relace na A. Potom VE 

[

( [ id) ( [ id)

+

= ( [  [ id)+

je nejmens ekvivalence obsahujc relaci  (E -ekvivalence na A, clE () = ( [  [ id)+ ) d ukaz

   

 [ id je re exivn S

( [ id) ( [ id) je re exivn a symetricka relace S  := (( [ id) ( [ id) )+ je ekvivalence Dale je treba dokazat jej minimalitu    clE ()   ( [ id)  clE [ id = clE () [ ( [ id) ( [ id) 1  clE () [ clE ( ) = clE () 

[

( [ id) ( [ id)

+

 clE ()+ = clE () QED

de nice Necht' A je algebra, A je system vsech podalgeber, X  A. R ekneme, ze X generuje (podalgebru) clA (X ) poznamka 2.9 Necht' A(i ji 2 I ), B ( i ji 2 I ) jsou algebry stejneho typu. Necht' f; g : A ! B jsou homomor smy. Pokud X generuje A a f (x) = g(x) 8x 2 X , pak f = g d ukaz

Y = f y 2 Aj f ( y ) = g ( y ) g = X A(i ) f (i (y1 ; ::; yn )) = i (f (y1 ); :::; f (yn ))) = i (g(y1 ); :::; g(yn )) = g (i (y1 ; :::; yn )) ) Y je uzavrena na i 8i 2 I , tj. Y je podalgebra, X  Y a X dle predpokladu generuje A, tedy Y = A

QED

19

prklady

 Necht' Z (+; ; 0) je grupa a G(+; ; 0) algebra, obe jsou stejneho typu. Necht' f; g : Z ! G jsou homomor smy < f1g >= f1| + {z ::: + 1} jn 2 N g [ f0g [ f( 1) + ::: + ( 1)jn 2 N g = Z {z } | n

n

 M (X ) - vsechna slova nad psmeny z X , M (X )(
; e) < X >= M (X ) f; g : M (X ) ! G(
; e) G(
; e) je nejaky monoid f (x) = g(x) 8x 2 X 2):9 f = g

 G tak, ze < Y >= G M (Y )(
; e) 9!' : M (Y ) ! G ' je homomor smus ker ' - kongruence na M (Y ), '(y) 8y 2 Y

Y

3 Isomor smy algeber de nice Necht' A, B jsou algebry stejneho typu. A ' B (A je isomorfn B ), pokud 9f : A ! B vzajemne jednoznacny homomor smus (isomor smus). poznamka 3.1 Necht' M je mnozina algebra, pak ' tvor ekvivalenci na M. d ukaz Id : A ! A je isomor smus ) re exivita ', symetrie a transitivita

z (1:2)

QED de nice Necht'    je dvojice ekvivalenc na A. Pak = je relace na A= dana predpisem ([a] ; [b] ) 2 =  (a; b) 2  poznamka 3.2 Necht'    jsou ekvivalence na A. Pak = je ekvivalence na A= d ukaz plyne okamzite z re exivity, symetrie a transitivity relace . poznamka 3.3 Necht' A je algebra,  bud' kongruence na A obsahujc . Pak  je kongruence na A prave tehdy, kdyz = je kongruence na algebre A=

20

d ukaz

dle 3.1 = je ekvivalence na A= Necht'  je libovolna n-arn operace na A a na A= a1 ; :::; an ; b1 ; :::; bn 2 A ([ai ] ; [bi ] ) 2 =  ([a1 ] ; :::; [an ] ) = [(a1 ; :::; an )]  ([b1 ] ; :::; [bn ] ) = [(b1 ; :::; bn )] Vme, ze ((a1 ; :::; an ); (b1 ; :::; bn )) 2  a podle de nice = (([a1 ] ; :::; [an ] ); ([b1 ] ; :::; [bn ] )) 2 =

")"

"(" = je kongruence,  je ekvivalence ma A. Dokazujeme, ze  je slucitelna s 

 Predpokladam

a1 ; :::; an ; b1 ; :::; bn (ai ; bi ) 2  ) ([ai ] ; [bi ] ) 2 =

 dale

( ([a1 ] ; :::; [an ] ) ; ([b1 ] ; :::; [bn ] )) 2 =  tedy dle de nice ((a1 ; :::; an ); (b1 ; :::; bn )) 2  QED

poznamka 3.3 1. Necht' f : A ! B je zobrazen slucitelne s operac , kde  je operace na A a B stejne arity. Necht'  je ekvivalence na A slucitelna s . Pak existuje zobrazen g : A= ! B slucitelna s . Pak existuje zobrazen g : A= ! B slucitelne s  splnujc podmnku

,   ker f Navc g je bijekce prave tehdy kdyz  = ker f 2. Necht' f : A ! B je homomor smus algeber A, B stejneho typu a  je kongruence na A. Pak existuje homomor smus g : A= ! B takovy, ze g = f ,   ker f Navc g je isomor smus prave tehdy kdyz g je na a  = ker f (veta o homomor smu) g  = f

21

d ukaz

1. Podle poznamky 1.6 9 zobrazen g : A= ! B : g = f )   ker f , chceme dokazeme, ze g ([a] ) = g (a) = f (a) 8a 2 A ")" prmo z poznamky 1.6(4))   ker f "(" vme, ze 9g - zobrazen a chceme dokazat, ze je slucitelne s  QED  TA 3.4 - 1. veta o isomor smu Necht' f : A ! B je homomor smus VE algeber stejneho typu. Pak f (A) je podalgebra B (tzn. je stejneho typu) a A=ker f ' f (A) d ukaz

   

f : A ! f (A) je podalgebra B (viz poznamka 1.3)

podle poznamky 3.3(2.) je  = ker f 9g : A=ker f ! f (A) podle 3.3(2) ker f =  a f je na f (A), potom g je isomor smus QED

 TA 3.7 Necht'    jsou dve kongruence na algebre A. Pak VE

A===

' A=

d ukaz

A ! A= 

A ! A=

Vme, ze   , ker  =  Z poznamky 3.3 9g : A= ! A= g([a] ) = [a] je homomor smus dle 3.3

ker g = f([a] ; [b] )j[a] = [b] g

to je podle de nice = g je na, a tedy dle 1. vety o isomor smu A==ker g ' A= a z toho hned plyne tvrzen QED 22

4 Svazy

de nice R ekneme, ze relace  na M je usporadan, pokud je re exivn, tran-

sitivn a slabe antisymetricka, neboli a  b&b  a ) a = b prklady

   

P (X ) - potence na X , pak  je usporadan Z a "standardni"  na N relace "j" je taktez usporadan Id na M - extremn prpad

de nice Necht'  je usporadan na M = 6 ; a A  M . R ekneme, ze m 2 A je nejvets (nejmens) prvek A, pokud

8a 2 A : a  m (m  a) de nice R ekneme, ze sup (A) (resp. inf  (A) 2 M ) je supremum (resp. in mum) mnoziny A, pokud sup (A) je nejmens prvek z mnoziny fm 2 M ja  m 8a 2 Ag. In mum je nejvets doln zavora de nice R ekneme, ze dvojice (M; ) je svaz, pak existuje sup (fa; bg) a inf  (fa; bg) pro (kazda dve) a; b 2 M de nice O svazu (M; ) rekneme, ze je uplny, existuje-li supremum i in mum pro kazdou (i nekonecnou) podmnozinu M de nice Zavedeme binarn operace _ a ^ na M predpisem a; b 2 M

 a ^ b = inf  (fa; bg)  a _ b = sup (fa; bg)

8a; b; c 2 M :  (S1) komutativita

poznamka 4.1

 (S2) idempotence

a^b=b^a a_b=b_a a^a=a=a_a

23

 (S3) asociativita

a ^ (b ^ c) = (a ^ b) ^ c a _ (b _ c) = (a _ b) _ c

 (S4) absorbce

a ^ (b _ a) = a a _ (b ^ a) = a

d ukaz

 (S1) a (S2) jsou trivialn  (S3) stac dokazat, ze a ^ (b ^ c) =? inf (fa; b; cg) (= c ^ (a ^ b)) |

{z

=:i

}

z de nice i  a; i  b; i  c i  (b ^ c) i  a ^ (b ^ c) a ^ (b ^ c)  a a ^ (b ^ c)  (b ^ c)  b a ^ (b ^ c)  (b ^ c)  c a ^ (b ^ c)  i slaba antisymetrie ) a ^ (b ^ c) = i Pujdeme-li z druhe strany, tak to taky vyjde, cmz mame existenci  (S4) a ^ (b _ a)  a a  a (re exivita) a  b _ a (horn odhad)) a  a ^ (b _ a) Tedy ze slabe antisymetrie a = a ^ (b _ a) QED poznamka 4.2 Necht' M (^; _) je algebra s dvojic binarnch operac splnujcch podmnky (S1)-(S4). De nujeme na M relaci  predpisem

ab

def:

 a_b=b Pak (M; ) je svaz a a ^ b = inf  (fa; bg) a a _ b = sup (fa; bg)

24

d ukaz

tm je dokazana re exivita

(S 1)a ^ a = a (S 1)a _ a = a



)aa

ab bc'b=a_b c=b_c c = (a _ b) _ c S=3 a _ (b _ c) = a _ c | {z }

=c

Neboli a  c a tm je hotov dukaz transitivity

a  b; b  a ) b = a _ b S=1 b _ a = a

A to je presne slaba symetrie Neboli takto de novana relace  tvor usporadan na M Dale a ^ b = a ^ (a _ b) S=1 a ^ (b _ a) S=4 a Touto rovnost je dokazan vztah a  b , a = a ^ b Dale budeme predpokladat (c  d ) c = c ^ d) (a ^ b) ^ a S=1 a ^ (a ^ b) S=3 (a ^ a) ^ b S=2 a ^ b tj. (a ^ b)  a, pro (a ^ b) ^ a dostanu podobnym postupem a ^ b  b, tj. a ^ b je dolnm odhadem pro fa; bg Vezmu c  a; b, c = c ^ a c ^ (a ^ b) S=3 (c ^ a) ^ b = c ^ b = c ) c  (a ^ b) To znamena, ze a ^ b je nejvets v mnozine dolnch odhadu, a ^ b pak mus byt in mum fa; bg. QED d usledek

(S; ) ! S (^; _) ! (S; ~ ) )= ~ S (^; _) ! (S; ) ! S (^; _) ) ^ = ^; _ = ^ Dky tomu mame jednoznacnou korespondenci svazu a pruseku+sloucen. Dale budeme svazem nazyvat i algebry S (^; _) splnujcm (S1)-(S4).  TA 4.3 Kazdy uzaverovy system je uplnym svazem S (C ; ), B  C VE [

sup B = clC ( B) = clC 

inf B= 

\

B=

25

\

B 2B

[

B 2B

B

!

B

d ukaz plyne ihned z vlastnost uzaveroveho systemu znacen Vezmu svaz (S; ). R ekneme, ze a pokryva b, a; b 2  (a < b), pokud b 6= a, b  a, b  c  a ) b = c _ a = c: Necht' f resp. g 2 S je nejvets resp. nejmens prvek S , potom a resp. b nazveme atomem resp. koatomem svazu S , pokud f < a resp. b < e Hasseovym diagramem svazu nazvu orientovany graf s vrcholy S . Mezi a a b bude hrana vedouc od a k b, pokud a < b poznamka 4.4 Je-li S (^; _) svaz, pak S (_; ^) je take svaz d ukaz Plyne hned z 4.1 a 4.2. poznamka 4.5 Necht' (S; ) je svaz a a; b; c a _ (b ^ c)  (a _ b) ^ c

2 S . Pokud a  c, potom

d ukaz a  (a _ b) a a  c, tedy a  (a _ b) ^ c b ^ c  b  a _ b a b ^ c  c, tedy (b ^ c)  (a _ b) ^ c

Tedy

a _ (b ^ c)  (a _ b) ^ c

QED de nice O svazu S (^; _) rekneme, ze je modularn, pokud plat

8a; b; c 2 S a  c ) a _ (b ^ c) = (a _ b) ^ c de nice Necht'  je usporadan na A a na B . R ekneme, ze zobrazen f : A ! B je monotonn, pokud a1  a2 ) f (a1 )  f (a2 ). poznamka 4.6 Necht' f : A ! B je homomor smus svaz u A(^; _) a B (^; _). Potom f je monotonn. d ukaz Necht' a1  a2 (, a2 = a1 _ a2 ).

f (a2 ) = f (a1 _ aa2 ) homomorfismus = f (a1 ) _ f (a2 )

Podle de nice potom f (a1 )  f (a2 ) QED poznamka 4.7 Necht' f : A ! B je bijektivn zobrazen dvou svaz u (A; ) a (B; ). Pak f je isomor smus svazu , f i f 1 jsou monotonn zobrazen

26

d ukaz

")" f; f 1 jsou isomor smy, tedy podle poznamky 4.6 jsou obe zobrazen monotonn "(" f; f 1 stac ukazat, ze f je slucitelne s _, zbytek uz plyne ze symetri. Necht' a; b 2 A. Necht' a  a _ b, b  a _ b. Zobrazen f je monotonn, takze mame f (a)  f (a _ b) f (b)  f (a _ b) ) |f (a) {z_ f (b})  f| (a{z_ b}) (1) nejmens{ horn{ odhad

nejaky horn{ odhad

Dale necht' d = f (a) _ f (b). f (a)  d a f (b)  d, vme ze f 1 jsou monotonn a = f 1 (f (a))  f 1 (d) b = f 1 (f (b))  f 1 (d) a _ b  f 1 (d) Opet pouzijeme monotonnost f
f (a _ b)  f f 1 (d) = d = f (a) _ f (b)(2) Dky slabe symetrii, (1) a (2) f (a _ b) = f (a) _ f (b) Neboli f je slucitelne s _ QED poznamka 4.8 Necht' C je uzaverovy system lez v mnozine vsech ekvivalenc na A. Necht' N je nejaky podsystem P (A) a e 2 A tak, ze   2 C ) [ e]  2 N  N 2 N ) 9ekvivalence  2 C , ze N = [e]=rho  [e]  [e] pro ;  2 C )    Pak N je uzaverovy system (a tudz svaz) a zobrazen ' : C ! N dane predpisem '() = [e] je svazovy isomor smus.

27

d ukaz A = [e]AA A  A 2 C , A  A je ekvivalence a to ta nejets, takze lez v C . A = faj(e; a) 2 A  Ag 2 N (to plat z prvnho predpokladu) Necht' Ni 2 N i 2 I , potom s vyuzitm druheho predpokladu 9i 2 C Ni = [e]i  TA 4.9 Nevht' G(
; 1 ; 1) je grupa, pak svaz vsech kongruenc na G je VE isomorfn svazu vsech normalnch podgrup G (s usporadanm ) \

T

i2I

=

\

i2I

[e]i = fa 2 Aj(e; a) 2 i 8i 2 I g = [e]Ti2I i 2 N

i 2 C , nebot' C je uzaverovy system | Je ' bijekce?  dobre de novane zobrazen  je to na 8N 2 N prirad   [e]  [e] )    - a stejne pro =;  Tedy ano, ' je bijekce '; ' 1 je prmo z de nice monotonn 4):7 ' je isomor smus svaz u.

QED

D ukaz Necht' C jsou vsechny kongruence na G

 2 C ) [1] 2 N

kde N jsou vsechny normaln podgrupy G Z 4.8 evidentne plat [1]  [1] , 1 :14 (a; b) 2  ) a
b 1 2 [1]  [1] , (a; b) 2  Tedy z 4:8 je N uzaverovy system a ' je isomor smus

QED

de nice Necht' A; B jsou mnoziny a  : P (A) ! P (B ), : P (B ) ! (P )(A). R ekneme, ze ; tvor Galiosovu korespondenci, plat-li 8A1 ; A2 2 P (A); B1 ; B2 2 P (B )  (1) A1  A2 ) (A1 )  (A2 )  B1  B2 ) (B1 )  (B2 )  (2) A1  (A1 ); B1   (B1 )

28

poznamka 4.10 Necht'  : P (A) ! P (B ) a : P (B ) ! P (A) je Galoisova korespondence. Pak  (respektive  ) je uzaverovy operator na P (A) (resp. na P (B )). Necht' A resp B je uzaverovy sysem na A resp. B prslusny  resp.  . Dale (A)  B, (B)  A. Restrikce  resp. na A resp B (oznacme je 0 : A ! B, 0 : B ! A) jsou vzajemne inverzn bijekce d ukaz

 nejdrve dokazme, ze  je uzaverovy operator ( symetricky)  (2) ) A1  (A1 ) A1  A2 ) (A1 )  (A2 ) ) (A1 )  (A2 ) Tm je dokazana monotonie  ?(( )( )) (A1 ) =? (A1 )? (A1 )

(2)

  ( (A1 ))

(2)

  ((A1 )) (1) )  (A1 )  (A1 )  Tedy mame uzaverove systemy A = fA1 2 P (A)j (A1 ) = A1 g B = fB1 2 P (B )j (B1 ) = B1 g  ?(A)  B? (symetricky (B )  A) Necht' A1 2 A ) (A1 ) = A1  ( ((A1 ))) =  ( (A1 )) = (A1 ) ) (A1 2 B ) B1 = (A1 )

 0 0 : B ! B =? IdB 0 0 : A ! A =? IdA Jinymi slovy to znamena, ze 0 a 0 jsou bijekce a jsou k sobe vzajemne inverzn 0 0 (B )1 ) =  (B1 ) predpoklad = B1 ) 0 0 = IdB

5 Grupy de nice G(
; 1 ; 1) je grupa, pokud
je asociativ binarn operace, 1 je unarn a
a 1 = a 1
a = 1 a 1 je neutraln prvek poznamka 5.1 Je-li f zobrazen dvou grup slucitelne s binarn operac, pak f je homomor smus

29

d ukaz



f (1) = f (1
1) = f (1)
f (1)



) f (1) = f (1)
f (1) j
f (1) 1 2 H ) 1 = f (1) Tedy f je slucitelne s operac 1 1 = f (1) = f (a
a 1 ) = f (a)
f (a)

1

1 = f (a)
f (a 1 ) j (f (a)) 1
) (f (a)) 1 = f (a 1 ) Tedy f je slucitelne s operac  QED de nice Necht' G(
; 1 ; 1) je grupa a

 H; K  G; HK = H
K = fh
kjh 2 H; k 2 K g  hK = fhgK  Kh = K fhg Zavedeme relaci rmod H  G  G (respektive lmod H  G  G) tak, ze (a; b) 2 rmod H (respektive 2 rmod H ) def:  ab 1 2 H (a 1 h 2 H ) poznamka 5.2 Necht' G(
; 1 ; 1) je grupa a H jej podgrupa. Pak pro a; b 2 G

plat 1. rmod H a lmod H jsou ekvivalence na G 2. (a; b) 2 rmod H , (a 1 ; b 1 ) 2 lmod H 3. jG=rmod H j = jG=lmod H j (pro nekonecne mnoziny: maj stejnou kardinalitu) 4. [a]rmod H = Ha, [a]lmod H = aH 5. jH j = j[a]rmod H j = j[a]lmod H j

30

d ukaz

1.

 Necht' Tedy rmod je re exivn  Necht' (a; b) 2 rmod H

a
a 1 =12H


ab 1 2 H ) ba 1 = a
b 1 1

Tedy rmod je symetricka  Necht' ab 1 ; ac 1 2 H ac 1 = (ab 1 )(bc 1 ) 2 H

Tedy je i transitivn a je to ekvivalence na G - lmod H symetricky 2. (a; b) 2 rmod H a
b 1 2 H uzav:)na

1



ab 1 = b 1 1 a 1 2 H ) (b 1 ; a 1 ) 2 lmod H

Opacna implikace se dokaze symetricky 3. Z predchozho bodu mame bijekci mezi lmod a rmod. Potom obe faktormnoziny mus byt stejne velke. 4.  [a]rmod H = fx 2 G; ax 2 rmod H g = x 2 H j9h 2 H : x = h 1 a = Ha (protoze H je podgrupa, tudz je uzavrena na 1 ) Pro lmod je opet tvrzen dokaze symetricky 5. Podle predchozho bodu [a]rmod H = Ha, b : H ! Ha je zjevne na, stac ukazat, ze b je proste b(h1 ) = b(h2 ) = h2 a h1 = h1
a
a 1 = h2
a
a 1 = h2 QED de nice Necht' Hi je podgrupa grupy G(
; 1 ; 1). Pak indexem H na grupe G rozumme [G : H ] = G=rmod H = G=lmod H  TA 5.3 - Lagrangeova Je-li G grupa a H jej podgrupa, pak VE

jGj = [G : H ]
jH j 31

d ukaz

[



jGj =  fA(= [a]rmod H )jA 2 G=rmod H g =

X

a2G=rmod

H

A |{z} =jH j

= [G : H ]
jH j QED

d usledek 5.4 Velikost podgrupy del velikost konecne grupy de nice Necht' G(
; 1 ; 1) je grupa g 2 G. Indukcne de nujeme  g0 = 1

 gn+1 = g
gn pro n > 0  gn = (g 1 )jnj pro n < 0

poznamka 5.5 Necht' G(
; 1 ; 1) je grupa a a 2 G. Zobrazen ' : Z ! G dane predpisem '(n) = an je homomor smus grupy Z (+; ; 0) do grupy G(
; 1 ; 1).

Navc

'(Z ) = hai = fan jn 2 Z g

d ukaz Stac dokazat uzavrenost na
. Zbytek uz vyplyne sam.

?'(n + m) = gn
gm ? Tady se mus vysetrit jednotlive prklady podle toho, jestli je m; n vets nebo mens nez 0. Vsechny jsou vzasade trivialn. QED poznamka 5.6 Necht' G(
; 1 ; 1) je grupa a a 2 G. Potom pro kazde n; m 2 Z plat, ze (an )m = amn d ukaz

 Je-li m = 0 nebo n = 0, potom vztah zrejme plat  Pro n > 0, m > 0 lze pouzt jednoduchou indukci podle m { (an )1 = an = an
1 - Tedy pro m = 1 plat { a pro m > 1? (an )m = (an )m 1
an IP = an(m 1) an = anm  pro n < 0 < m 

(an )m def = a


1
n m predchoz = { a 1 nm def: = anm

32

 pro m < 0 < n je to dky (a
b) 1 = b 1
a 1 to same  n < 0, m < 0 je to samy.

QED

de nice Necht' G(
; 1 ; 1) je grupa. Oznacme hai nejmens podgrupu grupy G obsahujc prvek a 2 G. R ekneme, ze grupa G je cyklicka, pokud existuje takovy prvek g 2 G, ze hgi = G poznamka 5.7 1. Je-li A  Z , pak A je podgrupa Z , prave kdyz existuje k  0 takze A = kZ 2. Je-li A  Zn , pak A je podgrupa Zn , prave kdyz existuje k 2 Zn tak, ze k je 0 nebo k del n a A = kZn d ukaz

1. Budeme predpokladat, ze H 6= f0g (H = f0g ) k = 0)

9k 2 H ; k 6= 0 : (k < 0 ) k > 0 ) k 2 H ) ) 9k 2 H; k > 0 Vezmu nejmens k > 0, k 2 H , takoveze < k > H ; a 2 H , vydelme cslo cslem k se zbytkem. a = kx + y y < k y = a + (k
( x)) k
( x) 2 H , protoze je to nasobek k, tedy y 2 H Z minimality volby plyne, ze y  0 a y  0, tedy y = 0 ) a = kx ) a 2 hki 2. dokazeme stejne jako predchoz bod, vse pseme modulo n a = (k
x)n + (y)n ) hki = H |{z} =0

zbyva dokazat, ze k del n Pro spor necht' tomu tak nen a l = gcd(k; n); l < k l mod n = (
k +
n) mod n ; 2 Z ale l mod n = 
k mod n l 2 hki  H Z minimality dostavame spor s l < k, tedy mus k delit n 33

QED

 TA 5.8 Necht' G(
; 1 ; 1) je cyklicka grupa. VE 1. Je-li G nekonecna, potom G(
; 1 ; 1) ' Z (+; ; 0)

2. Necht' jGj = n, potom G(
; 1 ; 1) ' Zn (+; ; 0) d ukaz obecna pozorovan

hg i = G ' : Z ! G('(z ) = gz ) Z poznamky 5.5 je ' homomor smus g = g1 2 '(Z ) G = hgi = '(Z ) neboli ' je na Dle 1. vety o isomor smu (veta 3.4) vezmu Z= ker ' ' G Podle vety 1.14 ker ' je kongruence na Z prave tehdy, kdyz 9H normaln podgrupa Z a dle 5.7 .1 9n 2 Z : H = nZ ) [(a; b) 2 ker ' , a b 2 nZ ] n = 0 ) ker ' = id ) Z ' Z= ker ' ' G neboli zadne dva prvky nesplynou Druhy bod se dokaze z prvnho Z=nZ ' Z= ker ' ' Zn Zn ' Z=nZ ' Z= ker ' ' G QED d usledek 5.9 Podgrupa i faktorova podgrupa kazde cyklicke grupy je opet

cyklicka

d ukaz

 Necht' G je cyklicka, potom je isomorfn Z nebo Zn (podle konecnosti) a obe tyto zase maj cyklicke podgrupy  Necht'  je kongruence ) Z= ' Z=nZ ' Zn Ta je cyklicka Zn= = Z=nZ= ~ = =nZ To je podle 2. vety o isomor smu Z= QED ~

34

d usledek 5.10 Necht' G je cyklicka konecna grupa. Necht' k del jGj, pak 9!H podgrupa G takova, ze jH j = k d ukaz

G ' Zn n = jGj k = 1 ) H = f0g n n n n k > 1(kjn) H = h i = f0; ; 2
; :::; (k 1)
g k k k k

Jednoznacnost: vsechny podgrupy v Zn jsou cyklicke. jK j = k; K = hai:::9a 2 Zn 9b 2 Z : ka = bn n n a=b
)a2h i k k n Tedy hai  h k i jsou stejne velke mnoziny, z nichz jedna je obsazena v druhe. Pak mus byt stejne. QED poznamka 5.11 Necht' G(
; 1 ; 1) je konecna grupa. Pak 8g g j Gj = 1

2 G plat, ze

hgi je cyklicka podgrupa G velikosti k, tedy gk = 1. Dle 5.4 k del jGj
jGj jGj gjGj 5=:6 gk k = 1 k = 1 d ukaz

QED poznamka 5.12

1. Necht' n 2 N; a 2 Zn ; k = gcd(n; a). Potom aZn = kZn 2. aZn = Zn , gcd(a; n) = 1 d ukaz

1. Dle Eukleidova algoritmu 9x; y : k = a
x + n
y k = (a
x) mod n ) k 2 hai; hki  hai Podle predpokladu k del a, tedy 9u : (k
u) mod n = a ) a 2 hki tj: hai  hki ) kZn = a
Zn 35

2. "("

plyne z prvnho dobu pro k = 1

")"

9x; y : a
x + n
b = 1(1 2 Zn ) ) gcd(a; n) = 1 (gcd(a; n) muzu vydelit celou rovnici) QED

! N dane predpisem '(n) = jfkj0 < k < n; gcd(k; n) = 1gj nazveme Eulerovou funkc de nice Zobrazen ' : N

poznamka 5.13 :12 '(n) 5= jfk 2 Zn jhki = Zn gj = jZ  (
; 1)j = jfk 2 Zn j9x : x
k = 1gj n

d ukaz 5.12(2.)+de nice  TA 5.14 - Mala Fermatova VE

8a : a < n; gcd(a; n) = 1 : a'(n) mod n=1 d ukaz a 2 Zn (
; 1), to je dle 1.11 grupa :11 jZn j jZn j = '(n) 5) a| {z } mod n = 1 a'(n)

QED poznamka 5.15

1. Necht' p je prvocslo a n je prirozene cslo. Potom '(pn ) = (p 1)
pn 1 2. Necht' m; n jsou vzajemne nesoudelna prirozena csla. Potom '(n
m) = '(n)
'(m) 36

d ukaz

1.

'(pn ) = jf0 < k < pn

j gcd(k; pn ) = 1gj = = pn 1 jf0 < k < pn j gcd(p; k) > 1gj = (pn 1) (pn 1 1) = (1 p)pn 1 2. na Zn  Zm de nuji nasoben (k1 ; l1 )
(k2 ; l2 ) = (k1
k2 ; l1
l2 ) Algebra Zn  Zm (
; (1; 1)) je monoid. De nuji zobrazen f : Zn
m ! Zn  Zm , ktere k prirad (k mod n; k mod m). Tvrdm, ze f je homomor smus monoidu Zn
m (
; 1) a Zn  Zm (
; (1; 1))  f (1) = (1; 1)  f (k1
k2 ) = ((k1
k2 ) mod n; (k1
k2 ) mod n) = = (k1 mod n; k1 mod m)
(k2 mod n; k2 mod m) = f (k1 )
f (k2 ) Neboli f je slucitelne se vsemi operacemi a tm padem to je homomor smus. Dale je treba dokazat, ze f je bijektivn. Zn
m a Zn  Zm jsou stejne velke, stac tedy dokazat, ze f je proste. Necht' f (k) = f (l) a BU NO necht' k  l. Tzn. k mod n = l mod n ) (l k) mod n = 0 k mod m = l mod m ) (l k) mod m = 0 Neboli m; n del 0  (l k) < n
m. n; m jsou nesoudelne ) n
m del l k, ale to m uze byt jen 0. To znamena ze f je proste, dale jZn
m j = jZn  Zm j, f je homomor smus. Tedy f je isomor smus. Dale (a; b) 2 Zn  Zm je invertibiln , 9(c; d) 2 Zn  Zm tak, ze (a; b)
(c; d) = (a
c; b
d) = (1; 1) , a i b jsou invertibiln :13  'n
m 5= jZn
m j f isomorfismus =

j(Zn  Zm ) j = jZn j
jZm j 5=:13 '(n)
'(m) QED  TA 5.16 Je-li n = pk11
pk22
:::
pkr r prvocselny rozklad csla n, ki VE

potom

'(n) =

r Y

(pi 1)pki i

i=1

37

1

 1,

d ukaz indukce, to vymysl i cvicenej simpanz (ale treba gorila ne).  TA bez d VE ukazu Necht' T je teleso s operacemi +,
. Potom T nf0g(
; 1 ; 1) je komutativn grupa. Necht' G je konecna podgrupa grupy T nf0g(
; 1 ; 1), pak G je cyklicka

6 Okruhy de nice Necht' R(+;
; ; 0; 1) je algebra takova, ze  R(+; ; 0) je komutativn grupa

 R(
; 1) je monoid  a
(b + c) = a
b + a
c  (a + b)
c = a
c + b
c Takouvouto algebru nazyvame okruh

poznamka 6.1 8a; b 2 R(+;
; ; 0; 1) plat  0
a=a
0=0

 ( a)
b = a
( b) = (a
b)  ( a)
( b) = a
b  jRj > 1 , 0 6= 1

de nice Necht' R(+;
; ; 0; 1) je okruh a I  R. Pak I je pravy (levy) ideal,

pokud  I je podgrupa R(+; ; 0)  8i 2 I a r 2 R i
r 2 I (pravy ideal) r
i 2 I (levy ideal)

I je ideal, pokud je zaroven pravy i levy ideal prklady

1. f0g, R jsou trivialn idealy kazdeho okruhu 2. R(+;
; ; 0; 1) r 2 R rR = fr
s j s 2 Rg Rr = fs
r j s 2 Rg Potom rR je pravy a Rr levy ideal. 38

de nice O idealu I rekneme, ze je netrivialn pokud I 6= f0g; R  TA 6.2 Necht' R(+;
; ; 0; 1) je okruh. Pak zobrazen, ktere kongruenci  VE

prirad [0] je isomor smus svazu vsech kongruenc a svazu vsech idealu a navc (a; b) 2  , a| +{z( b}) 2 [0] a b

d ukaz pouzijeme 4.9

 Predpokladame, ze  je kongruence a chceme dokazat, ze [0] je ideal.  je kongruence na komutativn grupe ) [0] je normaln podgrupa R(+; ; 0) Dale vezmeme i 2 [0] a r 2 R. Plat (i; 0) 2  (r; r) 2  Vme, ze  je slucitelna s
(ir; |{z} 0r ) 2 ; (ri; |{z} r0 ) 2  ) ir; ri 2 [0] 0

0

Tm jsme overili obe podmnky de nice idalu ) [0] je ideal.  Mame I ideal a chceme dokazat, ze 9 kongruence takova, ze [0] Vme, ze I je podgrupa, a to dokonce normaln nebot' R(+; ; 0) je komutativn. De nujeme  : (a; b) 2   a b 2 I (to je presne tak, aby nam to vyhovovalo s ohledem na pokracovan vety) Je to kongruence na R(+; ; 0). S operac 1 je trivialne slucitelna dky re exivite, ale je treba dokazat slucitelnost s
. Necht' (a1 ; a2 ) 2  a (b1 ; b2 ) 2 , tedy a1 a2 ; b1 b2 2 [0] = I (a1 a2 )
b1 ; a2
(b1 b2 ) 2 I = [0] ) a1
b1 a2
b2 = (a1
b1 a2
b1 ) + (a2 b1 a2
a2 b2 ) = = (a1 a2 )
b1 + a2
(b1 b2 ) 2 I tj. (a1
b1 ; a2
b2 ) 2   To je splneno, ponevadz jsme si  de novali tak, aby to bylo splneno. QED

39