Mathematik: Typische Beweismotive
Released by matroid on So. 20. Juni 2021 16:23:34 [Statistics]
Written by Triceratops - 854 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\begingroup\)

Typische Beweismotive

Dies ist die Fortsetzung des Artikels Wie man einfache Beweise ohne Mühe finden kann. Dort ging es um einfache Beweise, die sich schon alleine durch eine gute "Buchführung" der Definitionen, Voraussetzungen und Behauptungen hinschreiben lassen. In diesem Teil soll es nun um Beweise gehen, wo mehr Kreativität benötigt wird. Dazu stelle ich einige Beweismotive vor und illustriere sie wieder mit zahlreichen Beispielen. Es geht hierbei um keine konkreten Beweistechniken wie Induktion, Widerspruchsbeweis und dergleichen, wozu es schon sehr viel Material gibt, sondern um viel grundsätzlichere Denkweisen, die einem dabei helfen, einen Beweis zu finden.
• Reduktion auf einen Spezialfall • Teile und herrsche • Verschärfe die Behauptung • Führe einen Parameter ein • Verallgemeinere den Kontext


Ich setze einfache Beweise als bekannt voraus. Die hier vorgestellten Beweise lassen die "offensichtlichen" Zwischenschritte daher ganz bewusst aus. Die Beispiele können unabhängig voneinander gelesen werden.

Reduktion auf einen Spezialfall

Eine sehr wichtige und sehr mächtige Beweismethode: Man löst das Problem erst unter vereinfachten Bedingungen, also in einem Spezialfall, und argumentiert schließlich, dass sich der allgemeine Fall darauf zurückführen lässt. In vielen Fällen gibt es zudem eine "Staffelung" von Spezialfällen: zuerst erledigt man die ganz einfachen Spezialfälle, danach schon kompliziertere Fälle, und erst ganz zum Schluss den allgemeinen Fall. Oder man schreibt es genau umgekehrt herum auf und argumentiert, dass für den allgemeinen Fall einfachere Fälle ausreichen, dafür wiederum noch einfachere Fälle usw. Davon abgesehen ist es aber immer ein guter Tipp, um mit dem Beweis warmzuwerden, zunächst einen einfachen Spezialfall anzuschauen, zumindest wenn einem nicht direkt der allgemeine Fall klar ist. \begin{tikzpicture} \draw[fill=blue!50!white] (0,0) circle [radius=12mm]; \draw[fill=blue!10!white] (0,0) circle [radius=5mm]; \end{tikzpicture}

Beispiel 1

Hilberts Hotel: Wenn $X$ eine unendliche Menge ist, und $x \in X$, dann ist $X \setminus \{x\} \cong X$.
Das $\cong$ steht hier für Gleichmächtigkeit; es ist also eine Bijektion $X \to X \setminus \{x\}$ zu finden. Zunächst einmal kann man sich hier den Spezialfall $X=\IN$, $x=0$ ansehen (zumal $\IN$ sowieso die "kleinste" unendliche Menge ist). Dann hat man eine Bijektion $\IN \to \IN^+$ zu finden, und die sollte sofort ins Auge fallen: $n \mapsto n+1$. Der nächste Fall ist $X \cong \IN$ und $x \in X$ beliebig. Hier kann man aber eine Abzählung finden mit $X = \{x=x_0,x_1,\dotsc,\}$ und die Bijektion verläuft wie vorher nur über die Indizes, also mit $x_n \mapsto x_{n+1}$. Im allgemeinen Fall gibt es eine Teilmenge $D \subseteq X$ mit $D \cong \IN$ und $x \in D$. Wenn wir nun $+$ für die disjunkte Vereinigung schreiben, folgt $X \cong D + (X \setminus D) \cong (D \setminus \{x\}) + (X \setminus D) \cong X \setminus \{x\}.$ Hier war also eine Reduktion auf den Spezialfall einer abzählbar-unendlichen Menge möglich, weil jede unendliche Menge eine solche Menge enthält und die gesuchte Bijektion mit dem Rest gar nichts tun muss, das heißt also alle Elemente außerhalb dieser Teilmenge festlässt.

Beispiel 2

Sei $\langle -,-\rangle$ ein Skalarprodukt auf einem reellen Vektorraum $V$ und $|{-}|$ die induzierte Norm auf $V$. Dann gilt die Cauchy-Schwarz-Ungleichung $|\langle u,v \rangle| \leq |u| \cdot |v|$ für $u,v \in V$.
Es gibt dafür zahlreiche bekannte Beweise (siehe hier), aber ich möchte hier einmal das folgende Argument bekannter machen, welches ich vor vielen Jahren von Buri gelernt habe. Den Ansatz sollte man sich auf jeden Fall merken, weil er in vielen anderen Beweisen eine Anwendung findet. Wenn $u,v$ linear abhängig sind (also $u = \lambda v$ oder $v = \lambda u$ für einen Skalar $\lambda \in \IR$), rechnet man die Ungleichung, die dann eine Gleichung wird, einfach nach. Ansonsten sind $u,v$ linear unabhängig, und der von $u,v$ erzeugte Teilraum $U \subseteq V$ ist $2$-dimensional. Wir können das Skalarprodukt auf $U$ einschränken. Fazit: Es reicht, die Behauptung für $2$-dimensionale reelle Vektorräume mit einem Skalarprodukt zu zeigen! Bemerkenswert ist, dass diese Reduktion selbst dann gültig ist, wenn $V$ unendlich-dimensional war. Nun ist jeder $2$-dimensionale reelle Vektorraum zu $\IR^2$ isomorph. Aber nicht nur das: wenn wir ein Skalarprodukt auf $\IR^n$ gegeben haben, finden wir mit dem Gram-Schmidt-Verfahren eine Orthonormalbasis, und eine Orthonormalbasis induziert einen orthogonalen (also Skalarprodukt-erhaltenen) Isomorphismus zu $\IR^n$ mit dem Standardskalarprodukt. Und natürlich ist die Cauchy-Schwarz-Ungleichung invariant unter solchen Isomorphismen. Daher ist unser zweites Fazit: Es reicht, die Ungleichung für $\IR^2$ mit dem Standardskalarprodukt zu zeigen! Sprich, wir müssen lediglich die (hier schon quadrierte) Ungleichung $(a_1 b_1 + a_2 b_2)^2 \leq (a_1^2 + a_2^2) \cdot (b_1^2 + b_2^2)$ für reelle Zahlen $a_1,a_2,b_1,b_2$ zeigen. Durch simples Ausmultiplizieren stellt man fest, dass die Differenz gleich $a_1^2 b_2^2 + b_1^2 a_2^2 - 2 a_1 a_2 b_1 b_2$, also $(a_1 b_2 - b_1 a_2)^2 \geq 0$ ist.

Beispiel 3

