Provas de Teoremas em Coq

fundo

Estou aprendendo assistência, Coq, sozinho. Até agora, concluí a leitura Coq apressado de Yves Bertot . Agora, meu objetivo é provar alguns resultados básicos relativos aos números naturais, culminando com o chamado algoritmo de divisão. No entanto, encontrei alguns contratempos no meu caminho em direção a esse objetivo. Em particular, os dois seguintes resultados provaram (trocadilhos) serem mais difíceis de provar em Coq do que eu imaginava inicialmente. De fato, depois de muitas tentativas infrutíferas, tentei prová-las manualmente (como mostrado abaixo). Claramente, isso não está me ajudando a me tornar mais proficiente no manuseio do Coq; é por isso que recorro a este fórum. Minha esperança é que alguém neste site seja capaz e dispostopara me ajudar a traduzir minhas provas abaixo em uma prova que a Coq aceita. Toda a ajuda é sinceramente apreciada!

Teorema A

Para todas as provas : $x,y \in N$

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

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

Suponha . Portanto, existe um com Portanto, por (Peano 1b e 3) $x < S(y)$ $z \in N$

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

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

I (N, x + z, y)

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

Q (u) := (I (N, x + u, y) \subset x < y \lor I (N, x, y)

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

$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}$

Teorema B

$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}$

$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)$

$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$ $S(x) < y$ $\text{I}(N,S(x),y)$

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

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

Os teoremas que desejo provar podem ser expressos da seguinte forma em Coq.

Lema less_lem (xy: N): menos x (succ y) -> ou (menos xy) (IN xy).

Teorema Ntricotomia: (para todos xy: N ou (menos xy) (ou (IN xy) (menos yx))).

Resultados úteis

Aqui, reuni alguns dos resultados que defini e provei até esse ponto. Estes são os que me refiro acima. * Este é o código que eu consegui escrever até agora, observe que a maioria consiste em definições. *

