Preuves théoriques à Coq

Contexte

J'apprends l'aide, Coq, par moi-même. Jusqu'à présent, j'ai terminé la lecture du Coq à la hâte d'Yves Bertot . Maintenant, mon objectif est de prouver quelques résultats de base concernant les nombres naturels, culminant avec l'algorithme dit de division. Cependant, j'ai rencontré quelques revers sur mon chemin vers cet objectif. En particulier, les deux résultats suivants se sont révélés (jeu de mots destinés) être plus difficiles à prouver en Coq que je ne l'avais initialement imaginé. En fait, j'ai, après de nombreuses tentatives infructueuses, recouru à les prouver à la main (comme indiqué ci-dessous). Cela ne m'aide clairement pas à devenir plus compétent dans la gestion du Coq; c'est pourquoi je me tourne vers ce forum. J'espère que quelqu'un sur ce site est capable et désireuxpour m'aider à traduire mes preuves ci-dessous en une preuve que Coq accepte. Toute aide est sincèrement appréciée!

Théorème A

Pour tout Preuve: $x,y \in N$

X < S (y) \subset X < y \lor je (N, X, y)

$\begin{equation} x < S(y) \subset x < y \lor \text{I}(N,x,y) \end{equation}$

Supposons que . Il y a donc un avec D'où par (Peano 1b et 3) $x < S(y)$ $z \in N$

\begin{matrix} (*) & je (N, X + S (z), S (y)) \end{matrix}

$\begin{equation} \text{I}(N,x+S(z),S(y)) \tag{*}\end{equation}$

je (N, X + z, y)

$\begin{equation} \text{I}(N,x+z,y) \end{equation}$

Définir un prédicat

