Library Coq.Init.Logic
Set Implicit Arguments.
Require Export Notations.
Require Import Ltac.
Notation "A -> B" := (
forall (
_ :
A),
B) :
type_scope.
Propositional connectives
True is the always true proposition
False is the always false proposition
Inductive False :
Prop :=.
not A, written ~A, is the negation of A
Create the "core" hint database, and set its transparent state for
variables and constants explicitly.
and A B, written
A /\ B, is the conjunction of
A and
B
conj p q is a proof of
A /\ B as soon as
p is a proof of
A and
q a proof of
B
proj1 and
proj2 are first and second projections of a conjunction
or A B, written A \/ B, is the disjunction of A and B
iff A B, written A <-> B, expresses the equivalence of A and B
Backward direction of the equivalences above does not need assumptions
Some equivalences
Theorem neg_false :
forall A :
Prop,
~ A <-> (A <-> False).
Theorem and_cancel_l :
forall A B C :
Prop,
(B -> A) -> (C -> A) -> ((A /\ B <-> A /\ C) <-> (B <-> C)).
Theorem and_cancel_r :
forall A B C :
Prop,
(B -> A) -> (C -> A) -> ((B /\ A <-> C /\ A) <-> (B <-> C)).
Theorem and_comm :
forall A B :
Prop,
A /\ B <-> B /\ A.
Theorem and_assoc :
forall A B C :
Prop,
(A /\ B) /\ C <-> A /\ B /\ C.
Theorem or_cancel_l :
forall A B C :
Prop,
(B -> ~ A) -> (C -> ~ A) -> ((A \/ B <-> A \/ C) <-> (B <-> C)).
Theorem or_cancel_r :
forall A B C :
Prop,
(B -> ~ A) -> (C -> ~ A) -> ((B \/ A <-> C \/ A) <-> (B <-> C)).
Theorem or_comm :
forall A B :
Prop,
(A \/ B) <-> (B \/ A).
Theorem or_assoc :
forall A B C :
Prop,
(A \/ B) \/ C <-> A \/ B \/ C.
Lemma iff_and :
forall A B :
Prop,
(A <-> B) -> (A -> B) /\ (B -> A).
Lemma iff_to_and :
forall A B :
Prop,
(A <-> B) <-> (A -> B) /\ (B -> A).
(IF_then_else P Q R), written IF P then Q else R denotes
either P and Q, or ~P and R
First-order quantifiers
ex P, or simply
exists x, P x, or also
exists x:A, P x,
expresses the existence of an
x of some type
A in
Set which
satisfies the predicate
P. This is existential quantification.
ex2 P Q, or simply
exists2 x, P x & Q x, or also
exists2 x:A, P x & Q x, expresses the existence of an
x of
type
A which satisfies both predicates
P and
Q.
Universal quantification is primitively written
forall x:A, Q. By
symmetry with existential quantification, the construction
all P
is provided too.
Inductive ex (
A:
Type) (
P:
A -> Prop) :
Prop :=
ex_intro :
forall x:
A,
P x -> ex (
A:=
A)
P.
Section Projections.
Variables (
A:
Prop) (
P:
A->Prop).
Definition ex_proj1 (
x:
ex P) :
A :=
match x with ex_intro _ a _ =>
a end.
Definition ex_proj2 (
x:
ex P) :
P (
ex_proj1 x) :=
match x with ex_intro _ _ b =>
b end.
End Projections.
Inductive ex2 (
A:
Type) (
P Q:
A -> Prop) :
Prop :=
ex_intro2 :
forall x:
A,
P x -> Q x -> ex2 (
A:=
A)
P Q.
Definition all (
A:
Type) (
P:
A -> Prop) :=
forall x:
A,
P x.
Notation "'exists' x .. y , p" := (
ex (
fun x => .. (
ex (
fun y =>
p)) ..))
(
at level 200,
x binder,
right associativity,
format "'[' 'exists' '/ ' x .. y , '/ ' p ']'")
:
type_scope.
Notation "'exists2' x , p & q" := (
ex2 (
fun x =>
p) (
fun x =>
q))
(
at level 200,
x ident,
p at level 200,
right associativity) :
type_scope.
Notation "'exists2' x : A , p & q" := (
ex2 (
A:=
A) (
fun x =>
p) (
fun x =>
q))
(
at level 200,
x ident,
A at level 200,
p at level 200,
right associativity,
format "'[' 'exists2' '/ ' x : A , '/ ' '[' p & '/' q ']' ']'")
:
type_scope.
Notation "'exists2' ' x , p & q" := (
ex2 (
fun x =>
p) (
fun x =>
q))
(
at level 200,
x strict pattern,
p at level 200,
right associativity) :
type_scope.
Notation "'exists2' ' x : A , p & q" := (
ex2 (
A:=
A) (
fun x =>
p) (
fun x =>
q))
(
at level 200,
x strict pattern,
A at level 200,
p at level 200,
right associativity,
format "'[' 'exists2' '/ ' ' x : A , '/ ' '[' p & '/' q ']' ']'")
:
type_scope.
Derived rules for universal quantification
Equality
eq x y, or simply
x=y expresses the equality of
x and
y. Both
x and
y must belong to the same type
A.
The definition is inductive and states the reflexivity of the equality.
The others properties (symmetry, transitivity, replacement of
equals by equals) are proved below. The type of
x and
y can be
made explicit using the notation
x = y :> A. This is Leibniz equality
as it expresses that
x and
y are equal iff every property on
A which is true of
x is also true of
y
Inductive eq (
A:
Type) (
x:
A) :
A -> Prop :=
eq_refl :
x = x :>A
where "x = y :> A" := (@
eq A x y) :
type_scope.
Notation "x = y" := (
eq x y) :
type_scope.
Notation "x <> y :> T" := (
~ x = y :>T) :
type_scope.
Notation "x <> y" := (
~ (x = y)) :
type_scope.
Hint Resolve I conj or_introl or_intror :
core.
Hint Resolve eq_refl:
core.
Hint Resolve ex_intro ex_intro2:
core.
Section Logic_lemmas.
Theorem absurd :
forall A C:
Prop,
A -> ~ A -> C.
Section equality.
Variables A B :
Type.
Variable f :
A -> B.
Variables x y z :
A.
Theorem eq_sym :
x = y -> y = x.
Theorem eq_trans :
x = y -> y = z -> x = z.
Theorem eq_trans_r :
x = y -> z = y -> x = z.
Theorem f_equal :
x = y -> f x = f y.
Theorem not_eq_sym :
x <> y -> y <> x.
End equality.
Definition eq_sind_r :
forall (
A:
Type) (
x:
A) (
P:
A -> SProp),
P x -> forall y:
A,
y = x -> P y.
Definition eq_ind_r :
forall (
A:
Type) (
x:
A) (
P:
A -> Prop),
P x -> forall y:
A,
y = x -> P y.
Defined.
Definition eq_rec_r :
forall (
A:
Type) (
x:
A) (
P:
A -> Set),
P x -> forall y:
A,
y = x -> P y.
Defined.
Definition eq_rect_r :
forall (
A:
Type) (
x:
A) (
P:
A -> Type),
P x -> forall y:
A,
y = x -> P y.
Defined.
End Logic_lemmas.
Module EqNotations.
Notation "'rew' H 'in' H'" := (
eq_rect _ _ H' _ H)
(
at level 10,
H' at level 10,
format "'[' 'rew' H in '/' H' ']'").
Notation "'rew' [ P ] H 'in' H'" := (
eq_rect _ P H' _ H)
(
at level 10,
H' at level 10,
format "'[' 'rew' [ P ] '/ ' H in '/' H' ']'").
Notation "'rew' <- H 'in' H'" := (
eq_rect_r _ H' H)
(
at level 10,
H' at level 10,
format "'[' 'rew' <- H in '/' H' ']'").
Notation "'rew' <- [ P ] H 'in' H'" := (
eq_rect_r P H' H)
(
at level 10,
H' at level 10,
format "'[' 'rew' <- [ P ] '/ ' H in '/' H' ']'").
Notation "'rew' -> H 'in' H'" := (
eq_rect _ _ H' _ H)
(
at level 10,
H' at level 10,
only parsing).
Notation "'rew' -> [ P ] H 'in' H'" := (
eq_rect _ P H' _ H)
(
at level 10,
H' at level 10,
only parsing).
Notation "'rew' 'dependent' H 'in' H'"
:= (
match H with
|
eq_refl =>
H'
end)
(
at level 10,
H' at level 10,
format "'[' 'rew' 'dependent' '/ ' H in '/' H' ']'").
Notation "'rew' 'dependent' -> H 'in' H'"
:= (
match H with
|
eq_refl =>
H'
end)
(
at level 10,
H' at level 10,
only parsing).
Notation "'rew' 'dependent' <- H 'in' H'"
:= (
match eq_sym H with
|
eq_refl =>
H'
end)
(
at level 10,
H' at level 10,
format "'[' 'rew' 'dependent' <- '/ ' H in '/' H' ']'").
Notation "'rew' 'dependent' [ 'fun' y p => P ] H 'in' H'"
:= (
match H as p in (
_ = y)
return P with
|
eq_refl =>
H'
end)
(
at level 10,
H' at level 10,
y ident,
p ident,
format "'[' 'rew' 'dependent' [ 'fun' y p => P ] '/ ' H in '/' H' ']'").
Notation "'rew' 'dependent' -> [ 'fun' y p => P ] H 'in' H'"
:= (
match H as p in (
_ = y)
return P with
|
eq_refl =>
H'
end)
(
at level 10,
H' at level 10,
y ident,
p ident,
only parsing).
Notation "'rew' 'dependent' <- [ 'fun' y p => P ] H 'in' H'"
:= (
match eq_sym H as p in (
_ = y)
return P with
|
eq_refl =>
H'
end)
(
at level 10,
H' at level 10,
y ident,
p ident,
format "'[' 'rew' 'dependent' <- [ 'fun' y p => P ] '/ ' H in '/' H' ']'").
Notation "'rew' 'dependent' [ P ] H 'in' H'"
:= (
match H as p in (
_ = y)
return P y p with
|
eq_refl =>
H'
end)
(
at level 10,
H' at level 10,
format "'[' 'rew' 'dependent' [ P ] '/ ' H in '/' H' ']'").
Notation "'rew' 'dependent' -> [ P ] H 'in' H'"
:= (
match H as p in (
_ = y)
return P y p with
|
eq_refl =>
H'
end)
(
at level 10,
H' at level 10,
only parsing).
Notation "'rew' 'dependent' <- [ P ] H 'in' H'"
:= (
match eq_sym H as p in (
_ = y)
return P y p with
|
eq_refl =>
H'
end)
(
at level 10,
H' at level 10,
format "'[' 'rew' 'dependent' <- [ P ] '/ ' H in '/' H' ']'").
End EqNotations.
Import EqNotations.
Section equality_dep.
Variable A :
Type.
Variable B :
A -> Type.
Variable f :
forall x,
B x.
Variables x y :
A.
Theorem f_equal_dep :
forall (
H:
x = y),
rew H in f x = f y.
End equality_dep.
Section equality_dep2.
Variable A A' :
Type.
Variable B :
A -> Type.
Variable B' :
A' -> Type.
Variable f :
A -> A'.
Variable g :
forall a:
A,
B a -> B' (
f a).
Variables x y :
A.
Lemma f_equal_dep2 :
forall {
A A' B B'} (
f :
A -> A') (
g :
forall a:
A,
B a -> B' (
f a))
{
x1 x2 :
A} {
y1 :
B x1} {
y2 :
B x2} (
H :
x1 = x2),
rew H in y1 = y2 -> rew f_equal f H in g x1 y1 = g x2 y2.
End equality_dep2.
Lemma rew_opp_r :
forall A (
P:
A->Type) (
x y:
A) (
H:
x=y) (
a:
P y),
rew H in rew <- H in a = a.
Lemma rew_opp_l :
forall A (
P:
A->Type) (
x y:
A) (
H:
x=y) (
a:
P x),
rew <- H in rew H in a = a.
Theorem f_equal2 :
forall (
A1 A2 B:
Type) (
f:
A1 -> A2 -> B) (
x1 y1:
A1)
(
x2 y2:
A2),
x1 = y1 -> x2 = y2 -> f x1 x2 = f y1 y2.
Theorem f_equal3 :
forall (
A1 A2 A3 B:
Type) (
f:
A1 -> A2 -> A3 -> B) (
x1 y1:
A1)
(
x2 y2:
A2) (
x3 y3:
A3),
x1 = y1 -> x2 = y2 -> x3 = y3 -> f x1 x2 x3 = f y1 y2 y3.
Theorem f_equal4 :
forall (
A1 A2 A3 A4 B:
Type) (
f:
A1 -> A2 -> A3 -> A4 -> B)
(
x1 y1:
A1) (
x2 y2:
A2) (
x3 y3:
A3) (
x4 y4:
A4),
x1 = y1 -> x2 = y2 -> x3 = y3 -> x4 = y4 -> f x1 x2 x3 x4 = f y1 y2 y3 y4.
Theorem f_equal5 :
forall (
A1 A2 A3 A4 A5 B:
Type) (
f:
A1 -> A2 -> A3 -> A4 -> A5 -> B)
(
x1 y1:
A1) (
x2 y2:
A2) (
x3 y3:
A3) (
x4 y4:
A4) (
x5 y5:
A5),
x1 = y1 ->
x2 = y2 ->
x3 = y3 -> x4 = y4 -> x5 = y5 -> f x1 x2 x3 x4 x5 = f y1 y2 y3 y4 y5.
Theorem f_equal_compose :
forall A B C (
a b:
A) (
f:
A->B) (
g:
B->C) (
e:
a=b),
f_equal g (
f_equal f e)
= f_equal (
fun a =>
g (
f a))
e.
The groupoid structure of equality
Theorem eq_trans_refl_l :
forall A (
x y:
A) (
e:
x=y),
eq_trans eq_refl e = e.
Theorem eq_trans_refl_r :
forall A (
x y:
A) (
e:
x=y),
eq_trans e eq_refl = e.
Theorem eq_sym_involutive :
forall A (
x y:
A) (
e:
x=y),
eq_sym (
eq_sym e)
= e.
Theorem eq_trans_sym_inv_l :
forall A (
x y:
A) (
e:
x=y),
eq_trans (
eq_sym e)
e = eq_refl.
Theorem eq_trans_sym_inv_r :
forall A (
x y:
A) (
e:
x=y),
eq_trans e (
eq_sym e)
= eq_refl.
Theorem eq_trans_assoc :
forall A (
x y z t:
A) (
e:
x=y) (
e':
y=z) (
e'':
z=t),
eq_trans e (
eq_trans e' e'')
= eq_trans (
eq_trans e e')
e''.
Theorem rew_map :
forall A B (
P:
B->Type) (
f:
A->B)
x1 x2 (
H:
x1=x2) (
y:
P (
f x1)),
rew [fun x =>
P (
f x)
] H in y = rew f_equal f H in y.
Theorem eq_trans_map :
forall {
A B} {
x1 x2 x3:
A} {
y1:
B x1} {
y2:
B x2} {
y3:
B x3},
forall (
H1:
x1=x2) (
H2:
x2=x3) (
H1':
rew H1 in y1 = y2) (
H2':
rew H2 in y2 = y3),
rew eq_trans H1 H2 in y1 = y3.
Lemma map_subst :
forall {
A} {
P Q:
A->Type} (
f :
forall x,
P x -> Q x) {
x y} (
H:
x=y) (
z:
P x),
rew H in f x z = f y (
rew H in z).
Lemma map_subst_map :
forall {
A B} {
P:
A->Type} {
Q:
B->Type} (
f:
A->B) (
g :
forall x,
P x -> Q (
f x)),
forall {
x y} (
H:
x=y) (
z:
P x),
rew f_equal f H in g x z = g y (
rew H in z).
Lemma rew_swap :
forall A (
P:
A->Type)
x1 x2 (
H:
x1=x2) (
y1:
P x1) (
y2:
P x2),
rew H in y1 = y2 -> y1 = rew <- H in y2.
Lemma rew_compose :
forall A (
P:
A->Type)
x1 x2 x3 (
H1:
x1=x2) (
H2:
x2=x3) (
y:
P x1),
rew H2 in rew H1 in y = rew (eq_trans H1 H2) in y.
Extra properties of equality
Theorem eq_id_comm_l :
forall A (
f:
A->A) (
Hf:
forall a,
a = f a),
forall a,
f_equal f (
Hf a)
= Hf (
f a).
Theorem eq_id_comm_r :
forall A (
f:
A->A) (
Hf:
forall a,
f a = a),
forall a,
f_equal f (
Hf a)
= Hf (
f a).
Lemma eq_refl_map_distr :
forall A B x (
f:
A->B),
f_equal f (
eq_refl x)
= eq_refl (
f x).
Lemma eq_trans_map_distr :
forall A B x y z (
f:
A->B) (
e:
x=y) (
e':
y=z),
f_equal f (
eq_trans e e')
= eq_trans (
f_equal f e) (
f_equal f e').
Lemma eq_sym_map_distr :
forall A B (
x y:
A) (
f:
A->B) (
e:
x=y),
eq_sym (
f_equal f e)
= f_equal f (
eq_sym e).
Lemma eq_trans_sym_distr :
forall A (
x y z:
A) (
e:
x=y) (
e':
y=z),
eq_sym (
eq_trans e e')
= eq_trans (
eq_sym e') (
eq_sym e).
Lemma eq_trans_rew_distr :
forall A (
P:
A -> Type) (
x y z:
A) (
e:
x=y) (
e':
y=z) (
k:
P x),
rew (eq_trans e e') in k = rew e' in rew e in k.
Lemma rew_const :
forall A P (
x y:
A) (
e:
x=y) (
k:
P),
rew [fun _ =>
P] e in k = k.
Notation sym_eq :=
eq_sym (
only parsing).
Notation trans_eq :=
eq_trans (
only parsing).
Notation sym_not_eq :=
not_eq_sym (
only parsing).
Notation refl_equal :=
eq_refl (
only parsing).
Notation sym_equal :=
eq_sym (
only parsing).
Notation trans_equal :=
eq_trans (
only parsing).
Notation sym_not_equal :=
not_eq_sym (
only parsing).
Hint Immediate eq_sym not_eq_sym:
core.
Basic definitions about relations and properties
Unique existence
Notation "'exists' ! x .. y , p" :=
(
ex (
unique (
fun x => .. (
ex (
unique (
fun y =>
p))) ..)))
(
at level 200,
x binder,
right associativity,
format "'[' 'exists' ! '/ ' x .. y , '/ ' p ']'")
:
type_scope.
Lemma unique_existence :
forall (
A:
Type) (
P:
A->Prop),
((exists x, P x) /\ uniqueness P) <-> (exists! x, P x).
Lemma forall_exists_unique_domain_coincide :
forall A (
P:
A->Prop),
(exists! x, P x) ->
forall Q:
A->Prop,
(forall x,
P x -> Q x) <-> (exists x, P x /\ Q x).
Lemma forall_exists_coincide_unique_domain :
forall A (
P:
A->Prop),
(forall Q:
A->Prop,
(forall x,
P x -> Q x) <-> (exists x, P x /\ Q x))
-> (exists! x, P x).
Being inhabited
The predicate
inhabited can be used in different contexts. If
A is
thought as a type,
inhabited A states that
A is inhabited. If
A is
thought as a computationally relevant proposition, then
inhabited A weakens
A so as to hide its computational meaning.
The so-weakened proof remains computationally relevant but only in
a propositional context.
Declaration of stepl and stepr for eq and iff
Equality for ex
Equality for ex2