Was bedeutet das Instanziieren existenzieller Variablen mit Variablen außerhalb des Gültigkeitsbereichs?

7

Ich habe folgenden unvollendeten Beweis für ein Lemma:

Goal forall (P : Type -> Prop) (Q : Prop),
  ((forall x, (P x)) -> Q) -> (exists x, P x -> Q).
Proof.
  intros. 
  eapply ex_intro. intros. apply H. intros. eapply H0.

Das Problem ist das letzte eapplyfehlgeschlagene mit der Nachricht

Error:
In environment
P : Type -> Prop
Q : Prop
H : (forall x : Type, P x) -> Q
H0 : P ?x
x : Type
Unable to unify "?x" with "x" (cannot instantiate "?x" because "x" is not in
its scope: available 
arguments are "P" "Q" "H").

Die Beweisschritte selbst sehen schon sehr phishy aus. Der Beweis konstruiert existenzielle Variablen, die anstelle von sitzen sollenx in der zweiten Hälfte und versucht dann, es mit dem zu instanziieren xals Voraussetzung nach Anwendung der Hypothese erhalten (forall x, (P x)) -> Q. Die Beweisschritte sehen für mich zyklisch aus.

Was bedeutet diese Nachricht im Allgemeinen? Welche Arten von logischen Fehlern zeigt diese Meldung hier an?

Es gibt ein aktuelles Github-Problem von Coq, das tatsächlich darauf hinweist, dass das Instanziieren von Evars außerhalb des Gültigkeitsbereichs Unwahrheit beweisen kann, außer dass es von QED blockiert wird.

https://github.com/coq/coq/issues/8215

logic coq Jason Hu
quelle
2
Sie werden dies nicht konstruktiv beweisen können. Sie können, wenn Sie ein geeignetes Axiom der klassischen Logik annehmen.
Derek Elkins verließ SE
2
@DerekElkins Das habe ich gelernt. Aber würde die Instanziierung außerhalb des Geltungsbereichs den Grund aufzeigen, warum dies in der konstruktiven Logik nicht funktioniert?
Jason Hu
1
Ich würde es nicht sagen, obwohl es anfängt, es vorzuschlagen. Es gibt alle Arten von Möglichkeiten, dies nicht konstruktiv zu beweisen, und offensichtlich müssen alle Ansätze fehlschlagen, damit dies nicht beweisbar ist. Um ein Existenzielles konstruktiv zu beweisen, muss ein Zeuge vorgelegt werden. In diesem Fall müssen wir einen beliebigen Wert eines beliebigen Typs erstellen, der unmöglich ist, und keine der Annahmen liefert uns einen Wert des Typs. Das Gesetz der ausgeschlossenen Mitte erlaubt es uns andererseits, Werte aus dem Nichts zu zaubern.
Derek Elkins verließ SE
1
Der Standardbeweis für LEM in der klassischen Sequenzrechnung ist in der Tat "eine Variable, die ihrem Anwendungsbereich entgeht". Ich habe mir das nicht zu genau angesehen, aber es könnte sein, dass Sie eine ähnliche Situation haben.
Gallais
Meinten Sie wirklich (P : Type -> Prop)? Und nicht (A : Type) (P : A -> Prop)? Wenn Sie Letzteres gemeint haben, können Sie die Negation Ihres Lemmas beweisen .
Anton Trunov

Antworten:

8

Wenn Sie eine existenzielle Einführung machen, sagen Sie, dass es einen Begriff gibt t, die durch die Vereinigungsvariable dargestellt wird ?x, so dassP.(t)→Q.. Sie versuchen dann, sich zu bewerbenP.(t) zu H.::(∀x.P.(x))→Q.. Es versucht zu verallgemeinern P ?x, denn wenn es das zeigen kannP.(c) für eine frische Konstante c(dargestellt durch xin der Coq-Ausgabe), dann∀x.P.(x)würde folgen. Es wird versucht, diese neue Konstante xmit der Vereinigungsvariablen zu vereinheitlichen, ?xdies ist jedoch nicht zulässig. ?xRepräsentiert aus logischer Sicht einen Begrifft und dieser Begriff unterscheidet sich per Definition von Frische c(dh x) was nur zu sagen istc war nicht im Umfang, als wir vorstellten t, damit t kann nicht davon abhängen.

Als einfacheres Szenario können wir nicht beweisen ∃x.∀y.x=y durch existenzielle Einführung mit y. y ist zu diesem Zeitpunkt nicht im Geltungsbereich.

Derek Elkins verließ SE
quelle