Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Defining constants using existence proofs in Coq

Tags:

coq

After proving an existence statement, it is often notationally convenient to introduce a constant symbol for some witness of this theorem.

As a simple example, it is much more simple to write (in typical mathematical notation)

∀x. ∅ ⊆ x.

than it is to write

∀x. ∃y. empty(y) and y ⊆ x.

I am looking to replicate this effect in Coq. Here is the basic scenario I am encountering and my attempt which leads to an error (now in real Coq code):

Variable A:Type.
Hypothesis inhabited: exists x:A, x=x.

Definition inhabitant:A.
  destruct inhabited.  
  (*Error: Case analysis on sort Type is not allowed for inductive definition ex.*)

I am wondering what this error message even means and if there is any way to get around this. Thanks!

like image 224
user4614475 Avatar asked Feb 27 '15 12:02

user4614475


People also ask

How do you prove that Coq exists?

All that you need is to provide the witness first: Inductive A := X | Y . Definition P (a: A) : bool := match a with X => true | Y => false end. Theorem test : exists a: A, P a = true.

What is prop in Coq?

The language of Coq Coq objects are sorted into two categories: the Prop sort and the Type sort: Prop is the sort for propositions, i.e. well-formed propositions are of type Prop. Typical propositions are: ∀ A B : Prop, A /\ B -> B \/ B ∀ x y : Z, x * y = 0 -> x = 0 \/ y = 0.


1 Answers

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 a variation like sigS or sigT) type whose notation is :

Hypothesis inhabited : {x : A | x = x }.
like image 90
Vinz Avatar answered Oct 10 '22 23:10

Vinz