Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Ein neutrales Element ${\displaystyle {}e\in M}$ zu einer Verknüpfung

   ${\displaystyle \circ \colon M\times M\longrightarrow M,\,(x,y)\longmapsto x\circ y.}$

2. Die Symmetrie einer Relation ${\displaystyle {}R}$ auf einer Menge ${\displaystyle {}M}$.
3. Geordnete Menge/Teilmenge/Untere Schranke/Definition/Begriff
4. Ungerichteter Graph/Pfad/Definition/Begriff
5. Ungerichteter Graph/Zyklus/Definition/Begriff
6. Ungerichter Graph/Paarungszahl/Definition/Begriff

Formuliere die folgenden Sätze.

1. Der Satz über die Wohldefiniertheit der Anzahl.
2. Das allgemeine Distributivgesetz für einen kommutativen Halbring.
3. Der Satz von Kirchhoff über die Anzahl der Spannbäume.

Es sei ${\displaystyle {}a\in \mathbb {N} _{+}}$. Zeige, wie man ${\displaystyle {}a^{10}}$ mit vier Multiplikationen berechnen kann.

Sei

${\displaystyle {}b:=a\cdot a=a^{2}\,}$

und

${\displaystyle {}c:=b\cdot b=b^{2}=a^{4}\,.}$

Dann ist

${\displaystyle {}a^{10}=(c\cdot c)\cdot b\,}$

eine Berechnung mit vier Multiplikationen.

Gabi Hochster möchte sich die Fingernägel ihrer linken Hand (ohne den Daumennagel) lackieren, wobei die drei Farben ${\displaystyle {}B,G,R}$ zur Verfügung stehen. Sie möchte nicht, dass zwei benachbarte Finger die gleiche Farbe bekommen. Wie viele Möglichkeiten gibt es?

Sie beginnt mit dem Zeigefinger, dafür hat sie drei Möglichkeiten. Für den Mittelfinger hat sie zwei Möglichkeiten, da die Farbe des Zeigefingers ausgeschlossen ist. Für den Ringfinger hat sie wieder zwei Möglichkeiten, da die Farbe des Mittelfingers ausgeschlossen ist. Für die Farbe des kleinen Fingers hat sie wieder zwei Möglichkeiten, da die Farbe des Ringfingers ausgeschlossen ist. Insgesamt gibt es also

${\displaystyle {}3\cdot 2\cdot 2\cdot 2=24\,}$

Möglichkeiten.

Zeige, dass die Binomialkoeffizienten die rekursive Beziehung

${\displaystyle {}{\binom {n+1}{k}}={\binom {n}{k}}+{\binom {n}{k-1}}\,}$

erfüllen.

Es ist

${\displaystyle {}{\begin{aligned}{\binom {n}{k}}+{\binom {n}{k-1}}&={\frac {n!}{(n-k)!k!}}+{\frac {n!}{(n-(k-1))!(k-1)!}}\\&={\frac {n!}{(n-k)!k!}}+{\frac {n!}{(n+1-k)!(k-1)!}}\\&={\frac {(n+1-k)\cdot n!}{(n+1-k)!k!}}+{\frac {k\cdot n!}{(n+1-k)!k!}}\\&={\frac {(n+1-k+k)\cdot n!}{(n+1-k)!k!}}\\&={\frac {(n+1)!}{(n+1-k)!k!}}\\&={\binom {n+1}{k}}.\end{aligned}}}$

Es sei ${\displaystyle {}G}$ eine zweielementige Menge. Erstelle eine Verknüpfungstabelle für die Verknüpfung „Vereinigung“ auf der Potenzmenge ${\displaystyle {}{\mathfrak {P}}\,(G)}$.

Die Menge sei ${\displaystyle {}M=\{a,b\}}$, die Potenzmenge ist dann

${\displaystyle {}{\mathfrak {P}}\,(M)=\{\emptyset ,\{a\},\{b\},\{a,b\}\}\,.}$

Die Verknüpfungstabelle für die Vereinigung ist

${\displaystyle {}\cup }$	${\displaystyle {}\emptyset }$	${\displaystyle {}\{a\}}$	${\displaystyle {}\{b\}}$	${\displaystyle {}\{a,b\}}$
${\displaystyle {}\emptyset }$	${\displaystyle {}\emptyset }$	${\displaystyle {}\{a\}}$	${\displaystyle {}\{b\}}$	${\displaystyle {}\{a,b\}}$
${\displaystyle {}\{a\}}$	${\displaystyle {}\{a\}}$	${\displaystyle {}\{a\}}$	${\displaystyle {}\{a,b\}}$	${\displaystyle {}\{a,b\}}$
${\displaystyle {}\{b\}}$	${\displaystyle {}\{b\}}$	${\displaystyle {}\{a,b\}}$	${\displaystyle {}\{b\}}$	${\displaystyle {}\{a,b\}}$
${\displaystyle {}\{a,b\}}$	${\displaystyle {}\{a,b\}}$	${\displaystyle {}\{a,b\}}$	${\displaystyle {}\{a,b\}}$	${\displaystyle {}\{a,b\}}$

