Übung.

Seien $X,Y$ Mengen. Welche Aussagen sind (immer) wahr und welche sind (manchmal) falsch?

(i)

(W/F) 

🚫 

 $(\forall x\in X\exists y\in Y:A(x,y\left)\right)\Rightarrow (\exists y\in Y\forall x\in X:A(x,y\left)\right)$

(ii)

(W/F) 

✅ 

 $(\exists y\in Y\forall x\in X:A(x,y\left)\right)\Rightarrow (\forall x\in X\exists y\in Y:A(x,y\left)\right)$

(iii)

(W/F) 

✅ 

 $\forall x\in X:\left(A\right(x)\wedge B(x\left)\right)\Rightarrow (\forall x\in X:A(x\left)\right)\wedge (\forall x\in X:B(x\left)\right)$

(iv)

(W/F) 

✅ 

 $(\forall x\in X:A(x\left)\right)\wedge (\forall x\in X:B(x\left)\right)\Rightarrow \forall x\in X:\left(A\right(x)\wedge B(x\left)\right)$

(v)

(W/F) 

🚫 

 $\forall x\in X:\left(A\right(x)\vee B(x\left)\right)\Rightarrow (\forall x\in X:A(x\left)\right)\vee (\forall x\in X:B(x\left)\right)$

(vi)

(W/F) 

✅ 

 $(\forall x\in X:A(x\left)\right)\vee (\forall x\in X:B(x\left)\right)\Rightarrow \forall x\in X:\left(A\right(x)\vee B(x\left)\right)$

Übung.

Seien $X,Y$ Mengen, $f:X\to Y$ eine Abbildung und $A\subseteq X$, $B\subseteq Y$ Teilmengen. Welche der folgenden Aussagen sind immer wahr?

(i)

(W/F) 

✅ 

 $A\subseteq f^{-1}\left(f\right(A\left)\right)$

(ii)

(W/F) 

🚫 

 $A\supseteq f^{-1}\left(f\right(A\left)\right)$

(iii)

(W/F) 

🚫 

 $B\subseteq f\left(f^{-1}\right(B\left)\right)$

(iv)

(W/F) 

✅ 

 $B\supseteq f\left(f^{-1}\right(B\left)\right)$

Übung.

Seien $X,Y,Z$ Mengen und $f:X\to Y$ sowie $g:Y\to Z$ Funktionen. Gelten die folgenden Schlüsse allgemein?

(i)

(J/N) 

🚫 

  Wenn $g\circ f$ surjektiv ist, dann ist $f$ surjektiv.

(ii)

(J/N) 

✅ 

  Wenn $g\circ f$ surjektiv ist, dann ist $g$ surjektiv.

(iii)

(J/N) 

✅ 

  Wenn $g\circ f$ injektiv ist, dann ist $f$ injektiv.

(iv)

(J/N) 

🚫 

  Wenn $g\circ f$ injektiv ist, dann ist $g$ injektiv.

(v)

(J/N) 

✅ 

  Wenn $A=f^{-1}\left(f\right(A\left)\right)$ für jede Teilmenge $A\subseteq X$ gilt, dann ist $f$ injektiv.

(vi)

(J/N) 

✅ 

  Wenn $B=f\left(f^{-1}\right(B\left)\right)$ für jede Teilmenge $B\subseteq Y$ gilt, dann ist $f$ surjektiv.

Übung (Allgemeinere Bereiche unter der Parabel).

Berechnen Sie die Fläche unter der Parabel

wobei $a,b\in ℝ$ zwei gegebene reelle Zahlen mit $a<b$ sind.

Übung.

In dieser Übung möchten wir eine Beweisvariante illustrieren, wie man auf Lemma 1.3 schliessen kann ohne zuerst im Besitz der richtigen Formel zu sein. Wir schreiben dazu für $n\in \mathbb{N}$

Gehen Sie nun wie folgt vor.

(i)

Zeigen Sie für $a,b\in ℝ$ $$\begin{array}{lll}\hfill {(a+b)}^3=a^3+3a^{2}b+3a{b}^2+b^3.& & \hfill \end{array}$$

Können Sie alle dabei verwendenten Rechenregeln benennen?

(ii)

Verifizieren Sie die Gleichung $$\begin{array}{lll}\hfill {(n+1)}^3=1+3(1^2+2^2+\dots +n^2)+3(1+2+\dots +n)+n.& & \hfill \end{array}$$

(iii)

