Definition nach Eigenschaft in Coq

Question

Ich habe Probleme mit der Formalisierung von Definitionen der folgenden Form: Definieren Sie eine ganze Zahl, so dass einige Eigenschaft gilt.

Lassen Sie uns sagen, dass ich die Definition der Eigenschaft formalisiert:

Definition IsGood (x : Z) : Prop := ... 

Jetzt brauche ich eine Definition der Form:

Definition Good : Z := ... 

davon aus, dass ich bewiesen, dass eine ganze Zahl mit der Eigenschaft vorhanden ist und einzigartig ist:

Lemma Lemma_GoodExistsUnique : exists! (x : Z), IsGood x. 

gibt es eine einfache Möglichkeit, Good definieren mit IsGood und ?

Da die Eigenschaft auf Integer-Zahlen definiert ist, scheint es, dass keine zusätzlichen Axiome notwendig sein sollten. Auf jeden Fall sehe ich nicht, wie das Hinzufügen von etwas wie dem Entscheidungsaxiom bei der Definition helfen kann.

Auch ich habe Probleme mit Definitionen der folgenden Form zu formalisieren (Ich vermute, das auf das Problem zusammenhängt ich oben beschrieben, jedoch ist anzugeben, wenn das nicht der Fall ist): Für jeden x gibt es y und Diese y sind für verschiedene x unterschiedlich. Wie zum Beispiel, wie man definiert, dass es N verschiedene gute Integer-Zahlen sind mit IsGood:

Definition ThereAreNGoodIntegers (N : Z) (IsGood : Z -> Prop) := ...? 

In der realen Welt der Mathematik, Definitionen wie, dass jeden kommt von Zeit zu Zeit, so sollte dies nicht schwer zu formalisieren, wenn Coq soll sich für die praktische Mathematik eignen.

Answer 1

Die kurze Antwort auf Ihre erste Frage lautet: Im Allgemeinen ist es nicht möglich, aber in Ihrem speziellen Fall ja.

In Coqs Theorie haben Sätze (d. H. Prop s) und ihre Beweise einen sehr speziellen Status. Insbesondere ist es im Allgemeinen nicht möglich, einen Wahloperator zu schreiben, der den Zeugen eines Existenzbeweises extrahiert. Dies geschieht, um die Theorie mit bestimmten Axiomen und Prinzipien kompatibel zu machen, wie zum Beispiel der Beweis-Irrelevanz, die besagt, dass alle Beweise eines gegebenen Satzes einander gleich sind. Wenn Sie in der Lage sein möchten, dies zu tun, müssen Sie diesen Wahloperator als zusätzliches Axiom zu Ihrer Theorie hinzufügen, wie in der standard library.

jedoch in einigen besonderen Fällen ist es ist möglich, einen Zeugen aus einem abstrakten Existenz Beweis zu zusätzlichen Axiomen ohne wiederkehrende zu extrahieren. Dies ist insbesondere bei zählbaren Typen möglich (z. B. Z), wenn die betreffende Eigenschaft entscheidbar ist. Sie können zum Beispiel die choiceType Schnittstelle in der Ssreflect Bibliothek verwenden, um genau das zu erhalten, was Sie wollen (suchen Sie nach der xchoose Funktion).

Das gesagt, würde ich normalerweise gegen Dinge in diesem Stil tun, weil es zu unnötiger Komplexität führt. Es ist wahrscheinlich einfacher, Good direkt zu definieren, ohne auf den Existenzbeweis zurückgreifen zu müssen, und dann separat zu beweisen, dass Good die gesuchte Eigenschaft hat.

Definition Good : Z := (* ... *) 
Definition IsGood (z : Z) : Prop := (* ... *) 

Lemma GoodIsGood : IsGood Good. 
Proof. (* ... *) Qed. 

Lemma GoodUnique : forall z : Z, IsGood z -> z = Good. 

Wenn Sie unbedingt definieren Good mit einem Existenzbeweis wollen, können Sie auch den Beweis Lemma_GoodExistsUnique ändern, um eine Binde in Type statt Prop zu verwenden, da es Ihnen, den Zeugen zu extrahieren direkt die proj1_sig Funktion :

Lemma Lemma_GoodExistsUnique : {z : Z | Good z /\ forall z', Good z' -> z' = z}. 
Proof. (* ... *) Qed. 

Wie für Ihre zweite Frage, ja, es ist ein bisschen auf den ersten Punkt bezogen. Noch einmal würde ich empfehlen, dass Sie eine Funktion y_from_x mit dem Typ Z -> Z notieren, die yx vorausgesetzt wird, und dann separat beweisen, dass diese Funktion auf eine bestimmte Weise Eingänge und Ausgänge bezieht. Dann können Sie sagen, dass die y s für verschiedene x s unterschiedlich sind, indem Sie beweisen, dass y_from_x injektiv ist.

Auf der anderen Seite bin ich mir nicht sicher, wie sich Ihr letztes Beispiel auf diese zweite Frage bezieht. Wenn ich verstehe, was Sie richtig machen wollen, können Sie so etwas wie

Definition ThereAreNGoodIntegers (N : Z) (IsGood : Z -> Prop) := 
    exists zs : list Z, 
    Z.of_nat (length zs) = N 
    /\ NoDup zs 
    /\ Forall IsGood zs. 

Hier schreiben können, Z.of_nat : nat -> Z die kanonische Injektion von Naturals auf ganze Zahlen, so ist NoDup ein Prädikat zu behaupten, dass eine Liste nicht wiederholt Elemente enthält, und Forall ist ein Prädikat höherer Ordnung, das bestätigt, dass ein gegebenes Prädikat (in diesem Fall IsGood) für alle Elemente einer Liste gilt.

Als letzte Anmerkung würde ich empfehlen, Z für Dinge zu verwenden, die nur natürliche Zahlen umfassen können. In Ihrem Beispiel verwenden Sie eine Ganzzahl, um über die Kardinalität eines Satzes zu sprechen, und diese Zahl ist immer eine natürliche Zahl.