Beweise das folgende Untergruppenkriterium. Eine nichtleere Teilmenge ${\displaystyle {}H\subseteq G}$ einer Gruppe ${\displaystyle {}G}$ ist genau dann eine Untergruppe, wenn gilt:

${\displaystyle {\text{ für alle }}g,h\in H{\text{ ist }}gh^{-1}\in H.}$

Zu ${\displaystyle {}n\in \mathbb {N} }$ sei

${\displaystyle {}[n]=\{0,1,2,\ldots ,n\}\,.}$

Zu jedem ${\displaystyle {}n\in \mathbb {N} }$ und jedem ${\displaystyle {}0\leq k\leq n}$ seien die Abbildungen

${\displaystyle D_{k}\colon [n]\longrightarrow [n+1]}$

durch

${\displaystyle {}D_{k}(j)={\begin{cases}j,{\text{ falls }}j<k,\\j+1{\text{ sonst}},\end{cases}}\,}$

und die Abbildungen

${\displaystyle S_{k}\colon [n+1]\longrightarrow [n]}$

durch

${\displaystyle {}S_{k}(j)={\begin{cases}j,{\text{ falls }}j\leq k,\\j-1{\text{ sonst}},\end{cases}}\,}$

definiert.

a) Erstelle eine Wertetabelle für

${\displaystyle D_{3}\colon [4]\longrightarrow [5].}$

b) Erstelle eine Wertetabelle für

${\displaystyle S_{3}\colon [6]\longrightarrow [5].}$

c) Beschreibe die durch die Wertetabelle

${\displaystyle {}j}$	${\displaystyle {}0}$	${\displaystyle {}1}$	${\displaystyle {}2}$	${\displaystyle {}3}$	${\displaystyle {}4}$	${\displaystyle {}5}$
${\displaystyle {}\varphi (j)}$	${\displaystyle {}0}$	${\displaystyle {}2}$	${\displaystyle {}2}$	${\displaystyle {}4}$	${\displaystyle {}5}$	${\displaystyle {}5}$

${\displaystyle \varphi \colon [5]\longrightarrow [5]}$

als eine Hintereinanderschaltung von geeigneten ${\displaystyle {}D_{k}}$ und ${\displaystyle {}S_{i}}$.

a)

${\displaystyle {}j}$	${\displaystyle {}0}$	${\displaystyle {}1}$	${\displaystyle {}2}$	${\displaystyle {}3}$	${\displaystyle {}4}$
${\displaystyle {}D_{3}(j)}$	${\displaystyle {}0}$	${\displaystyle {}1}$	${\displaystyle {}2}$	${\displaystyle {}4}$	${\displaystyle {}5}$

b)

${\displaystyle {}j}$	${\displaystyle {}0}$	${\displaystyle {}1}$	${\displaystyle {}2}$	${\displaystyle {}3}$	${\displaystyle {}4}$	${\displaystyle {}5}$	${\displaystyle {}6}$
${\displaystyle {}S_{3}(j)}$	${\displaystyle {}0}$	${\displaystyle {}1}$	${\displaystyle {}2}$	${\displaystyle {}3}$	${\displaystyle {}3}$	${\displaystyle {}4}$	${\displaystyle {}5}$

c) Wir behaupten

${\displaystyle {}\varphi =D_{3}\circ D_{1}\circ S_{3}\circ S_{1}\,.}$

Die Komposition hat für die Elemente ${\displaystyle {}0,1,2,3,4,5}$ jeweils den folgenden Effekt:

${\displaystyle 0\mapsto 0\mapsto 0\mapsto 0\mapsto 0,}$

${\displaystyle 1\mapsto 1\mapsto 1\mapsto 2\mapsto 2,}$

${\displaystyle 2\mapsto 1\mapsto 1\mapsto 2\mapsto 2,}$

${\displaystyle 3\mapsto 2\mapsto 2\mapsto 3\mapsto 4,}$

${\displaystyle 4\mapsto 3\mapsto 3\mapsto 4\mapsto 5,}$

${\displaystyle 5\mapsto 4\mapsto 3\mapsto 4\mapsto 5.}$

Das Gesamtergebnis stimmt also mit ${\displaystyle {}\varphi }$ überein.

Beweise das Lemma von Bezout für teilerfremde natürliche Zahlen ${\displaystyle {}a}$ und ${\displaystyle {}b}$ durch Induktion über das Maximum von ${\displaystyle {}a}$ und ${\displaystyle {}b}$.