Schliessen Sie auf Lemma 1.3.

Übung (Draculas Bücher).

In der Bibliothek des Grafen Dracula gibt es keine zwei Bücher, deren Inhalt aus gleich vielen Wörtern besteht. Die Anzahl der Bücher ist die Summe der Anzahl der Wörter jedes einzelnen Buches. Des Weiteren genügen diese Aussagen, um den Inhalt mindestens eines Buches aus Draculas Bibliothek genau zu beschreiben. Was steht in diesem Buch? Diese Übung enstammt dem Buch [AE06].

Übung (Vier Aussagen in Prädikatenlogik).

Wir sagen $m\in \mathbb{N}$ teilt $n\in \mathbb{N}$ falls es ein $d\in \mathbb{N}$ gibt mit $n=dm$. Beschreiben Sie die Bedeutung folgender Aussagen und bestimmen Sie, ob diese zutreffen.

Übung (Allgemeinere Existenzquantoren).

Sei $X$ eine Menge. In dieser Übung wollen wir Quantoren für die Aussage, dass mehrere Elemente mit einer Eigenschaft $A\left(x\right)$ in $X$ existieren, definieren.

(i)

Definieren Sie unter Verwendung des Existenzquantors einen neuen Quantor ${\exists }^{\ge 2}$, so dass die Aussage „${\exists }^{\ge 2}x\in X:A\left(x\right)$“ bedeutet, dass es mindestens zwei Elemente $x$ in $X$ gibt, die die Eigenschaft $A\left(x\right)$ haben.

(ii)

Verallgemeinern Sie (i) zu dem Quantor ${\exists }^{\ge n}$ für eine natürliche Zahl $n$, und verwenden Sie diese um auch den Quantor ${\exists }^{=n}$ zu definieren, der besagen soll, dass es genau $n$ Elemente in $X$ gibt, die die Eigenschaft $A\left(x\right)$ besitzen. (Sie dürfen entweder informell Punkte verwenden, oder formal korrekter den Funktionsbegriff, Eigenschaften von Funktionen, und die Menge $\left\{k\in \mathbb{N}\mid k\le n\right\}$, die genau $n$ Elemente hat.)

(iii)

Definieren Sie unter Verwendung des Existenzquantors, des Funktionsbegriffes, einer Eigenschaft von Funktionen und der natürlichen Zahlen $\mathbb{N}$ einen neuen Quantor ${\exists }^{\infty }$, der besagt, dass es unendlich viele Elemente in $X$ gibt, die die Eigenschaft $A\left(x\right)$ besitzen.

Übung (Injektive Funktionen durch Fallunterscheidungen).

Zeigen Sie folgende Behauptung: Seien $X$ und $Y$ Mengen und sei $\mathcal{𝒫}$ eine Partition von $X$. Angenommen es ist für jedes $P\in \mathcal{𝒫}$ eine injektive Funktion $f_P:P\to Y$ gegeben und sei $f:X\to Y$ die eindeutige Funktion mit $f{|}_P=f_P$ für jedes $P\in \mathcal{𝒫}$ nach Lemma 1.52. Zeigen Sie, dass $f$ genau dann injektiv ist, falls die Mengen $f\left(P\right)$ für $P\in \mathcal{𝒫}$ paarweise disjunkt sind.

Übung (Eine Äquivalenzrelation auf dem kartesischen Produkt).

Seien $X,Y$ zwei nicht-leere Mengen, sei ${\sim }_X$ eine Relation auf $X$ und sei ${\sim }_Y$ eine Relation auf $Y$. Wir definieren damit eine Relation $\sim$ auf $X\times Y$ durch

für $(x,y),(x^{\prime },y^{\prime })\in X\times Y$. Zeigen Sie, dass $\sim$ genau dann eine Äquivalenzrelation auf $X\times Y$ ist, wenn ${\sim }_X$ eine Äquivalenzrelation auf $X$ ist und ${\sim }_Y$ eine Äquivalenzrelation auf $Y$ ist. Gilt dies auch, wenn eine der beiden Mengen $X,Y$ leer ist? Diese Übung enstammt dem Buch [AE06].

Applet (Nichtvertauschbarkeit der Verknüpfung).

