The Coq mailing list

[roconnor AT theorem.ca]

(*
On Wed, 27 Jul 2005 
BruinBear123 AT aol.com
 wrote:

> Hi everyone.
> How can you use Coq to show that...
>
> (forall C: U0). C => (C => C) => C
>
> can be seen as a representation of the type of natural numbers?

I would show this by showing that this type and Coq's nat type are
isomorphic.
*)

Definition Nat := forall C: Set, C -> (C -> C) -> C.

Definition n2N (n:nat) : Nat :=
fun (C:_) (base:_) (next:_) => nat_rec (fun _ => C) base (fun _ => next)
n.

Definition N2n (n:Nat) : nat := n nat 0 S.

Lemma oneway : forall n, (N2n (n2N n)) = n.
Proof.
intros.
induction n.
reflexivity.
compute.
compute in IHn.
rewrite IHn.
reflexivity.
Qed.

(* We cannot porve that (n2N (N2n n)) = n because the two sides will be
intentionally different functions.  What you need to do is create an
equivalence relation stating when two Nats are the same. *)

Definition equivalent (n m : Nat) : Prop := (*...*)

Lemma theotherway : forall n, equivalent (n2N (N2n n)) n.
Proof.
(*...*)
Qed.

-- 
Russell O'Connor                                      <http://r6.ca/>
``All talk about `theft,''' the general counsel of the American Graphophone
Company wrote, ``is the merest claptrap, for there exists no property in
ideas musical, literary or artistic, except as defined by statute.''