patternMinor
Reversing an application of `sym` to `ua` and `isoToEquiv` in cubical type theory
Viewed 0 times
applicationtheoryisotoequivcubicaltypesymandreversing
Problem
I am proving a kind of structure invariance principle for magmas in Cubical Type Theory with the Agda/Cubical library. This is done by constructing a path between two simple magmas and then transporting proofs of simple properties about this path. I have already obtained most of the proof (see my code repository) but did not manage yet to complete the following lemma.
At some point in the proof I have the following given:
Now, I would like to prove that:
There are two parts to my question:
At some point in the proof I have the following given:
- A bijection between types:
f : ℕ → ℕ₀
- The isomorphism constructed with
f:fIso : Iso ℕ ℕ₀
- A function that gives the inverse isomorphism of an isomorphism:
invIso : Iso A B → Iso B A
Now, I would like to prove that:
sym (ua (isoToEquiv fIso)) ≡ ua (isoToEquiv (invIso fIso))There are two parts to my question:
- Is this a valid theorem in HoTT? Although this statement seems valid, maybe I have produced a false statement?
- Are there built-in functions in the Agda/Cubical that may help in the proof?
Solution
The original statement in my question
is a valid statement in Homotopy Type Theory but because (homotopy-) isomorphisms are a special case of equivalences, the statement can be generalized to
It is one of the properties of
Solution
The results from 1 have been implemented and proven in the lemmas in the Agda Cubical library. The function
Historical solution
Using the hint to use
sym (ua (isoToEquiv fIso)) ≡ ua (isoToEquiv (invIso fIso))is a valid statement in Homotopy Type Theory but because (homotopy-) isomorphisms are a special case of equivalences, the statement can be generalized to
sym (ua fEquiv) ≡ (ua (invEquiv fEquiv)) (*)It is one of the properties of
ua that are informally proven in the Univalent Foundations book in section 2.10.Solution
The results from 1 have been implemented and proven in the lemmas in the Agda Cubical library. The function
uaInvEquiv of those lemmas in particular solves my problem (*). For future applications it is better to use 4 because they are more general than my own approach below.Historical solution
Using the hint to use
EquivJ, I gave a proof for the theorem that may not be the most efficient one but it worked (typechecked) for my specific case:baseIndLemma : (A : Type ℓ-zero) → (λ i → ua (idEquiv A) (~ i)) ≡ ua (invEquiv (idEquiv A))
baseIndLemma A =
sym ( ua (idEquiv A) ) ≡⟨ uaIdEquiv ⟩
sym refl ≡⟨ refl ⟩
refl ≡⟨ sym uaIdEquiv ⟩
ua (idEquiv A) ≡⟨ cong ua (equivEq (idEquiv A) (invEquiv (idEquiv A)) refl) ⟩
ua (invEquiv (idEquiv A)) ∎
myUaInvEquiv : sym (ua fEquiv) ≡ (ua (invEquiv fEquiv))
myUaInvEquiv = EquivJ
(λ _ _ e → sym (ua e) ≡ ua (invEquiv e)) (λ A → baseIndLemma A) ℕ₀ ℕ fEquivCode Snippets
baseIndLemma : (A : Type ℓ-zero) → (λ i → ua (idEquiv A) (~ i)) ≡ ua (invEquiv (idEquiv A))
baseIndLemma A =
sym ( ua (idEquiv A) ) ≡⟨ uaIdEquiv ⟩
sym refl ≡⟨ refl ⟩
refl ≡⟨ sym uaIdEquiv ⟩
ua (idEquiv A) ≡⟨ cong ua (equivEq (idEquiv A) (invEquiv (idEquiv A)) refl) ⟩
ua (invEquiv (idEquiv A)) ∎
myUaInvEquiv : sym (ua fEquiv) ≡ (ua (invEquiv fEquiv))
myUaInvEquiv = EquivJ
(λ _ _ e → sym (ua e) ≡ ua (invEquiv e)) (λ A → baseIndLemma A) ℕ₀ ℕ fEquivContext
StackExchange Computer Science Q#109895, answer score: 3
Revisions (0)
No revisions yet.