1.9 Weitere Lernmaterialien

Wir wollen hier versuchen, Ihnen einen Überblick über dieses Kapitel zu geben und auch weitere Übungsaufgaben zu den Themen des Kapitels zu sammeln.

1.9.1 Verwendung des Kapitels

Wir haben in diesem Kapitel viele Themen und unter anderem Tipps, Motivationen, einige Theorie und auch noch etwas Geschichte der Mathematik besprochen. Auf Grund dieser Vielfalt wollen wir kurz noch betonen, was Sie aus diesem Kapitel eigentlich für das Folgende mitnehmen müssen: Die Themen aus den Abschnitten 1.3, 1.4 und 1.6 sind grundlegend und wir werden ohne Wiederholungen alle unsere weiteren Diskussionen auf diese Abschnitte aufbauen. Vor allem sollten Sie die folgenden Begriffe so lange üben, bis Sie diese ohne Zweifel im Gedächnis haben.

Bei logischen Aussagen werden wir, wie Sie vielleicht schon in Abschnitt 1.8 gemerkt haben, die Notation in Zukunft etwas leichter halten. Unter anderem werden wir die Anführungszeichen $\text{„}\dots \text{“}$ bei logischen Ausdrücken weglassen und teilweise die Klammerung unterschlagen, wenn diese implizit klar ist. Zum Beispiel kann $\exists n\in \mathbb{N}:n=n^2\Rightarrow n=1$ nur für den Ausdruck $\exists n\in \mathbb{N}:(n=n^2\Rightarrow n=1)$ stehen, da ansonsten die Zahl $n$ auf der rechten Seite von $(\exists n\in \mathbb{N}:n=n^2)\Rightarrow n=1$ nicht definiert ist. Im Zweifel empfehlen wir Ihnen aber lieber eine Klammer zu viel zu schreiben.

Die Diskussionen rund um Logik und Mengenlehre dieses Abschnitts könnte man mit Muskelübungen für einen Schwimmunterricht fern von jeglicher Wasseroberfläche vergleichen, denn wir haben logische Begriffe und Mengennotationen besprochen ohne konkrete Aussagen oder Mengen besprechen zu wollen. In der Tat sollten Sie den Abschnitt 1.5 (der als Übersicht gedacht war) eigentlich wieder vergessen. Denn wir werden im nächsten Kapitel logische Begriffe, Mengen und Funktionen verwenden um die reellen Zahlen axiomatisch einzuführen.

Abschnitt 1.8 und die Übungsaufgaben dieses Abschnitts sollen Ihnen helfen Ihren eigenen Zugang zu Beweisen zu finden. Schwierige Fragen, die immer wieder auftauchen, sind, „Was muss ich denn bei diesem Satz oder bei dieser Aufgabe eigentlich beweisen?“ und „Welche Aussage kann ich als gegeben annehmen?“. Dies ist in diesem Kapitel mitunter wirklich schwer zu beantworten (und wir haben hierzu im Laufe des Kapitels auch mehrmals unsere Meinung geändert). Nach Einführung der Axiome im nächsten Kapitel wird deutlich klarer sein, was wir beweisen müssen: nämlich ausser den Axiomen alles Weitere, wobei wir aber auf bereits bewiesene Aussagen zurückgreifen dürfen. Insbesondere dürfen Sie in den wöchentlichen Übungsaufgaben die Aussagen der Vorlesung und ebenso die Aussagen des Skripts verwenden, aber keine Übungsaufgaben des Skripts und auch nur jene Seiten des Skripts, die bereits in der Vorlesung behandelt wurden. Obwohl die Axiome sehr einfach sein werden, werden wir im Laufe der Vorlesung viele komplizierte und auch überraschende Aussagen beweisen können.

1.9.2 Flächeninhalt

Ü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.

1.9.3 Logik

Ü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.

1.9.4 Funktionen und Relationen

Ü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.10) betrachten wollen.

(ii)

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

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.

1.9.5 Beweismethoden

Ü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.

1.9.6 Geometrische Probleme

Wir empfehlen Ihnen folgende Übung zu lösen, da der „Satz von Pythagoras“ für uns später gewissermassen zu einer Definition werden wird.

Ü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.

1.9.7 Übungen zu Primzahlen

Eine natürliche Zahl $p$ grösser als $1$ ist irreduzibel, falls sie nicht als Produkt von zwei kleineren natürlichen Zahlen geschrieben werden kann. Eine natürliche Zahl $p$ grösser als $1$ heisst eine Primzahl, falls ein Produkt $ab$ zweier natürlicher Zahlen $a,b\in \mathbb{N}$ nur dann durch $p$ teilbar ist, falls eine der beiden Zahlen durch $p$ teilbar ist.

Übung (Primzahlen sind irreduzibel).

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

Diese beiden Begriffe sind in der Tat für die natürlichen Zahlen äquivalent (wir werden dies nochmals etwas genauer in Abschnitt 2.2.4 besprechen) und wir werden in diesem Abschnitt irreduzible Zahlen ebenso als Primzahlen bezeichnen. Es ist eine gute Übung im Folgenden genau zu erklären welche der beiden Begriffe eigentlich verwendet wird.