(* 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
fonte

Para entender até onde você chegou, ajudaria se você publicasse seu código Coq até agora, para que possamos carregá-lo e verificar se o que propomos funciona para suas definições.

Gilles 'SO- stop be evil'

Alguns comentários e perguntas esclarecedoras: - Seria suficiente para seus objetivos usar apenas a igualdade sintática ("=" no Coq) em vez de I (N, x, y)? Existe uma razão para usar 'ou' da maneira que você definiu? Coq (bem, as bibliotecas básicas para Coq) têm uma maneira de expressar disjunção lógica que facilita certos aspectos legais das provas. Da mesma forma, há uma maneira de definir 'menos' que pode ser mais viável para você. Para esse fim, você pode dar uma olhada nos primeiros capítulos do Software Foundations . Enquanto o final do livro ...

Luke Mathieson

... trata-se de verificar programas etc., o início é uma boa introdução ao Coq e possui teoremas como os que você tem como exercícios e exemplos. É gratuito e, na verdade, tudo está escrito como scripts Coq, para que você possa fazer os exercícios e compilá-los enquanto lê. Para o que você está fazendo aqui, há alguns trechos interessantes nos capítulos Básico, Indução, Prop e Lógica - e provavelmente algumas dependências dos bits entre eles.

Luke Mathieson

Outra observação: Thm P5 (princípio indutivo) é incorporado à Coq de uma forma mais forte (indução estrutural), portanto você não precisa explicitamente interpretá-lo como axioma.

Luke Mathieson

Publiquei o código Coq que escrevi até agora.

usar o seguinte comando

Respostas:

O Coq é um pouco mais cruel do que as provas em papel: quando você escreve "e pronto" ou "claramente" em uma prova em papel, muitas vezes há muito mais a fazer para convencer o Coq.

Agora, eu fiz uma pequena limpeza no seu código, enquanto tentava mantê-lo no mesmo espírito. Você pode encontrá-lo aqui .

Várias observações:

Eu usei tipos de dados e definições embutidos, onde pensei que não prejudicariam sua intenção. Observe que, se eu tivesse usado a igualdade embutida em vez de identitye a relação "menor que", as provas teriam sido muito mais fáceis, pois muitos de seus lemas estão no banco de dados de teoremas conhecidos, que são verificados a cada chamada de
```
auto with arith.
```
Usei algumas táticas das quais você provavelmente não está ciente, mas um superusuário "real" da Coq teria táticas muito mais poderosas à mão e escrevia suas próprias táticas para simplificar o trabalho. Eu sempre recomendo o CPDT como o lugar para aprender sobre o uso de táticas de maneira poderosa.
inductionless
$\exists x, m + (x + 1) = n$ $\exists x,\ m + (x+1) = n$ $\exists x, (x + m) + 1 = n$ $\exists x,\ (x + m)+1 = n$
Embora você possa obter respostas para esses tipos de perguntas aqui, recomendo que você envie seu trabalho ao Coq-Club, criado com o objetivo expresso de responder a esse tipo de perguntas.

cody
fonte

Ótima resposta Cody! É maravilhoso saber que existem pessoas generosas como você por aí, dispostas a ajudar os necessitados. Eu sinceramente aprecio isso! Definitivamente vou dar uma olhada no CPDT e no Coq-Club; dos quais eu provavelmente precisarei no futuro próximo, enquanto continuo trabalhando para provar o algoritmo de divisão no Coq.

user11942

Obrigado! Observe que isso geralmente é chamado de "divisão euclidiana" e já está presente em algumas bibliotecas (embora os números inteiros)

decod '

Não me surpreende, as bibliotecas Coq que eu observei foram notavelmente bem estocadas com definições, lemas e teoremas. Procurarei postar minha abordagem do algoritmo da divisão euclidiana como uma pergunta até amanhã, o mais tardar.

user11942

A resposta de Cody é excelente e atende sua pergunta sobre a tradução de sua prova para a Coq. Como complemento, eu queria adicionar os mesmos resultados, mas comprovado usando uma rota diferente, principalmente como ilustração de alguns bits de Coq e demonstrar o que você pode provar sintaticamente com muito pouco trabalho adicional. Esta não é uma afirmação de que esta é a rota mais curta - apenas uma rota diferente. As provas incluem apenas um lema auxiliar adicional e dependem apenas de definições básicas: não introduzo adição, multiplicação ou qualquer uma de suas propriedades ou extensionalidade funcional, e os únicos axiomas Peano são uma forma simples de um <= b -> a + c <= b + c no lema auxiliar (apenas para c = 1) e indução estrutural, que é fornecida de qualquer maneira com tipos indutivos gratuitamente.

Como Cody, onde achei que não fazia diferença, usei tipos predefinidos etc., portanto, antes da prova, vou descrevê-los:

Eu usei o tipo nat incorporado para números naturais, que tem (até nomes precisos) a mesma definição que a sua:

Indutivo nat: Conjunto: = O: nat | S: nat -> nat

Eu usei o arquivo embutido e lt para menor ou igual e menor que respectivamente, que possuem atalhos notáveis "<=" e "<" para facilitar a leitura. Eles são definidos:

Código indutivo: nat -> nat -> Prop: =
| le_n: forall n, le nn
| le_S: para todos os nm, (le nm) -> (le n (S m)).

Definição lt (nm: nat): = le (S n) m.

A eq incorporada (abreviação "=") é uma igualdade sintática e funciona da mesma forma que o seu "eu", com um construtor que apenas diz que qualquer coisa é igual a si mesma. As propriedades simétricas e transitivas são provas fáceis a partir daí, mas não precisaremos delas neste caso. A definição para eq abaixo tem a notação incorporada.

Equação indutiva (A: Tipo) (x: A): A -> Prop: = eq_refl: x = x

Por fim, usei o proposicional ou (atalho "\ /" - que é barra invertida para frente), que tem dois construtores, basicamente que você tem evidências para o argumento da esquerda ou o argumento da direita. A Coq também possui algumas táticas de taquigrafia, esquerda e direita, que significam apenas "aplicar or_introl" e "aplicar or_intror", respectivamente.

Indutivo ou (AB: Prop): Prop: =
ou_introl: A -> A / B | or_intror: B -> A / B

O que segue agora são minhas provas, em princípio, se a marcação não atrapalhar, você poderá recortar e colar isso em um arquivo Coq .v e funcionará. Incluí comentários para observar bits interessantes, mas eles estão em delimitadores (* *), portanto você não precisa removê-los.

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
fonte

Outra resposta maravilhosa! Sou verdadeiramente grato a você pelo tempo e esforço que dedicou em responder à minha pergunta.

user11942