Kurs:Diskrete Mathematik (Osnabrück 2020)/Arbeitsblatt 4

Die Pausenaufgabe

Aufgabe

Zeige, dass in Beispiel 4.12 das Distributivgesetz nicht gilt, wenn man die Rollen von Addition und Multiplikation vertauscht.

Übungsaufgaben

Aufgabe

Betrachte die ganzen Zahlen $\mathbb{Z}$ mit dem Betrag der Differenz als Verknüpfung, also die Abbildung

$\mathbb{Z}\times \mathbb{Z}⟶\mathbb{Z},(a,b)⟼|a-b|.$

Besitzt diese Verknüpfung ein neutrales Element? Ist diese Verknüpfung assoziativ, kommutativ, gibt es zu jedem Element ein inverses Element?

Aufgabe

Zeige, dass die Verknüpfung auf einer Geraden, die zwei Punkten ihren Mittelpunkt zuordnet, kommutativ, aber nicht assoziativ ist. Gibt es ein neutrales Element?

Aufgabe *

Wir betrachten auf der Menge

$M=\{a,b,c,d\}$

die durch die Tabelle

$\star$	$a$	$b$	$c$	$d$
$a$	$b$	$a$	$c$	$a$
$b$	$d$	$a$	$b$	$b$
$c$	$a$	$b$	$c$	$c$
$d$	$b$	$d$	$d$	$d$

gegebene Verknüpfung $\star$.

1. Berechne

   $b\star (a\star (d\star a)).$

2. Besitzt die Verknüpfung $\star$ ein neutrales Element?

Aufgabe *

Es sei $M$ eine $k$-elementige Menge. Wie viele Verknüpfungen gibt es auf $M$?

Aufgabe *

Wir betrachten den Binomialkoeffizienten als eine Verknüpfung

$\mathbb{N}\times \mathbb{N}⟶\mathbb{N},(n,k)⟼(\genfrac{}{}{0ex}{}{n}{k}),$

wobei bei  $k>n$  der Binomialkoeffizient als $0$ zu interpretieren ist. Diese Verknüpfung ist offenbar nicht kommutativ.

a) Bestimme $(\genfrac{}{}{0ex}{}{(\genfrac{}{}{0ex}{}{3}{2})}{1})$ und $(\genfrac{}{}{0ex}{}{3}{(\genfrac{}{}{0ex}{}{2}{1})})$.

b) Besitzt diese Verknüpfung ein neutrales Element von links?

c) Besitzt diese Verknüpfung ein neutrales Element von rechts?

d) Ist diese Verknüpfung assoziativ?

Aufgabe *

Es sei $M$ eine Menge. Wir betrachten die Verknüpfung

$𝔓(M)\times 𝔓(M)⟶𝔓(M),(A,B)⟼A\setminus B.$

Ist diese Verknüpfung assoziativ?

Aufgabe *

Es sei $M$ eine zweielementige Menge. Erstelle eine Verknüpfungstabelle für die Verknüpfung „Vereinigung“ auf der Potenzmenge $𝔓(M)$.

Aufgabe *

Es sei  $S=\{0,1\}$.  Betrachte das Monoid $M$, das aus allen Abbildungen von $S$ nach $S$ besteht mit der Hintereinanderschaltung $\circ$ von Abbildungen als Verknüpfung.

a) Beschreibe die Elemente in $M$ und erstelle eine Verknüpfungstabelle für $M$.

b) Bestimme sämtliche Untermonoide von $M$ und entscheide jeweils, ob sie kommutativ sind und ob es sich um Gruppen handelt.

Aufgabe

Es sei $M$ ein Monoid,  $a,b\in M$  und  $m,n\in \mathbb{N}$.  Zeige die folgenden Potenzgesetze.

1. $a^{m+n}=a^m\cdot a^n.$

2. $(a^m{)}^n=a^{mn}.$

3. Wenn $M$ kommutativ ist, so ist

   $(a\cdot b{)}^n=a^n\cdot b^n.$

Aufgabe *

Es sei $(M,\circ ,e)$ ein Monoid und  $x,y,a\in M$. 

a) Folgt aus  $x=y$  die Beziehung  $a\circ x=a\circ y$? 

b) Folgt aus  $a\circ x=a\circ y$  die Beziehung  $x=y$? 

