Thegi1_06 (1).vl-4

Zusammenfassung 5. VL

6.VL TheGI 1 Homomorphismen

 Datenstrukturen D sind ! - Algebren A  Signatur ! ist Syntax von D  ! - Algebra A ist Semantik von D

Themen:  Homomorphismen  Isomorphismen  Bildalgebra  Abbildungssatz  Kategorie von Algebren

 Klassische Algebren, wie 

Halbgruppen, Monoide und Gruppen, sind 

!

- Algebren mit nur einer Sorte, deren Operationen die bekannten Axiome erfüllen Ehrig

6. VL TheGI1

2

Thema : Homomorphismen

Was ist ein Homomorphismus ?

 Was ist ein Homomorphismus ?

 Signatur ! = (S, OP) und ! - Algebren A,B :  Homomorphismus h : A  B ist  h = (hs)s" S Fam. von Abbildungen hs: As Bs



... Isomorphismus ?

 Welche Bedeutung haben



Homomorphismen und Isomorphismen für Datenstrukturen ?

 

 Welche Konzepte lassen sich übertragen

von Abbildungen auf Homomorphismen ?  Wie lassen sich Homomorphismen zerlegen? Ehrig

6. VL TheGI1

3

hs (cA) = cB # ( c:$ s ) " OP hs( fA(a1,...,an)) = fB ( hs1 (a1), ...,hsn(an) ) # f " OP ( Operationsverträglichkeit )

 Homomorphismus h = (hs)s" S heisst  injektiv (surjektiv, bijektiv) , falls  Abbildung hs injektiv (surjektiv, bijektiv) # s"S Ehrig

6. VL TheGI1

4

! - string - Algebren

