Equality

Authors:

Yannick Forster

Théo Winterhalter

Files:

This time we're going to look at equality and how it is defined in Rocq. We'll also look at other possible definitions of equality and their properties. In fact, we'll start with one which is more common in set theory.

From Stdlib Require Import List Lia.
Import ListNotations.

Set Default Goal Selector "!".

Leibniz equality

Leibniz proposed the following definition for equality: two objects are equal when they have exactly the same properties.

Formally, we can define u = v as P u <-> P v for all predicates P. It is in fact enough to define it using an implication instead of equivalence, i.e. as forall P, P u -> P v. Indeed, the two definitions are equivalent:

A: Type
u, v: A

(forall P : A -> Prop, P u <-> P v) <-> (forall P : A -> Prop, P u -> P v)
A: Type
u, v: A

(forall P : A -> Prop, P u <-> P v) <-> (forall P : A -> Prop, P u -> P v)
A: Type
u, v: A

(forall P : A -> Prop, P u <-> P v) -> forall P : A -> Prop, P u -> P v
A: Type
u, v: A
(forall P : A -> Prop, P u -> P v) -> forall P : A -> Prop, P u <-> P v
A: Type
u, v: A

(forall P : A -> Prop, P u <-> P v) -> forall P : A -> Prop, P u -> P v
firstorder.
A: Type
u, v: A

(forall P : A -> Prop, P u -> P v) -> forall P : A -> Prop, P u <-> P v
A: Type
u, v: A
e: forall P : A -> Prop, P u -> P v
P: A -> Prop

P u <-> P v
A: Type
u, v: A
e: forall P : A -> Prop, P u -> P v
P: A -> Prop

P u -> P v
A: Type
u, v: A
e: forall P : A -> Prop, P u -> P v
P: A -> Prop
P v -> P u
A: Type
u, v: A
e: forall P : A -> Prop, P u -> P v
P: A -> Prop

P u -> P v
apply e.
A: Type
u, v: A
e: forall P : A -> Prop, P u -> P v
P: A -> Prop

P v -> P u
A: Type
u, v: A
e: forall P : A -> Prop, P u -> P v
P: A -> Prop

P u -> P u
auto. Qed.

The magic operates above with the second apply e. It turns P v -> P u into P u -> P u. That's because it applied e with a predicate Q x := P u -> P x. Indeed e Q now has type (P u -> P u) -> (P u -> P v).

Module Leibniz.

Let us now play with this notion of equality. We define it as follows.

  Definition leib_eq {A} (u v : A) : Prop :=
    forall (P : A -> Prop), P u -> P v.

We pick a nice notation for it.

  Notation "u == v" := (leib_eq u v) (at level 80).

We can prove various properties of this equality, in particular that it is an equivalence and a congruence.

We'll start with reflexivity. Proving a == a is the same as proving forall P, P a -> P a. Seen that way, it should be easy to see what one is supposed to do. We assume P and some h : P a and we have to prove P a. That we do using h. In a sense we are just defining a particular case of the identity function.

  Definition refl {A} (a : A) : a == a :=
    fun P (h : P a) => h.

The proof of symmetry is the same as showing that the definition of equality can be given with both <-> and ->.

  Definition sym {A} (u v : A) (e : u == v) : v == u :=
    fun P => e (fun x => P x -> P u) (refl u P).

Transitivity is composition:

  
A: Type
u, v, w: A
e: u == v
e': v == w

u == w
A: Type
u, v, w: A
e: u == v
e': v == w

u == w
A: Type
u, v, w: A
e: u == v
e': v == w
P: A -> Prop

P u -> P w
A: Type
u, v, w: A
e: u == v
e': v == w
P: A -> Prop

P u -> P v
apply e. Defined.
trans = fun (A : Type) (u v w : A) (e : u == v) (e' : v == w) => (fun P : A -> Prop => e' (fun w0 : A => P u -> P w0) (e P)) : u == w : forall {A : Type} (u v w : A), u == v -> v == w -> u == w Arguments trans {A}%_type_scope u v w e e' P _