Ü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.

1.9.8 Online Lernhilfen

Bei erster Verwendung dieses Skripts in der entsprechenden Vorlesung hat ein Student mehrere online-Tools zum Erlernen der Inhalte des Skripts programmiert. Leider haben sich aber die Inhalte seitdem etwas verändert, ohne dass die Inhalte in den online-Tools angepasst wurden. Wir erwähnen hier die Webseite einmalig. Sollte jemand dieses App aktualisieren oder ein alternatives App mit aktuellen Daten zur Verfügung stellen wollen, so werden wir dieses gerne auch wieder am Ende von jedem Kapitel bewerben.

1.9.9 SageMath

Schlussendlich wollen wir die auf Python basierende Programmiersprache SageMath erwähnen. Diese ist für mathematische Experimente bestens geeignet und kann auch ohne einer aufwendigen Installation mittels SageMathCell benützt werden. Für aufwendigere oder auch rechenintensivere Programme empfiehlt sich allerdings eine lokale Installation von SageMath.

Versuchen Sie doch folgende Zeilen in SageMath aus und experimentieren Sie etwas damit.

 table( [["A","B","A => B"]]      + [[A,B,(not A) or B] for A in [true, false] for B in [true, false]] ) 

Wir bemerken, dass einzelne Befehle normalerweise innerhalb einer Zeile stehen sollten, dass aber bei einer vorhanden offenen Klammer die anschliessende(n) Zeile(n) als Teil der ersten Zeile aufgefasst werden. Der Ausdruck in der ersten Zeile beschriftet die Kopfzeile und mit den beiden ’for’-Konstruktionen werden alle Möglichkeiten durchgetestet. Insgesamt wird durch den Befehl table hier die Wahrheitstabelle der Implikation dargestellt. Ändern Sie obiges Beispiel und versuchen Sie zum Beispiel damit eine der Tautologie aus Abschnitt 1.3.1 zu überprüfen.

Hier einige Zeilen, die zeigen, wie wir in SageMath mit Mengen operieren können. Bei mehreren Befehlen hintereinander, die alle ein Ergebnis darstellen sollten, müssen sie den Befehl print verwenden.

 A = Set( "abcdabcd" ) B = Set( [0,"a"] ) print("A =",A,"und B =",B) print("Durchschnitt:", A.intersection(B) ) print("Vereingigung:", A + B ) print("Ist 0 in A?", 0 in A ) print("Ist 0 in B?", 0 in B ) def Produktmenge(X,Y):     return Set( (x,y) for x in X for y in Y )  print("Produktmenge:", Produktmenge(A,B) ) 

Zur Definition neuer Befehle mittels der obigen def-Konstruktion sollte man bemerken, dass die konsistente Einrückung der folgenden Zeilen wichtig ist und man zur Erhöhung der Übersicht die Definition mit einer Leerzeile beenden sollte.

Die folgende Routine testet die Injektivität der Einschränkung einer Funktion $f$ auf einer endlichen Menge $X$. Dazu wollen wir bemerken, dass all der Allquantor und any der Existenzquantor in SageMath ist. Des Weiteren, sollten Sie wissen, dass = wie in obigem Beispiel eine Anweisung ist, die einer Variable einen Wert zuweist, aber == die Frage nach Gleichheit und != die Frage nach Ungleichheit darstellt.

 def TestInj(F,X):     return all( (x==y) or (F(x)!=F(y)) for x in X for y in X )  X = [0..10]         # X ist die Liste aller ganzen Zahlen von 0 bis 10 g(n) = n^2-2*n+1    # die Funktion print("Ist g eingeschränkt auf X injektiv?") TestInj(g,X) 

Schreiben Sie anschliessend eine Routine TestWohl(F,X,Y), die überprüft, ob $F\left(X\right)\subseteq Y$ gilt. Schreiben Sie eine Routine TestSurj(F,X,Y), die überprüft, ob $F\left(X\right)=Y$ gilt. Schreiben Sie schlussendlich eine Routine TestGraph(G,X,Y), die für eine Menge $G$ überprüft ob $G\subseteq (X\times Y)$ der Graph einer Funktion $f:X\to Y$ ist.

Folgende Zeilen sollten auch zeigen, warum wir Ihnen SageMath als Programmiersprache für mathematische Experimente empfehlen.

 print("Wofür steht QQ?", QQ) print("Ist 2 eine rationale Zahl?", 2 in QQ) print("Ist 2^2 eine rationale Zahl?", 2^2  in QQ) print("Ist die Wurzel aus 2 eine rationale Zahl?", sqrt(2) in QQ)  print("Wofür steht RR?", RR) print("Ist pi eine reelle Zahl?", pi in RR) print("Ist pi eine rationale Zahl?", pi in QQ) 

Wir überlassen Ihnen die entsprechenden Internetnachforschungen, falls Sie mehr über SageMath wissen wollen.