Seien $(X_1,\mu_1)$, $(X_2,\mu_2)$ zwei Maßräume und $f : X_1 \to X_2$ eine messbare Abbildung mit $\mu_1(f^{-1}(B))=\mu_2(B)$ für alle messbaren Teilmengen $B \subseteq X_2$. Eine messbare Abbildung $g : X_2 \to \IR$ ist genau dann $\mu_2$-integrierbar, wenn $g \circ f : X_1 \to \IR$ $\mu_1$-integrierbar ist, und in diesem Fall gilt die Formel $\int g ~ \mathrm{d} \mu_2 = \int g \circ f ~ \mathrm{d} \mu_1$.
Man schaut sich hier (natürlich nachdem man die Definitionen von messbar, Maß, integrierbar usw. wiederholt hat) erst einmal den Spezialfall einer charakteristischen Funktion $g = \chi_B$ für eine messbare Teilmenge $B \subseteq X_2$ an. Dann ist die Integralgleichung wegen $g \circ f = \chi_{f^{-1}(B)}$ einfach $\mu_2(B) = \mu_1(f^{-1}(B))$, sprich gerade die Voraussetzung. Ist allgemeiner $g$ eine einfache Funktion, das heißt eine Linearkombination von solchen charakteristischen Funktionen, so können wir einfach die Linearität des Integrals benutzen, um die Behauptung aus dem bereits behandelten Spezialfall abzuleiten. Eine messbare Funktion $g \geq 0$ ist nun der punktweise aufsteigende Limes von einfachen Funktionen $(g_n)$. Die Funktionen $g_n \circ f$ sind ebenfalls einfach und konvergieren punktweise und aufsteigend gegen $g \circ f$. Also erhält man unmittelbar mit der Definition des Integrals (den Satz von der monotonen Konvergenz braucht man hier nicht einmal) die gewünschte Gleichung der Integrale (in $[0,\infty]$) aus dem bereits behandelten Spezialfall von einfachen Funktionen. Die Äquivalenz der Integrierbarkeitsbedingungen (sprich dass die Integrale $<\infty$ sind) folgt hier aus der Gleichung. Der allgemeine Fall einer messbaren Funktion $g$ lässt sich auf den Fall $g \geq 0$ zurückführen, indem wir $g = g^+ - g^-$ mit messbaren Funktionen $g^+,g^- \geq 0$ schreiben, was ja dann auch $g \circ f = g^+ \circ f - g^- \circ f$ impliziert usw. Bei diesem Beweis ist zu beachten, dass man sich die Spezialfälle gar nicht selbst überlegen musste: sie sind durch die Definition bzw. Konstruktion des Integrals bereits vorgegeben. Insofern ist selbst dieser Beweis erzwungen.

Beispiel 4

Sei $A$ ein kommutativer lokaler Ring und seien $M,N$ zwei endlich-erzeugte $A$-Moduln mit $M \otimes_A N = 0$. Dann gilt $M = 0$ oder $N = 0$.
Körper sind die vermutlich einfachsten kommutativen lokalen Ringe. Schauen wir uns diesen Spezialfall also zuerst an. Dann haben $M,N$ Basen $(b_i)_{i \in I}$ bzw. $(c_j)_{j \in J}$, und es ist bekannt, dass dann $(b_i \otimes c_j)_{i \in I, j \in J}$ eine Basis des Tensorproduktes $M \otimes_A N$ ist. Aus $M \otimes_A N = 0$ folgt also $I \times J = \emptyset$ und damit (das ist tatsächlich der Spezialfall $A=\IF_1$, siehe hier) $I=\emptyset$ oder $J=\emptyset$, also $M=0$ oder $N=0$. Im allgemeinen Fall sei $\mathfrak{m}$ das (eindeutige) maximale Ideal von $A$, sodass also $A/\mathfrak{m}$ ein Körper ist. Aus $M \otimes_A N =0$ folgt dann $M/\mathfrak{m}M \otimes_{A/\mathfrak{m}} N/\mathfrak{m}N = (M \otimes_A N) \otimes_A A/\mathfrak{m} = 0$. Aus dem bereits behandelten Spezialfall folgt daher $M/\mathfrak{m}M=0$ oder $N/\mathfrak{m}N=0$. Nun können wir das Lemma von Nakayama verwenden, welches nämlich $M/\mathfrak{m}M=0 \iff M =0$ besagt, und sind fertig. Auf die Endlich-Erzeugtheit kann man indes nicht verzichten, zum Beispiel gilt $\IQ_p / \IZ_p \otimes_{\IZ_p} \IQ_p / \IZ_p = 0$.

Beispiel 5

