Kurs:Mathematik (Osnabrück 2009-2011)/Teil I/Arbeitsblatt 4

Aufwärmaufgaben

Aufgabe

Es sei ${}S$ eine Menge und

${}M=\operatorname {Abb} \,{\left(S,S\right)}\,$

sei versehen mit der Hintereinanderschaltung von Abbildungen als Verknüpfung. Ist die Verknüpfung assoziativ, kommutativ, gibt es ein (eindeutiges) neutrales Element, für welche ${}F\in M$ gibt es ein inverses Element?

Aufgabe

Es sei ${}M$ die Menge der Abbildungen einer zweielementigen Menge in sich selbst, also

${}M={\left\{F:\{0,1\}\rightarrow \{0,1\}\mid F{\text{ Abbildung}}\right\}}\,.$

Benenne die Elemente aus ${}M$ und lege eine Wertetabelle für die Verknüpfung auf ${}M$ an, die durch die Hintereinanderschaltung von Abbildungen definiert ist.

Aufgabe *

Zeige, das zwei Mengen ${}\mathbb {N} _{1}$ und ${}\mathbb {N} _{2}$, die beide die Dedekind-Peano-Axiome erfüllen, zueinander isomorph sind. Man gebe also eine bijektive Abbildung ${}\mathbb {N} _{1}\rightarrow \mathbb {N} _{2}$ an, die ${}0_{1}$ in ${}0_{2}$ überführt und die die Nachfolgeabbildungen respektiert.

Aufgabe *

Es sei ${}(\mathbb {N} ,0,^{\prime })$ ein Dedekind-Peano-Modell der natürlichen Zahlen. Zeige, dass die Addition durch die Bedingungen

$x+0=x{\text{ für alle }}x\in \mathbb {N} {\text{ und }}x+y'=(x+y)'{\text{ für alle }}x,y\in \mathbb {N}$

eindeutig bestimmt ist.

Aufgabe

Zeige, dass die Addition auf den natürlichen Zahlen kommutativ und assoziativ ist und dass die Abziehregel (d.h., dass aus ${}n+k=m+k$ für ein ${}k$ stets ${}n=m$ folgt) gilt.

Aufgabe