We saw the tactic f_equal in the first lecture. It allows proving f x = f y from x = y, i.e. it lets us apply a function to both sides of an equality. When u == v, we have P u -> P v for all P, so in particular, by taking P x := Q (f x) we have Q (f u) -> Q (f v) for all Q. This is how we get f u == f v from u == v.

  
A, B: Type
f: A -> B
u, v: A
e: u == v

f u == f v
A, B: Type
f: A -> B
u, v: A
e: u == v

f u == f v
A, B: Type
f: A -> B
u, v: A
e: u == v
P: B -> Prop

P (f u) -> P (f v)
A, B: Type
f: A -> B
u, v: A
e: u == v
P: B -> Prop

P (f u) -> P (f u)
apply refl. Defined.

We can still prove equalities like we did before with this definition. The main difference is that instead of tactics like f_equal, we have to apply the lemmas manually.

  
n: nat

n + 0 == n
n: nat

n + 0 == n

0 + 0 == 0
n: nat
ih: n + 0 == n
S n + 0 == S n

0 + 0 == 0
apply refl.
n: nat
ih: n + 0 == n

S n + 0 == S n
n: nat
ih: n + 0 == n

S (n + 0) == S n
n: nat
ih: n + 0 == n

n + 0 == n
assumption. Qed.

We can also discriminate between 0 and S n this way. We just have to instantiate S n == 0 with the right P. We're going to get P (S n) -> P 0 so we want P 0 to be False and P (S n) to be provable, so we pick True.

  
n: nat

S n == 0 -> False
n: nat

S n == 0 -> False
n: nat
e: S n == 0

False
n: nat
e: (fun x : nat => match x with | 0 => False | S _ => True end) (S n) -> (fun x : nat => match x with | 0 => False | S _ => True end) 0

False
n: nat
e: True -> False

False
n: nat
e: True -> False

True
constructor. Qed.
Exercise: Properties of Leibniz equality

Prove that Leibniz equality is reflexive, symmetric, transitive and a congruence, using proof terms. Then prove n + 0 == n and that S n == 0 is absurd.

  Definition refl' {A} (a : A) : a == a :=
    REPLACE_ME.

  Definition sym' {A} (u v : A) (e : u == v) : v == u :=
    REPLACE_ME.

  Definition trans' {A} (u v w : A) (e : u == v) (e' : v == w) : u == w :=
    REPLACE_ME.

  Definition f_equal' {A B} (f : A -> B) {u v} (e : u == v) : f u == f v :=
    REPLACE_ME.

  

forall n : nat, n + 0 == n

forall n : nat, n + 0 == n
Admitted.

forall n : nat, S n == 0 -> False

forall n : nat, S n == 0 -> False
Admitted.

The standard equality of Rocq, the one you've been using since lesson 1, is not defined using Leibniz's principle. Instead it is defined as an inductive type. We will see however that the two notions are equivalent, even though the inductive one has serious advantages.

  Module EqDef.

Below is how Rocq's equality is defined (Print "=" would have yielded the same result).

    Inductive eq {A} (u : A) : A -> Prop :=
    | eq_refl : eq u u.

Let us analyse this inductive type a bit. It has two uniform parameters A : Type and u : A, and one index of type A. In the end it produces a proposition (Prop). Crucially it has only one constructor which takes no non-parameter arguments, meaning it satisfies the subsingleton criterion. This alone provides a serious advantage over Leibniz equality because it lets us eliminate equality into Type.

Now see how close the induction principle is to Leibniz equality.

    
eq_ind : forall (A : Type) (u : A) (P : A -> Prop), P u -> forall a : A, eq u a -> P a

As we were saying, we also get one in Type.

    
eq_rect : forall (A : Type) (u : A) (P : A -> Type), P u -> forall a : A, eq u a -> P a