Wir betrachten zwei Funktionen $f,g:ℝ\to ℝ$, wobei $f$ nur durch den Graphen beschrieben ist und $g:x\in ℝ\mapsto g\left(x\right)=ax+b$ eine affine Funktion ist, die durch zwei Konstanten $a,b\in ℝ$ definiert wird. Durch Bewegen zweier Punkte am Graph von $g$ lassen sich $a$ und $b$ definieren. Experimentieren Sie damit um sich an die geometrische Bedeutung von den Zahlen $a$ und $b$ zu errinnern, und beobachten Sie, wie sich die beiden Funktionen $g\circ f$ und $f\circ g$ im rechten Fenster unterschiedlich verändern. Es ist nützlich sich diese Phänomene vollständig zu erklären, denn wir werden ähnlichen Verknüpfungen in unseren weiteren Überlegungen begegnen.

Übung (Konstruktion der Menge der ganzen Zahlen).

Wir nehmen an, dass wir bereits die Menge der natürlichen Zahlen $\mathbb{N}$ und damit auch die Menge der nicht-negativen ganzen Zahlen ${\mathbb{N}}_0=\mathbb{N}\bigsqcup \left\{0\right\}$ mit allen üblichen Operationen und Eigenschaften kennen und wollen daraus die ganzen Zahlen definieren. Dazu betrachten wir eine Relation auf ${\mathbb{N}}_0^2$: für $(m_1,m_2),(n_1,n_2)\in {\mathbb{N}}_0^2$ definieren wir

(i)

Erklären Sie unter der Annahme, dass die ganzen Zahlen schon bekannt sind, wieso wir die Relation $\sim$ in (1.13) betrachten wollen.

Lösung.

Motiviert ist das ganze dadurch, dass man eine ganze Zahl als Differenz von zwei nicht-negativen ganzen Zahlen auffassen kann. Diese sind aber nicht eindeutig gegeben; deswegen führt man auf Tupeln von natürlichen Zahlen obige Äquivalenzrelation ein. In der Tat hat man bei Definition (1.13) eigentlich $(m_1,m_2)\sim (n_1,n_2)\iff m_1-m_2=n_1-n_2$ im Hinterkopf, darf dies aber formal nicht verwenden, da die Subtraktion (noch) nicht erlaubt ist. Wenn wir über ${\left[\right(m_1,m_2\left)\right]}_{\sim }$ sprechen, werden wir leicht schizophren an $m_1-m_2$ denken, dies aber nicht verwenden.

Informell können wir uns das Tupel $(m_1,m_2)$ als einen Vektor mit Anfangspunkt $m_1\in {\mathbb{N}}_0$ und Endpunkt $m_2\in {\mathbb{N}}_0$ vorstellen, womit die Äquivalenzklassen allen Vektoren mit gleicher Länge und Richtung entspricht. Alternativ könnte $m_1$ der Kontostand vor und $m_2$ der Kontostand nach einer Transaktion darstellen und die Äquivalenzklasse entspricht dann dem Nettogewinn/-verlust.

(ii)

Zeigen Sie, dass $\sim$ eine Äquivalenzrelation definiert.

Lösung.

Es gilt für alle $(m_1,m_2),(n_1,n_2),(q_1,q_2)\in {\mathbb{N}}_0^2$

•

Reflexivität: $(m_1,m_2)\sim (m_1,m_2)$, denn $m_1+m_2=m_1+m_2$.

•

Symmetrie: $(m_1,m_2)\sim (n_1,n_2)$ denn $m_1+n_2=n_1+m_2$ impliziert $n_1+m_2=m_1+n_2$ und daher auch $(n_1,n_2)\sim (m_1,m_2)$.

•

Transitivität: $(m_1,m_2)\sim (n_1,n_2)$ und $(n_1,n_2)\sim (q_1,q_2)$ impliziert $m_1+n_2=n_1+m_2$ und $n_1+q_2=q_1+n_2$. Durch Summieren dieser Gleichungen ergibt sich $$\begin{array}{lll}\hfill m_1+n_2+n_1+q_2=n_1+m_2+q_1+n_2& & \hfill \end{array}$$

und durch Wegstreichen von $n_1+n_2$ (was eine der Eigenschaften von ${\mathbb{N}}_0$ ist und nicht die Subtraktion verwendet) erhalten wir $m_1+q_2=q_1+m_2$, also $(m_1,m_2)\sim (q_1,q_2)$.

