Bearbeiten von: Abschnitt [Änderungshistorie]
  Zeilenumbrüche automatisch mache ich selbst mit HTML    

Ich möchte eine Mail an , nachdem mein Vorschlag bearbeitet ist.
  Nachricht zur Änderung:

Input assistance tools (JavaScript): [Link extern intern] [MathML?] [$$?]
[fed-area] [LaTeX-inline] [LaTeX-display] [Tikz] [hide-area][show-area] [Source code [num.]][?]
[Link zurück zum Artikelabschnitt]

Vorschau:
Verschärfe

Verschärfe die Behauptung

Das ist zwar auf den ersten Blick nicht intuitiv, aber manche Aussagen lassen sich erst dann leichter oder überhaupt beweisen, indem man sie verschärft (bzw. verstärkt). Das kann zum Beispiel vorkommen, wenn man im Rahmen einer vollständigen Induktion beim Induktionsschritt tatsächlich etwas Stärkeres als die Induktionsannahme braucht, um auf die Induktionsbehauptung zu schließen. Auch bei Reduktionsargumenten kann so etwas passieren. \begin{tikzpicture} \draw[fill=blue!50!white] (0,0) circle [radius=5mm]; \draw[fill=blue!10!white] (2,0) circle [radius=12mm]; \end{tikzpicture}

Beispiel 1

Die Folge $(a_n)_{n \in \IN}$ sei rekursiv definiert durch $a_0 = 0$ und $a_{n+1} = a_n^2 + \frac{1}{4}$. Dann gilt $0 \leq a_n < 1$ für alle $n \in \IN$.
Bei $0 \leq a_n$ gibt es keine Probleme, aber $a_n < 1$ überlebt den naheliegenden Induktionsschritt nicht: $a_{n+1} = a_n^2 + \frac{1}{4} < 1 + \frac{1}{4} = \frac{5}{4}$. Man muss stattdessen die schärfere Ungleichung $a_n < \frac{1}{2}$ zeigen (auf die Schranke $\frac{1}{2}$ kommt man experimentell durch ein paar Zahlenwerte oder durch Auflösen der Gleichung $g = g^2 + \frac{1}{4}$ eines hypothetischen Grenzwertes $g$). Der Induktionsschritt geht hier problemlos durch: $a_{n+1} = a_n^2 + \frac{1}{4} < \left(\frac{1}{2}\right)^2 + \frac{1}{4} = \frac{1}{4} + \frac{1}{4} = \frac{1}{2}. $

Beispiel 2

Jede mit $\neg,\vee,\wedge$ gebildete aussagenlogische Formel ist zu einer Formel äquivalent, in der $\neg$ nur direkt vor den Aussagenvariablen vorkommt.
Für Beispiele ist das relativ klar, zum Beispiel gilt ja $\neg (p \vee q) \equiv \neg p \wedge \neg q$. Das Problem ist allerdings, dass es gar nicht direkt möglich ist, diese Aussage induktiv nach dem Aufbau der Formel $\varphi$ zu zeigen. Wenn sie zum Beispiel die Form $\neg \psi$ hat, wobei die Behauptung für $\psi$ bereits gezeigt sei, können wir zwar $\psi$ entsprechend umwandeln, haben davon aber gar nichts! Stattdessen müssen wir die Induktionsbehauptung über $\varphi$ verstärken: sowohl $\varphi$ als auch $\neg \varphi$ sollen sich wie gewünscht umformen lassen. Sei nun $\varphi$ eine Formel und die (verstärkte) Behauptung gelte für alle kleineren Formeln. Zeigen wir sie für $\varphi$. Es gibt vier Fälle. 1) $\varphi$ ist eine Aussagenvariable $p$. Dann haben $p$ und $\neg p$ bereits die gewünschte Form. 2) $\varphi = \alpha \wedge \beta$. Nach Induktionsannahme lassen sich $\alpha,\beta$ wie gewünscht umwandeln, also auch $\varphi$. Nach Induktionsannahme lassen sich aber auch $\neg \alpha$ und $\neg \beta$ umwandeln, und daher auch $\neg \varphi \equiv \neg \alpha \vee \neg \beta$. 3) $\varphi = \alpha \vee \beta$. Der Fall geht analog zum vorigen. 4) $\varphi = \neg \psi$. Nach Induktionsannahme lassen sich $\psi$ und $\neg \psi$ wie gewünscht umformen, das heißt also $\neg \varphi$ und $\varphi$, was zu zeigen war.