Let us now prove the equivalence.

    
A: Type
u, v: A

eq u v -> u == v
A: Type
u, v: A

eq u v -> u == v
A: Type
u, v: A
e: eq u v

u == v
A: Type
u: A

u == u
apply refl. Qed.
A: Type
u, v: A

u == v -> eq u v
A: Type
u, v: A

u == v -> eq u v
A: Type
u, v: A
e: u == v

eq u v
A: Type
u, v: A
e: u == v

eq u u
apply eq_refl. Qed. End EqDef.
Exercise: Leibniz equality and eq

Show the equivalence between Leibniz equality and eq (from the standard library) using eq_rect, not rewrite or destruct. You can use refine if it helps.

  
Inductive eq (A : Type) (x : A) : A -> Prop := eq_refl : x = x. Arguments eq {A}%_type_scope x _ Arguments eq_refl {A}%_type_scope {x}, [_] _
eq_rect : forall [A : Type] (x : A) (P : A -> Type), P x -> forall y : A, x = y -> P y eq_rect is not universe polymorphic Arguments eq_rect [A]%_type_scope x P%_function_scope eq_refl y e (where some original arguments have been renamed) eq_rect is transparent Expands to: Constant Corelib.Init.Logic.eq_rect Declared in library Corelib.Init.Logic, line 379, characters 0-115
End Leibniz.

Equality as an inductive type

We go back to using eq with notation = from the standard library.

We first prove symmetry and transitivity using eq_ind. They are essentially the same proofs as for Leibniz equality.

Definition eq_sym {A} {u v : A} (e : u = v) : v = u :=
  eq_ind _ (fun x => x = u) eq_refl _ e.

Definition eq_trans {A} {u v w : A} (e : u = v) (e' : v = w) : u = w :=
  eq_ind _ (fun x => u = x) e _ e'.

Since eq is an inductive type we can also use pattern matching to reason about it. When matching on an equality e : u = v, the only constructor is eq_refl forcing v to be exactly u in the eq_refl branch.

This is why, for symmetry, we don't need to prove v = u but actually u = u and so eq_refl is a valid proof.

Definition eq_sym' {A} {u v : A} (e : u = v) : v = u :=
  match e with
  | eq_refl => eq_refl
  end.

Now we prove transitivity, that is u = v -> v = w -> u = w. For this, we match on e : u = v, so v is unified with u, meaning we only need to prove u = w -> u = w which is easy.

Note that to do it, we abstract over e' inside and apply it again outside: This is because the change of v to u only applies to everything in the branch.

In other words, we first write a proof of v = w -> u = w using equality e : u = v, and then we apply it to e' : v = w.

The command has indeed failed with message: In environment A : Type u : A v : A w : A e : u = v e' : v = w The term "e'" has type "v = w" while it is expected to have type "u = w".
Definition eq_trans' {A} {u v w : A} (e : u = v) (e' : v = w) : u = w := match e with | eq_refl => fun e' => e' end e'.

As for all other inductive types, we can also use the destruct tactic on equalities. It does the same as pattern matching. If you destruct e : u = v it will unify v with u in the goal, so that f u = f v becomes f u = f u which is provable by reflexivity.

A, B: Type
f: A -> B
u, v: A

u = v -> f u = f v
A, B: Type
f: A -> B
u, v: A

u = v -> f u = f v
A, B: Type
f: A -> B
u, v: A
e: u = v

f u = f v
A, B: Type
f: A -> B
u: A

f u = f u
reflexivity. Qed. Definition f_equal'' A B (f : A -> B) u v (e : u = v) : f u = f v := match e with | eq_refl => eq_refl end.
Exercise: Symmetry, transitivity and congruence of eq

Show symmetry, transitivity and congruence (f_equal) for eq, once using eq_ind / eq_rect and once using pattern matching on equality.

eq_ind is similar to eq_rect but for propositions.