Beispiel : Homomorphismus  A = NAT = ( % , 0, suc, + )  B = ( { |n | n" % },  , sucB, addB ) Bierfilzalgebra  sucB ( |n) = |n+1 , addB ( |n , |m ) = |n+m  h : NAT  B Homomorphismus mit  h(n) = |n (n & 1) , h(0) = 

 STRING = ( A, A*, , makeSTR , concatSTR )  STRINGalphabet = A (1.Trägermenge)  STRINGstring = A* (2.Trägermenge)  emptySTR =  " A* (empty: $ string)  makeSTR( a ) = a (make: alph $ string)  concatSTR( u, v ) = u v (concat: string2 $ string)

 Homomorphismus – Eigenschaften :  h(zNAT ) = h(0) =  = zB  h(suc(n)) = h(n+1) = |n+1 = sucB( |n) = sucB(h(n))  h(n+m) = |n+m = addB( | n, | m) = addB(h(n), h(m))  h : NAT  B bijektiv Ehrig

6. VL TheGI1

 SET = ( A, (A), ' , makeSET , concatSET )  makeSET( a ) = { a } ( a "A )  concatSET ( B, C ) = B ( C ( B, C " ) (A) ) 5

Ehrig

6. VL TheGI1

6

Beispiel : !-string Homomorphismus

Komposition von Homomorphismen

 h : STRING  SET

h:AB, g:B C Homomorphismen  Komposition gh : A  C def. durch  ( gh )s = gshs ( s " S )  Satz :  Komposition gh : A  C ist Homomorphismus  Beweis :  ( gh )s (cA) = gs( hs (cA) ) = gs(cB) = cC  ( gh)s ( fA(a1,...,an) ) = ... = fC( (gh)s1(a1), ... , (gh)sn(an) )

halph = idA : A  A  hstr : A*  (A) , a1...an * { a1, ... ,an } 

hstr( emptySTR ) = hstr () = ' = emptySET  hstr( makeSTR(a)) = hstr(a) = {a} = makeSET( halph(a))  hstr( concatSTR(u,v) ) = hstr(uv) = {a1,..,an,b1,..,bm} =concatSET( hstr(u), hstr(v) )  Bemerkung : 



Existiert kein Homom. g : SET  STRING

Ehrig

6. VL TheGI1

7

Ehrig

6. VL TheGI1

8

Beispiel : Komposition

Was ist ein Isomorphismus ?

 h : NAT  B

 h : A  B Isomorphismus , falls  h : A  B Homomorphismus und  - g : B  A Homomorphismus mit  gh = idA und hg = idB



g : B  NAT :

und

( n & 1 ) , g () = 0

g ( |n ) = n

 idNAT : NAT  NAT , 

idB : B  B

Satz :

Identitäten auf NAT bzw. B

 gh = idNAT und

hg = idB , denn

gh ( n ) = g ( |n ) = n  hg ( |n ) = h ( n ) = |n 

 + h : NAT  B 



h:AB

Isomorphismus



h:AB

bijektiver

Homomorphismus

 Beweis : 

Isomorphismus

h Isom 



geschr. NAT, B Ehrig

.

hsgs = idBs

(# s" S )

h bijektiver Hom. + 

6. VL TheGI1

+ gshs = id As ,

+ hs bijektiv

gs = hs-1 : Bs  As (# s" S ) Zu zeigen : g = (gs)s" S : B  A Homomorphismus

9

Ehrig

6. VL TheGI1

Bildalgebra

Übertragung von Konzepten

 h : A  B Homomorphismus , ! = ( S, OP )

 Menge

h(A)

Bildalgebra

h ( A )s = hs ( As ) /  fh(A) = fB /h(A) 

def. durch

Bs

(# s" S )

(# f : w$ s " OP )

 Satz : 

Bildalgebra h ( A ) / B ist Unteralgebra

 Beispiel :

h : NAT  INT Inklusion  h ( NAT ) = NAT / INT 

Ehrig

6. VL TheGI1

11

10

+ Algebra  Abbildung + Homomorphismus  Untermenge + Unteralgebra  Äquivalenzrelation + Kongruenzrelation  Quotientenmenge + Quotientenalgebra  Abbildungssatz + von Abbildungen auf Homomorphismen  Kategorie + von Mengen auf !-Algebren Ehrig

6. VL TheGI1

12

Abbildungssatz für Homomorphismen

Beispiel : Abbildungssatz

 Für jeden Homomorph. h : A  B existiert

 h : NAT  INT/mod2 , h(n) = [n]mod2

 Zerlegung h = me mit 

 Kern(h) = mod2 Kongruenzrelation auf NAT

surj. e : A  C und inj. Homom. m : C  B

 h(NAT) = NAT/mod2 = NAT/Kern(h)

 Eindeutigkeit der Zerlegung bis auf Isomorphie :  Für h = me = m‘e‘ mit surj. e,e‘, inj. m,m‘ existiert 

Isom. g : C  C‘ mit ge = e‘ und m‘g = m f

A

e e'

Ehrig

C 0g C‘

m = id h(NAT) (inj.,bij.)

h

NAT

B

m

 h = e = nat (surj.) ,

e

INT/mod2 m

h(NAT) = NAT/mod2 m‘

6. VL TheGI1

13

Ehrig

6. VL TheGI1

Kategorie Alg(!) von Algebren

Zusammenfassung

 Objekte von Alg(!) : !- Algebren A, B  Morphismen von Alg(!) : Homom. h : A  B  Komposition von Homom. und Identitäten  Kategorienaxiome erfüllt :  Assoziativität : (hg)f = h(gf)  Neutralität : hidA = h = idBh  Bemerkung :  h Monomorphismus . h inj. Homom.  h Epimorphismus . h surj. Homom.  h Isomorphismus . h bij. Homom.

 Homomorphismus h : A  B ist  Strukturverträgliche Abbildung zwischen Algebren bzw. Datenstrukturen  Isomorphismus h : A  B ( A , B ) ist  Strukturäquivalenz von Algebren bzw. Datenstrukturen  Übertragung von Konzepten der Kategorie Set auf die Kategorie Alg(!) :  Kongruenzrelation und Quotientenalgebra  Abbildungs – und Faktorisierungssatz

Ehrig

6. VL TheGI1

15

Ehrig

6. VL TheGI1

14

16