Es sei ${}(\mathbb {N} ,0,')$ ein Dedekind-Peano-Modell der natürlichen Zahlen. Zeige, dass die Multiplikation durch die Bedingungen

$x\cdot 0=0{\text{ für alle }}x\in \mathbb {N} {\text{ und }}x\cdot y'=x\cdot y+x{\text{ für alle }}x,y\in \mathbb {N}$

eindeutig bestimmt ist.

Aufgabe

Es sei ${}(\mathbb {N} ,0,^{\prime })$ ein Dedekind-Peano-Modell der natürlichen Zahlen und ${}n\in \mathbb {N}$. Zeige durch Induktion, dass die Beziehung

${}\{0,\ldots ,n^{\prime }\}=\{0,\ldots ,n\}\cup \{n^{\prime }\}\,$

gilt.

(Zur Erinnerung: ${}\{0,\ldots ,n\}={\left\{k\in \mathbb {N} \mid k\leq n\right\}}$.)

Aufgabe

Es seien ${}M$ und ${}N$ zwei disjunkte endliche Mengen. Zeige, dass die Anzahl der (disjunkten) Vereinigung ${}M\cup N$ gleich der Summe der beiden Anzahlen der beiden Mengen ist.

Aufgabe

Es seien ${}M$ und ${}N$ endliche Mengen. Zeige, dass die Produktmenge ${}M\times N$ ebenfalls endlich ist, und dass die Beziehung

${}{\#\left(M\times N\right)}={\#\left(M\right)}\cdot {\#\left(N\right)}\,$

gilt.

Aufgabe

Beweise durch Induktion die folgenden Formeln.

1. ${}\sum _{i=1}^{n}i={\frac {n(n+1)}{2}}\,,$

2. ${}\sum _{i=1}^{n}i^{2}={\frac {n(n+1)(2n+1)}{6}}\,.$

3. ${}\sum _{i=1}^{n}i^{3}={\left({\frac {n(n+1)}{2}}\right)}^{2}\,.$

Aufgabe

Zeige, dass mit der einzigen Ausnahme ${}n=3$ die Beziehung

${}2^{n}\geq n^{2}\,$

gilt.

Aufgaben zum Abgeben

Aufgabe (3 Punkte)

Es sei ${}(\mathbb {N} ,0,^{\prime })$ ein Dedekind-Peano-Modell der natürlichen Zahlen. Zeige, dass für ${}x,y\in \mathbb {N}$ die Beziehung ${}x\leq y$ genau dann gilt, wenn es ein ${}z\in \mathbb {N}$ gibt mit ${}y=x+z$.

Aufgabe (7 Punkte)

Es sei ${}(\mathbb {N} ,0,')$ ein Dedekind-Peano-Modell der natürlichen Zahlen mit der in Definition 4.10 festgelegten Multiplikation. Zeige die folgenden Aussagen.

1. ${}0\cdot n=0=n\cdot 0\,$

   für alle ${}n$.

2. ${}1\cdot n=n=n\cdot 1\,$

   für alle ${}n$, d.h. ${}1=0'$ ist das neutrale Element für die Multiplikation.

3. ${}k'\cdot n=k\cdot n+n\,$

   für alle ${}n,k\in \mathbb {N}$.

4. Die Multiplikation ist kommutativ.
5. Die Multiplikation ist assoziativ.
6. Aus einer Gleichung ${}n\cdot k=m\cdot k$ mit ${}k\neq 0$ folgt ${}n=m$ (Kürzungsregel).
7. Für beliebige ${}k,m,n\in \mathbb {N}$ gilt

   ${}k\cdot (m+n)=k\cdot m+k\cdot n\,$

   (Distributivgesetz).

Ausschnitt aus Albrecht Dürers Melencolia I.

Aufgabe (2 Punkte)

Es sei ${}n\in \mathbb {N}$. Ein „magisches Quadrat“ zur Seitenlänge ${}n$ ist eine Anordnung der natürlichen Zahlen ${}1,2,3,\ldots ,n^{2}-1,n^{2}$ in ein ${}n\times n$-Quadrat derart, dass die Summe aller Zeilen, die Summe aller Spalten und die Summe der beiden Diagonalen konstant ist. Welcher Wert ist das?

Formuliere mittels Abbildungen, was ein magisches Quadrat ist, und drücken Sie die Summenbedingungen mit dem Summenzeichen und geeigneten Indexmengen aus.

Aufgabe (4 Punkte)

Wir sagen, dass zwei magische Quadrate ${}Q_{1}$ und ${}Q_{2}$ äquivalent sind, wenn sie durch eine Folge aus Drehungen oder Spiegelungen ineinander überführt werden können (dies ist in der Tat eine Äquivalenzrelation). Zeige, dass alle magischen Quadrate zur Seitenlänge ${}3$ untereinander äquivalent sind. Wie viele Elemente enthält die Quotientenmenge und wie viele die Äquivalenzklassen?

Aufgabe * (2 Punkte)

Beweise durch Induktion, dass die Summe von aufeinanderfolgenden ungeraden Zahlen (beginnend bei ${}1$) stets eine Quadratzahl ist.

Aufgabe (2 Punkte)

Die Folge ${}a_{n},\,n\in \mathbb {N}$, sei rekursiv durch

$a_{1}=1{\text{ und }}a_{n}=\sum _{k=1}^{n-1}ka_{k}{\text{ für }}n\geq 2$

definiert. Zeige, dass für ${}n\geq 2$

${}a_{n}={\frac {1}{2}}n!\,$

gilt.

Aufgabe (2 Punkte)

Beweise durch Induktion die Abschätzung

${}1\cdot 2^{2}\cdot 3^{3}\cdots n^{n}\leq n^{\frac {n(n+1)}{2}}\,.$