It really depends on what you want to do with it. In Coq, there is a comprehension type {x : T | P x} which is the type of all elements x in type T that satisfy property P. However, it is a type, meaning that it is used to...

If you want to show such an equality, you need to (1) show the associated relations are equal, and (2) show that the corresponding proofs are equal. There are two problems, however. The first one is that the notion of equality on functions is too weak in Coq. In other...

As usual, you must apply the convoy pattern (cf. Adam Chlipala's CPDT book) and make the pattern-matching return a function: Require Import Coq.Numbers.NaryFunctions. Fixpoint app_1 {X Y Z : Type} {n : nat} (f : X ^^ n --> Y) (z : Z) : (Z -> X) ^^ n -->...

The short answer to your first question is: in general, it is not possible, but in your particular case, yes. In Coq's theory, propositions (i.e., Props) and their proofs have a very special status. In particular, it is in general not possible to write a choice operator that extracts the...

In Coq there are two terminator commands for proof scripts: Qed and Defined. The difference between them is that the former creates opaque terms, which cannot be unfolded, even by Eval compute. The latter creates transparent terms, which can then be unfolded as usual. Thus, you just have to put...

Parameter g: nat -> nat. (* You could restructure f in one of two ways: *) (* 1. Use a helper then prove an unrolling lemma: *) Definition fhelp fhat (x:nat) := match g x with | O => O | S y => match x with | O =>...

Just for the sake of clarity, I take it that Heap must look like this: Inductive Heap A : Type := | Node : Heap A -> A -> Heap A -> Heap A | Leaf : Heap A. with f being defined as Fixpoint f A (h : Heap...

I don't know whether this is a bug or not, but notice that when you write something like Functor F -> SomeType, you are implicitly saying that SomeType does not depend on the Functor instance, which is not true in your case: the full type of your theorem, printing all...

In "standard" Verifiable-C, memory references cannot occur in expressions except at top level within a load statement: x = a[e]; or x = *(e.field); (same as x = e->field;) where e is any expression that does not access memory. Or, a store statement, a[e1] = e2; or e1->field = e2;...

Even though with default display settings, the subterm seems to appear in the goal, with Set Printing All enabled, it becomes clear that the the subterm does not match the goal because in the goal, stack has been unfolded to list nat. So fold stack is needed to turn list...

I don't know much about type classes myself, but doesn't B need to be variable? By separating it from foldr, you're making it fixed. I think it only makes sense to make C and A fixed. Class Foldable (C : Type -> Type) (A : Type) (foldr : forall B,...

Power_set is an operation on Ensembles, not on Sets. Require Import Coq.Sets.Powerset. Parameter S : Set. Parameter E : Ensemble S. Check Power_set _ (Power_set _ E). Ensemble S already is the powerset monoid. Every E : Ensemble S is a subset of S and vice versa (read x :...

Following your answer to my comment, I don't think you can define a "function" g, because you need a constructive way do distinguish x from other instances of type X. However you could define a relation between the two, which could be transformed into a function if you get decidability....

It's probably a limitation. You need to provide an argument to FileIO and you're not allowed to inline it. Extract Constant FileIO "x" => "IO x". ...

simpl (and all of the other computation tactics) apply conversion rules. Since your goal is an equality, you could directly use reflexivity if your terms were convertible. But (fix f (n : nat) : nat := n) x and x are not convertible. The rule for reducing fix is iota...

Maybe the missing key is that the goal: forall n, P n -> (Some goal) is to be read as: forall n, (P n -> (Some goal)) and not as: (forall n, P n) -> (Some goal) That is, the goal you are given just gives you an arbitrary n...

I think what's happening here is that qu is not in your existential variable's context. You see, every time an existential variable is created, it inherits the current context (a.k.a. environment) and can't be instanciated by a term that contains variables not in that context. This is to prevent some...

Your issue is related to the usual Prop vs Type distinction. The existence of your witness lies in Prop (see definition of type ex), so you can't inspect it to build a concrete term, you need to have this fact proved in Type. You are looking for the sig (or...

pred is a function taking a sig type (try to Print sig.). Simply put, it's an inductive type with one constructor stating that "there exists an x of type A such that P x is true". If you want to create a term of type {n : nat | n...

Here is a proof that uses induction on n. Require Import NPeano. Theorem my_thm: forall n m, (n <? m) = false -> m <= n. induction n; destruct m; intros ; auto using (Le.le_n_S); discriminate. Qed. ...

New versions of the coq:io and coq:io:system libraries were just released. Run: opam update opam upgrade to make sure you have coq:io:system in version at least 2.3.0. Now Extraction.launch should be available. System.effects has been replaced by System.effect....

zltz has the same type as nltz 0. Check zltz. Check nltz 0. To use your function with 2 and [1; 2; 3] from within another function, you can use lt_dec. Eval compute in match lt_dec 2 (length [1; 2; 3]) with | left pf => safe_nth 2 [1; 2;...

Side channel attacks are for instance timing attacks, e.g. you can get information about the secrets by measuring timing differences when using different inputs. It is already hard to do this right in a low level language like C where you have lots of control about processor instructions, cache handling,...

That library actually formalizes an abstract module of integers, that can be later instantiated with a concrete implementation. In Coq, the implementation of integers from the standard library is called Z. There's an instance of the Int module type in terms of Z defined in that library, called Z_as_Int; to...

You will have two separate issues here: You have mutual inductive type, so you need to declare a mutual fixpoint, for example Fixpoint a_dec (x y : a) : { x = y } + { x <> y } with b_dec (x y : t) : { x =...

As it has been said before, It is easier to prove this theorem using the length of the list : Theorem rev_pal_aux {X:Type} : forall (l:list X) (n:nat) , length l<= n -> l = rev l -> pal l. Then you can start an induction on n. The key...

The closest thing I got from your code his the following: Record ToyRec {Labels : Set} := { X:Set; r:X->Labels }. Definition GoodPair {Labels:Set} (T1 T2 : @ToyRec Labels) : Prop := forall x1: X T1, exists x2: X T2, r T1 x1 = r T2 x2. By having Labels...

After banging on this problem for a few more days, I have typeclass inheritance of different Kinds that, as far as I can tell, is correct. I was on the right track in my question update. All I needed to do was add an explicit inheritance of Semigroup. I am...

Here is what I managed to do, but was not sure it is the easiest way, since I use dependent type and dependent pattern matching to encode the family g1, ... , gn: Require Import NaryFunctions Vector. Open Scope type. First I need a function to apply a function f:...

arguments,coq,implicit-typing,coqide

I just tried it on my (somewhat old) Coq 8.4 and I don't have any problem with the implicit declaration. However if I write Argument instead of Arguments (notice the lack of "s"), I get Error: Unknown command of the non proof-editing mode. Did you correctly spelled it ? EDIT:...

You want to do destruct (split A B tx). This will break it up, binding the two pieces to ta and tb

You can use the omega tactic. Just do Require Import Omega. at the beginning of your file and you should be good to go.

Tactics like intuition, firstorder or auto try to solve your goal with some automatic reasoning, but you can always replace one of their proofs by one you crafted by hand. In previous version of Coq, you could do info intuition to get the proof script, but I heard it doesn't...

This can't be done in the term language. Coq's language is very powerful in itself, thanks to its dependent types, but it isn't its own metalanguage; there's no way to write a Coq term that manipulates Coq constructors as such (only as terms, and that's not good enough to build...

What you're trying to prove doesn't hold if y <= z, because with nat a-b is zero if a <= b. Omega is a useful tactic to use for inequalities and simple arithmetic over nat. Require Import Omega. Theorem foo: forall x y z:nat, (x = 0 \/ z <=...

I don't know much about Coq, but Isabelle's type system is very different. Isabelle values do not take ‘type parameters’, and Isabelle types do not take ‘value parameters’. In Isabelle, your example is a simple polymorphic definition which can be done like this: inductive monoid :: "('a ⇒ 'a ⇒...

You could assert B. before split. and prove it, then split and prove B by using the assumption, and go ahead and prove C with B available. Alternatively, you could build a: Theorem and_intro_2 : forall A B C : Prop, (A -> B) -> (A -> B -> C)...

Coq erases values of type Prop during extraction—they're considered to have no computational meaning. If you have a computation which requires computing with a Prop then extraction will fail.

I just saw your answer, but here is an explanation why your initial attempt didn't work, and how to make it run: You can't directly use Nat.pow_add_r because your goal neither contains a term of the shape a ^ (b + c) nor a ^ b * a ^ c....

It is definitely provable, for example, by case analysis. I think, you have a problem doing this because you formulated theorem incorrectly. a b and c should be Bool not Prop. In case of Prop it's provable via reflexivity tactics (if / is left associative)....

You just have to use inversion on your hypothesis that states that length l > 0: intros [|x l] def n H. - (* Case l = [], contradiction *) simpl in H. inversion H. - (* Continue normally *) ...

vector,coq,idris,convoy-pattern

It's not possible to implement this function so easily in plain Coq: you need to rewrite your function using the convoy pattern. There was a similar question posted a while ago about this. The idea is that you need to make your match return a function in order to propagate...

I finally had the time to install ssreflect to test your issue. As we discussed in the comments, you should rely on the ssreflect's integer, to get the correct canonical structure instances loaded. Here is my code, using ssr1.4 and coq8.4pl5: Require Import ssreflect ssrfun ssrbool eqtype ssrnat seq choice...

The principle you want is known as functional extensionality; in its most general form, it says Axiom fun_ext : forall (A B : Type) (f g : A -> B), (forall x : A, f x = g x) -> f = g. Unfortunately, in spite of being useful, this...

coqdoc parses Coq's .v files to extract the documentation information, and the language provides ways to "hide" parts of the .v file so it is not visible on the documentation. Trying to parse back the .html into .v might not be possible as is. If you want the actual content...

What is a bit confusing in Coq is that there are two different forms of destructing let. The one you are looking for needs a quote before the pattern: Definition p (a : nat) := (a + 1, a + 2, a + 3). Definition q := let '(s, r,...

The URL git+ssh://... is probably for developers who need to be able to check in code. You could use git clone https://gforge.inria.fr/git/coq-contribs/math-classes.git instead, but it is less recently updated than the github repo. Or, you can download it from the official page: http://www.lix.polytechnique.fr/coq/pylons/contribs/files/MathClasses/v8.4/MathClasses.interfaces.abstract_algebra.html To compile, I did git clone https://github.com/math-classes/math-classes.git...

Because you invert H before building something similar-ish back again by using constructor ; apply H0, you get a term_lemma with a pattern matching that's equivalent to what you'd want but confuses Coq's termination checker (You can inspect a term by using Print NAME.). You don't need to do all...

You ended the definition of C2_nat with Qed. Definitions ending with Qed are opaque and cannot be unfolded. Write the following instead Instance C2_nat: C2 nat:= {v2:=4}. trivial. Defined. and your proof finishes without problems....

(I'm not 100% sure of what I'm writing here, but) Coq never 'guess' anything, but it can infer information from more complex ones. Your general scheme here is that you ask Coq to use transitivity of equality to solve your goal. Therefore, Coq needs two statements of equality to succeed....

If f is an anonymous function (that is, something of the form fun x => expr), then simpl should be enough. If it is an identifier and you cannot unfold it, then either (1) it is a local variable bound in your context, or (2) it is a global definition...

After playing with the Program command I managed to build a refine that might suites you, but I don't understand everything I did. The main idea is to help Coq with the substitution by introducing intermediate equalities that will serve as brige within the substitution refine ((fun fl => match...

The instance of module FMapInterface (obtained from FMapAVL.Make) changes the definition of In, so this basic property is lost in the instance. Instead, the result must be proved at the level of FMapInterface. The solution is to create an auxiliary module with these two properties. Require Coq.FSets.FMapFacts. Require Coq.FSets.FMapInterface. Module...

This is a common Ltac pattern. You can use the fail tactic to avoid executing a branch when some condition matches: Variable X Y Z : Prop. Hypothesis A : X -> Y. Hypothesis B : X -> Z. Ltac does_not_have Z := match goal with | _ : Z...

There are a few misunderstandings about some Coq concepts which I'll try to clarify. First, in Coq, you shouldn't view Set as what we call "set" in traditional mathematics. Instead, you should view it as a type. Coq also has Type, but for the purposes of this post you can...

You are right: type classes in Coq are just records with special plumbing and inference (there's also the special case of single-method type classes, but it doesn't really affect this answer in any way). Therefore, the only reason you would choose type classes over "pure" dependent records is to benefit...

I think you are right. To the best of my knowledge, you can't even correctly state what it means for two streams to be equal, since it would imply that you can inspect them in finite time, but they are infinite terms. What you could do, is state that any...

Writing this function requires an instance of what is known as the convoy pattern (see here). I believe the following should work, although I can't test it, since I don't have the rest of your definitions. Definition gen `{A:Type} {i o: nat} (f: nat -> (option nat)) {ibound: forall (n...

You are absolutely right! Writing this function should be easy in any reasonable programming language, and, fortunately, Coq is no exception. In your case, it is much easier to define your function by simply ignoring the proof argument you are supplying: Definition f (n : nat) : nat := n...

For integers, either ring or omega should be able to solve such a goal. It can also be done manually. It helps to disable notations so that function names appear (in order use SearchAbout to find useful lemmas). The following is probably not the shortest possible proof, just the first...

types,module,encapsulation,coq

Yes. You can define your type inside a module and assign a module type to it: Module Type FOO. Variable t : Type. End FOO. Module Foo : FOO. Inductive typ := | T : typ. Definition t := typ. End Foo. (* This fails *) Check Foo.T. Another possibility...

I can only speak constructively for Isabelle here: the formal syntax uses standard de-Bruijn representation of lambda terms internally, and there are various ways to reuse that for your own syntax and special notation. In fact, Isabelle/HOL is just another application of Isabelle, so its quantifiers and other binders are...

To see why inversion isn't able to solve this goal on its own, we need to understand what it is doing in more detail. When you invert a hypothesis of (co)inductive type, what Coq does, roughly speaking, is to extract as much information as it can from it using only...

Because of type dependency, inversion can't directly generate what you expect, because it is not true in general. However, it is true for a large family of types, whose equality is decidable. In your case, you can apply Eqdep_dec.inj_pair2_eq_dec to get the equality you want, if you provide the fact...

You can control definition unfolding with the Transparent and Opaque commands. In your example, you should be able to say something like Opaque Z.add. simpl. Transparent Z.add. Alternatively, the Arguments command can be used to instruct the simpl tactic to avoid simplifying terms in certain contexts. E.g. Arguments Z.add _...

Essentially, Coq has both because they are useful for different things: booleans correspond to facts that can be checked mechanically (i.e., with an algorithm), whereas propositions can express more concepts. Strictly speaking, the logical and boolean worlds are not separate in Coq: the boolean world is a subset of the...

exponent_valid has type forall (fmt : float_format) (f : float fmt), minimum_exponent fmt <= exponent fmt f. Without notations it's forall (fmt : float_format) (f : float fmt), Z.le (minimum_exponent fmt) (exponent fmt f). Z.le is defined as = fun x y : Z => not (@eq comparison (Z.compare x...

I would said it's because of dependent types, and you don't actually prove the exact same things in both case (try to Set Printing All. to see implicit types and hidden information). The fact that such a destruct fails is often due to the fact that the dependency will introduce...

You can do this by using the -R option. Compile your file using coqc -R Foo Foo Foo/Bar.v. The -R flag takes two options: (1) the directory you want to add to your include path, and (2) the name you want to give in in the module namespace. Later on,...

Your guess_sqrt_spec has an error in line 68 of verif_sqrt.v, where you give the return type as "tint" (signed integer) where the sqrt.c program has "tuint" (unsigned integer). Then the VST's forward_call tactic has a misleading and unhelpful error message, complaining about the witness type instead of the return-type mismatch....

Pattern-matching on match statements is somewhat weird. The first thing you should know is that, inside Coq, there's no such thing as a match on several variables or with deep matching: everything is translated in terms of simpler match statements. Thus, the term you wrote is actually syntax sugar for...

It seems that you just want the apply tactic. If you have a lemma negb_inj : forall b c, negb b = negb c -> b = c, doing apply negb_inj on your goal would give you exactly that.

Setting up sub-projects You can always set up the load path in the project Makefile, so that it finds exactly the version of the library you want. Suppose that your copy MathClasses lives in /path/to/MathClasses. You can then add the following line to the Make.in file in the CoRN distribution:...

infinite-loop,coq,non-termination

Reading your question made me realize that I didn't quite understand Adam's argument either. But inconsistency in this case results quite easily from Cantor's usual diagonal argument (a never-ending source of paradoxes and puzzles in logic). Consider the following assumptions: Section Diag. Variable T : Type. Variable test : T...

palindrome,coq,theorem-proving

This is a nice example where "direct" induction does not work well at all because you don't directly make the recursive call on the tail, but on part of the tail. In such cases, I usually advice to state your lemma with the length of the list, not on the...

To remember what the list you are pattern-matching on looks like, you need to simply change the return type of your match like so. Fixpoint picksome (l:list nat) (H : Acc lt (length l)) {struct H}: list nat. refine ( (match l as m return l = m -> list...

It is quite easy with Coq to follow step by step what is going on. But before we can do that, we need to know what your program looks like to Coq without all the syntactic sugar. To do that, type the following in your program: Set Printing All. If...

You can define them mutually with the Inductive command. Inductive a : Set := | basic : string -> a | complex : string -> list t -> a with t : Set := | t_intro : string * a * a -> t. Or you can substitute using the...

What about using the case tactic to create two subgoals, one to be solved given S a <= x and the other given x < S a ? case IHa. intro x. intro H. case (le_lt_dec (S a) x). Or you could do destruct IHa. case (le_lt_dec (S a) x)....

coq,dependent-type,convoy-pattern

You got it almost right. The issue is in your return clause, which is non-dependent. What you need is match n return forall (w: svector A n), (svector_is_dense w) -> (Vector.t A n) with so that D0 is not of type svector_is_dense v as it would be in your case,...

You can use tauto to prove it automatically: Section Question1. Variables P Q R: Prop. Hypotheses H1 : R -> P \/ Q. Hypotheses H2 : R -> ~Q. Theorem trans : R -> P. Proof. intro HR. tauto. Qed. If you want to prove it manually, H1 says that...

If you absolutely need to use an assumption multiple times as you suggested, you can use forward-reasoning tactics such as assert to do so without clearing it from the context, e.g. assert (HA := l1 H). assert (HB := l2 H). You can also do something like assert (H' :=...

The following is a proof that every proposition P is true forall n>=1, if P is true for 1 and if P is inductively true. Require Import Omega. Parameter P : nat -> Prop. Parameter p1 : P 1. Parameter pS : forall n, P n -> P (S n)....

If Concat is indeed a regular language constructor, you will not be able to prove your goal. There's two problems going on here: When you wrote down reglang_eq, you defined a proposition, but didn't give any proof of it. What you want to do is to replace the := by...

If we have this metatheory/hello_world.v: $ cat metatheory/hello_world.v Theorem hello_world : forall a b:Prop, a /\ b -> b /\ a. intros a b H. split. destruct H as [H1 H2]. exact H1. (* A bug: We actually need H2 here. *) intuition. Then we can see the error (with...

With the pow_func function that gallais defined, you can state your specification as lemmas, such as: Lemma pow_func0: forall (A:Type) (f: A -> A) (x: A), pow_fun f O x = f x. and Lemma pow_funcS: forall (n:nat) (A: Type) (f: A->A) (x:A), pow_fun f (S n) x = f...

You can use Sections and Let for local definitions. Section thm. Let X := ABCDEFGHIJKLMNOPQRSTUVWXYZ. Theorem succinct : prop_1 X -> prop_2 X. .... End thm. ...

c++,verification,coq,proof-of-correctness

It depends on what you mean by "proving a property". As far as I know, there are many static analysis tools for checking simple properties of C programs, and they vary widely in terms of expressiveness, ease to use, soundness of the analysis, etc. They are typically used for checking...

ocaml,type-inference,coq,induction,coinduction

You need to declare A as implicit to ask Coq to infer it for you. There are a few ways of doing it: Add the following declaration to your file: Set Implicit Arguments.. This will cause Coq to turn on automatic inference for arguments such as A for Cons, allowing...

By default, Coq assumes that if you define a notation, you want to it for pretty-printing. If you want the notation to never appear in pretty-printing, declare it as “only parsing”. Notation "a >> b" := (b a) (at level 50, only parsing). If you want a >> b to...

I'm fairly certain that this is not provable. Given your proof context: 4 subgoal a : aexp a0 : aexp st : state ______________________________________(1/4) (BEq a a0 = BTrue \/ BEq a a0 = BFalse) \/ (exists b' : bexp, BEq a a0 / st ==>b b') You need to...