Es seien $(G,\circ ,e_G)$ und $(H,\circ ,e_H)$ Monoide. Eine Abbildung

$\psi :G⟶H$

heißt Monoidhomomorphismus, wenn  $\psi (e_G)=e_H$  und die Gleichheit

$\psi (g\circ g^{\prime })=\psi (g)\circ \psi (g^{\prime })$

für alle  $g,g^{\prime }\in G$  gilt.

Aufgabe

Es sei $(M,\cdot ,1)$ ein Monoid und  $N=\mathrm{Abb}(M,M)$  das Monoid der Abbildungen von $M$ nach $M$. Zeige, dass durch

$M⟶\mathrm{Abb}(M,M),x⟼{\lambda }_x,$

mit  ${\lambda }_x(y):=x\cdot y$  ein injektiver Monoidhomomorphismus gegeben ist.

Kommentar:

Hier sollte man sich zunächst klar machen, worum es überhaupt geht. Man hat einerseits ein Monoid $M$ mit einer Verknüpfung $\cdot$ und einem neutralen Element. Andererseits hat man nach Beispiel 4.7 das Abbildungsmonoid ist  $N=\mathrm{Abb}(M,M)$,  mit der Hintereinanderschaltung von Abbildungen als Verknüpfung und der Identität ${\mathrm{Id}}_M$ auf $M$ als neutrales Element. Dies hängt nur von der Menge $M$, aber nicht von der Verknüpfung des Monoids ab.

Betrachten wir beispielsweise  $M=(\mathbb{N},+,0)$.  Das Abbildungsmonoid zu $\mathbb{N}$ besteht aus allen möglichen Abbildungen von $\mathbb{N}$ nach $\mathbb{N}$, das ist riesengroß und die allermeisten haben nichts mit der Addition auf den natürlichen Zahlen zu tun. Der Punkt der Aufgabe ist, dass dennoch jedes Element des Monoids eine Abbildung des Monoids in sich festlegt. Im Beispiel der natürlichen Zahlen mit der Addition legt etwa  $5\in \mathbb{N}$  die Abbildung

$\mathbb{N}⟶\mathbb{N},n⟼5+n$

fest. Man betrachtet also einfach die Wirkungsweise eines Elements auf alle anderen Elemente. Wenn man stattdessen $(\mathbb{N},\cdot ,1)$, also mit der Multiplikation, betrachtet, so ist die zugehörige Abbildung

$\mathbb{N}⟶\mathbb{N},n⟼5\cdot n.$

Es geht also immer um die Gesamtabbildung

$M⟶\mathrm{Abb}(M,M),x⟼(z\mapsto x\cdot z),$

einem jeden Element aus $M$ wird eine Abbildung zugeordnet, die die Verknüpfung mit diesem Element ist. Diese Abbildung nennen wir ${\lambda }_x$. Wenn man sich dies klar gemacht hat, ist der Nachweis einfach.

Zu zeigen sind also die folgenden Aussagen:

1. ${\lambda }_1={\mathrm{Id}}_M$,
2. ${\lambda }_{x\cdot y}={\lambda }_x\circ {\lambda }_y$ für alle $x,y\in M$,
3. für je zwei verschiedene Elemente $x,y\in M$ sind auch ${\lambda }_x$ und ${\lambda }_y$ verschieden.

Die 1. Aussage ist klar. Die 2. Aussage ergibt sich aus

${\lambda }_{x\cdot y}(z)=(x\cdot y)\cdot z=x\cdot (y\cdot z)=x\cdot {\lambda }_y(z)={\lambda }_x({\lambda }_y(z))={\lambda }_x\circ {\lambda }_y(z)$

für alle $z\in M$. Für die letzte Aussage beachtet man, dass

${\lambda }_x(1)=x\ne y={\lambda }_y(1),$

also ${\lambda }_x\ne {\lambda }_y$.

Die Gesamtaussage bedeutet, dass jedes Monoid ein Untermonoid eines Abbildungsmonoides ist. In einem gewissen Sinne gilt deshalb: Wenn man die Abbildungsmonoide versteht, so versteht man alle Monoide.

 

Aufgabe *

Es seien $(M,\ast )$ und $(N,\circ )$ Mengen mit Verknüpfungen und es sei

