Example for various evidence of equality

Question

I am looking for an example in Coq for various proofs of equality.
This means:
Give some type T and two elements x, y: T and two proofs p1, p2: x = y with p1 <> p2.

Answer 1

This is a classic example of incompleteness in Coq. In its main theory (i.e., without any additional axioms) it is impossible to prove or disprove the following statement:

exists (T : Type) (x y : T) (p q : x = y), p <> q.

, . ? , , , . , , forall x y : T, x = y \/ x <> y; :

UIP : forall (x y : T) (p q : x = y), p = q.

, . , , , UIP. :

proof_irrelevance : forall (P : Prop) (p q : P), p = q.

Kok's theory was developed in such a way as to allow such an axiom, avoiding contradictions, and many events do this. In this case, it is UIPperformed for all types, and not only for those that have decidable equality.

On the other hand, there are useful axioms that we can add that are incompatible with UIP. The most famous of them - Single Member axiom of the theory of homotopy type , in which roughly states that for all types Aand Bthere is a one-to-one correspondence between the evidence of equality A = Band equivalents between Aand B, ie, functions of A -> Bhaving two-way reverse. Here is a simplified version, just to explain the main idea:

Record Equiv (A B : Type) : Type := {
  equiv_l : A -> B;
  equiv_r : B -> A;
  _ : forall x, equiv_l (equiv_r x) = x;
  _ : forall x, equiv_r (equiv_l x) = x
}.

Axiom univalence : forall A B, Equiv (A = B) (Equiv A B).

, , , bool = bool: , , , :

Definition id_Equiv : Equiv bool bool.
Proof.
  apply (BuildEquiv _ _ (fun x => x) (fun x => x)); trivial.
Defined.

Definition negb_Equiv : Equiv bool bool.
Proof.
  apply (BuildEquiv _ _ negb negb); intros []; trivial.
Defined.

Lemma not_UIP : exists p q : bool = bool :> Type , p <> q.
Proof.
  exists (equiv_r _ _ (univalence bool bool) id_Equiv).
  exists (equiv_r _ _ (univalence bool bool) negb_Equiv).
  intros H.
  assert (H' : id_Equiv = negb_Equiv).
  { now rewrite <- (equiv_lr _ _ (univalence bool bool)), <- H,
                   (equiv_lr _ _ (univalence bool bool)). }
  assert (H'' : equiv_l _ _ id_Equiv true = equiv_l _ _ negb_Equiv true).
  { now rewrite H'. }
  simpl in H''. discriminate.
Qed.

, , , , . , , , . . IsEquiv isequiv_equiv_path . , Homotopy, : HoTT UniMath. , - Coq.