Korrektheit eines Beweises

14.12.2006, 16:44

papahuhn

Korrektheit eines Beweises

Hallo zusammen,
ich beschäftige mich gerade mit einem Beweis aus dem Bereich der Informatik, habe aber ein logisches Problem ihn nachzuvollziehen.
Ich werde versuchen, mich auf den Kern zu beschränken, damit ihr das Infozeug ignorieren könnt.

Es gibt einen Algorithmus, der eine streng monoton steigende Folge $\begin{eqnarray*} (x_i) \end{eqnarray*}$ erzeugt. Das Ziel des Beweises ist, eine Ungleichung $\begin{eqnarray*} c \geq C \end{eqnarray*}$ zu zeigen, wobei $\begin{eqnarray*} c \end{eqnarray*}$ eine bestimmte Eigenschaft des Algorithmus ist, und $\begin{eqnarray*} C \end{eqnarray*}$ eine bekannte Konstante.

Aus informatischen Überlegungen ergibt sich eine Familie von Ungleichungen, die eine weitere Familie von Ungleichungen $\begin{eqnarray*} U_i \end{eqnarray*}$ impliziert, die "schöner" aussehen. Der Autor konstruiert die Ungleichung $\begin{eqnarray*} U_{i+1} \end{eqnarray*}$ aus den ursprünglichen Ungleichungen und den neuen Ungleichungen $\begin{eqnarray*} U_1, \hdots, U_i \end{eqnarray*}$ . Aus dieser Konstruktion ergibt sich eine natürliche Notation für $\begin{eqnarray*} U_i \end{eqnarray*}$ , nämlich $\begin{eqnarray*} U_i : x_{i+1} \leq \alpha_i x_i \end{eqnarray*}$ . Die Koeffizienten $\begin{eqnarray*} \alpha_i \end{eqnarray*}$ ergeben sich ebenso natürlich (rekursiv) aus der Konstruktion. $\begin{eqnarray*} \alpha_{i+1} \end{eqnarray*}$ hängt nur von $\begin{eqnarray*} \alpha_i \end{eqnarray*}$ und von $\begin{eqnarray*} c \end{eqnarray*}$ ab, $\begin{eqnarray*} \alpha_1 \end{eqnarray*}$ nur von $\begin{eqnarray*} c \end{eqnarray*}$ .

Da man weiss, dass die Folge $\begin{eqnarray*} (x_i) \end{eqnarray*}$ streng monoton steigt, folgt aus den Ungleichungen $\begin{eqnarray*} U_i \end{eqnarray*}$ , dass $\begin{eqnarray*} \alpha_i > 1 \end{eqnarray*}$ sein muss. Aus der Annahme, dass $\begin{eqnarray*} c \leq C \end{eqnarray*}$ ist, kann man rein analytisch folgern, dass $\begin{eqnarray*} \alpha_i \end{eqnarray*}$ monoton fällt und somit gegen ein $\begin{eqnarray*} \alpha \end{eqnarray*}$ konvergiert. Aus der Existenz von $\begin{eqnarray*} \alpha \end{eqnarray*}$ lässt sich wiederum rein analytisch folgern, dass $\begin{eqnarray*} c \geq C \end{eqnarray*}$ gilt, und der Beweis ist vollbracht.

Ich hoffe, ihr habt noch nicht abgeschaltet, denn jetzt kommt mein Problem.
Die Folge $\begin{eqnarray*} (\alpha_i) \end{eqnarray*}$ hängt nicht von der Folge $\begin{eqnarray*} (x_i) \end{eqnarray*}$ ab. Dass $\begin{eqnarray*} \alpha_i > 1 \end{eqnarray*}$ ist, hat also nichts mit $\begin{eqnarray*} (x_i) \end{eqnarray*}$ zu tun. Ebenso hat es nichts mit $\begin{eqnarray*} (x_i) \end{eqnarray*}$ oder dem Algorithmus zu tun, dass $\begin{eqnarray*} (\alpha_i) \end{eqnarray*}$ monoton fällt; das hängt alleine von $\begin{eqnarray*} c \end{eqnarray*}$ ab. $\begin{eqnarray*} (\alpha_i) \end{eqnarray*}$ ist zwar "natürlich" aus der Konstruktion der $\begin{eqnarray*} U_i \end{eqnarray*}$ entstanden, aber die Monotonie und Konvergenz ändern sich ja nicht, selbst wenn $\begin{eqnarray*} (x_i) \end{eqnarray*}$ plötzlich ganz anders aussieht. Im Grunde habe ich also irgendeine konvergente und von $\begin{eqnarray*} c \end{eqnarray*}$ abhängige Folge hergenommen und gezeigt, dass meine gewünschte Ungleichung aus ihrer Konvergenz folgt, vollkommen ohne Bezug zum Algorithmus. Ich denke, da ist etwas faul.

Was meint ihr?

14.12.2006, 20:32

Korrektheit eines Beweises

Verwandte Themen