eq_ind : forall [A : Type] (x : A) (P : A -> Prop), P x -> forall y : A, x = y -> P y eq_ind is not universe polymorphic Arguments eq_ind [A]%_type_scope x P%_function_scope eq_refl y e (where some original arguments have been renamed) eq_ind is transparent Expands to: Constant Corelib.Init.Logic.eq_ind Declared in library Corelib.Init.Logic, line 379, characters 0-115
Exercise: Parameters and indices of equality

Identify the parameters (uniform and non-uniform) and indices of eq. Then consider the following definition of equality eq_ts with rules for transitivity and symmetry. What are the parameters (uniform and non-uniform) and indices? Could the definition be changed (only syntactically) to have more parameters?

Show that eq and eq_ts are equivalent.

Inductive eq_ts {X} : X -> X -> Prop :=
| refl_eq x : eq_ts x x
| sym_eq x y : eq_ts x y -> eq_ts y x
| trans_eq x y z : eq_ts x y -> eq_ts y z -> eq_ts x z.

So why is eq defined inductively and not as Leibniz equality? The reason is that Leibniz equality only quantifies over predicates P : X -> Prop, because otherwise it would not live in Prop. However, this means that Leibniz equality cannot (directly) be used to perform rewriting in types:


forall (A : Type) (u v : A), Leibniz.leib_eq u v -> forall P : A -> Type, P u -> P v

forall (A : Type) (u v : A), Leibniz.leib_eq u v -> forall P : A -> Type, P u -> P v
A: Type
u, v: A
e: Leibniz.leib_eq u v
P: A -> Type

P u -> P v
The command has indeed failed with message: In environment A : Type u, v : A e : Leibniz.leib_eq u v P : A -> Type The term "P" has type "A -> Type" while it is expected to have type "A -> Prop" (universe inconsistency: Cannot enforce lesson7_part1.150 <= Prop).
A: Type
u, v: A
e: Leibniz.leib_eq u v
P: A -> Type

P u -> P v
Abort.

As we mentioned above, eq on the other hand satisfies the subsingleton criterion, which is why rewriting is allowed.


forall (A : Type) (u v : A), u = v -> forall P : A -> Type, P u -> P v

forall (A : Type) (u v : A), u = v -> forall P : A -> Type, P u -> P v
A: Type
u, v: A
e: u = v
P: A -> Type

P u -> P v
A: Type
u, v: A
e: u = v
P: A -> Type

P v -> P v
auto.
(fun (A : Type) (u v : A) (e : u = v) (P : A -> Type) => eq_rect_r (fun u0 : A => P u0 -> P v) (fun X : P v => X) e)
Qed.

Of course, since Leibniz equality is equivalent to eq it could still be used as definition, but every rewrite in types would require using the equivalence. Thus, we use eq directly, because it allows both pattern matching and Leibniz-like reasoning through eq_ind.

The property we just proved is called transport. We prove it again, this time with a proof term and using eq_rect:

Definition transport {A u v} (e : u = v :> A) (P : A -> Type) : P u -> P v :=
  match e with
  | eq_refl => fun a => a
  end.

Definition transport' {A u v} (e : u = v :> A) (P : A -> Type) : P u -> P v :=
  eq_rect u (fun v : A => P u -> P v) (fun a => a) v e.

Congruence for dependent functions

We've now seen essentially all the definitions we've been using until now. Let us have a look at more complicated things. We're first going to look at dependent functions and try to adapt f_equal to them.

The command has indeed failed with message: In environment A : Type B : A -> Type f : forall x : A, B x u : A v : A The term "f v" has type "B v" while it is expected to have type "B u".

Even just stating the lemma fails. That's because f u : B u and f v : B v and B u and B v are not a priori the same type. They are equal, assuming u = v, however! Thankfully we have just seen how to go from B u to B v: we just use transport.

We'll provide a nice notation for it, to make things more readable.

Notation "e # t" := (transport e _ t) (t at next level, at level 19).