Q (u) : = (je (N, X + u, y) \subset X < y \lor je (N, X, y)

$\begin{equation} Q(u):=(\text{I}(N,x+u,y) \subset x<y \lor \text{I}(N,x,y) \end{equation}$

Il suffit de montrer . Nous le prouvons par récurrence sur . Pour voir , pas que si est valide alors est vrai par Peano 1a. Ainsi, . Maintenant, nous prouvons : Supposons . De cette définition, nous avons et donc également dans ce cas. Enfin, le cinquième axiome de Peano donne et par nous obtenons . $Q(z)$ $z$ $Q(0)$ $\text{I}(N,x+0,y)$ $\text{I}(N,x,y)$ $x<y \lor \text{I}(n,x,y)$ $Q(S(v))$ $\text{I}(N,x+S(v),y)$ $x<y$ $x<y \lor \text{I}(N,x,y)$ $Q(z)$ $(*)$ $x < y \lor \text{I}(N,x,y)$

\begin{matrix} (◻) \end{matrix}

$\begin{equation} \tag{$\square$} \end{equation}$

Théorème B

Pour tout Preuve: $x,y \in N$

x < y \lor I (N, x, y) \lor y < x

$\begin{equation} x <y \lor \text{I}(N,x,y) \lor y<x \end{equation}$

Si alors par définition, et si alors également par définition. Si et alors par transitivité et réflexivité, nous avons , ce qui est une contradiction. Par conséquent, pas plus d'une des affirmations n'est vraie. $x<y$ $\neg \text{I}(N,x,y)$ $x>y$ $\neg \text{I}(N,x,y)$ $x>y$ $y>x$ $\text{I}(N,x,y)$

Nous gardons fixe et introduisons sur . Lorsque nous avons pour tout , ce qui prouve le cas de base. Supposons ensuite que le théorème est valable pour ; maintenant, nous voulons prouver le théorème de . De la trichotomie pour , il y a trois cas: et . Si , alors clairement . Si , alors (comme pour tous les ). Enfin, supposons que $y$ $x$ $\text{I}(N,0,y)$ $0 < y \lor \text{I}(N,0,y)$ $y$ $x$ $S(x)$ $x$ $x<y,\text{I}(N,x,y)$ $x>y$ $x>y$ $S(x) >y$ $\text{I}(N,x,y)$ $S(x) >y$ $S(x) >x$ $x\in \mathbb{N}$ $x <y$ Ensuite, par le théorème A, nous avons ou , et dans les deux cas, nous avons terminé. $S(x) < y$ $\text{I}(N,S(x),y)$

\begin{matrix} (◻) \end{matrix}

$\begin{equation} \tag{$\square$} \end{equation}$

Les théorèmes que je souhaite prouver peuvent être exprimés comme suit dans Coq.

Lemme less_lem (xy: N): moins x (succ y) -> ou (less xy) (IN xy).

Ntrichotomie du théorème: (pour tout xy: N, ou (moins xy) (ou (IN xy) (moins yx))).

Des résultats utiles

Ici, j'ai rassemblé certains des résultats que j'ai définis et prouvé jusqu'à présent. Ce sont ceux que je mentionne ci-dessus. * C'est le code que j'ai réussi à écrire jusqu'à présent, notez que la plupart se compose de définitions. *

(* Sigma types *)


Inductive Sigma (A:Set)(B:A -> Set) :Set :=
  Spair: forall a:A, forall b : B a,Sigma A B.

Definition E (A:Set)(B:A -> Set)
  (C: Sigma A B -> Set)
  (c: Sigma A B)
  (d: (forall x:A, forall y:B x, 
      C (Spair A B x y))): C c :=

match c as c0 return (C c0) with
| Spair a b => d a b
end. 


(* Binary sum type *)

Inductive sum' (A B:Set):Set := 
inl': A -> sum' A B | inr': B -> sum' A B.

Print sum'_rect.

Definition D (A B : Set)(C: sum' A B -> Set)
(c: sum' A B)
(d: (forall x:A, C (inl' A B x)))
(e: (forall y:B, C (inr' A B y))): C c :=

match c as c0 return C c0 with
| inl' x => d x
| inr' y => e y
end.

(* Three useful finite sets *)

Inductive N_0: Set :=.

Definition R_0
  (C:N_0 -> Set)
  (c: N_0): C c :=
match c as c0 return (C c0) with
end.

Inductive N_1: Set := zero_1:N_1.

Definition R_1 
  (C:N_1 -> Set)
  (c: N_1)
  (d_zero: C zero_1): C c :=
match c as c0 return (C c0) with
  | zero_1 => d_zero
end.

Inductive N_2: Set := zero_2:N_2 | one_2:N_2.

Definition R_2 
  (C:N_2 -> Set)
  (c: N_2)
  (d_zero: C zero_2)
  (d_one: C one_2): C c :=
match c as c0 return (C c0) with
  | zero_2 => d_zero
  | one_2  => d_one
end.


(* Natural numbers *)

Inductive N:Set :=
zero: N | succ : N -> N.

Print N. 

Print N_rect.

Definition R 
  (C:N -> Set)
  (d: C zero)
  (e: (forall x:N, C x -> C (succ x))):
  (forall n:N, C n) :=
fix F (n: N): C n :=
  match n as n0 return (C n0) with
  | zero => d
  | succ n0 => e n0 (F n0)
  end.

(* Boolean to truth-value converter *)

Definition Tr (c:N_2) : Set :=
match c as c0 with
  | zero_2 => N_0
  | one_2 => N_1
end.

(* Identity type *)

Inductive I (A: Set)(x: A) : A -> Set :=
r :  I A x x.

Print I_rect.

Theorem J 
  (A:Set)
  (C: (forall x y:A, 
              forall z: I A x y, Set))
  (d: (forall x:A, C x x (r A x)))
  (a:A)(b:A)(c:I A a b): C a b c.
induction c.
apply d.
Defined.

(* functions are extensional wrt
  identity types *)

Theorem I_I_extensionality (A B: Set)(f: A -> B):
(forall x y:A, I A x y -> I B (f x) (f y)).
Proof.
intros x y P.
induction P.
apply r.
Defined.


(* addition *)

Definition add (m n:N) : N 
 := R (fun z=> N) m (fun x y => succ y) n.

(* multiplication *)

Definition mul (m n:N) : N 
 := R (fun z=> N) zero (fun x y => add y m) n.


(* Axioms of Peano verified *)

Theorem P1a: (forall x: N, I N (add x zero) x).
intro x.
(* force use of definitional equality
  by applying reflexivity *)
apply r.
Defined.


Theorem P1b: (forall x y: N, 
I N (add x (succ y)) (succ (add x y))).
intros.
apply r.
Defined.


Theorem P2a: (forall x: N, I N (mul x zero) zero).
intros.
apply r.
Defined.


Theorem P2b: (forall x y: N, 
I N (mul x (succ y)) (add (mul x y) x)).
intros.
apply r.
Defined.

Definition pd (n: N): N :=
R (fun _=> N) zero (fun x y=> x) n.

(* alternatively
Definition pd (x: N): N :=
match x as x0 with
  | zero => zero
  | succ n0 => n0
end.
*)

Theorem P3: (forall x y:N, 
I N (succ x) (succ y) -> I N x y).
intros x y p.
apply (I_I_extensionality N N pd (succ x) (succ y)).
apply p.
Defined.

Definition not (A:Set): Set:= (A -> N_0).

Definition isnonzero (n: N): N_2:=
R (fun _ => N_2) zero_2 (fun x y => one_2) n.


Theorem P4 : (forall x:N, 
not (I N (succ x) zero)).
intro x.
intro p.

apply (J N (fun x y z => 
    Tr (isnonzero x) -> Tr (isnonzero y))
    (fun x => (fun t => t)) (succ x) zero)
.
apply p.
simpl.
apply zero_1.
Defined.

Theorem P5 (P:N -> Set):
P zero -> (forall x:N, P x -> P (succ x))
   -> (forall x:N, P x).
intros base step n.
apply R.
apply base.
apply step.
Defined.

(* I(A,-,-) is an equivalence relation *)

Lemma Ireflexive (A:Set): (forall x:A, I A x x).
intro x.
apply r.
Defined.

Lemma Isymmetric (A:Set): (forall x y:A, I A x y -> I A y x).
intros x y P.
induction P.
apply r.
Defined.

Lemma Itransitive (A:Set): 
(forall x y z:A, I A x y -> I A y z -> I A x z).
intros x y z P Q.
induction P.
assumption.
Defined.


Lemma succ_cong : (forall m n:N, I N m n -> I N (succ m) (succ n)).
intros m n H.
induction H.
apply r.
Defined.

Lemma zeroadd: (forall n:N, I N (add zero n) n).
intro n.
induction n.
simpl.
apply r.
apply succ_cong.
auto.

Defined.

Lemma succadd: (forall m n:N, I N (add (succ m) n) (succ (add m n))).
intros.
induction n.
simpl.
apply r.
simpl.
apply succ_cong.
auto.

Defined.

Lemma commutative_add: (forall m n:N, I N (add m n) (add n m)).
intros n m; elim n.
apply zeroadd.
intros y H; elim (succadd m y).
simpl.
rewrite succadd.
apply succ_cong.
assumption.


Defined.

Lemma associative_add: (forall m n k:N, 
I N (add (add m n) k) (add m (add n k))).
intros m n k.
induction k.
simpl.
apply Ireflexive.
simpl.
apply succ_cong.
assumption.
Defined.

Definition or (A B : Set):= sum' A B.


Definition less (m n: N) :=
 Sigma N (fun z => I N (add m (succ z)) n).



Lemma less_lem (x y:N) : 
less x (succ y) -> or (less x y) (I N x y).
intro.
destruct H.
right.

(* Here is where I'm working right now *)

Defined.


Theorem Ntrichotomy: (forall x y:N, 
or (less x y) (or (I N x y) (less y x))).

automated-theorem-proving proof-assistants mathematical-programming coq user11942
la source

Pour comprendre jusqu'où vous en êtes, il serait utile de publier votre code Coq jusqu'à présent, afin que nous puissions le charger et vérifier que ce que nous proposons fonctionne pour vos définitions.

Gilles 'SO- arrête d'être méchant'

Quelques commentaires et clarifications: - Serait-il suffisant pour vous d'utiliser simplement l'égalité syntaxique ("=" dans Coq) au lieu de I (N, x, y)? Y a-t-il une raison d'utiliser "ou" la façon dont vous l'avez défini? Coq (enfin, les bibliothèques de base pour Coq) ont un moyen d'expression de disjonction logique qui facilite certains beaux aspects des preuves. De même, il existe un moyen de définir «moins» qui peut être plus pratique pour vous. À cette fin, vous voudrez peut-être jeter un œil aux premiers chapitres de Software Foundations . Alors que la fin du livre ...

Luke Mathieson

... consiste à vérifier des programmes, etc., le début est une assez bonne introduction à Coq, et a des théorèmes comme ceux que vous avez comme exercices et exemples. C'est gratuit, et tout est en fait écrit sous forme de scripts Coq, vous pouvez donc faire les exercices et les compiler pendant que vous lisez. Pour ce que vous faites ici, il y a des morceaux intéressants dans les chapitres Bases, Induction, Prop et Logic - et probablement quelques dépendances des bits entre les deux.

Luke Mathieson

Une autre note, Thm P5 (principe inductif) est intégrée à Coq sous une forme plus forte (induction structurelle), vous n'avez donc pas besoin de prendre explicitement cela comme un axiome.

Luke Mathieson

J'ai publié le code Coq que j'ai écrit jusqu'à présent.

user11942

Réponses:

Coq est un peu plus cruel que les épreuves papier: lorsque vous écrivez "et nous avons terminé" ou "clairement" dans une épreuve papier, il y a souvent beaucoup plus à faire pour convaincre Coq.

Maintenant, j'ai fait un peu de nettoyage de votre code, tout en essayant de le garder dans le même esprit. Vous pouvez le trouver ici .

Plusieurs remarques:

J'ai utilisé des types de données et des définitions intégrés où je pensais que cela ne nuirait pas à votre intention. Notez que si j'avais utilisé l'égalité intégrée au lieu de identityet la relation "moins que" intégrée, les preuves auraient été beaucoup plus faciles, car beaucoup de vos lemmes sont dans la base de données de théorèmes connus, qui sont vérifiés à chaque appel de
```
auto with arith.
```
J'ai utilisé des tactiques que vous ne connaissez probablement pas, mais un "vrai" super-utilisateur Coq aurait des tactiques beaucoup plus puissantes à portée de main et aurait écrit ses propres tactiques pour simplifier le travail. Je recommande toujours CPDT comme endroit pour apprendre à utiliser les tactiques de manière puissante.
J'ai utilisé des notations et des tabulations pour améliorer la lisibilité et des constructions intégrées comme l'appariement et la inductiontactique pour rendre les choses plus faciles à prouver et à re-factoriser. En particulier, votre définition de lessétait difficile à travailler, vous pouvez voir comment je l'ai légèrement modifiée de à l'équivalent (mais plus facile à utiliser) ce type de "réglage de définition" se produit souvent dans les preuves formelles.
$\exists X, m + (X + 1) = n$ $\exists x,\ m + (x+1) = n$ $\exists X, (X + m) + 1 = n$ $\exists x,\ (x + m)+1 = n$
Bien que vous puissiez obtenir des réponses à ce genre de questions ici, je vous recommande fortement de soumettre votre travail au Coq-Club qui a été créé dans le but exprès de répondre à ce genre de questions.

cody
la source

Excellente réponse Cody! C'est merveilleux d'apprendre qu'il y a des gens généreux comme vous là-bas, qui sont prêts à aider les autres dans le besoin. Je l'apprécie sincèrement! Je vais certainement jeter un coup d'œil au CPDT et au Coq-Club; les deux dont j'aurai probablement besoin dans un avenir proche alors que je continue à travailler pour prouver l'algorithme de division dans Coq.

user11942

Merci! Notez que cela est souvent appelé "division euclidienne" et est déjà présent dans certaines bibliothèques (sur les entiers cependant)

cody

Cela ne me surprend pas, les bibliothèques Coq que j'ai examinées ont été remarquablement bien garnies de définitions, de lemmes et de théorèmes. Je chercherai à poster mon approche de l'algorithme de division euclidienne au plus tard demain.

user11942

La réponse de Cody est excellente et répond à votre question sur la traduction de votre preuve en Coq. En complément, je voulais ajouter les mêmes résultats, mais prouvés en utilisant une route différente, principalement comme illustration de quelques bits de Coq et pour montrer ce que vous pouvez prouver syntaxiquement avec très peu de travail supplémentaire. Ce n'est pas une affirmation cependant que c'est la route la plus courte - juste une autre. Les preuves ne comprennent qu'un seul lemme auxiliaire, et ne s'appuient que sur des définitions de base, je n'introduis pas d'addition, de multiplication ou aucune de leurs propriétés, ou d'extensionnalité fonctionnelle, et les seuls axiomes de Peano sont une forme simple de <= b -> a + c <= b + c dans le lemme auxiliaire (juste pour c = 1) et l'induction structurelle, qui vient de toute façon gratuitement avec les types inductifs.

Comme Cody, où je pensais que cela ne faisait aucune différence, j'ai utilisé des types prédéfinis, etc., donc avant la preuve, je vais les décrire:

J'ai utilisé le type nat intégré pour les nombres naturels, qui a (jusqu'à un nom précis) la même définition que la vôtre:

Inductive nat: Set: = O: nat | S: nat -> nat

J'ai utilisé les chiers et lt intégrés pour respectivement inférieur ou égal et inférieur à, qui ont des raccourcis notationnels "<=" et "<" pour plus de lisibilité. Ils sont définis:

Fichier inductif: nat -> nat -> Prop: =
| le_n: forall n, le nn
| le_S: pour tout nm, (le nm) -> (le n (S m)).

Définition lt (nm: nat): = le (S n) m.

L'eq intégré (raccourci "=") est égal à la syntaxe et fonctionne de la même manière que votre "je", avec un constructeur qui dit simplement que tout est égal à lui-même. Les propriétés symétriques et transitives en sont des preuves faciles, mais nous n'en aurons pas besoin dans ce cas. La définition de l'eq ci-dessous a la notation intégrée.

Éq inductif (A: Type) (x: A): A -> Prop: = eq_refl: x = x

Enfin, j'ai utilisé le propositionnel ou (raccourci "\ /" - qui est une barre oblique inversée), qui a deux constructeurs, essentiellement que soit vous avez des preuves pour l'argument de gauche, soit l'argument de droite. Coq a également quelques tactiques sténographiques, gauche et droite, qui signifient simplement "appliquer or_introl" et "appliquer or_intror" respectivement.

Inductif ou (AB: Prop): Prop: =
or_introl: A -> A / B | or_intror: B -> A / B

Ce qui suit maintenant sont mes preuves, en principe, si le balisage ne gêne pas, vous devriez pouvoir couper et coller cela dans un fichier Coq .v et cela fonctionnera. J'ai inclus des commentaires pour noter des bits intéressants, mais ils sont dans des délimiteurs (* *), vous ne devriez donc pas avoir à les supprimer.

Theorem lt_or_eq: forall (n m : nat),
  n < S m -> n < m \/ n = m.
Proof.
(*
  This proof is just a case analysis on n and m, whether they're zero or
  a successor of something.
*)
destruct n as [|n']; destruct m as [|m']. 

(*n = 0, m = 0*)
intros.
  right. reflexivity.

(*n = 0, m = S m'*)
intros H.
  inversion H.
  inversion H1.
  left. unfold lt. constructor.
  (*The constructor tactic tries to match the goal to a constructor
    that's in the environment.*) 
  left. unfold lt. constructor. assumption.
  (*Assumption tries to match the goal to something that's in the
    current context*)

(*n = S n', m = 0
  This case is false, so we can invert our way out of it.*)
intros.
  inversion H. inversion H1.

(*n = S n', m = S m'*)
intros.
  inversion H.
    right. reflexivity.
    left. unfold lt. assumption.
Qed.


(*
  The following lemma with be useful in the proof of the trichotomy theorem,
  it's pretty obviously true, and easy to prove. The interesting part for
  anyone relatively new to Coq is that the induction is done on the
  hypothesis "a <= b", rather than on either a or b.
*)
Lemma a_le_b_implies_Sa_le_Sb: forall a b, a <= b -> S a <= S b.
Proof.
  intros a b Hyp.
  induction Hyp.
  constructor.
  constructor.
  apply IHHyp.
Qed.

(*
  The proof of the trichotomy theorem is a little more involved than the
  last one but again we don't use anything particularly tricky. 
  Other than the helper lemma above, we don't use anything other than the
  definitions.

  The proof proceeds by induction on n, then induction on m.  My personal
  feeling is that this can probably be shortened.  
*)
Theorem trich: forall (n m : nat),
  n < m \/ n = m \/ m < n.
Proof.
  induction n.
    induction m.
      right. left. reflexivity.
        inversion IHm.
          left. unfold lt. constructor. unfold lt in H. assumption.
          inversion H.
          left. unfold lt. subst. constructor.
          inversion H0.     
    induction m.
      assert (n < 0 \/ n = 0 \/ 0 < n).
      apply IHn.
      inversion H.
      inversion H0.
      inversion H0.
      right. right. subst. unfold lt. constructor.
      right. right. unfold lt. constructor. assumption.
      inversion IHm. unfold lt in H.
      left. unfold lt. constructor. assumption.
      inversion H; subst.
      left. unfold lt. constructor.
      inversion H0.
      right. left. reflexivity.
      right. right. apply lt_or_eq in H0.

      inversion H0.
      apply a_le_b_implies_Sa_le_Sb. assumption.
      subst. unfold lt. apply a_le_b_implies_Sa_le_Sb. assumption.
Qed.

(*
  The following is just to show what can be done with some of the tactics
  The omega tactic implements a Pressburger arithmetic solver, so anything
  with natural numbers, plus, multiplication by constants, and basic logic
  can just be solved. Not very interesting for practicing Coq, but cool to
  know.
*)

Require Import Omega.

Example trich' : forall (n m : nat),
  n < m \/ n = m \/ m < n.
Proof.
  intros.
  omega.
Qed.

Luke Mathieson
la source

Une autre merveilleuse réponse! Je vous suis vraiment reconnaissant du temps et des efforts que vous avez consacrés à répondre à ma question.

user11942