Wann kann die Koinduktionshypothese verwendet werden?

Question

Wir können die Induktionshypothese verwenden, wenn wir eine Eigenschaft für eine wohlgeordnete Struktur beweisen.Mir ist bewusst, dass es dafür einen Beweis gibt.

Wenn es um Koinduktion geht, bin ich verwirrt.

Eine der Antworten auf eine andere Frage "Was ist Coinduktion?" erwähnt, dass es eine Vorstellung von einer kursiven Definition gibt, die wohlgeformt sein muss.

Viele Dinge, die ich im Zusammenhang mit Koinduktion lese (versuche), sprechen hauptsächlich von Bisimulation und Äquivalenz.Aber nach meinem besten Wissen versuchen diese, eine Beziehung für zwei koinduktive Datenstrukturen zu beweisen.Zum Beispiel beweisen sie, dass zwei Ströme äquivalent sind.Und die koinduktive Hypothese leitet sich irgendwie von einer Hypothese der Bisimulation ab.Trotzdem glaube ich, dass ich immer noch verloren bin in Bezug auf die Anforderungen dessen, was Wohlgeformtheit in der koinduktiven Welt ausmacht.

Ich kann irgendwie sehen, dass die Koinduktionshypothese funktioniert, wenn solche Sätze bewiesen werden, aber mir ist immer noch unklar, wann sie verwendet werden können, um allgemeinere Sätze wie die in erwähnte zu beweisen Was ist Coinduktion?.In diesem Zusammenhang besagt der Satz, dass "etwas unendlich ist".Dies scheint eine allgemeinere Form der Aussage zu sein, die man beweisen möchte.

Eine möglicherweise verwandte Frage ist, ob ein Satz konvertiert und als Äquivalenzsatz neu formuliert werden kann oder nicht.

Gibt es eine einfache informelle Argumentation, die erklärt, warum die Koinduktion für einige Wohlgeformtheitsanforderungen funktioniert?

Ich hoffe auf eine Erklärung, wenn möglich: https://math.stackexchange.com/questions/432293/well-ordering-and-mathematical-induction/432302#432302.

Answer 1

Lassen Sie mich zunächst an die kleinsten und größten Fixpunkte für erinnern $\subseteq$.Wir arbeiten relativ zu einem Satz $U$, Universum.Bei (ko)induktiven Definitionen, $U$ ist die Menge aller Begriffe.Funktion $f: 2^U\bis 2^U$ (aus Teilmengen von $U$ zu Teilmengen von $U$) is monoton, wenn $A eilmenge Q B$ impliziert immer $f(A) eilmenge q f(B)$.A Fixpunkt von $f$ ist ein set $Ein$ so dass $ f (EIN) = EIN $.

Für monotone $f$ es gibt immer einen am wenigsten festen Punkt $\mu f$, nämlich die Schnittmenge aller $A eilmenge Q U$ so dass $f(A) eilmenge q A$. Mindestens bedeutet, dass für beliebige Fixpunkte $F$ wir haben immer $\mu f eilmenge q F$.

Lassen Sie zum Beispiel $f_{ t nat}$ definiert werden durch $f_{ t nat}(A)=\{0\} asse\{n+1\ Mitte n\ in A\}$.Funktion $f_{ t nat}$ ist die einstufige Schließfunktion unter den Konstruktoren $0$ und $+1$.Bedingung $f_{ t nat}(A) eilmenge q A$ bedeutet, dass $Ein$ ist unter den Konstrukteuren geschlossen $0$ und $+1$.Der Schnittpunkt bedeutet, dass die $\mu f_{ t nat}$ enthält nur die Elemente, die in jeder Menge unter den Konstruktoren geschlossen sind.Dies sind zufällig die natürlichen Zahlen.Das Beispiel zeigt, wie die induktive Definition von natürlichen Zahlen der am wenigsten feste Schließpunkt unter den Konstruktoren der natürlichen Zahlen ist.Im Allgemeinen sind induktiv definierte Mengen die am wenigsten festen Schließpunkte unter Konstruktoren.

Doppelt, für monoton $f$ es gibt auch einen größten Fixpunkt $\jetzt f$, nämlich die Vereinigung aller $A eilmenge Q U$, so dass $f(A)\supseteq A$. Größtmögliche bedeutet, dass für beliebige Fixpunkte $F$ wir haben immer $ u f\supseteq F$.Um die Dualität zu vervollständigen, stellen wir fest, dass die Schnittmenge die ist $\subseteq$-infimum und Union die $\subseteq$-supremum und damit die $\supseteq$-infimum.Also, in der Tat, größte Fixpunkte für $\subseteq$ sind nur die wenigsten Fixpunkte für $\supseteq$ und umgekehrt.(Beachten Sie auch, dass das Erfordernis der Monotonie dasselbe ist für $\subseteq$ wie für $\supseteq$.)

Nun zu den Beweistechniken.Beginnen wir mit dem Beispiel der Induktion über natürliche Zahlen.Um zu zeigen, dass eine Eigenschaft $P$ gilt für alle natürlichen Zahlen, zeigen wir, dass $P(0)$ und das $P(n)$ implizieren $P(n+1)$.Aussichtsplattform $P$ als Teilmenge von $U$ (die Menge aller Elemente, in denen die Eigenschaft enthalten ist), ist die Beweispflicht für die natürliche Induktion, dass $P$ ist geschlossen unter $f_{ t nat}$.Korrektheit der Beweistechnik der natürlichen Induktion folgt dann aus der Definition des kleinsten Fixpunktes:Wenn $f_{ t nat}(P) eilmenge q P$, dann $P$ ist Teil der Kreuzung, die sich bildet $\mu f_{ t nat}$, so hält das Eigentum überall $\mu f_{ t nat}$, das ist $\mu f_{ t nat} eilmenge q P$.

Induktion ist nur die Verallgemeinerung des vorherigen Absatzes auf willkürliche Monotonie $f$ statt $f_{ t nat}$.Coinduktion ist das Dual der Induktion:Die Beweispflicht ist $f(P)\supseteq P$.Dies bedeutet, dass wenn $P$ hält an einem Element fest $x$, dann $x$ wird nur mit Basiselementen konstruiert, auf denen $P$ auch hält.Anstatt also zu zeigen, dass die Eigenschaft die Anwendung von Konstruktoren überlebt, müssen wir zeigen, dass sie die Dekonstruktion überlebt.Sobald die Beweispflicht erfüllt ist, erhalten wir $ u f\supseteq P$.

Was nützt die Schlussfolgerung $ u f\supseteq P$?Lassen Sie uns noch einmal darüber nachdenken $P$ nicht als Eigentum, sondern als Teilmenge von $U$.Der Abschluss der Coinduktion legt fest, dass alle Elemente von $P$ sind wohlgeformte Mitglieder der koinduktiv definierten Menge $\jetzt f$.Dies geschieht im Beispiel in Was ist Coinduktion? zeigen forall n, Infinite (from n).Hier, $f$ ist Schließung unter den Konstrukteuren von Infinite (nicht von colist!) und $P$ ist die Menge aller Terme der Form from n für einige n.