A: Type
B: A -> Type
f: forall x : A, B x
u, v: A
e: u = v

e # f u = f v
A: Type
B: A -> Type
f: forall x : A, B x
u, v: A
e: u = v

e # f u = f v
A: Type
B: A -> Type
f: forall x : A, B x
u: A

eq_refl # f u = f u

Notice how transport computes!

  
A: Type
B: A -> Type
f: forall x : A, B x
u: A

f u = f u
reflexivity. Qed.
Exercise: Congruence for dependent functions

Show a lemma similar to f_equal but for dependent functions, i.e. functions of type forall (x : A), B x. This time, do not use transport.

Equality and inversion

If you remember, we've been using equality through the remember tactic to help when induction (or destruct) was forgetting information. Like so:

Inductive even : nat -> Prop :=
| even0 : even 0
| evenS : forall n, even n -> even (S (S n)).

n: nat

even (S (S n)) -> even n
n: nat

even (S (S n)) -> even n
n: nat
h: even (S (S n))

even n
n: nat

even n
n, n0: nat
h: even n0
even n
Abort.
n: nat

even (S (S n)) -> even n
n: nat

even (S (S n)) -> even n
n: nat
h: even (S (S n))

even n
n, m: nat
e: m = S (S n)
h: even m

even n
n: nat
e: 0 = S (S n)

even n
n, n0: nat
e: S (S n0) = S (S n)
h: even n0
even n
n: nat
e: 0 = S (S n)

even n
discriminate.
n, n0: nat
e: S (S n0) = S (S n)
h: even n0

even n
n, n0: nat
e: S (S n0) = S (S n)
h: even n0
H0: n0 = n

even n
n: nat
h: even n
e: S (S n) = S (S n)

even n
assumption. Qed.

This you already knew. Let's now do it with a proof term directly.

Here we use a more advanced pattern matching notation that lets us give a name to the index of the thing we match on: we write h in even m to give a name m to the index. We write a return clause that depends on this m that says m = S (S n) -> even n.

So since h : even (S (S n)), the type of the whole match expression is going to be m = S (S n) -> even n where m is replaced by S (S n), in other words it will have type S (S n) = S (S n) -> even n. This is why we apply the whole match to eq_refl : S (S n) = S (S n) and it then has type even n.

Now we get two branches, one in which m is replaced by 0 and one in which it is replaced by S (S m). In the 0 branch, we thus have to show 0 = S (S n) -> even n. We discriminate the equality using transport to go from P 0 to P (S (S n)) such that P 0 is True and P (S (S n)) is even n (no need to go through False).

In the S (S m) branch, we have S (S m) = S (S n) so we first prove that m = n by applying pred on both sides twice and use that equality to go from even m to even n.

Definition evenSS_inv_alt n (h : even (S (S n))) : even n :=
  match h in even m return m = S (S n) -> even n
  with
  | even0 =>
    fun (e : 0 = S (S n)) =>
      transport e (fun x => match x with 0 => True | _ => even n end) I
  | evenS m h' =>
    fun (e : S (S m) = S (S n)) =>
      (f_equal (fun x => pred (pred x)) e) # h'
  end eq_refl.
Exercise: Even numbers

Define the inductive predicate for even natural numbers we already saw several times (try to do it without having to look it up).

Then prove that even (S (S n)) implies even n. Try to do it both using tactics (for instance using the remember tactic, but ideally without using inversion directly on even) and by writing a proof term directly.

Do the same to prove that even 1 is false.

Finally, show that n cannot be even at the same time as S n. (This time you can just do it using tactics.)

Equality principles

Some equalities that we would expect to hold cannot be proven in Rocq without assuming extra principles (axioms). The following exercises explore some of them.

Exercise: Mapping the identity

Define the map function on lists.

Show that map (fun x => x) l is the same as l. Can you prove that map (fun x => x) is equal to the identity function?

Exercise: Equality principles

We give some equality principles below. You may assume some of them when solving the exercises below. Try to assume only what you need.