Wir beweisen die Aussage durch Induktion über das Maximum von ${\displaystyle {}a}$ und ${\displaystyle {}b}$, wobei wir ohne Einschränkung ${\displaystyle {}a\leq b}$ wählen können. Wenn das Maximum ${\displaystyle {}0}$ ist, so sind beide Zahlen ${\displaystyle {}0}$ und somit nicht teilerfremd. Wenn das Maximum ${\displaystyle {}1}$ ist, so ist ${\displaystyle {}b=1}$ und somit ergeben ${\displaystyle {}r=0}$ und ${\displaystyle {}s=1}$ eine Darstellung der ${\displaystyle {}1}$. Seien nun ${\displaystyle {}a\leq b}$ teilerfremd, ${\displaystyle {}b\geq 2}$ und die Aussage sei für alle Zahlenpaare, deren Maxima kleiner als ${\displaystyle {}b}$ sind, schon bewiesen. Dann ist ${\displaystyle {}a<b}$, da bei ${\displaystyle {}a=b}$ die beiden Zahlen nicht teilerfremd sind. Ebenso können wir ${\displaystyle {}a=0}$ ausschließen. Wir betrachten das Zahlenpaar ${\displaystyle {}(a,b-a)}$ und wollen darauf die Induktionsvoraussetzung anwenden. Das Maximum dieses neuen Paares ist jedenfalls kleiner als ${\displaystyle {}b}$. Allerdings müssen wir, damit die Induktionsvoraussetzung wirklich eingesetzt werden kann, wissen, dass auch ${\displaystyle {}a}$ und ${\displaystyle {}b-a}$ teilerfemd sind. Dazu führen wir einen Widerspruchsbeweis.  Nehmen wir also an, dass ${\displaystyle {}a}$ und ${\displaystyle {}b-a}$ nicht teilerfremd sind. Dann gibt es eine natürliche Zahl ${\displaystyle {}t\geq 2}$, die sowohl ${\displaystyle {}a}$ als auch ${\displaystyle {}b-a}$ teilt. Dies bedeutet wiederum, dass es natürliche Zahlen ${\displaystyle {}m,n}$ mit ${\displaystyle {}a=mt}$ und ${\displaystyle {}b-a=nt}$ gibt. Doch dann ist

${\displaystyle {}b=(b-a)+a=nt+mt=(n+m)t\,}$

ebenfalls ein Vielfaches von ${\displaystyle {}t}$, im Widerspruch zur Teilerfremdheit von ${\displaystyle {}a}$ und ${\displaystyle {}b}$.  Die Induktionsvoraussetzung ist also auf ${\displaystyle {}a}$ und ${\displaystyle {}b-a}$ anwendbar und somit gibt es ganze Zahlen ${\displaystyle {}r,s}$ mit

${\displaystyle {}ra+s(b-a)=1\,.}$

Dann ist aber auch

${\displaystyle {}(r-s)a+sb=ra+s(b-a)=1\,}$

und wir haben eine Darstellung der ${\displaystyle {}1}$ mit ${\displaystyle {}a}$ und ${\displaystyle {}b}$ gefunden.

Es sei ${\displaystyle {}M}$ die Menge der zweimal stetig differenzierbaren Funktionen von ${\displaystyle {}\mathbb {R} }$ nach ${\displaystyle {}\mathbb {R} }$. Definiere auf ${\displaystyle {}M}$ eine Relation durch

${\displaystyle f\sim g{\text{ falls }}f(0)=g(0),\,f'(0)=g'(0){\text{ und }}f^{\prime \prime }(1)=g^{\prime \prime }(1).}$

a) Zeige, dass dies eine Äquivalenzrelation ist.

b) Finde für jede Äquivalenzklasse dieser Äquivalenzrelation einen polynomialen Vertreter.

c) Zeige, dass diese Äquivalenzrelation mit der Addition von Funktionen verträglich ist.

d) Zeige, dass diese Äquivalenzrelation nicht mit der Multiplikation von Funktionen verträglich ist.

a) Wir betrachten die Abbildung

${\displaystyle H\colon M\longrightarrow \mathbb {R} ^{3},\,f\longmapsto (f(0),f'(0),f^{\prime \prime }(1)).}$

Zwei Funktionen ${\displaystyle {}f}$ und ${\displaystyle {}g}$ stehen genau dann in dieser Relation zueinander, wenn ihre Bilder unter ${\displaystyle {}H}$ übereinstimmen. Daher liegt eine Äquivalenzrelation vor (und ${\displaystyle {}H}$ beschreibt die Äquivalenzklassenbildung).

b) Das Polynom

${\displaystyle a+bx+{\frac {c}{2}}x^{2}}$

wird unter ${\displaystyle {}H}$ auf ${\displaystyle {}(a,b,c)}$ abgebildet, so dass dieses Polynom diese Klasse repräsentiert.

c) Es sei ${\displaystyle {}f_{1}\sim g_{1}}$ und ${\displaystyle {}f_{2}\sim g_{2}}$. Es ist ${\displaystyle {}(f_{1}+f_{2})\sim (g_{1}+g_{2})}$ zu zeigen. Dies folgt aber sofort aufgrund der Additivität der Ableitung.

