Beweis durch Induktion über die Länge einer Formel $\phi$.

Question

Arbeit an dem Buch: Derek Goldrei. " Aussagen- und Prädikatenrechnung "

Auf P. In 19 wird das Induktionsprinzip wie folgt angegeben:

Beweisen Sie das nach wie vor $0 \in A$ und dann beweise das für alle $n \in A$, wenn $k \in A$ für alle $k \leq n$, dann $k \in A$ für alle $k \leq n + 1$, um daraus zu schließen $A = N$.

Auf P. 32, vor dem Nachweis:

Satz 2.1 Beliebige Formel$\phi$ enthält eine gleiche Anzahl von linken Klammern (und rechten Klammern).

der Autor erklärt

Zeigen Sie zunächst, dass das Ergebnis für alle Formeln der Länge 0 gilt - die Basis der Induktion. Dann machen wir den induktiven Schritt: Nehmen wir an, dass das Ergebnis für alle Formeln des gegebenen Typs mit Länge gilt$\leq n$ - Dies ist die Induktionshypothese für $n$ - und aus dieser Show, dass es für alle Formeln der Länge gilt $\leq n + 1$. Da wir davon ausgehen, dass die Hypothese für alle Längenformeln gilt$\leq n$Dies läuft darauf hinaus zu zeigen, dass die Hypothese für Formeln gilt, deren Länge genau ist $n + 1$.

Vielleicht fehlt mir etwas, aber ich denke gewöhnlich als das Prinzip der Induktion auf diese Weise. Eine Immobilie beweisen$P$ gilt für alle $n \in \mathbb{N}$, beläuft sich auf:

• Show $P(0)$ hält.
• Show $\forall k \in \mathbb{N}(k \geq 0 \land P(k) \to P(k + 1))$

Meine Fragen sind also:

• Inwiefern hängt die vom Autor verwendete Definition mit der gemeinsamen Definition des Beweises durch Induktion zusammen?

• Ich war es gewohnt zu sehen $k \geq 0$ und nicht $k \leq n$. Wird diese Annahme verwendet$\leq$ in irgendeiner Weise verwandt mit $k \geq 0$?

Answer 1

Die Definition des Autors entspricht logisch der üblichen.

Es ist nur "stärker" in dem Sinne, dass es das Anwenden der Induktion erleichtert. Seine Definition kann in einigen Fällen sehr nützlich sein, z. B. wenn der Beweis dafür$N+1$ erfordert, dass Sie wissen, dass die Aussage nicht nur für gilt $N$, aber auch für einige kleinere Werte als $N$ (sagen wir für $N-1$ und $N-2$).

In diesem Fall unter der Annahme, dass die Aussage für alle gilt $k \le N$ macht das Leben leichter.

Ich sage "stärker" (in Anführungszeichen), weil es nicht wirklich stärker ist, ich habe nur gesagt, dass es logisch äquivalent ist. In einigen Fällen ist es nur bequemer.

Dieser Beweis, zB mit der Anzahl der Klammern, scheint ein solcher Fall zu sein.