Show that map (fun x => x) is equal to the identity function.

Show that inhabited propositions are equal to True. Similarly, show that uninhabited propositions are equal to False.

Show that two predicates are equal as soon as they are logically equivalent: i.e. as soon as forall x, P x <-> Q x.

Show that proof irrelevance follows from proposition extensionality.

Show that UIP follows from proof irrelevance.

Show that UIP and K are equivalent.

Definition FunExt :=
  forall A B (f g : A -> B), (forall x, f x = g x) -> f = g.

Definition PropExt :=
  forall (P Q : Prop), (P <-> Q) -> P = Q.

Definition ProofIrrelevance :=
  forall (P : Prop) (p q : P), p = q.

Definition UIP :=
  forall A (u v : A) (p q : u = v), p = q.

Definition K :=
  forall A (u : A) (e : u = u), e = eq_refl.
Exercise: Boolean equality of natural numbers

Define Boolean equality for natural numbers, i.e. some eq_nat : nat -> nat -> bool. (You may have already done it, but try to do it again.)

Show that when eq_nat n m is true, then n = m. Show that when it is false, then n <> m.

Deduce that equality of natural numbers is decidable. This is typically achieved by defining eq_dec : forall n m, { n = m } + { n <> m }. You can first do it with tactics but try to do it with a proof term.

To know more about the { _ } + { _ } type, execute the following commands. Locate can tell you what is the name of an object or notation. Print for an inductive will tell you the name and type of its constructors.

Notation "{ A } + { B }" := (sumbool A B) (* A in scope _type_scope, B in scope _type_scope *) : type_scope (default interpretation) (from Corelib.Init.Specif)
Inductive sumbool (A B : Prop) : Set := left : A -> {A} + {B} | right : B -> {A} + {B}. Arguments sumbool (A B)%_type_scope Arguments left {A B}%_type_scope _, [_] _ _ Arguments right {A B}%_type_scope _, _ [_] _
Exercise: Extensionality of subset types

Show extensionality for subset types. In other words, to prove that exist _ x hx = exist _ y hy, it is enough to show x = y.

Equivalences

There are many ways to define equivalence (of types) in Rocq. We will choose one using some notion of unique existence, defined below.

We will say that a function is an equivalence when there exists a unique antecedent to each point.

