Equality
- 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 vA: Type
u, v: A(forall P : A -> Prop, P u -> P v) -> forall P : A -> Prop, P u <-> P vfirstorder.A: Type
u, v: A(forall P : A -> Prop, P u <-> P v) -> forall P : A -> Prop, P u -> P vA: Type
u, v: A(forall P : A -> Prop, P u -> P v) -> forall P : A -> Prop, P u <-> P vA: Type
u, v: A
e: forall P : A -> Prop, P u -> P v
P: A -> PropP u <-> P vA: Type
u, v: A
e: forall P : A -> Prop, P u -> P v
P: A -> PropP u -> P vA: Type
u, v: A
e: forall P : A -> Prop, P u -> P v
P: A -> PropP v -> P uapply e.A: Type
u, v: A
e: forall P : A -> Prop, P u -> P v
P: A -> PropP u -> P vA: Type
u, v: A
e: forall P : A -> Prop, P u -> P v
P: A -> PropP v -> P uauto. Qed.A: Type
u, v: A
e: forall P : A -> Prop, P u -> P v
P: A -> PropP u -> P u
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 == wu == wA: Type
u, v, w: A
e: u == v
e': v == wu == wA: Type
u, v, w: A
e: u == v
e': v == w
P: A -> PropP u -> P wapply e. Defined.A: Type
u, v, w: A
e: u == v
e': v == w
P: A -> PropP u -> P v
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 == vf u == f vA, B: Type
f: A -> B
u, v: A
e: u == vf u == f vA, B: Type
f: A -> B
u, v: A
e: u == v
P: B -> PropP (f u) -> P (f v)apply refl. Defined.A, B: Type
f: A -> B
u, v: A
e: u == v
P: B -> PropP (f u) -> P (f u)
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: natn + 0 == nn: natn + 0 == n0 + 0 == 0n: nat
ih: n + 0 == nS n + 0 == S napply refl.0 + 0 == 0n: nat
ih: n + 0 == nS n + 0 == S nn: nat
ih: n + 0 == nS (n + 0) == S nassumption. Qed.n: nat
ih: n + 0 == nn + 0 == n
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: natS n == 0 -> Falsen: natS n == 0 -> Falsen: nat
e: S n == 0Falsen: 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) 0Falsen: nat
e: True -> FalseFalseconstructor. Qed.n: nat
e: True -> FalseTrue
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 == nAdmitted.forall n : nat, n + 0 == nforall n : nat, S n == 0 -> FalseAdmitted.forall n : nat, S n == 0 -> False
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.
As we were saying, we also get one in Type.
Let us now prove the equivalence.
A: Type
u, v: Aeq u v -> u == vA: Type
u, v: Aeq u v -> u == vA: Type
u, v: A
e: eq u vu == vapply refl. Qed.A: Type
u: Au == uA: Type
u, v: Au == v -> eq u vA: Type
u, v: Au == v -> eq u vA: Type
u, v: A
e: u == veq u vapply eq_refl. Qed. End EqDef.A: Type
u, v: A
e: u == veq u u
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.
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.
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: Au = v -> f u = f vA, B: Type
f: A -> B
u, v: Au = v -> f u = f vA, B: Type
f: A -> B
u, v: A
e: u = vf u = f vreflexivity. 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.A, B: Type
f: A -> B
u: Af u = f u
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.
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 vforall (A : Type) (u v : A), Leibniz.leib_eq u v -> forall P : A -> Type, P u -> P vA: Type
u, v: A
e: Leibniz.leib_eq u v
P: A -> TypeP u -> P vAbort.A: Type
u, v: A
e: Leibniz.leib_eq u v
P: A -> TypeP u -> P v
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 vforall (A : Type) (u v : A), u = v -> forall P : A -> Type, P u -> P vA: Type
u, v: A
e: u = v
P: A -> TypeP u -> P vauto.A: Type
u, v: A
e: u = v
P: A -> TypeP v -> P vQed.
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.
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 = ve # f u = f vA: Type
B: A -> Type
f: forall x : A, B x
u, v: A
e: u = ve # f u = f vA: Type
B: A -> Type
f: forall x : A, B x
u: Aeq_refl # f u = f u
Notice how transport computes!
reflexivity. Qed.A: Type
B: A -> Type
f: forall x : A, B x
u: Af u = f u
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: nateven (S (S n)) -> even nn: nateven (S (S n)) -> even nn: nat
h: even (S (S n))even nAbort.n: nateven nn, n0: nat
h: even n0even nn: nateven (S (S n)) -> even nn: nateven (S (S n)) -> even nn: nat
h: even (S (S n))even nn, m: nat
e: m = S (S n)
h: even meven nn: nat
e: 0 = S (S n)even nn, n0: nat
e: S (S n0) = S (S n)
h: even n0even ndiscriminate.n: nat
e: 0 = S (S n)even nn, n0: nat
e: S (S n0) = S (S n)
h: even n0even nn, n0: nat
e: S (S n0) = S (S n)
h: even n0
H0: n0 = neven nassumption. Qed.n: nat
h: even n
e: S (S n) = S (S n)even n
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.
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.
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 <> boolunit <> boole: unit = boolFalsee: unit = boolall_equal unite: unit = bool
h: all_equal unitFalsee: unit = boolall_equal unitreflexivity.e: unit = booltt = tte: unit = bool
h: all_equal unitFalsee: unit = bool
h: all_equal boolFalsediscriminate. Qed.e: unit = bool
h: true = falseFalse
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: Bheq u v -> Heq u vAdmitted.A, B: Type
u: A
v: Bheq u v -> Heq u vA, B: Type
u: A
v: BHeq u v -> heq u vAdmitted.A, B: Type
u: A
v: BHeq u v -> heq u v
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: Typeforall f : X -> X -> Y, (forall g : X -> Y, exists x : X, f x = g) -> forall g : Y -> Y, exists y : Y, g y = yAdmitted.X, Y: Typeforall f : X -> X -> Y, (forall g : X -> Y, exists x : X, f x = g) -> forall g : Y -> Y, exists y : Y, g y = y
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 eAdmitted.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
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_propAdmitted.(forall (A : Type) (x : A), all_equal (singleton x)) -> J_propJ_prop -> forall (A : Type) (x : A), all_equal (singleton x)Admitted. End Leibniz2.J_prop -> forall (A : Type) (x : A), all_equal (singleton x)
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: natPeanoNat.Nat.eq_dec x x = left eq_reflAdmitted.x: natPeanoNat.Nat.eq_dec x x = left eq_reflx, y: natforall 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 endAdmitted.x, y: natforall 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 endx: natforall e : x = x, e = eq_reflAdmitted.x: natforall e : x = x, e = eq_reflUIP_for natAdmitted.UIP_for nat
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 XAdmitted.X: Type(exists y, HF X y) -> UIP_for XX: Type(forall x y : X, x = y \/ x <> y) -> UIP_for XAdmitted.X: Type(forall x y : X, x = y \/ x <> y) -> UIP_for X
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: TypeFunExt -> (forall x y : X, stable (x = y)) -> {x : forall x y : X, x = y -> x = y | HF X x}Admitted.X: TypeFunExt -> (forall x y : X, stable (x = y)) -> {x : forall x y : X, x = y -> x = y | HF X x}FunExt -> forall f g : nat -> bool, stable (f = g)Admitted.FunExt -> forall f g : nat -> bool, stable (f = g)
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 -> ~ UIPAdmitted.Univalence -> ~ UIP