Der Quotient ${\mathbb{N}}_0^2∕\sim$kann als Definition von $\mathbb{Z}$ angesehen werden, wobei wir die Äquivalenzklasse auch als ${\left[\right(m_1,m_2\left)\right]}_{\sim }=m_2-m_1$ schreiben. Insbesondere identifizieren wir $n\in {\mathbb{N}}_0$ mit ${\left[\right(n,0\left)\right]}_{\sim }$ und schreiben ${\left[\right(0,n\left)\right]}_{\sim }$ auch als $0-n=-n$ für $n\in \mathbb{N}$. Folgende Übungen erklären, wieso dies Sinn ergibt.

(iii)

Zeigen Sie, dass die Abbildungen $$\begin{array}{llll}\hfill {\iota }_{+}:n\in {\mathbb{N}}_0& \mapsto {\left[\right(n,0\left)\right]}_{\sim }\in \mathbb{Z}& \hfill & \\ \hfill {\iota }_{-}:n\in \mathbb{N}& \mapsto -n={\left[\right(0,n\left)\right]}_{\sim }\in \mathbb{Z}& \hfill & \end{array}$$

injektiv sind und disjunkte Bilder ${\iota }_{+}\left({\mathbb{N}}_0\right),{\iota }_{-}\left(\mathbb{N}\right)$ haben, welche wir mit ${\mathbb{N}}_0={\iota }_{+}\left({\mathbb{N}}_0\right)$ und $-\mathbb{N}={\iota }_{-}\left(\mathbb{N}\right)$ bezeichnen werden.

(iv)

Zeigen Sie, dass $\mathbb{Z}={\mathbb{N}}_0^2∕\sim ={\iota }_{+}\left({\mathbb{N}}_0\right)\bigsqcup {\iota }_{-}\left(\mathbb{N}\right)$ gilt.

Übung.

Sei $n$ eine natürliche Zahl. Zeigen Sie, dass die Implikation

gilt.

Übung (Türme von Hanoi).

Es seien $3$ Ablageflächen gegeben. Angenommen auf der linken Ablagefläche seien $n$ Blöcke für eine natürliche Zahl $n$ aufgetürmt, wobei nie ein kleinerer Block unter einem grösseren Block liegt.

Zeigen Sie, dass Sie den Turm von links nach rechts umschichten können, ohne dass je ein kleinerer Block unter einem grösseren Block zu liegen kommt.

Übung.

Zeigen Sie mittels vollständiger Induktion, dass für alle natürliche Zahlen $n\ge 5$ gilt $4n<2^n$.

Übung.

Zeigen Sie mittels vollständiger Induktion, dass die Ungleichung $n^2<3^n$ für alle natürlichen Zahlen $n$ gilt. Beschreiben Sie die Variante des Induktionsbeweises, die sie hier verwenden.

Übung.

Wir färben jeden Punkt im Gitter ${\mathbb{Z}}^2$ mit einer von $17$ verschiedenen Farben ein. Zeigen Sie, dass es ein achsenparalleles Rechteck $R$ in diesem Gitter gibt, dessen Ecken alle dieselbe Farbe besitzen.

Übung.

Sei $n\in \mathbb{N}$ und sei $S$ eine Teilmenge von $\left\{1,\dots ,2n\right\}$ mit Kardinalität $n+1$. Zeigen Sie, dass es Elemente $a,b\in S$ gibt mit $a|b$.

Übung.

Sei $T$ eine endliche Menge und seien $S_1,\dots ,S_n$ Teilmengen von $T$ mit

Zeigen Sie, dass es ein Element $t\in T$ gibt, welches in mindestens $k+1$ der Mengen $S_1,\dots ,S_n$ liegt.

Übung (Satz von Pythagoras).

Wir betrachten ein rechtwinkliges Dreieck mit Katheten der Länge $a$ und $b$ und Hypotenuse der Länge $c$. Zeigen Sie, dass

Hinweis: Betrachten Sie folgende Bilder

und gehen Sie dabei davon aus, dass gewisse geometrische Begriffe wie Winkel, Länge und Fläche für elementare Bereiche und intuitiv anschauliche Eigenschaften wie Invarianz der Fläche unter Verschiebung und Drehung bekannt sind.

Übung (Primzahlen sind irreduzibel).

Zeigen Sie, dass jede Primzahl in $\mathbb{N}$ auch irreduzibel ist.

Übung (Primfaktorzerlegung).

Zeigen Sie mittels vollständiger Induktion, dass jede natürliche Zahl grösser als $1$ als Produkt von Primzahlen geschrieben werden kann.

Übung (Unendlich viele Primzahlen).

Zeigen Sie, dass es unendliche viele Primzahlen gibt.