Stuck in the construction of a very simple function

Question

I am learning Coq. I am stuck on a quite silly problem (which has no motivation, it is really silly). I want to build a function from ]2,+oo] to the set of integers mapping x to x-3. That should be simple... In any language I know, it is simple. But not in Coq. First, I write (I explain with a lot of details so that someone can explain what I don't understand in the behaviour of Coq)

Definition f : forall n : nat, n > 2 -> nat.

I get a subgoal

  ============================
   forall n : nat, n > 2 -> nat

which means that Coq wants a map from a proof of n>2 to the set of integers. Fine. So I want to tell it that n = 3 + p for some integer p, and then return the integer p. I write :

intros n H.

And I get the context/subgoal

  n : nat
  H : n > 2
  ============================
   nat

Then i suppose that I have proved n = 3 + p for some integer p by

cut(exists p, 3 + p = n).

I get the context/subgoal

  n : nat
  H : n > 2
  ============================
   (exists p : nat, 3 + p = n) -> nat

subgoal 2 (ID 6) is:
 exists p : nat, 3 + p = n

I move the hypothesis in the context by

intro K.

I obtain:

  n : nat
  H : n > 2
  K : exists p : nat, 3 + p = n
  ============================
   nat

subgoal 2 (ID 6) is:
 exists p : nat, 3 + p = n

I will prove the existence of p later. Now I want to finish the proof by exact p. So i need first to do a

destruct K as (p,K).

and I obtain the error message

Error: Case analysis on sort Set is not allowed for inductive definition ex.

And I am stuck.

Arthur Azevedo De Amorim Arthur Azevedo De Amorim · Accepted Answer · 2015-01-31T18:34:41

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 - 3.

You may then wonder "but wait a second, the natural numbers aren't closed under subtraction, so how can this make sense?". Well, in Coq, subtraction on the natural numbers isn't really subtraction: it is actually truncated. If you try to subtract, say, 3 from 2, you get 0 as an answer:

Goal 2 - 3 = 0. reflexivity. Qed.

What this means in practice is that you are always allowed to "subtract" two natural numbers and get a natural number back, but in order for this subtraction make sense, the first argument needs to be greater than the second. We then get lemmas such as the following (available in the standard library):

le_plus_minus_r : forall n m, n <= m -> n + (m - n) = m

In most cases, working with a function that is partially correct, such as this definition of subtraction, is good enough. If you want, however, you can restrict the domain of f to make its properties more pleasant. I've taken the liberty of doing the following script with the ssreflect library, which makes writing this kind of function easier:

Require Import Ssreflect.ssreflect Ssreflect.ssrfun Ssreflect.ssrbool.
Require Import Ssreflect.ssrnat Ssreflect.eqtype.

Definition f (n : {n | 2 < n}) : nat :=
  val n - 3.

Definition finv (m : nat) : {n | 2 < n} :=
  Sub (3 + m) erefl.

Lemma fK : cancel f finv.
Proof.
move=> [n Pn] /=; apply/val_inj=> /=.
by rewrite /f /= addnC subnK.
Qed.

Lemma finvK : cancel finv f.
Proof.
by move=> n; rewrite /finv /f /= addnC addnK.
Qed.

Now, f takes as an argument a natural number n that is greater than 2 (the {x : T | P x} form is syntax sugar for the sig type from the standard library, which is used for forming types that work like subsets). By restricting the argument type, we can write an inverse function finv that takes an arbitrary nat and returns another number that is greater than 2. Then, we can prove lemmas fK and finvK, which assert that fK and finvK are inverses of each other.

On the definition of f, we use val, which is ssreflect's idiom for extracting the element out of a member of a type such as {n | 2 < n}. The Sub function on finv does the opposite, packaging a natural number n with a proof that 2 < n and returning an element of {n | 2 < n}. Here, we rely crucially on the fact that the < is expressed in ssreflect as a boolean computation, so that Coq can use its computation rules to check that erefl, a proof of true = true, is also a valid proof of 2 < 3 + m.

To conclude, the mysterious error message you got in the end has to do with Coq's rules governing computational types, with live in Type, and propositional types, which live in Prop. Coq's rules forbid you from using proofs of propositions to build elements that have computational content (such as natural numbers), except in very particular cases. If you wanted, you could still finish your definition by using {p | 3 + p = n} instead of exists p, 3 + p = n -- both mean the same thing, except the former lives in Type while the latter lives in Prop.

Stuck in the construction of a very simple function

1 Answers