[Agda] Prop in Agda 2.6
Jon Sterling
jon at jonmsterling.com
Wed May 22 22:04:11 CEST 2019
Dear Andy,
On Wed, May 22, 2019, at 2:50 PM, Andrew Pitts wrote:
> Dear John,
>
> > On 22 May 2019, at 18:28, Jon Sterling <jon at jonmsterling.com> wrote:
> >
> > Hi Andy,
> >
> > This seems consistent with an interpretation of non-cubical agda into extensional type theory,
>
> or, to put it crudely, the set theoretic model of type theory can give
> a model of these axioms.
>
> > but I just want to mention something I'd noticed before: if you wanted to add 'untrunc' to Agda, you might be tempted to have a beta rule. But this appropriate beta rule would induce equality reflection for proofs of propositions, which one probably doesn't want in the formal system.
>
> Interesting. Can we clarify what you mean? If A : Set and e : isProp A,
> then for any x : A we have that untrunc e (squash x) and x are
> propositionally equal (using e). Conversely for any y : ∥ A ∥ we have
> that squash (untrunc e y) and y are both elements of ∥ A ∥ in Prop and
> so are definitionally equal. Were you suggesting not making a REWRITE
> for untrunc e (squash x) and x? (I don’t think I need to)
Indeed, I note that if you have such a REWRITE rule, then you can prove the following instance of equality reflection:
M, N : A P : is-prop(A)
-----------------------------------------
M = N : A
The proof works as follows:
1. I have squash(M) == squash(N) : is-prop(A) by proof irrelevance
2. I have untrunc(P,squash(M)) == untrunc(P,squash(N)) : A by the congruence with untrunc
3. I have M == N : A by transitivity on both sides with the judgmental beta rule
This is why in the proof assistant, one would not want to construe the beta principle for unsquash as a judgmental rewrite.
Best,
Jon
>
> Andy
>
> >
> > Best,
> > Jon
> >
> >
> >
> > On Wed, May 22, 2019, at 12:47 PM, Andrew Pitts wrote:
> >> I’m interested in using the built-in sort of definitionally
> >> proof-irrelevant propositions that Agda 2.6 introduced. I have
> >> readthedocs at
> >> <https://agda.readthedocs.io/en/latest/language/prop.html>.
> >>
> >> For the development I have in mind (which assumes axiom K) I need Prop
> >> to be extensional
> >>
> >> postulate
> >> propext :
> >> {l : Level}
> >> {P Q : Prop l}
> >> (_ : P → Q)
> >> (_ : Q → P)
> >> → ------------
> >> P ≡ Q
> >>
> >> and to be able to “untruncate hprops" (in particular, to be able to
> >> untruncate identity types, in the presence of axiom K).
> >>
> >> data ∥_∥ {l : Level}(A : Set l) : Prop l where
> >> squash : A → ∥ A ∥
> >>
> >> isProp : {l : Level} → Set l → Set l
> >> isProp A = (x y : A) → x ≡ y
> >>
> >> postulate
> >> untrunc :
> >> {l : Level}
> >> {A : Set l}
> >> (_ : isProp A)
> >> → ------------
> >> ∥ A ∥ → A
> >>
> >> Neither of the postulates propext or untrunc is provable in Agda 2.6, is it?
> >>
> >> I think they are logically consistent axioms. But is there a better way
> >> than just postulating them?
> >>
> >> Andy
> >>
> >>
> >>
> >> _______________________________________________
> >> Agda mailing list
> >> Agda at lists.chalmers.se
> >> https://lists.chalmers.se/mailman/listinfo/agda
> >>
> > _______________________________________________
> > Agda mailing list
> > Agda at lists.chalmers.se
> > https://lists.chalmers.se/mailman/listinfo/agda
>
>
More information about the Agda
mailing list