Ich versuche, induktive Typen aus Kapitel 7 von "Theorem Beweisen in Lean" . Ich habe mir selbst die Aufgabe gestellt zu beweisen, dass der Nachfolger natürlicher Zahlen eine Substitutionseigenschaft über Gleichheit hat: Nach einigen Ratespielen und ziemlich erschöpfender Suche konnte ich den Compiler mit ein paar Möglichkeiten zufriedenstellen: Ich verstehe nicht, wie einige der Beweise, die ich gerade gegeben habe, tatsächlich funktionieren.
eq (induktiv)? In VSCode kann ich die Typensignatur von eq als eq Π {α : Type} α → α → Prop sehen, aber ich kann einzelne (induktive) Konstruktoren nicht sehen (Analoga von zero und succ von natural ). Das Beste, was ich im Quellcode finden konnte sieht nicht ganz richtig aus . eq.subst einen Beweis von (natural.succ a) = (natural.succ a) , um einen Beweis für (natural.succ a) = (natural.succ b) ? #check (eq.rec_on H (eq.refl (natural.succ a))) eintippe, was [Lean] invalid 'eq.rec_on' application, elaborator has special support for this kind of application (it is handled as an "eliminator"), but the expected type must be known eq.rec_on : Π {α : Sort u} {a : α} {C : α → Sort l} {a_1 : α}, a = a_1 → C a → C a_1 ist?
eq ist unter Ссылка definiert Sein
%Code%
Die Idee ist, dass jeder Begriff sich selbst gleich ist, und der einzige Weg für zwei Begriffe ist, dass sie der gleiche Begriff sind. Dies mag sich wie ein bisschen ITT Magie anfühlen. Die Schönheit kommt von dem automatisch generierten Rekursor für diese Definition:
%Code%
Dies ist das Substitutionsprinzip für die Gleichheit. "Wenn C von a und a = a_1 gilt, dann gilt C für a_1." (Es gibt eine ähnliche Interpretation, wenn C Typ-Wert anstelle von Prop-Wert ist.)
inductive eq {α : Sort u} (a : α) : α → Prop
| refl : eq a
nimmt einen Beweis von
eq.rec : Π {α : Sort u_2} {a : α} {C : α → Sort u_1}, C a → Π {a_1 : α}, a = a_1 → C a_1
zusammen mit dem Beweis von eq.subst . Beachten Sie, dass a = b grundsätzlich eine Neuformulierung von succ a = succ a ist. Angenommen, die Eigenschaft eq.subst , parametrisiert über eine Variable x, ist eq.rec . C gilt für succ a = succ x nach Reflexivität und seit C haben wir a von a = b .
Wenn Sie C schreiben, muss Lean herausfinden, was die Eigenschaft (oder "Motiv") b sein soll. Dies ist ein Beispiel für die Vereinheitlichung höherer Ordnung: Die unbekannte Variable muss mit einem Lambda-Ausdruck vereinheitlichen. Es gibt eine Diskussion darüber in Abschnitt 6.10 in Ссылка und einige allgemeine Informationen unter Ссылка .
Sie bitten Lean, eq.subst H rfl in C zu ersetzen, ohne ihm zu sagen, was Sie zu beweisen versuchen. Sie könnten versuchen, a = b oder succ a = succ a oder sogar succ b = succ b zu beweisen (indem Sie Nirgendwo ersetzen). Lean kann das Motiv succ b = succ a nur dann ableiten, wenn es diese Information hat.
Im Allgemeinen ist es schwierig, die Ersetzungen "manuell" (mit succ a = succ a , C usw.) durchzuführen, da die Vereinheitlichung höherer Ordnung heikel und teuer ist. Sie werden oft feststellen, dass es besser ist Taktiken wie eq.rec (rewrite) zu verwenden:
subst
Wenn Sie clever sein wollen, können Sie den Lean-Gleichung-Compiler verwenden, und die Tatsache, dass der "einzige" Beweis für rw
lemma succ_over_equality (a b : natural) (H : a = b) :
(natural.succ a) = (natural.succ b) := by rw H
ist:
a=b
Tags und Links dependent-type theorem-proving formal-verification lean