TU Wien:Mathematik 1 VO (Panholzer)/Stoff WS05/21. VO 28.11.2005

Beispiel für algebraische Strukturen

• M beliebige Menge

$F_{M}=\{f:M\rightarrow M\}$

$F_{M}$ ist Menge der Abbildungen von M in M

Def.: $\circ :F_{M}\times F_{M}\rightarrow F_{M}$

folgendermaßen: f,g \in F_M

$g\circ f$ eine Abbildung

$(g\circ f)(x):=g(f(x)),\forall x\in M$

$\langle F_{M},\circ \rangle$ ist algebraische Struktur

$\circ$ ist assoziativ

$h\circ (g\circ f)=(h\circ g)\circ f$

$h\circ (g\circ f))(x)=h((g\circ f)(x))$

$h(g(f(x))),\forall x\in M$

$((h\circ g)\circ f)(x)=(\circ g)(f(x))=h(g(f(x))),\forall x\in M$

d.h. $\langle F_{M},\circ \rangle$ ist eine Halbgruppe

die sog. "symmerische Halbgruppe"' von M

$\circ$ ist die "Hintereinanderausführung von Abbildungen" (= Komposition von Abbildungen)

Beispiel: A ist endl. Menge (sog. Alphabet)

$A^{*}$ ... Menge aller endlichen Wörter mit Buchstaben aus A (also über dem Alphabet A) zusammen mit dem Leerwort $\lambda$ (manchmal auch $\epsilon$ genannt)

endliche Wörter, d.h.

$x_{1},x_{2},...,x_{m}$ mir $x_{i}\in A\qquad 1\leq i\leq n$

Schreibweise $x_{1}x_{2}..x_{m}$ ... Wort der Länge M

$\circ$ .... "Aneinanderketten" von Wörtern (concantenation)

d.h.: $w_{1},w_{2}\in A^{*}$

• $w_{1}=x_{1}x_{2}...x_{m}$
• $w_{2}=y_{1}y_{2}...y_{m}$

$w_{1}\circ w_{2}=x_{1}x_{2}...x_{m}y_{1}y_{2}...y_{n}$

Bedeutung von $\lambda$

es gilt: $w\circ \lambda =\lambda \circ w=w$

d.h. $\lambda$ ist das neutrale Element bez. Operation $\circ$

$\Rightarrow \langle A^{*},\circ ,\lambda \langle$ ... ist ein Monoid

$\circ$ ist assoziativ: $w_{1}\circ (w_{2}\circ w_{3})=(w_{1}\circ w_{2})\circ w_{3}$

genannt freies Monoid

Bsp.: M = {1,-1,i,-i}

$a\circ b=a*b$ wobei * übliche Multplikation in $\mathbb {C}$

  0   1   -1   i   -i
  1   1   -1   i   -i
  -1  -1  1    -i  i
  i   i   -i   -1  1
  -i  -i  i    1   -1

Op. * ist assoziativ und kommutativ

neutrales Element: 1

jedes Element besitzt ein inverses Element (ist nachzuprüfen)

$\langle M,\circ \rangle$ ist eine kommutative (abelsche) Gruppe

M ist beliebige Menge

$S_{M}:=\{f:M\rightarrow M,f{\text{ bijektiv }}\}$

$\circ$ .... Hintereinanderausführung von Abbildungen (= Komposition)

$\Rightarrow \circ$ ist abgeschlossen in $S_{M}$, da: f.g bijektiv $\Rightarrow g\circ f$ bijektiv

$\circ$ ist Oper. in $S_{M}$

$\circ$ ist assoziativ

id: id(x) = x, $\forall x\in M$

ist ident Abb. auf M

id ist neutrales Element bez. $\circ$

$(f\circ id)(x)=((id(x))=f(x)=(id\circ f)(x)$

$f\in S_{M}$ bel. $\Rightarrow f^{-1}\in S_{M}$

($f^{-1})$ ist die Umkehrabb., inverse Abb.)

$\Rightarrow \langle S_{M},\circ \rangle$ ... ist eine Gruppe

sog. symmetrische Gruppe in M

sei M endlich

Annahme: M = {1,2, ..., n}

bez. S_n ... Symmetrische Gruppe auf {1,...,n}

$\pi \in S_{n}$, d.h.

  1   2   3  ...   n-1   m
  $\pi (1)$ $\pi (2)$ $\pi (3)$ .... $\pi (n-1)<math>\pi (n)$</math>

$\pi$ ... Permutation der Elemente {1,...,n}

Sei pi: $\in S_{6}$

  1  2  3  4  5  6
  4  2  5  1  6  3

Sei rho: $\in S_{6}$

  1  2  3  4  5  6
  2  4  3  6  1  5

$\pi \circ \rho =$

   1  2  3  4  5  6
   2  1  5  3  4  6

$\rho \circ \pi =$

   1  2  3  4  5  6
   6  4  1  2  5  3

$\Rightarrow \rho \circ \pi \neq \pi \circ \rho$

$\Rightarrow \circ$ ist nicht kommutativ

Zyklendarstellung von Permutationen.

(Graph Mitschrift)

Notation: Zyklen geklammert anschreiben (bez. auf o.g. Graphen

$\pi =(14)(356)(2)$

Soll heien $\pi (3)=5,\pi (5)=6,\pi (6)=3$ usw.

Manchmal werden Fixpunkte nicht extra angegeben => o.g. Notation entspr. auch

$\pi =(14)(356)$

$\rho =(12465)(3)=(12465)$ ... Zyklus der Länge 5

$\pi \in S_{n}$ ist ein Zyklus der Länge n, falls $\pi (a_{1})=a_{2},\pi (a_{2})=a_{3},...,\pi (a_{m-1}=a_{m},\pi (a_{m})=a_{1}...$

für paarweise versch, Elemente $a_{1},...,a_{m}\in$ {1,...,n}

und $\pi (b)=b\qquad \forall b\neq \{a_{1},...,a_{m}\}$

$(a_{1},a_{2},...,a_{m-1},a_{m}$ ... Zyklus der Länge m