$\phi :M⟶N$

eine mit den Verknüpfungen verträgliche surjektive Abbildung, es gelte also

$\phi (x\ast y)=\phi (x)\circ \phi (y).$

Die Verknüpfung auf $M$ sei assoziativ. Zeige, dass auch die Verknüpfung auf $N$ assoziativ ist.

Aufgabe

Es seien  $a,b\in R$  Elemente in einem kommutativen Halbring $R$. Berechne

$(a+b)\cdot (a+2b)\cdot (a+3b).$

Aufgabe

Es seien  $a,b,c,d\in R$  Elemente in einem kommutativen Halbring $R$. Berechne

$(ab+2d)\cdot (a^2+4bc)\cdot (3bd+ac).$

Aufgabe

Es seien  $a,b,c\in R$  Elemente in einem kommutativen Halbring $R$. Berechne

$(a+b+c{)}^2.$

Aufgabe

Berechne

$(2+4+3)\cdot (4+5+1+2)$

mit und ohne Distributivgesetz.

Aufgabe

Es sei $R$ ein kommutativer Halbring und $f,a_i,b_j\in R$. Zeige die folgenden Gleichungen:

$\sum _{i=0}^n{a}_i{f}^i+\sum _{j=0}^m{b}_j{f}^j=\sum _{k=0}^{max(n,m)}(a_k+b_k)f^k$

und

$\left(\sum _{i=0}^n{a}_i{f}^i\right)\cdot \left(\sum _{j=0}^m{b}_j{f}^j\right)=\sum _{k=0}^{n+m}{c}_k{f}^k\text{ mit }{c}_k=\sum _{r=0}^k{a}_r{b}_{k-r}.$

Bei einer Summe oder einem Produkt von mehreren Zahlen (oder Elementen eines kommutativen Halbringes) ist es nicht immer sinnvoll, eine feste Reihenfolge der Indexmenge zu haben. Häufig ist es besser, die Reihenfolge zu wechseln und oft gibt es gar keine natürliche Reihenfolge. Man muss sich zuerst klar machen, dass die Summe nicht von der Reihenfolge abhängt. Die Argumente sind ähnlich wie im Beweis zu Lemma 1.2.

Aufgabe

Es sei $R$ ein kommutativer Halbring, $I$ eine endliche Menge und seien $a_i$, $i\in I$, Elemente aus $R$. Man definiert die Summe $\sum _{i\in I}{a}_i$, indem man eine Nummerierung (eine Bijektion)

$\phi :\{1,\dots ,n\}⟶I$

fixiert und

$\sum _{i\in I}{a}_i:=\sum _{k=1}^n{a}_{\phi (k)}$

setzt.

1. Zeige, dass diese Summe unabhängig von der gewählten Nummerierung ist.
2. Zeige

   $\sum _{i\in I}{a}_i=\left(\sum _{i\in I\setminus \{j\}}{a}_i\right)+a_j$

   für ein beliebiges $j\in I$.

3. Es sei

   $I=I_1\cup I_2$

   eine disjunkte Vereinigung. Zeige

   $\sum _{i\in I}{a}_i=\left(\sum _{i\in I_1}{a}_i\right)+\left(\sum _{i\in I_2}{a}_i\right).$

4. Formuliere die entsprechenden Gesetze für das Produkt $\prod _{i\in I}{a}_i$.

Kommentar:

1. Die Definition der Summe $\sum _{i\in I}{a}_i$ bedeutet: für eine gewählte Nummerierung $\phi$ von $I$ ist $\sum _{i\in I}{a}_i$ das Ergebnis der folgenden endlich viele Summen

$(\cdots ((a_{\phi (1)}+a_{\phi (2)})+a_{\phi (3)})+\cdots +a_{\phi (n-1)})+a_{\phi (n)},$

also das letzte Element der folgenden Folge

$\begin{array}{cc}& a_{\phi (1)}+a_{\phi (2)},(a_{\phi (1)}+a_{\phi (2)})+a_{\phi (3)},((a_{\phi (1)}+a_{\phi (2)})+a_{\phi (3)})+a_{\phi (4)},\dots ,\\ & (\cdots ((a_{\phi (1)}+a_{\phi (2)})+a_{\phi (3)})+\cdots +a_{\phi (n-1)})+a_{\phi (n)}.\end{array}$