unique = fun (A : Type) (P : A -> Prop) (x : A) => P x /\ (forall x' : A, P x' -> x = x') : forall [A : Type], (A -> Prop) -> A -> Prop Arguments unique [A]%_type_scope P%_function_scope x
Notation "{ ! x | P }" := (sig (unique (fun x => P))) : type_scope. Notation "{ ! x : A | P }" := (sig (A := A) (unique (fun x => P))) : type_scope. Definition isEquiv {X Y} (f : X -> Y) := forall y, { ! x | y = f x }. Definition equivalence X Y := { f : X -> Y & isEquiv f }.
Exercise: Equivalences

Show that equivalences form an equivalence relation, that is that they are reflexive, symmetric and transitive.

Next, show that nat is equivalent to nat*, i.e. nonzero natural numbers.

Discriminating types

We've seen before how to show true <> false or 0 <> S n. We can also distinguish types. We cannot do it the same way as before by matching on them because we cannot match on types. Instead we have to exploit properties that hold for one and not the other.

For instance, we can show that unit and bool are different by first showing that all elements of unit are equal. Then if unit = bool, then all elements of bool must be equal. But we already know two different elements of type bool: true and false.

Definition all_equal A := forall (x y : A), x = y.


unit <> bool

unit <> bool
e: unit = bool

False
e: unit = bool

all_equal unit
e: unit = bool
h: all_equal unit
False
e: unit = bool

all_equal unit
e: unit = bool

tt = tt
reflexivity.
e: unit = bool
h: all_equal unit

False
e: unit = bool
h: all_equal bool

False
e: unit = bool
h: true = false

False
discriminate. Qed.
Exercise: Distinguishing types

Define a predicate on types that says that a type has at most one inhabitant.

Deduce that unit is different from bool.

Next, show that nat is different from bool.

Advanced exercises

The following exercises are more advanced.

Exercise: Heterogeneous equality

Until now, the equalities we considered have been homogeneous, meaning u = v requires both u and v to have the same type. You even have a notation to give the common type: u = v :> A.

In some cases, it makes sense to compare two objects of a priori different types. We can say that u : A and v : B are heterogeneously equal when, first A = B and then u = v up to a transport from A to B.

We can also define it inductively. Show that the two versions are equivalent.

Definition cast {A B} (e : A = B) (t : A) : B :=
  REPLACE_ME.

Definition heq {A B} (u : A) (v : B) :=
  { e : A = B & cast e u = v }.

Inductive Heq {A} (u : A) : forall {B}, B -> Prop :=
| heq_refl : Heq u u.

A, B: Type
u: A
v: B

heq u v -> Heq u v
A, B: Type
u: A
v: B

heq u v -> Heq u v
Admitted.
A, B: Type
u: A
v: B

Heq u v -> heq u v
A, B: Type
u: A
v: B

Heq u v -> heq u v
Admitted.
Exercise: From heterogeneous to homogeneous equality

Does heterogeneous equality imply homogeneous equality? In other words, can you prove the following? forall A (u v : A), Heq u v -> u = v

Exercise: nat and even numbers

Show that nat is equivalent to even natural numbers.

Exercise: Cantor's theorem

Prove Cantor's theorem for bool: show that there are no surjections from X to X -> bool. In other words there are no f : X -> (X -> bool) such that for all p there exists x such that f x = p.

Prove Cantor's theorem: show that there are no surjections from X to X -> Prop.

Exercise: Lawvere's fixed point theorem

Now prove the following theorem.

X, Y: Type

forall f : X -> X -> Y, (forall g : X -> Y, exists x : X, f x = g) -> forall g : Y -> Y, exists y : Y, g y = y
X, Y: Type

forall f : X -> X -> Y, (forall g : X -> Y, exists x : X, f x = g) -> forall g : Y -> Y, exists y : Y, g y = y
Admitted.
Exercise: Cantor's theorem, again

Can you get a simpler proof of Cantor's theorem for bool now?

J eliminator

We have seen eq_rect / eq_ind, but equality actually enjoys a stronger induction principle called the J eliminator. Instead of considering a predicate on an element, we also consider that the predicate depends on an equality and that we only need to show it when the equality is reflexivity to get it for all equalities.

Exercise: Deriving J

The type of J is the following. Show that you can indeed derive it.


forall (A : Type) (u : A) (P : forall z : A, u = z -> Prop) (v : A), P u eq_refl -> forall e : u = v, P v e

forall (A : Type) (u : A) (P : forall z : A, u = z -> Prop) (v : A), P u eq_refl -> forall e : u = v, P v e
Admitted.
Exercise: J and contractible singletons

We are now going to show that J is equivalent to singletons being contractible, i.e. that singletons have exactly one element. For this we are going back to the world of Leibniz equality which does not enjoy J.

You have to fill a few REPLACE_ME but you should have solved them already so you can easily copy paste your definitions.

You can then prove the equivalence at the end of the module Leibniz2.

Module Leibniz2.

  Definition leib_eq {A} (u v : A) :=
    forall (P : A -> Prop), P u -> P v.

  Notation "u == v" := (leib_eq u v) (at level 80).

  Definition refl {A} (a : A) : a == a :=
    REPLACE_ME.

  Definition sym {A} (u v : A) (e : u == v) : v == u :=
    REPLACE_ME.

  Definition trans {A} (u v w : A) (e : u == v) (e' : v == w) : u == w :=
    REPLACE_ME.

  Definition J_prop :=
    forall A (u : A) (P : forall z, u == z -> Prop) v (t : P u (refl u)) (e : u == v),
      P v e.

  Definition singleton {A} (x : A) := { y | x == y }.

  Definition incl {A} (x : A) : singleton x :=
    exist _ x (refl x).

  Definition all_equal (A : Type) : Prop :=
    REPLACE_ME.

  

(forall (A : Type) (x : A), all_equal (singleton x)) -> J_prop

(forall (A : Type) (x : A), all_equal (singleton x)) -> J_prop
Admitted.

J_prop -> forall (A : Type) (x : A), all_equal (singleton x)

J_prop -> forall (A : Type) (x : A), all_equal (singleton x)
Admitted. End Leibniz2.

Uniqueness of identity proofs

Exercise: UIP for nat

Uniqueness of identity proofs (UIP) is not provable in general but it still holds for specific types, namely types with a decidable equality. This fact is known as Hedberg's theorem.

We thus state UIP_for, so that UIP_for X means UIP holds for type X.

We're going first to prove UIP holds for nat.

Definition UIP_for X :=
  forall (u v : X) (p q : u = v), p = q.

x: nat

PeanoNat.Nat.eq_dec x x = left eq_refl
x: nat

PeanoNat.Nat.eq_dec x x = left eq_refl
Admitted.
x, y: nat

forall e : x = y, match PeanoNat.Nat.eq_dec x y with | left e' => eq_ind x (eq x) eq_refl y e' = e | right _ => True end
x, y: nat

forall e : x = y, match PeanoNat.Nat.eq_dec x y with | left e' => eq_ind x (eq x) eq_refl y e' = e | right _ => True end
Admitted.
x: nat

forall e : x = x, e = eq_refl
x: nat

forall e : x = x, e = eq_refl
Admitted.

UIP_for nat

UIP_for nat
Admitted.
Exercise: Hedberg's theorem

We are now going to prove the general case. Prove Hedberg's theorem as follows.

Definition HF X (f : forall (x y : X), x = y -> x = y) :=
  forall x y (e e' : x = y), f x y e = f x y e'.

X: Type

(exists y, HF X y) -> UIP_for X
X: Type

(exists y, HF X y) -> UIP_for X
Admitted.
X: Type

(forall x y : X, x = y \/ x <> y) -> UIP_for X
X: Type

(forall x y : X, x = y \/ x <> y) -> UIP_for X
Admitted.
Exercise: Stable equality

Using FunExt, we can show that two functions of type nat -> bool are equal if and only if they are not not equal. Prove it.

Definition stable (P : Prop) :=
  ~~P -> P.

X: Type

FunExt -> (forall x y : X, stable (x = y)) -> {x : forall x y : X, x = y -> x = y | HF X x}
X: Type

FunExt -> (forall x y : X, stable (x = y)) -> {x : forall x y : X, x = y -> x = y | HF X x}
Admitted.

FunExt -> forall f g : nat -> bool, stable (f = g)

FunExt -> forall f g : nat -> bool, stable (f = g)
Admitted.

Univalence

Exercise: Univalence

You may or may not have heard of homotopy type theory (HoTT) and univalent foundations. This is a relatively recent development in which equality of types corresponds to equivalences. This essentially justifies the informal mathematical practice of considering isomorphic objects to be the same.

Define a term to_equiv that inhabits equivalence X Y from X = Y.

Univalence is then stated as this function itself being an equivalence.

Definition to_equiv X Y : X = Y -> equivalence X Y :=
  REPLACE_ME.

Definition Univalence :=
  forall (X Y : Type), isEquiv (to_equiv X Y).
Exercise: Equivalent types are equal

Show that, assuming univalence, equivalent types are equal.

Exercise: Univalence and UIP

Univalence is incompatible with UIP. One way is to show that equivalence A B = (A = B) and that there are two equivalences between bool and itself, thus negating UIP.


Univalence -> ~ UIP

Univalence -> ~ UIP
Admitted.