Beispiel 3

Seien $p_1,\dotsc,p_n$ verschiedene Primzahlen. Dann gilt $[\IQ(\sqrt{p_1},\dotsc,\sqrt{p_n}):\IQ]=2^n$.
Die naheliegende Idee ist, den Gradsatz und eine Induktion zu verwenden; im Induktionsschritt muss man dann $(\ast) \quad \sqrt{p_n} \notin \IQ(\sqrt{p_1},\dotsc,\sqrt{p_{n-1}})$ zeigen: dann ist $\sqrt{p_n}$ vom Grad $2$ über $\IQ(\sqrt{p_1},\dotsc,\sqrt{p_{n-1}})$, was nach Induktionsannahme Grad $2^{n-1}$ über $\IQ$ hat, sodass die gesamte Erweiterung $\IQ(\sqrt{p_1},\dotsc,\sqrt{p_{n}})$ also Grad $2 \cdot 2^{n-1} = 2^n$ über $\IQ$ hat. Das Problem ist nur, dass $(\ast)$ keinen offensichtlichen Beweis hat: Wenn wir die Annahme $\sqrt{p_n} \in \IQ(\sqrt{p_1},\dotsc,\sqrt{p_{n-1}})$ zu einem Widerspruch führen möchten und dann die Gleichung quadrieren, bekommen wir auch gemischte Terme, mit denen wir erst einmal nichts anfangen können. Es bietet sich daher an, die Behauptung $(\ast)$ zu verstärken (zumal man sich überlegen kann, dass $(\star)$ unten aus der zu zeigenden Gradgleichung folgt): $(\star) \quad \sqrt{p_{i_1} \cdots p_{i_s}} \notin \IQ(\sqrt{p_1},\dotsc,\sqrt{p_m})$ für $m < i_1 < \dotsc < i_s \leq n$ Hier gelingt nun auf einmal trotz bzw. gerade wegen der Verstärkung eine Induktion nach $m$, und zwar mühelos: Der Fall $m=0$ ist klar (warum man eine Induktion oftmals mit der Null starten kann, steht hier). Wenn nun $\sqrt{p_{i_1} \cdots p_{i_s}} \in \IQ(\sqrt{p_1},\dotsc,\sqrt{p_{m+1}})$ für $m+1 < i_1 < \dotsc < i_s \leq n$, gibt es $ u,v \in \IQ(\sqrt{p_1},\dotsc,\sqrt{p_{m}})$ mit $p_{i_1} \dotsc p_{i_s} = (u+v \sqrt{p_{m+1}})^2 = u^2 + p_{m+1} v^2 + 2uv \sqrt{p_{m+1}}.$ Wenn $u,v \neq 0$, folgte $\sqrt{p_{m+1}} \in \IQ(\sqrt{p_1},\dotsc,\sqrt{p_{m}})$, Widerspruch zur Induktionsannahme. Wenn $u=0 \neq v$, folgte $\sqrt{p_{i_1} \dotsc p_{i_s} p_{m+1}} \in \IQ(\sqrt{p_1},\dotsc,\sqrt{p_{m}})$, Widerspruch zur Induktionsannahme, und für $v=0 \neq u$ folgte $\sqrt{p_{i_1} \dotsc p_{i_s}} \in \IQ(\sqrt{p_1},\dotsc,\sqrt{p_{m}})$, ebenfalls Widerspruch zur Induktionsannahme. In einem allgemeineren Rahmen (siehe hier) hätte man hier gleich die "richtige" Aussage aufgestellt.

Beispiel 4