d) Wir betrachten ${\displaystyle {}f_{1}=g_{1}=x}$ und ${\displaystyle {}f_{2}=x}$ und ${\displaystyle {}g_{2}=x^{3}-3x^{2}+x}$. Offenbar ist ${\displaystyle {}f_{1}\sim g_{1}}$. Die relevanten Werte für ${\displaystyle {}f_{2}}$ sind wegen ${\displaystyle {}f_{2}=x,\,f_{2}'=1,\,f_{2}^{\prime \prime }=0}$ einfach

${\displaystyle H(f_{2})=(0,1,0).}$

Für ${\displaystyle {}g_{2}}$ ergibt sich ${\displaystyle {}g_{2}=x^{3}-3x^{2}+x,\,g_{2}'=3x^{2}-6x+1,\,g_{2}^{\prime \prime }=6x-6}$. Daher ist

${\displaystyle H(g_{2})=(0,1,0),}$

so dass ${\displaystyle {}f_{2}\sim g_{2}}$ ist. Wir behaupten, dass ${\displaystyle {}f_{1}f_{2}}$ und ${\displaystyle {}g_{1}g_{2}}$ nicht äquivalent sind. Es ist ${\displaystyle {}f_{1}f_{2}=x^{2}}$ mit den Ableitungen ${\displaystyle {}(x^{2},2x,2)}$ und daher ist

${\displaystyle H(f_{1}f_{2})=(0,0,2).}$

Für ${\displaystyle {}g_{1}g_{2}=x(x^{3}-3x^{2}+x)=x^{4}-3x^{3}+x^{2}}$ hat man die Ableitungen ${\displaystyle {}(x^{4}-3x^{3}+x^{2},4x^{3}-9x^{2}+2x,12x^{2}-18x+2)}$ und daher ist

${\displaystyle H(g_{1}g_{2})=(0,0,-4)\neq H(f_{1}f_{2}).}$

Beweise den Charakterisierungssatz für Bäume.

Aus (1) folgt (2). Da ${\displaystyle {}G}$ nach Voraussetzung zusammenhängend ist, gibt es zu ${\displaystyle {}u,v}$ zumindest einen verbindenden Weg. Würde es zwei Wege geben, so könnte man daraus direkt einen Zyklus und dann auch einen Kreis konstruieren, was ausgeschlossen ist.

Aus (2) folgt (1). Die Zusammenhangseigenschaft ist klar. Würde es einen Kreis geben, so könnte man dies direkt als einen zweifachen Weg ohne Wiederholung zwischen zwei Punkten auffassen.

Aus (1) folgt (3). Wir führen Induktion über die Anzahl der Punkte von ${\displaystyle {}G}$. Bei einem einzigen Punkt gibt es keine Kante und die Gleichung stimmt. Sei also ${\displaystyle {}G}$ ein Baum mit ${\displaystyle {}n\geq 2}$ Punkten. Nach Fakt ***** besitzt ${\displaystyle {}G}$ ein Blatt und nach Fakt ***** ist ${\displaystyle {}G\setminus b}$ ebenfalls ein Baum. Dabei wird ein Punkt und eine Kante herausgenommen. Nach Induktionsvoraussetzung gilt die Gleichung für den verkleinerten Baum, also gilt sie auch für ${\displaystyle {}G}$.

Von (3) nach (1). Wir führen wieder Induktion über die Knotenanzahl, bei einem Knoten ist alles klar. Aufgrund der Voraussetzung und Fakt ***** gilt

${\displaystyle {}\sum _{v\in V}d(v)=2\cdot {\left({\#\left(V\right)}-1\right)}=2{\#\left(V\right)}-2\,.}$

Wegen der Zusammenhangseigenschaft sind die Grade zumindest ${\displaystyle {}1}$. Deshalb muss es (zumindest ${\displaystyle {}2}$) Punkte mit Grad ${\displaystyle {}1}$, also Blätter geben. Sei ${\displaystyle {}b}$ ein Blatt. Die Formel gilt dann auch für ${\displaystyle {}G\setminus b}$. Nach Induktionsvoraussetzung ist ${\displaystyle {}G\setminus b}$ ein Baum, und daher ist nach Fakt ***** auch ${\displaystyle {}G}$ ein Baum.