← Back to branch summary

~ubuntu-branches/ubuntu/wily/coq-doc/wily

« back to all changes in this revision

Viewing changes to theories/Arith/EqNat.v

  • Committer: Bazaar Package Importer
  • Author(s): Stéphane Glondu, Stéphane Glondu, Samuel Mimram
  • Date: 2010-01-07 22:50:39 UTC
  • mfrom: (1.2.2 upstream)
  • Revision ID: james.westby@ubuntu.com-20100107225039-n3cq82589u0qt0s2
Tags: 8.2pl1-1
http://bugs.debian.org/563669
http://bugs.debian.org/543545
[ Stéphane Glondu ]
* New upstream release (Closes: #563669)
  - remove patches
* Packaging overhaul:
  - use git, advertise it in Vcs-* fields of debian/control
  - use debhelper 7 and dh with override
  - use source format 3.0 (quilt)
* debian/control:
  - set Maintainer to d-o-m, set Uploaders to Sam and myself
  - add Homepage field
  - bump Standards-Version to 3.8.3
* Register PDF documentation into doc-base
* Add debian/watch
* Update debian/copyright

[ Samuel Mimram ]
* Change coq-doc's description to mention that it provides documentation in
  pdf format, not postscript, closes: #543545.

Show diffs side-by-side

added added

removed removed

Lines of Context:
theories/Arith/EqNat.v
 
1
(************************************************************************)
 
2
(*  v      *   The Coq Proof Assistant  /  The Coq Development Team     *)
 
3
(* <O___,, * CNRS-Ecole Polytechnique-INRIA Futurs-Universite Paris Sud *)
 
4
(*   \VV/  **************************************************************)
 
5
(*    //   *      This file is distributed under the terms of the       *)
 
6
(*         *       GNU Lesser General Public License Version 2.1        *)
 
7
(************************************************************************)
 
8
 
 
9
(*i $Id: EqNat.v 9966 2007-07-10 23:54:53Z letouzey $ i*)
 
10
 
 
11
(** Equality on natural numbers *)
 
12
 
 
13
Open Local Scope nat_scope.
 
14
 
 
15
Implicit Types m n x y : nat.
 
16
 
 
17
(** * Propositional equality  *)
 
18
 
 
19
Fixpoint eq_nat n m {struct n} : Prop :=
 
20
  match n, m with
 
21
    | O, O => True
 
22
    | O, S _ => False
 
23
    | S _, O => False
 
24
    | S n1, S m1 => eq_nat n1 m1
 
25
  end.
 
26
 
 
27
Theorem eq_nat_refl : forall n, eq_nat n n.
 
28
  induction n; simpl in |- *; auto.
 
29
Qed.
 
30
Hint Resolve eq_nat_refl: arith v62.
 
31
 
 
32
(** [eq] restricted to [nat] and [eq_nat] are equivalent *)
 
33
 
 
34
Lemma eq_eq_nat : forall n m, n = m -> eq_nat n m.
 
35
  induction 1; trivial with arith.
 
36
Qed.
 
37
Hint Immediate eq_eq_nat: arith v62.
 
38
 
 
39
Lemma eq_nat_eq : forall n m, eq_nat n m -> n = m.
 
40
  induction n; induction m; simpl in |- *; contradiction || auto with arith.
 
41
Qed.
 
42
Hint Immediate eq_nat_eq: arith v62.
 
43
 
 
44
Theorem eq_nat_is_eq : forall n m, eq_nat n m <-> n = m.
 
45
Proof.
 
46
  split; auto with arith.
 
47
Qed.
 
48
 
 
49
Theorem eq_nat_elim :
 
50
  forall n (P:nat -> Prop), P n -> forall m, eq_nat n m -> P m.
 
51
Proof.
 
52
  intros; replace m with n; auto with arith.
 
53
Qed.
 
54
 
 
55
Theorem eq_nat_decide : forall n m, {eq_nat n m} + {~ eq_nat n m}.
 
56
Proof.
 
57
  induction n.
 
58
  destruct m as [| n].
 
59
  auto with arith.
 
60
  intros; right; red in |- *; trivial with arith.
 
61
  destruct m as [| n0].
 
62
  right; red in |- *; auto with arith.
 
63
  intros.
 
64
  simpl in |- *.
 
65
  apply IHn.
 
66
Defined.
 
67
 
 
68
 
 
69
(** * Boolean equality on [nat] *)
 
70
 
 
71
Fixpoint beq_nat n m {struct n} : bool :=
 
72
  match n, m with
 
73
    | O, O => true
 
74
    | O, S _ => false
 
75
    | S _, O => false
 
76
    | S n1, S m1 => beq_nat n1 m1
 
77
  end.
 
78
 
 
79
Lemma beq_nat_refl : forall n, true = beq_nat n n.
 
80
Proof.
 
81
  intro x; induction x; simpl in |- *; auto.
 
82
Qed.
 
83
 
 
84
Definition beq_nat_eq : forall x y, true = beq_nat x y -> x = y.
 
85
Proof.
 
86
  double induction x y; simpl in |- *.
 
87
    reflexivity.
 
88
    intros n H1 H2. discriminate H2.
 
89
    intros n H1 H2. discriminate H2.
 
90
    intros n H1 z H2 H3. case (H2 _ H3). reflexivity.
 
91
Defined.
 
92
 
 
93
Lemma beq_nat_true : forall x y, beq_nat x y = true -> x=y.
 
94
Proof.
 
95
 induction x; destruct y; simpl; auto; intros; discriminate.
 
96
Qed.
 
97
 
 
98
Lemma beq_nat_false : forall x y, beq_nat x y = false -> x<>y.
 
99
Proof.
 
100
 induction x; destruct y; simpl; auto; intros; discriminate.
 
101
Qed.