Je zwei abzählbar-unendliche dichte unbeschränkte lineare Ordnungen (DLO) sind zueinander isomorph.
Eine lineare Ordnung heißt hierbei dicht, wenn es für alle Elemente $x,y$ mit $x < y$ ein Element $p$ gibt mit $x < p < y$, und unbeschränkt, wenn es weder minimales noch maximales Element gibt. Um die Aussage zu beweisen, nehmen wir zwei Ordnungen des genannten Typs $D = \{x_1,x_2,\dotsc\},~E = \{y_1,y_2,\dotsc\}$ und würden gerne induktiv zeigen, dass es einen Isomorphismus von Ordnungen $\{x_1,\dotsc,x_n\} \to \{y_1,\dotsc,y_n\}$ gibt. Das stimmt allerdings nicht mit jeder Abzählung von $D$ bzw. $E$. Und damit der Induktionsschritt funktioniert und die Isomorphismen auf eine Weise miteinander kompatibel sind, dass sie dann zu einem Isomorphismus $D \to E$ "verkleben", muss die Behauptung außerdem verstärkt werden; nämlich zur folgenden Aussage: $(\ast)$: Seien $D' \subseteq D$, $E' \subseteq E$ zwei endliche Teilmengen. Sei $f' : D' \to E'$ ein Isomorphismus von Ordnungen. Für jedes $d \in D \setminus D'$ gibt es dann ein $e \in E \setminus E'$, sodass sich $f'$ zu einem Isomorphismus von Ordnungen $f : D' \cup \{d\} \to E' \cup \{e\}$ durch $f(d) := e$ fortsetzen lässt. Analog (das folgt per Symmetrie, betrachte $f'^{-1}$ usw.) gibt es für jedes $e \in E \setminus E'$ auch ein passendes $d \in D \setminus D'$, sodass sich $f$ so fortsetzen lässt. Wenn wir das bewiesen haben, wenden wir das abwechselnd (!) auf das dem Index nach kleinste bisher noch nicht einbezogene Element von $D$ bzw. $E$ an, um rekursiv aufsteigende und vor allem ausschöpfende endliche Teilmengen $\emptyset = D_0 \subseteq D_1 \subseteq \dotsc \subseteq D, \quad \emptyset = E_0 \subseteq E_1 \subseteq \dotsc \subseteq E$ sowie Isomorphismen $f_n : D_n \to E_n$ mit $f_{n+1} |_{D_n} = f_n$ zu finden, die also zu einem Isomorphismus $f : D \to E$ verkleben. Diese Methode kennt man übrigens als Back-and-forth method. Um nun $(\ast)$ zu beweisen, schreibt man sich einfach $D' = \{d_1 < \dotsc < d_n\}$ hin und macht eine Fallunterscheidung, wo das neue Element $d$ hier anzuordnen ist: Wenn $d < d_1$, wählen wir $e \in E$ mit $e < f(d_1)$ (gibt es, weil $E$ unbeschränkt ist), analoges machen wir wenn $d > d_n$. Ansonsten gibt es einen Index $i$ mit $d_i < d < d_{i+1}$, und dann wählen wir natürlich $e \in E$ so, dass $f(d_i) < e < f(d_{i+1})$ (gibt es, weil $E$ dicht ist).

Beispiel 5

Satz von Cauchy: Ist $G$ eine endliche Gruppe und $p$ eine Primzahl mit $p \mid \mathrm{ord}(G)$, so enthält $G$ ein Element der Ordnung $p$.
Der Trick besteht darin, nicht nach einem Element zu suchen, sondern die Anzahl $s$ dieser Elemente zu untersuchen und $s \equiv -1 \bmod p$ zu zeigen, woraus ja insbesondere $s \neq 0$ folgt. Zum Beweis schaut man sich aber eine noch viel allgemeinere Menge von Elementen an, nämlich $X := \{(x_1,\dotsc,x_p) \in G^p : x_1 \cdots x_p = 1\}$. Auf $X$ lässt man die zyklische Gruppe $C_p$ durch "zyklisches Verschieben" operieren. Die Bahnen haben $1$ oder $p$ Elemente (Bahnformel). Die Bahnen mit genau einem Element sind die $\{(x,\dotsc,x)\}$ mit $x^p = 1$. Es gibt also genau $s+1$ davon, und die Bahnengleichung zeigt nun $s+1 \equiv \# X = \mathrm{ord}(G)^{p-1} \equiv 0 \bmod p$. Überhaupt ist es ein allgemeines Prinzip, dass man die Existenz eines Objektes aus der Anzahl solcher Objekte ableiten kann. Beispiele dafür sind Sperners Lemma, die Existenz transzendenter Zahlen, das Chevalley–Warning Theorem und der Primzahlsatz von Dirichlet. Eng verwandt damit ist auch die probabilistische Methode, bei der man die Existenz eines Objektes dadurch zeigt, dass die Wahrscheinlichkeit für dessen Existenz positiv ist.
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]