Provable coherence in OTT

Question

I'm playing with observational type theory.

Here is equality of π-types (π is the lowercase Π, i.e. π A B is the code for (x : A) -> B x) defined mutually with coercions:

π A₁ B₁ ≃ π A₂ B₂ = σ (A₂ ≃ A₁) λ P -> π _ λ x -> B₁ (coerce P x) ≃ B₂ x

and equality of functions defined accordingly (σ is the lowercase Σ):

_≅_ {A = π A₁ B₁} {π A₂ B₂} f₁ f₂ = σ (A₂ ≃ A₁) λ P -> π _ λ x -> f₁ (coerce P x) ≅ f₂ x

So instead of "equal functions map equal inputs to equal outputs" we have "equal functions map definitionally equal inputs to equal outputs".

In this setting coherence

coerce : ∀ {α β} {A : Univ α} {B : Univ β} -> ⟦ A ≃ B ⟧ᵀ -> ⟦ A ⟧ᵀ -> ⟦ B ⟧ᵀ
coherence : ∀ {α β} {A : Univ α} {B : Univ β}
          -> (P : ⟦ A ≃ B ⟧ᵀ) -> (x : ⟦ A ⟧ᵀ) -> ⟦ x ≅ coerce P x ⟧ᵀ

(Univ 0 is Prop, Univ (suc α) is Type α)

is provable. The only thing I needed to postulate is

postulate ≃-refl : ∀ {α} -> (A : Univ α) -> ⟦ A ≃ A ⟧ᵀ

But we can tweak equality to handle A ≃ A as a special case (I think, trustMe needs a friend _≟_ : ∀ {α} {A : Set α} (x y : A) -> Maybe (x ≡ y)).

We still need to postulate something to define subst and other stuff.

Did I miss something? Do we lose any irrelevance? It seems suspicious to mention type equality in the definition of equality of functions. Do we lose much by restricting inputs of equal functions to be definitionally equal? Is there anything good about having strongly normalizing coherence or it doesn't matter, since it's computationally irrelevant anyway?

The code (I ignored positivity, termination and cumulativity issues altogether).

Answer 1

Firstly, thanks for asking about Observational Type Theory. Secondly, what you've done here does seem to hang together, even though it has things in different places from where Thorsten Altenkirch, Wouter Swierstra and I put them in our version of the story. Thirdly, it's no surprise (at least not to me) that coherence is derivable, leaving reflexivity the only postulate. That's true of our OTT as well, and Wouter did the proofs in Agda 1, back when we wrote that paper. Proof irrelevance and the shortness of life meant I didn't port his proofs to Agda 2.

If you've missed anything, it's lurking in your remark

We still need to postulate something to define subst and other stuff.

If you have some P : X -> Set, some a, b : X and some q : a = b, you expect to get a function in P a -> P b. The "equal functions take equal inputs to equal outputs" formulation gives you that, as refl P : P = P, so from q, we can deduce P a = P b. Your "equal functions take a given input to equal outputs" formulation does not allow you to let q bridge the gap from a to b.

In the presence of refl and subst, "two equal inputs" amounts to the same thing as "one input used in two places". It seems to me that you've moved the work into whatever else you need to get subst. Depending on how lazy your definition of coerce is (and that's how you get proof irrelevance), you will need only a postulate.

With your particular formulation, you might even get away with a homogeneous value equality. If you're fixing type gaps with coercions rather than equations, you might save yourself some trouble (and maybe get rid of that equation on the domain type in function equality). Of course, in that case, you'd need to think about how to replace the statement of coherence.

We tried quite hard to keep coercion out of the definition of equality, to retain some sort of symmetry, and to keep type equations out of value equations, mostly to have less to think about at one go. It's interesting to see that at least some parts of the construction might get easier with "a thing and its coercion" replacing "two equal things".