Da die Addition auf $R$ kommutativ ist, soll es "klar" sein, dass diese Definition nicht von der Nummerierung von $I$ abhängig ist. Für einen strengen Beweis muss mann aber zeigen, dass

$\sum _{k=1}^n{a}_{\phi (k)}=\sum _{k=1}^n{a}_{\psi (k)}$

für jede andere Nummerierung $\psi$ von $I$, also eine beliebige Bijektion

$\psi :\{1,\dots ,n\}⟶I.$

Dies kann man eine Induktion nach $n$ durchführen. Die Behauptung ist klar für $n\le 2$. Sei $l\in \{1,\dots ,n\}$ mit $\psi (l)=\phi (n)$. Es ist dann zu zeigen

$\sum _{k=1}^{n-1}{a}_{\phi (k)}=\sum _{k=1}^{l-1}{a}_{\psi (k)}+\sum _{k=l+1}^n{a}_{\psi (k)},$

da die Addition kommutativ ist. Im Beweis zu Lemma 1.2 sieht man schon, dass die Abbildung

$\lambda :\{1,\dots ,n-1\}⟶\{1,\dots ,n\}\setminus \{l\}$

gegeben durch

$\lambda (k)=\{\begin{array}{cc}k& \text{falls }1\le k\le l-1,\\ k+1& \text{falls }l\le k\le n-1\end{array}$

eine Bijektion ist. Nun sind sowohl $\phi$ als auch $\psi \circ \lambda$ Bijektionen von $\{1,\dots ,n-1\}$ auf $I\setminus \{\phi (n)\}$, und man kann die Induktionsvoraussetzung verwenden.

2. Die Behauptung ist "klar", da die Addition kommutativ ist. Für einen Beweis sollte man geeignete Nummerierungen $\phi$ von $I$ und ${\phi }^{\prime }$ von $I\setminus \{j\}$ wählen. Da wir $\sum _{i\in I}{a}_i$ und $\sum _{i\in I\setminus \{j\}}{a}_i$ vergleichen wollen, sollte ${\phi }^{\prime }$ die Einschränkung von $\phi$ sein. Dies ist aber einfach zu erreichen: man wählt zuerst eine beliebige Nummerierung ${\phi }^{\prime }$ von $I\setminus \{j\}$ und dann erweitert ${\phi }^{\prime }$ auf eine Nummerierung $\phi$ von $I$, indem man $\phi (n)=j$ setzt. Dann gilt

$\sum _{i\in I}{a}_i=\sum _{k=1}^n{a}_{\phi (k)}=\sum _{k=1}^{n-1}{a}_{\phi (k)}+a_{\phi (n)}=\sum _{k=1}^{n-1}{a}_{{\phi }^{\prime }(k)}+a_{\phi (n)}=\sum _{i\in I\setminus \{j\}}{a}_i+a_j.$

3. Gegenben Nummerierungen ${\phi }_1$ von $I_1$ und ${\phi }_2$ von $I_2$, wie konstruiert man eine geeignete Nummerierung $\phi$ von $I$? Welches Ergebnis der Vorlesung kann man hier verwenden?

 

Aufgabe *

Beweise die folgende Form des allgemeinen Distributivgesetzes für einen kommutativen Halbring $R$ durch Induktion über $k$, wobei der Fall  $k=2$  verwendet werden darf (dabei sind $n_1,\dots ,n_k$ natürliche Zahlen und $a_{j,i}\in R$).

$\begin{array}{cc}\left(\sum _{i_1=1}^{n_1}{a}_{1,i_1}\right)\cdot \left(\sum _{i_2=1}^{n_2}{a}_{2,i_2}\right)\cdots \left(\sum _{i_k=1}^{n_k}{a}_{k,i_k}\right)& =\sum _{(i_1,i_2,\dots ,i_k)\in \{1,\dots ,n_1\}\times \{1,\dots ,n_2\}\times \cdots \times \{1,\dots ,n_k\}}{a}_{1,i_1}\cdot a_{2,i_2}\cdots a_{k,i_k}.\end{array}$

Aufgabe

Es sei $R$ ein kommutativer Halbring. Zeige, dass

$0\cdot (1+1+\cdots +1)=0$

ist (mit einer beliebig langen Summe von Einsen).

Aufgabe

Es sei $R$ ein kommutativer Halbring,  $a,b\in R$  und  $m,n\in \mathbb{N}$.  Zeige, dass die folgenden Potenzgesetze gelten.

1. $a^{m+n}=a^m\cdot a^n.$

2. $(a^m{)}^n=a^{mn}.$

3. $(a\cdot b{)}^n=a^n\cdot b^n.$

Aufgabe

Zeige, dass  ${\mathbb{N}}^2=\mathbb{N}\times \mathbb{N}$  mit der komponentenweisen Addition und der komponentenweisen Multiplikation ein kommutativer Halbring ist. Gilt in diesem Halbring die Eigenschaft, dass aus  $xy=0$  folgt, dass $x$ oder $y$ gleich $0$ ist?

Kommentar:

1. Die Eigenschaften der Addition und Multiplikation auf ${\mathbb{N}}^2$ ergeben sich aus den entsprechenden Eigenschaften der Addition und Multiplikation auf $\mathbb{N}$. Zum Beispiel gilt das Distributivgesetz, da

$\begin{array}{cc}(a_1,a_2)\cdot ((b_1,b_2)+(c_1,c_2))& =(a_1,a_2)\cdot (b_1+c_1,b_2+c_2)=(a_1\cdot (b_1+c_1),a_2\cdot (b_2+c_2))\\ & =(a_1\cdot b_1+a_1\cdot c_1,a_2\cdot b_2+a_2\cdot c_2)=(a_1\cdot b_1,a_2\cdot b_2)+(a_1\cdot c_1,a_2\cdot c_2)\\ & =(a_1,a_2)\cdot (b_1,b_2)+(a_1,a_2)\cdot (c_1,c_2).\end{array}$

2. Man überlegt sich, was sind die neutralen Elemente der Addition und Multiplikation auf ${\mathbb{N}}^2$? Was ist nun das Ergebnis der Multiplikation $(0,1)\cdot (1,0)$?

 

Für die folgenden Aufgaben ist die allgemeine binomische Formel hilfreich.

Aufgabe *

Beweise durch Induktion, dass für  $n\ge 10$  die Abschätzung

$3^n\ge n^4$

gilt.

Aufgabe *

Zeige, dass für  $n\ge 3$  die Abschätzung

$n^{n+1}\ge (n+1{)}^n$

gilt.

Aufgaben zum Abgeben

Aufgabe (4 (2+2) Punkte)

Es sei $M$ eine Menge mit einer Verknüpfung darauf, die wir als Produkt schreiben.

1. Wie viele sinnvolle Klammerungen gibt es für die Verknüpfung von vier Elementen?
2. Die Verknüpfung sei nun assoziativ. Zeige, dass das Produkt von vier Elementen nicht von irgendeiner Klammerung abhängt.

Aufgabe (4 Punkte)

Es sei  $S=\{1,2,3\}$.  Man schreibe ein Computerprogramm, das die Menge $M$ aller Abbildungen von $S$ nach $S$ auflistet und eine Verknüpfungstabelle für $M$ ausgibt.

Aufgabe (3 Punkte)

Wir betrachten die natürlichen Zahlen $\mathbb{N}$ mit den beiden Verknüpfungen Addition und Potenzierung und den ausgezeichneten Elementen $0$ und $1$. Welche Eigenschaften eines kommutativen Halbringes erfüllt diese Struktur, welche nicht?

Aufgabe (2 Punkte)

Es seien $a,b,c\in R$ Elemente in einem kommutativen Halbring $R$. Berechne

$(2ac+b^2)\cdot (a+5bc)\cdot (2a+3bc).$

Aufgabe (4 (2+2) Punkte)

Es seien  $a,b\in R$  Elemente in einem kommutativen Halbring $R$. Zeige die binomische Formel für die vierte Potenz, also

$(a+b{)}^4=a^4+4a^{3}b+6a^2{b}^2+4a{b}^3+b^4,$

auf die beiden folgenden Arten.

1. Berechne

   $(a+b)\cdot {(a+b)}^3.$

2. Berechne

   ${(a+b)}^2\cdot {(a+b)}^2.$