Sei $P : \IC^n \to \IC^n$ eine injektive polynomielle Abbildung. Dann ist $P$ bereits surjektiv.
Das ist das Ax-Grothendieck-Theorem und ein recht fortgeschrittenes Beispiel für diesen Artikel. Ich nehme es hier auf, weil es hier einen Beweis mit einer wunderschönen und – wenn man es noch nie gesehen hat – absolut verblüffenden Reduktion gibt, und die Beweismethode auch vielseitig anwendbar ist: Man reduziert das Theorem auf den Fall von endlichen Körpern! Wenn $F$ ein endlicher Körper (bzw. irgendeine endliche Menge) ist, dann ist jede injektive Abbildung $F^n \to F^n$ natürlich surjektiv, das ist reine Kombinatorik. Aber was hat $\IC$ mit endlichen Körpern zu tun? Nun, sei $P : \IC^n \to \IC^n$ eine injektive polynomielle Abbildung, repräsentiert durch Polynome $P_i \in \IC[X_1,\dotsc,X_n]$, $i=1,\dotsc,n$. Die Injektivität kann man auch so umformulieren, dass für die Polynome $Q_i := P_i(X)-P_i(X') \in \IC[X_1,\dotsc,X_n,X'_1,\dotsc,X'_n]$ gilt: Jede gemeinsame Nullstelle $(x,x') \in \IC^{2n}$ aller $Q_i$ ist von der Form $(x,x)$ mit $x \in \IC^n$. Das können wir prägnant als $V(Q_1,\dotsc,Q_n) \subseteq V(X_1-X'_1,\dotsc,X_n-X'_n)$ schreiben, wobei $V(-)$ für die gemeinsame Nullstellenmenge steht. Jetzt benutzen wir den Hilbertschen Nullstellensatz: Er liefert $\sqrt{ \langle X_1-X'_1,\dotsc,X_n-X'_n \rangle } \subseteq \sqrt{ \langle Q_1,\dotsc,Q_n \rangle },$ womit es also ein $N \in \IN$ gibt, sodass $(X_i - X'_i)^N$ eine $\IC[X_1,\dotsc,X_n,X'_1,\dotsc,X'_n]$-Linearkombination von $Q_1,\dotsc,Q_n$ ist. Hierbei sind nur endlich viele Koeffizienten in $\IC$ beteiligt. Es gibt daher einen endlich-erzeugten Teilring $A \subseteq \IC$, sodass die $P_i$ Koeffizienten in $A$ haben und die Linearkombination jeweils schon in $A[X_1,\dotsc,X_n,X'_1,\dotsc,X'_n]$ besteht. Bemerken wir zwischendurch, dass solche Linearkombinationen umgekehrt auch die Injektivität von $(P_1,\dotsc,P_n) : A^n \to A^n$ sichern. Jetzt müssen wir ähnlich mit der Annahme vorgehen, dass $P$ nicht surjektiv ist: Es gibt ein $y \in \IC^n$, sodass die $P_i(X)-y_i \in \IC[X_1,\dotsc,X_n]$ keine gemeinsame Nullstelle haben, und mit dem Hilbertschen Nullstellensatz folgt nun, dass es Polynome $R_i \in \IC[X_1,\dotsc,X_n]$ gibt mit $\displaystyle\sum_{i=1}^{n} (P_i(X)-y_i) R_i = 1.$ Wieder sind hier in $ y$, $P_i$, $R_i$ nur endlich viele Koeffizienten in $\IC$ beteiligt. Die Gleichung gilt also bereits in $B[X_1,\dotsc,X_n]$ für einen endlich-erzeugten Teilring $B \subseteq \IC$. Umgekehrt impliziert die Gleichung, dass $(P_1,\dotsc,P_n) : B^n \to B^n$ nicht surjektiv ist. In dem von $A$ und $B$ erzeugten Teilring $C \subseteq \IC$ gelten nun beide Gleichungssysteme. Wegen $C \neq 0$ hat $C$ ein maximales Ideal $\mathfrak{m}$, das heißt, $F:=C/\mathfrak{m}$ ist ein Körper, und er ist endlich-erzeugt als Ring. Wegen Zariskis Lemma muss $F$ dann ein endlicher Körper sein. Alle genannten Gleichungen gelten nun auch mit $F$ als Koeffizienten. Aus den bereits erwähnten Umkehrungen folgt daher, dass $(P_1,\dotsc,P_n) : F^n \to F^n$ eine polynomielle Abbildung ist, die injektiv, aber nicht surjektiv ist. Und das ist der gesuchte Widerspruch. Es sei nur kurz erwähnt, dass man die Reduktion alternativ auch mit dem Isomorphismus in das Ultraprodukt $\IC \cong \bigl(\prod_{p \text{ prim}} \overline{\IF_p}\bigr) / \mathfrak{m}$ und dem Satz von Łoś hätte begründen können.

Teile und herrsche

Das folgende Verfahren ist eine sehr hilfreiche und typische Beweismethode; hierbei sei $X$ ein mathematisches Objekt, von dem wir etwas zeigen möchten.
  1. Man teile $X$ in mehrere Teilobjekte $X_1,\dotsc,X_s$ auf. Was das im Einzelnen bedeutet, entscheidet sich im Kontext.
  2. Man löse das Problem für die Teilobjekte $X_1,\dotsc,X_s$ einzeln. Weil sie kleiner sind und/oder andere schöne Eigenschaften haben, die $X$ nicht besitzt, sollte das einfacher gehen.
  3. Man überzeuge sich davon, dass damit bereits das Problem für $X$ gelöst ist.
\begin{tikzpicture}[scale=0.7] \draw[fill=blue!50!white,rounded corners=2mm] (-0.1,-0.1) -- (8.4,-0.1) -- (8.4,2.1) -- (-0.1,2.1) --cycle; \draw[fill=blue!10!white,rounded corners=2mm] (0,0) -- (2,0) -- (2,2) -- (0,2) --cycle; \draw[fill=blue!10!white,rounded corners=2mm] (2.1,0) -- (4.1,0) -- (4.1,2) -- (2.1,2) --cycle; \draw[fill=blue!10!white,rounded corners=2mm] (4.2,0) -- (6.2,0) -- (6.2,2) -- (4.2,2) --cycle; \draw[fill=blue!10!white,rounded corners=2mm] (6.3,0) -- (8.3,0) -- (8.3,2) -- (6.3,2) --cycle; \end{tikzpicture} Im Prinzip ist dies eine Variante der Reduktion auf einen Spezialfall. Starten wir mit einem sehr einfachen Beispiel für dieses Prinzip.

Beispiel 1

Die Funktion $f : \IR^2 \to \IR$, $f(x,y) = e^{x - y}$ ist stetig.
Wir können nämlich $f$ zerlegen als $f = \exp \circ s$, wobei die Exponentialfunktion $\exp : \IR \to \IR$ und die Subtraktion $s : \IR^2 \to \IR$, $s(x,y) := x-y$ beides stetige Funktionen sind (was man entweder schon weiß, oder in dem Kontext noch beweisen muss). Jetzt wenden wir einfach den bekannten Satz an, dass die Verkettung von stetigen Funktionen wieder stetig ist. Man kürzt das üblicherweise so ab: Wir haben es mit einer Zusammensetzung von stetigen Funktionen zu tun, die also wieder stetig ist.

Beispiel 2

Sei $K$ ein Körper. Sei $V$ ein $K$-Vektorraum der Dimension $2n$ mit $n \in \IN^+$. Dann gibt es einen Endomorphismus $f : V \to V$ mit $f^2=-\mathrm{id}$.
Zunächst einmal reicht es (das ist die Methode der Reduktion auf einen Spezialfall), das Problem für den Spezialfall $V = K^{2n}$ zu lösen. Denn im allgemeinen Fall gibt es einen Isomorphismus $\vartheta : K^{2n} \to V$ (weil $V$ ja $2n$-dimensional ist), und wenn wir eine lineare Abbildung $f : K^{2n} \to K^{2n}$ mit $f^2 = -\mathrm{id}$ gefunden haben, dann löst $\vartheta \circ f \circ \vartheta^{-1} : V \to V$ unser Problem. Weil nun aber $K^{2n} = K^2 \oplus \cdots \oplus K^2$ gilt (mit $n$ Kopien von $K^2$), liegt es nahe, das Problem erst einmal für das Beispiel $K^2$ zu lösen, also im Spezialfall $n=1$. Stellen wir uns $K^2$ geometrisch als die Ebene vor, dann wäre eine Drehung um $90^{\circ}$ eine lineare Abbildung $f : K^2 \to K^2$, sodass $f^2$ die Drehung um $180^{\circ}$ ist, also $f^2 = - \mathrm{id}$. Formal definieren wir also $f$ durch lineare Fortsetzung von $f(1,0)=(0,1)$ und $f(0,1)=(-1,0)$, sprich $f(x,y) := (-y,x)$. Zurück zu $K^{2n}$: Dort können wir nun einfach $F := f \oplus \cdots \oplus f$ nehmen (mit $n$ Kopien von $f$), also formal $F(x_1,y_1,\dotsc,x_n,y_n) := (-y_1,x_1,\dotsc,-y_n,x_n)$. Geometrisch gesprochen gruppieren wir je zwei der $2n$ Dimensionen und nehmen jeweils dort eine Drehung vor.

Beispiel 3

Sei $n \in \IN$ und $\pi \in \Sigma_n$ eine Permutation. Dann ist $\pi$ genau dann ein endliches Produkt von Kommutatoren, wenn $\pi$ gerade ist (also wenn $\mathrm{sgn}(\sigma)=1$).
Jeder Kommutator $a b a^{-1} b^{-1}$ ist eine gerade Permutation wegen $\mathrm{sgn}(a b a^{-1} b^{-1}) = \mathrm{sgn}(a) \mathrm{sgn}(b) \mathrm{sgn}(a)^{-1} \mathrm{sgn}(b)^{-1}=1$. Produkte von Kommutatoren sind folglich ebenfalls gerade. Wenn umgekehrt $\pi$ eine gerade Permutation ist, so kann $\pi$ als Produkt von $3$-Zykeln geschrieben werden; das setze ich hier als bekannt voraus. Wir müssen das Problem also nur für $3$-Zykel lösen! Tatsächlich kann man aber jeden $3$-Zykel $(x\,y\,z)$ folgendermaßen als Kommutator zu schreiben: $(x\,y\,z) = (x \, y) (x \, z) (x \, y) (x \, z)$.

Beispiel 4

Betrachte die Kreislinie als abelsche Gruppe $S^1 = \{z \in \IC^* : |z|=1\}$. Für eine abelsche Gruppe $A$ sei $D(A) := \mathrm{Hom}(A,S^1)$ die zu $A$ duale Gruppe. Für jede endliche abelsche Gruppe $A$ gilt $D(A) \cong A$.
Der Struktursatz für endliche abelsche Gruppen impliziert, dass $ A \cong A_1 \oplus \cdots \oplus A_n$ mit endlichen zyklischen Gruppen $A_i$. Es bietet sich daher an, allgemein die duale Gruppe einer direkten Summe auszurechnen. Die universelle Eigenschaft der direkten Summe impliziert $D(\bigoplus_{i \in I} A_i) \cong \prod_{i \in I} D(A_i)$, was für endliche Indexmengen $I$ wie hier zugleich isomorph zu $\bigoplus_{i \in I} D(A_i)$ ist. Daher dürfen wir annehmen, dass $A$ eine endliche zyklische Gruppe ist, etwa erzeugt von einem Element $a$ der Ordnung $n$. Dann gilt $D(A) \cong \{z \in S^1 : z^n=1\}$ via $\varphi \mapsto \varphi(a)$. Das ist die Gruppe der $n$-ten Einheitswurzeln, die bekanntlich ebenfalls zyklisch der Ordnung $n$ ist mit dem Erzeuger $\exp(2\pi i/n)$. Sie ist also zu $A$ isomorph.

Beispiel 5

Seien $m,n,k \in \IN^+$ mit $m \mid n$ und $\mathrm{ggT}(k,m)=1$. Dann gibt es ein $k' \in \IN^+$ mit $k' \equiv k \bmod m$ mit $\mathrm{ggT}(k',n)=1$.
Weil jede positive natürliche Zahl sich (eindeutig) als Produkt von Primpotenzen schreiben lässt, liegt es nahe, erst einmal das Problem für Primpotenzen zu lösen und dann den allgemeinen Fall daraus abzuleiten. Wenn $n = p^t$ eine Primzahlpotenz ist, ist $m=p^s$ mit $0 \leq s \leq t$. Wenn $s=0$, können wir $k'=1$ nehmen. Ansonsten sind sowohl $\mathrm{ggT}(k,m)=1$ als auch $\mathrm{ggT}(k,n)=1$ zu $p \nmid k$ äquivalent, und wir können $k' = k$ nehmen. Im allgemeinen Fall sind $n = \prod_p p^{t_p}$ und $m=\prod_p p^{s_p}$ endliche Produkte von Primpotenzen, und es gibt jeweils ein $k'_p \in \IN^+$ mit $k'_p \equiv k \bmod p^{s_p}$ und $\mathrm{ggT}(k'_p,p^{t_p})=1$. Die $p^{s_p}$ sind aber paarweise teilerfremd. Wegen des chinesischen Restsatzes gibt es daher ein $k' \in \IN^+$ mit $k' \equiv k'_p \bmod p^{s_p}$ für alle $p$. Dann gilt $k' \equiv k \bmod m$ (weil das jeweils $\bmod p^{s_p}$ gilt) und $\mathrm{ggT}(k',n)=1$. Die Aussage ist übrigens äquivalent dazu, dass der von dem surjektiven Ringhomomorphismus $\IZ/n\IZ \to \IZ/m\IZ$ induzierte Homomorphismus auf den Einheitengruppen $(\IZ/n\IZ)^{\times} \to (\IZ/m\IZ)^{\times}$ surjektiv ist. Man könnte nun den Kontext verallgemeinern (diese Beweismethode besprechen wir weiter unten) und allgemeiner zeigen, dass für jeden surjektiven Homomorphismus $R \to S$ endlicher kommutativer Ringe auch der induzierte Homomorphismus $R^{\times} \to S^{\times}$ surjektiv ist.

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.

Führe einen Parameter ein

Diese Methode ist eng mit der vorigen verwandt, weil durch die Einführung eines Parameters natürlich die Aussage ebenfalls verallgemeinert wird. Vor allem aber stehen einem dann Techniken zur Verfügung, die ohne diesen Parameter gar nicht möglich wären. Man kann dieses Motto auch so formulieren: anstatt mit einem Objekt zu arbeiten, erkenne, dass es tatsächlich Teil einer ganzen Familie von Objekten ist, und arbeite stattdessen mit der Familie. \begin{tikzpicture} \draw[gray,rounded corners=5mm] (0.2,-1) -- (0.9,0) -- (1.9,0.8) -- (3.1,1.2) -- (4.3,1.3); \draw[fill=blue!10!white] (0.2,-1) circle [radius=3mm]; \draw[fill=blue!10!white] (0.9,0) circle [radius=3mm]; \draw[fill=blue!50!white] (1.9,0.8) circle [radius=3mm]; \draw[fill=blue!10!white] (3.1,1.2) circle [radius=3mm]; \draw[fill=blue!10!white] (4.3,1.3) circle [radius=3mm]; \end{tikzpicture}

Beispiel 1

Zeige, dass $1+3+5+\cdots + 2021$ ein Quadrat ist.
Auch wenn in dieser Aufgabe lediglich von einer einzigen Zahl die Rede ist: sie ohne weitere Hilfsmittel konkret auszurechnen, ist viel komplizierter als das allgemeinere Problem zu lösen, nämlich dass für jedes $n \in \IN$ die Summe der ersten $n$ ungeraden $\sum_{k=0}^{n-1} 2k+1$ ein Quadrat ist, genauer gesagt $n^2$. Das kann man zum Beispiel per Induktion beweisen oder auf die Summenformel von Gauß $\sum_{k=0}^{n} k = n(n+1)/2$ zurückführen. Oder man starrt einfach lange genug hier drauf: \begin{tikzpicture}[scale=0.6] \fill[blue!20!white] (0,0) -- (5,0) -- (5,5) -- (0,5) --cycle; \fill[blue!35!white] (0,0) -- (4,0) -- (4,4) -- (0,4) --cycle; \fill[blue!50!white] (0,0) -- (3,0) -- (3,3) -- (0,3) --cycle; \fill[blue!65!white] (0,0) -- (2,0) -- (2,2) -- (0,2) --cycle; \fill[blue!80!white] (0,0) -- (1,0) -- (1,1) -- (0,1) --cycle; \draw[gray] (0,0) grid (5,5); \end{tikzpicture}

Beispiel 2

Bestimme die Summe $\displaystyle\sum_{k=1}^{n} \frac{k}{2^k}$.
Tatsächlich ist es einfacher, allgemein für $x \neq 1$ die Summe $\displaystyle\sum_{k=1}^{n} k x^k$ zu bestimmen. Dazu leiten wir nämlich die geometrische Reihe $\displaystyle\sum_{k=0}^{n} x^k = \frac{x^{n+1}-1}{x-1}$ auf beiden Seiten ab und erhalten (mit den üblichen Ableitungsregeln) $\displaystyle \sum_{k=1}^{\infty} k x^{k-1} = \frac{(n+1) x^n (x-1) - (x^{n+1}-1)}{(x-1)^2} = \frac{n x^{n+1} - (n+1) x^n + 1}{(x-1)^2}$ Jetzt muss man nur noch beide Seiten mit $x$ multiplizieren. Anschließend kann man (zum Beispiel) $x = \frac{1}{2}$ einsetzen. Die Verallgemeinerung auf beliebige $x$ war hier notwendig, weil sich die Ableitung einer Funktion auch in einem festen Punkt auf die umgebenden Funktionswerte stützt. Ein ähnlicher Trick funktioniert bei Integralen:

Beispiel 3

Berechne das Integral $\displaystyle\int_{-\infty}^{\infty} \frac{1}{(x^2+1)^2} \, \mathrm{d}x$.
Der Trick besteht darin, die $1$ im Nenner durch einen Parameter $a > 0$ zu ersetzen. Dann können wir nämlich unter dem Integralzeichen differenzieren: $\begin{align*} \int_{-\infty}^{\infty} \frac{1}{(x^2+a)^2} \, \mathrm{d}x &= -\int_{-\infty}^{\infty} \frac{\mathrm{d}}{\mathrm{d}a} \frac{1}{x^2+a} \, \mathrm{d}x \\ & = -\frac{\mathrm{d}}{\mathrm{d}a} \int_{-\infty}^{\infty} \frac{1}{x^2+a} \, \mathrm{d}x \quad \mid x=\sqrt{a} y \\ & = - \frac{\mathrm{d}}{\mathrm{d}a} \frac{1}{\sqrt{a}} \int_{-\infty}^{\infty} \frac{1}{y^2+1} \, \mathrm{d}y \\ & = \frac{1}{2 a^{3/2}} \bigl( \arctan(\infty) - \arctan(-\infty) \bigr) \\ & = \frac{1}{2 a^{3/2}} \left( \frac{\pi}{2} - \frac{-\pi}{2} \right) \\ & = \frac{\pi}{2 a^{3/2}} \end{align*}$ Speziell für $a=1$ bekommen wir $\frac{\pi}{2}$ als Ergebnis. Diese Methode funktioniert bei vielen Integralen und ist auch als Feynmans Integral-Trick bekannt.

Beispiel 4

Berechne die Determinante der Matrix $\displaystyle\left(\frac{1}{i+j}\right)_{1 \leq i,j \leq n}$.
Wir ersetzen hierfür die konkreten natürlichen Zahlen im Nenner durch polynomielle Variablen und berechnen allgemeiner die Determinante der Matrix $\displaystyle\left(\frac{1}{X_i + Y_j} \right)_{1 \leq i,j \leq n}$ über dem Funktionenkörper $K(X_1,\dotsc,X_n,Y_1,\dotsc,Y_n)$, wobei $K$ irgendein Körper ist. Zunächst bringen wir, für jedes $i$, die Einträge der $i$-ten Zeile auf ihren Hauptnenner $H_i := \prod_k (X_i + Y_k)$ und ziehen diesen aus der Determinante heraus. Wir erhalten damit $\displaystyle \det\left(\frac{1}{X_i + Y_j} \right)_{1 \leq i,j \leq n} = \frac{1}{H_1 \cdots H_n} \det\left(\frac{H_i}{X_i + Y_j}\right)_{1 \leq i,j \leq n} = \frac{1}{\prod_{i,j} (X_i+Y_j)} \det\left(\prod_{k \neq j} (X_i+Y_k) \right)_{1 \leq i,j \leq n}$ Die verbleibende Determinante bezieht sich auf eine Matrix $M := (\prod_{k \neq j} (X_i+Y_k))_{i,j}$ über dem Polynomring $K[X_1,\dotsc,X_n,Y_1,\dotsc,Y_n]$. Die folgenden Argumente beruhen ganz wesentlich darauf, dass wir es mit Polynomen zu tun haben. Wenn wir für ein Indexpaar $i < p$ die Variable $X_p$ in $X_i$ überall in der Matrix $M$ einsetzen würden, würde die $i$-te mit der $p$-ten Zeile zusammenfallen, die Determinante also $0$ werden. Daher hat $\det(M)$, aufgefasst als Polynom in der Variablen $X_i$ über dem Polynomring in den restlichen Variablen, als Nullstelle $X_p$. Es folgt $X_i - X_p \mid \det(M)$. Das gilt für alle Indexpaare $i < p$, und weil die $X_i - X_p$ paarweise teilerfremd sind, folgt sogar $\prod_{i < p} (X_i - X_p) \mid \det(M)$. Wir benennen den Index $p$ nun in $j$ um. Nun könnten wir unser bisheriges Vorgehen aber auch genauso gut über Spalten (statt Zeilen) aufbauen, der Hauptnenner $\prod_{i,j} (X_i + Y_j)$ über alle Spalten wäre derselbe. Daher können wir analog schließen, dass auch $\prod_{i < j} (Y_i - Y_j) \mid \det(M)$. Mit der Teilerfremdheit folgt schließlich $(\ast) \qquad \det(M) = Q \cdot \prod_{i < j} (X_i - X_j) (Y_i - Y_j)$ für ein Polynom $Q \in K[X_1,\dotsc,X_n,Y_1,\dotsc,Y_n]$. Nun vergleichen wir einmal die Grade auf beiden Seiten: Es gilt $\deg \prod_{i < j} (X_i - X_j) (Y_i - Y_j) = \sum_{i < j} \deg((X_i - X_j)(Y_i - Y_j)) = \sum_{i < j} 2 = \frac{n(n-1)}{2} \cdot 2 = n(n-1).$ Es gilt also $\deg \det(M) =\deg Q + n(n-1)$. Wegen $\deg M_{i,j} = \deg \prod_{k \neq j} (X_i+Y_k) = n-1$ folgt mit der Leibniz-Formel aber $\deg \det(M) \leq n(n-1).$ Daher ist $\deg(Q) \leq 0$ und damit $Q \in K$. Wir müssen also nur noch diese Konstante bestimmen! Das geht nun einfach dadurch, indem wir $-X_i$ für $Y_i$ einsetzen, also formal einen Homomorphismus $\varphi$ nach $K[X_1,\dotsc,X_n]$ durch $X_i \mapsto X_i$ und $Y_i \mapsto -X_i$ definieren, der ja Konstanten wie unser $Q$ unberührt lässt. Dann ist $M_{i,j}^{\varphi} = \prod_{k \neq j} (X_i - X_k) = 0$ für $i \neq j$. Also wird $M^{\varphi}$ eine Diagonalmatrix und wir sehen $\det(M^{\varphi}) = \prod_i M_{i,i}^{\varphi} = \prod_{i \neq j} (X_i - X_j) = \prod_{i < j} (X_i-X_j) (-X_i-(-X_j))$ Vergleichen wir das mit unserer Definition von $Q$ in $(\ast)$ oben, folgt $Q=1$. Damit ist $\det(M)=\prod_{i < j} (X_i - X_j) (Y_i - Y_j)$ und folglich $\displaystyle \det\left(\frac{1}{X_i + Y_j} \right)_{1 \leq i,j \leq n} = \frac{\prod_{i < j} (X_i - X_j)(Y_i - Y_j)}{\prod_{i,j} (X_i + Y_j)}.$ Jetzt können wir insbesondere (zum Beispiel für $K=\IQ$) die Werte $X_i=i$, $Y_i=i$ einsetzen und erhalten $\displaystyle \det\left(\frac{1}{i+j} \right)_{1 \leq i,j \leq n} = \frac{\prod_{i < j} (i-j)^2}{\prod_{i,j} (i+j)}.$ Das ist tatsächlich ein Stammbruch. Der Kehrwert ist die OEIS-Folge A067689. Mit derselben Methode, nur viel schneller, kann man auch die Vandermonde-Determinante bestimmen.

Beispiel 5

Für zusammenhängende ebene endliche Graphen gilt die die Eulersche Formel $V-E+F=2$, wobei $V,E,F$ die Anzahl der Ecken (vertices), Kanten (edges) bzw. Flächen (faces) von $G$ sei.
Die "äußere Fläche" wird hier bei $F$ mitgezählt. Im üblichen induktiven Beweis hierfür entfernt man solange Kanten, bis man einen Baum erhält, ohne dass sich der Wert von $V-E+F$ verändert, und zeigt dann die Formel für Bäume. Wir müssen aber gar keinen Umweg über Bäume (nichts gegen Bäume!) gehen, wenn wir die allgemeinere Formel $V-E+F=1+C$ für ebene Graphen zeigen, wobei $C$ die Anzahl der Zusammenhangskomponenten sei (das ist der zusätzliche Parameter). Der induktive Beweis verläuft nun so: Wenn es keine Kante gibt, also nur $V$ voneinander isolierte Ecken, ist $E=0$, $F=1$, $C=V$, die Formel passt. Andernfalls benutzen wir die Induktionsannahme für den Graphen, der durch Entfernen einer Kante entsteht. Wenn sie Teil eines Kreises war, erhalten wir nach Induktionsannahme $V -( E-1 ) + (F-1) = 1 + C$ und damit die Behauptung. Wenn sie nicht Teil eines Kreises war, erhalten wir nach Induktionsannahme $V - (E-1) + F = 1 + (C+1)$ und damit wieder die Behauptung. Der Punkt ist, dass, selbst wenn wir mit einem zusammenhängenden Graphen hier starten, das Entfernen einer Kante früher oder später den Zusammenhang zerstören wird, der Beweis also ohne die Verallgemeinerung gar nicht funktionieren würde.

Verallgemeinere den Kontext

Diese Methode hängt eng mit der vorigen zusammen, geht aber noch einen Schritt weiter. Hier werden nicht nur irgendwelche Parameter eingeführt oder angepasst, damit der Beweis möglich wird. Vielmehr wird der gesamte Kontext verallgemeinert, man kann auch sagen abstrahiert. Von dem offensichtlichen Vorteil abgesehen, dass eine in diesem Kontext bewiesene Aussage mehr Anwendungsfälle besitzt, ergeben sich auch beweistechnisch Vorteile: Es kommt nämlich oft dazu, dass aufgrund der Verallgemeinerung (wenn man sie richtig gemacht hat) alle für den Beweis irrelevanten Strukturen wegfallen und nur noch das Wichtige übrig bleibt – wodurch der Beweis also einfacher zu finden ist. \begin{tikzpicture} \draw[fill=blue!50!white, rounded corners=4mm] (0.1,0) -- (0.8,-0.7) -- (0,-0.8) -- (-1,-0.5) -- (-0.1,0) -- (-0.9,0.9) -- (0,1.2) -- (0.9,0.9) --cycle; \draw[fill=blue!10!white] (2,-1) -- (3,-1) -- (3,0) -- (2,0) --cycle; \draw[fill=blue!10!white] (2.35,0) -- (2.35,0.3) -- (2.65,0.3) -- (2.65,0) -- (2.35,0); \draw[fill=blue!10!white] (2,0.3) -- (3,0.3) -- (3,1.3) -- (2,1.3) --cycle; \end{tikzpicture} Auch der Umgang mit den beteiligten mathematischen Objekten selbst fällt leichter, wenn sie allgemeiner gehalten sind (jedenfalls mit etwas Übung): Wenn zum Beispiel $\IR$ in einer Aussage vorkommt, ist erst einmal unklar, welche von den zahlreichen Strukturen auf $\IR$ (Gruppenstruktur(en), Körperstruktur, Ordnung, Topologie, Lebesgue-Maß usw.) überhaupt für den Beweis relevant ist; aber wenn lediglich von einer beliebigen Gruppe zum Beispiel die Rede ist, ist der Fokus sofort auf die Gruppenstruktur gelegt. Das bedeutet zusammengefasst, dass sich der "Beweistunnel" verengt. Die Kunst ist natürlich, die "richtige" Verallgemeinerung zu finden. Dafür ist einiges an mathematischer Erfahrung nötig, aber die hier vorgestellten Beispiele sind relativ einfach gehalten, und Übung macht bekanntlich die Meisterin. Die mathematische Logik und die Kategorientheorie haben sich das Motto "Verallgemeinere den Kontext" quasi einverleibt, und die Beispiele hier könnte man in diesem Rahmen sogar noch weiter auf ein ganz anderes Level verallgemeinern, aber das würde den Rahmen dieses Artikels sprengen, der nur einen ersten Einblick in diese Denkweise geben soll.

Beispiel 1

Die Menge $\IR$ wird mit der Verknüpfung $m(a,b) := a+b-1$ eine Gruppe.
Natürlich kann man das einfach nachrechnen, aber viel klarer wird der Zusammenhang mit der Schreibweise $m(a,b)=(a-1)+(b-1)+1$ und der folgenden Verallgemeinerung (die man ohnehin kennenlernen sollte), die wir dann auf die additive Gruppe $(\IR,+)$ anwenden werden: Sei $(X,\cdot)$ eine (multiplikativ geschriebene) Gruppe, $f : X \to Y$ eine bijektive Abbildung. Dann ist $(Y,\ast)$ mit der Verknüpfung $a \ast b := f(f^{-1}(a) \cdot f^{-1}(b))$ eine Gruppe. Wie sollte die Definition auch anders lauten? Wir müssen ja aus unseren beiden Elementen von $Y$ irgendwie Elemente in $X$ konstruieren, dort verknüpfen und dann wieder ein Element aus $Y$ erzeugen, und dafür gibt es nur eine Möglichkeit. Das neutrale Element ist $f(1)$ (was sonst?), wenn $1$ das neutrale Element von $(X,\cdot)$ ist, und es gilt $y^{-1}=f(f^{-1}(y)^{-1})$ (was sonst?). Der Beweis der Aussage schreibt sich von alleine hin (also mit der Methode aus meinem ersten Artikel). Was man hier auch noch nebenbei mitbeweist, ist, dass $f : (X,\cdot) \to (Y,\ast)$ ein Isomorphismus von Gruppen ist. Für das Beispiel $m$ könnte das neutrale Element erst einmal alles mögliche sein (man muss es ausrechnen), und das zu $a$ inverse Element (übrigens $2-a$) fällt wohl auch nicht direkt ins Auge, eben weil die Situation viel zu speziell ist und es daher viel zu viele Möglichkeiten gibt. Indes sehen wir auch, dass für jede reelle Zahl $c$ die Funktion $f : \IR \to \IR$, $f(x) := x+c$ bijektiv ist, und daher $m(a,b) := f(f^{-1}(a)+f^{-1}(b)) = a+b-c$ eine Gruppenverknüpfung auf $\IR$ ist.

Beispiel 2

Für beschränkte Teilmengen $A \subseteq \IR$ gilt die Beziehung $\sup(-A) = -\inf(A)$.
Anstatt das ad hoc nachzurechnen, überlegen wir uns allgemeiner zwei Aussagen (die man auch in einer Aussage zusammenfassen könnte, aber ich mag Antiisomorphismen nicht sonderlich). Erstens: Seien $(X,\leq),(Y,\leq)$ zwei partielle Ordnungen, und sei $f : (X,\leq) \to (Y,\leq)$ ein Isomorphismus (oder noch allgemeiner eine Galoisverbindung). Wenn $A \subseteq X$ ein Supremum besitzt, dann auch $f(A) \subseteq Y$, und es gilt $\sup(f(A)) = f(\sup(A)).$ Der Beweis schreibt sich wegen der allgemeinen Situation von selbst hin: $f(\sup(A))$ ist kleinste obere Schranke von $f(A)$ weil für alle $y \in Y$ gilt: $f(\sup(A)) \leq y \iff \sup(A) \leq f^{-1}(y) \iff \forall a \in A (a \leq f^{-1}(y)) \iff \forall a \in A (f(a) \leq y)$ Zweitens, ein formales Dualisierungsprinzip: Für eine partielle Ordnung $(X,\leq)$ kann man immer die umgedrehte partielle Ordnung $(X,\geq)$ bilden, wobei per Definition $x \geq y \iff y \leq x$. Für $A \subseteq X$ gilt dann (der Index deutet hier an, in Bezug auf welche Ordnung wir das Supremum bzw. Infimum bilden) $\sup_{(X,\leq)}(A)=\inf_{(X,\geq)}(A).$ Der Beweis schreibt sich von alleine hin. Kombinieren wir die beiden Aussagen und wenden sie auf den Isomorphismus von Ordnungen $f : (\IR,\leq) \to (\IR,\geq)$, $f(x) := -x$ an, so ergibt sich daraus sofort die behauptete Gleichung. Und nicht nur das, wir können die genannten Aussagen auch in vielen anderen Kontexten anwenden. Für den Isomorphismus von Ordnungen $f : (\IR^*,\leq) \to (\IR^*,\geq)$, $f(x) := 1/x$ erhalten wir zum Beispiel für $A \subseteq \IR^*$ die Beziehung $\inf(A)^{-1} = \sup(A^{-1}).$

Beispiel 3

Sei $A$ eine endliche partielle Ordnung und $f : A \to A$ eine monoton wachsende bijektive Abbildung. Dann ist $f$ ein Isomorphismus von partiellen Ordnungen (also $f(a) \leq f(a') \iff a \leq a'$).
Wir müssen zeigen, dass $f^{-1} : A \to A$ ebenfalls monoton wachsend ist. Wenn man hier versucht, irgendwie mit Elementen in $A$ herumzurechnen, wird man nicht zum Ziel kommen. Ein genereller Tipp ist: wann immer man eine Abbildung $f : A \to A$ hat, sollte man sich die Iterationen $f \circ f$, $f \circ f \circ f$, usw. anschauen, also die Folge $f^k : A \to A$ mit $k \in \IN$ (wobei $f^0 = \mathrm{id}_A$). Nun wissen wir, dass $A$ endlich ist (und ohne diese Annahme gilt die Behauptung auch nicht), also kann es nur endlich viele Abbildungen $A \to A$ geben. Es muss daher zwei natürliche Zahlen $k < n$ geben mit $f^k = f^n$. Jetzt müssen wir die bisher noch nicht verwendete Bijektivität von $f$ ins Spiel bringen und folgern $f^{-1} = f^{n-k-1}$. Also ist $f^{-1}$ eine Verkettung von monoton wachsenden Abbildungen und daher ebenfalls monoton wachsend. Der Beweis ist damit abgeschlossen, aber auffällig ist, dass wir hier kaum über die Axiome einer partiellen Ordnung gesprochen haben. Und tatsächlich kann man eine viel allgemeinere Aussage beweisen: Wann immer wir es mit "strukturierten" Mengen mit "strukturerhaltenden" Abbildungen zwischen ihnen zu tun haben, welche unter endlichen Kompositionen abgeschlossen sind (zum Beispiel Gruppen mit Gruppenhomomorphismen, topologische Räume mit stetigen Abbildungen, Graphen mit Graphhomomorphismen, usw.), dann gilt bereits: Wenn $A$ eine endliche strukturierte Menge und $f : A \to A$ eine bijektive strukturerhaltende Abbildung ist, dann ist auch $f^{-1}$ strukturerhaltend. Es ist einfach derselbe Beweis wie vorher, nur dass wir eben nicht dazu verleitet sind, irgendwelche Spezialitäten von partiellen Ordnungen auszunutzen.

Beispiel 4

Sei $G$ eine Gruppe, $U$ eine Untergruppe von $G$, und $N$ ein Normalteiler von $G$. Dann ist $U \cap N$ ein Normalteiler von $U$.
Es ist zwar einfach, das direkt anhand der Definitionen nachzurechnen, aber der Punkt ist, dass es hier eine allgemeinere Aussage gibt, die (1) mindestens genauso einfach zu beweisen ist, (2) durch ihre Allgemeinheit viel mehr Anwendungen besitzt, zum Beispiel bei der Bestimmung der Normalteiler einer Quotientengruppe, (3) sich (meiner Ansicht nach) viel einfacher merken lässt: Urbilder von Normalteilern unter Homomorphismen sind Normalteiler. Also wenn $\varphi : H \to G$ ein Homomorphismus von Gruppen und $N \subseteq G$ ein Normalteiler ist, dann ist auch $\varphi^{-1}(N) \subseteq H$ ein Normalteiler. Wendet man das für eine Untergruppe $U \subseteq G$ auf die Inklusionsabbildung $i : U \hookrightarrow G$ an, bekommt man gerade die erste Aussage, weil offenbar $i^{-1}(N) = U \cap N$ gilt. Der Beweis der allgemeinen Aussage ergibt sich von selbst, weil die beiden Gruppen $H$ und $G$ voneinander getrennt sind (also nicht Untergruppen voneinander), $\varphi$ zwischen ihnen vermittelt, und es daher selbstverständlich ist, dass im Beweis jeder Teil der Definition eines Normalteilers mittels $\varphi$ übertragen werden muss. Wenn wir uns in nur einer Gruppe aufhalten würden und kein Homomorphismus in Sicht wäre, hätte man viel mehr Freiheiten, irgendwelche Elemente miteinander zu multiplizieren, ohne dass das zielführend wäre. Bemerkenswert ist hier außerdem, dass es sogar einen Beweis der allgemeineren Aussage gibt, der fast ohne Rechnung auskommt. Wir müssen lediglich als bekannt voraussetzen, dass eine Teilmenge einer Gruppe genau dann ein Normalteiler ist, wenn sie der Kern eines Homomorphismus auf dieser Gruppe ist. Mit dieser Charakterisierung ist die Behauptung äquivalent dazu, dass es für alle Homomorphismen $\varphi : H \to G$, $\psi : G \to K$ einen Homomorphismus $\alpha : H \to K$ gibt mit $\ker(\alpha) = \varphi^{-1}(\ker(\psi))$. Wir haben keine andere Wahl als $\alpha := \psi \circ \varphi : H \to K$ zu definieren, und die Gleichung $\ker(\alpha) = \varphi^{-1}(\ker(\psi))$ bestätigt sich unmittelbar mit den Definitionen: $\ker(\psi \circ \varphi) = \{h \in H : \psi(\varphi(h)) = 1 \} = \{h \in H : \varphi(h) \in \ker(\psi)\} = \varphi^{-1}(\ker(\psi)).$

Beispiel 5

Sei $A \in M_n(\IR)$ eine nilpotente Matrix. Dann ist $E+A$ invertierbar (mit $E = $ Einheitsmatrix).
In dieser Formulierung denkt man vermutlich zunächst an einen Beweis mit Methoden aus der linearen Algebra. Und das ist auch möglich. Die Beweisschritte lauten: (1) Jede nilpotente Matrix ist ähnlich zu einer strikten oberen Dreiecksmatrix. (2) Wenn die Behauptung für eine Matrix gilt, dann auch für jede dazu ähnliche Matrix. (3) Für eine strikte obere Dreiecksmatrix $A$ ist $E+A$ eine obere Dreiecksmatrix mit Einsen auf der Diagonale. (4) Eine solche Matrix ist invertierbar (sie hat offenbar vollen Rang). Der Punkt ist allerdings wieder, dass man eine viel allgemeinere Aussage beweisen kann, und dabei auch viel weniger zu tun ist: Sei $R$ ein Ring und $a \in R$ nilpotent. Dann ist $1+a$ invertierbar. Indem wir $a$ durch $-a$ substituieren (was ebenfalls nilpotent ist), sehen wir, dass wir lediglich die Invertierbarkeit von $1-a$ zeigen müssen. Wenn aber $a^n=0$, dann liefert die geometrische Reihe den Ansatz $(1-a)^{-1} = 1+a+a^2+\dotsc+a^{n-1}$ (wegen $a^n=0$ verschwinden alle höheren Terme). Dass das Element auf der rechten Seite tatsächlich zu $1-a$ invers ist, liegt an der allgemeinen Formel $(1+a+a^2+\dotsc+a^{n-1})(1-a)=1-a^n$. Wenn man hier weder auf die Substitution noch auf die geometrische Reihe kommt, kann man auch den Ansatz $(1+a)b=1$ machen. Er führt zu $b=1-ab = 1-a(1-ab)=1-a(1-a(1-ab)) = \cdots = 1-a+a^2 \pm \cdots$.

Schluss

Es gibt noch viele weitere Beweismotive, aber das scheinen mir die wichtigsten zu sein. Kennt ihr weitere Beweismotive, die sich immer wieder anwenden lassen? Konkrete Techniken wie etwa Induktion oder auch komplizierte Techniken wie Grothendiecks Dévissage würde ich hier gerne einmal ausklammern, sondern die Frage stellen, welche grundsätzlichen Denkweisen immer wieder in Beweisen vorkommen.
Danke an tactac fürs Korrekturlesen!

\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Beweistechnik :: Beweistechniken :
Typische Beweismotive [von Triceratops]  
@import url('dl.php?id=2308');Dies ist die Fortsetzung des Artikels Wie man einfache Beweise ohne Mühe finden kann. Dort ging es um einfache Beweise, die sich schon alleine durch eine gute "Buchführung" der Definitionen, Voraussetzungen und Behauptungen hinschreiben lassen. In
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 854
 
Aufrufstatistik des Artikels
Insgesamt 6 externe Seitenaufrufe zwischen 2021.07 und 2021.10 [Anzeigen]
DomainAnzahlProz
https://google.com350%50 %
https://matheplanet.com116.7%16.7 %
https://google.de233.3%33.3 %

Aufrufer der letzten 5 Tage im Einzelnen
Insgesamt 3 Aufrufe in den letzten 5 Tagen. [Anzeigen]
DatumAufrufer-URL
2021.10.08-2021.10.28 (3x)https://google.com/

[Top of page]

"Mathematik: Typische Beweismotive" | 5 Comments
The authors of the comments are responsible for the content.

Re: Typische Beweismotive
von: Kezer am: So. 20. Juni 2021 17:25:06
\(\begingroup\)Schöner Artikel wie immer, den ich noch komplett lesen muss, wenn ich mehr Zeit habe. Ein wichtiges Beweismotiv ist wahrscheinlich "Finde/Zeichne das richtige Bild". Passend zum Abschnitt "Verallgemeinere den Kontext" finde ich noch den berühmten Beweis zu Desargues Satz bzgl. der Perspektivität von Punkten und Geraden in der projektiven Geometrie. Es ist (a priori) eine zwei-dimensionale Aussage, aber man kann den Beweis in 3D führen und sieht zugleich ein intuitives Bild! (Die Antwort von Stillwell auf MO/28788 enthält ein schönes Bild.)\(\endgroup\)
 

Re: Typische Beweismotive
von: Saki17 am: Mo. 21. Juni 2021 00:13:30
\(\begingroup\)Sehr schöner Artikel; werde ich später genauer lesen. Hättest du vielleicht vor, einen Artikel von ähnlichem Stil über die Berechnung der (Ko)Homologie zu schreiben?\(\endgroup\)
 

Re: Typische Beweismotive
von: nzimme10 am: Mi. 23. Juni 2021 13:23:10
\(\begingroup\)Hallo Martin, wie immer ein toller Artikel. Vermutlich hast du das in dem Artikel zumindest zwischen den Zeilen bei "Führe einen Parameter ein" schon so oder so ähnlich gesagt, aber: Was ich manchmal hilfreich finde ist wann immer man zusätzliche Dinge zu seinen Überlegungen hinzugefügt hat, die einem weitergeholfen haben (eben z.B. einen neuen Parameter), so kann es manchmal hilfreich sein, die gesamte Frage im Kontext der hinzugefügten Dinge neu zu formulieren. Ein Beispiel dafür ist z.B. diese Frage. Liebe Grüße, Nico\(\endgroup\)
 

Re: Typische Beweismotive
von: AlphaSigma am: Sa. 24. Juli 2021 17:13:16
\(\begingroup\)Hallo Triceratops, ein sehr schöner Artikel. Im Beispiel 2 ist der Satz "... eine Orthonornalbasis kann auch gesehen werden als ein orthogonaler (also Skalarprodukt-erhaltener) Isomorphismus zu $\IR^n$ mit dem Standardskalarprodukt." etwas ungenau formuliert. Eine Basis ist eine Menge von Vektoren und ein Isomorphismus ist eine Abbildung zwischen zwei Vektorräumen. Die beiden Begriffe kann man nicht als gleich ansehen. P.S. In "Orthonornalbasis" ist noch ein Tippfehler.\(\endgroup\)
 

Re: Typische Beweismotive
von: Triceratops am: Sa. 24. Juli 2021 23:55:38
\(\begingroup\)Vielen Dank für das Feedback! @AlphaSigma: Mit "kann angesehen werden als" war "entspricht" gemeint. Ich habe es geändert.\(\endgroup\)
 

 
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]