tło
Uczę się pomocy, Coq, na własną rękę. Do tej pory w pośpiechu przeczytałem Coq Yvesa Bertota . Teraz moim celem jest udowodnienie podstawowych wyników dotyczących liczb naturalnych, których zwieńczeniem jest tak zwany algorytm podziału. Jednak na drodze do tego celu napotkałem pewne niepowodzenia. W szczególności dwa następujące wyniki okazały się (gra słów zamierzona) trudniejsze do udowodnienia w Coq, niż początkowo sobie wyobrażałem. W rzeczywistości, po wielu bezowocnych próbach, postanowiłem je udowodnić ręcznie (jak pokazano poniżej). To najwyraźniej nie pomaga mi w opanowaniu Coq; dlatego zwracam się do tego forum. Mam nadzieję, że ktoś na tej stronie jest w stanie i chceaby pomóc mi przetłumaczyć poniższe dowody na dowód, który akceptuje Coq. Wszelka pomoc jest szczerze doceniana!
Twierdzenie A
Dla wszystkich
Przypuszczać . Stąd jest z
Zdefiniuj predykat
Wystarczy pokazać . Udowadniamy to przez włączenie indukcyjne. Zobaczyć, nie etat, jeśli trzyma się wtedy jest zgodne z Peano 1a. A zatem,. Teraz udowodnimy: Załóżmy . Z tej definicji mamy a zatem także w tym przypadku. Na koniec podaje piąty aksjomat Peano i przez dostajemy .
Twierdzenie B
Dla wszystkich
Gdyby następnie z definicji i jeśli następnie również z definicji. Gdyby i potem mamy przechodniość i refleksyjność , co jest sprzecznością. W związku z tym nie więcej niż jedno ze stwierdzeń jest prawdziwe.
Trzymamy naprawiono i włączono . Kiedy mamy dla wszystkich , co potwierdza przypadek podstawowy. Następnie załóżmy, że twierdzenie to obowiązuje; teraz chcemy udowodnić to twierdzenie. Z trichotomii dlaistnieją trzy przypadki: , i . Gdyby, więc wyraźnie . Gdyby, następnie (tak jak dla wszystkich ). Wreszcie załóżmy Następnie twierdzenie A mamy lub , w obu przypadkach skończymy.
Twierdzenia, które chcę udowodnić, można wyrazić w Coq w następujący sposób.
Lemma less_lem (xy: N): mniej x (sucy y) -> lub (mniej xy) (IN xy).
Twierdzenie Ntrikotomia: (dla wszystkich xy: N lub (mniej xy) (lub (IN xy) (mniej yx))).
Przydatne wyniki
Tutaj zebrałem niektóre wyniki, które zdefiniowałem i do tej pory udowodniłem. To są te, o których mówię powyżej. * To jest kod, który udało mi się napisać do tej pory, zauważ, że większość składa się z definicji. *
(* 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))).
źródło
Odpowiedzi:
Coq jest nieco bardziej okrutny niż papierowe dowody: kiedy piszesz „a skończyliśmy” lub „wyraźnie” w papierowym dowodzie, często można zrobić znacznie więcej, aby przekonać Coq.
Teraz trochę wyczyściłem twój kod, starając się zachować go w tym samym duchu. Możesz go znaleźć tutaj .
Kilka uwag:
Użyłem wbudowanych typów danych i definicji, w których myślałem, że nie zaszkodzi to twoim zamiarom. Zauważ, że gdybym użył wbudowanej równości zamiast
identity
i wbudowanej relacji „mniej niż”, dowody byłyby znacznie łatwiejsze, ponieważ wiele twoich lematów znajduje się w bazie danych znanych twierdzeń, które są sprawdzane przy każdym wywołaniuUżyłem pewnych taktyk, o których prawdopodobnie nie wiesz, ale „prawdziwy” superużytkownik Coq miałby pod ręką znacznie mocniejsze taktyki i napisał własne taktyki, aby uprościć zadanie. Zawsze polecam CPDT jako miejsce, w którym można dowiedzieć się, jak stosować taktykę w potężny sposób.
Użyłem notacji i tabulacji, aby poprawić czytelność, oraz wbudowanych konstrukcji, takich jak dopasowywanie i
induction
taktyka, aby ułatwić sprawdzanie i ponowne uwzględnianie czynników. W szczególności twoja definicjaless
była trudna w użyciu, możesz zobaczyć, jak ją nieco zmodyfikowałemChociaż możesz tutaj uzyskać odpowiedzi na tego rodzaju pytania, zdecydowanie zalecamy przesłanie swojej pracy do Coq-Club, który został stworzony wyłącznie w celu udzielenia odpowiedzi na tego rodzaju pytania.
źródło
Odpowiedź Cody'ego jest doskonała i spełnia twoje pytanie dotyczące tłumaczenia twojego dowodu na Coq. Jako uzupełnienie tego chciałem dodać te same wyniki, ale udowodniłem, że używam innej trasy, głównie jako ilustrację niektórych bitów Coq i aby zademonstrować to, co możesz syntaktycznie wykazać przy bardzo niewielkiej dodatkowej pracy. Nie oznacza to jednak, że jest to najkrótsza droga - po prostu inna. Dowody zawierają tylko jeden dodatkowy lemat pomocniczy i opierają się tylko na podstawowych definicjach, nie wprowadzam dodawania, mnożenia ani żadnej z ich właściwości, ani funkcjonalnej ekstensywności, a jedyne aksjomaty Peano są prostą formą <= b -> a + c <= b + cw lemacie pomocnika (tylko dla c = 1) i indukcji strukturalnej, która i tak zawiera typy indukcyjne za darmo.
Podobnie jak Cody, gdzie myślałem, że to nie ma znaczenia, użyłem predefiniowanych typów itp., Więc przed dowodem opiszę te:
i
Teraz są moje dowody, w zasadzie, jeśli znaczniki nie przeszkadzają, powinieneś być w stanie po prostu wyciąć i wkleić to do pliku .v Coq i zadziała. Dodałem komentarze, aby zauważyć interesujące bity, ale są one w ogranicznikach (* *), więc nie powinieneś ich usuwać.
źródło