[Agda] Problem proving inequality with HeterogeneousEquality

Donnacha Oisín Kidney mail at doisinkidney.com
Wed May 20 21:53:13 CEST 2020


Unless I’ve misunderstood I think you can do it by converting to an unindexed type like Nat first:

∈-to-ℕ : x ∈ xs → ℕ
∈-to-ℕ this = zero
∈-to-ℕ (next x∈xs) = suc (∈-to-ℕ x∈xs)

this≇next : (x∈xs : x ∈ xs) → this ≇ next x∈xs
this≇next _ t≡n with cong ∈-to-ℕ t≡n
this≇next _ t≡n | ()

I’ve attached a file with the code.

Oisín.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: ThisNext.agda
Type: application/octet-stream
Size: 567 bytes
Desc: not available
URL: <http://lists.chalmers.se/pipermail/agda/attachments/20200520/af42ecdc/attachment.obj>
-------------- next part --------------



> On 20 May 2020, at 18:43, Shin-Cheng Mu <scm at iis.sinica.edu.tw> wrote:
> 
> Hi,
> 
> The following is a typical definition of a membership
> relation --- x ∈ xs indicates that x is a member of the
> list xs:
> 
> data _∈_ {A : Set} : A → List A → Set where
>   this : ∀ {x xs} → x ∈ (x ∷ xs)
>   next : ∀ {x y xs} → y ∈ xs → y ∈ (x ∷ xs)
> 
> I encountered a question: how do I prove that "this",
> does not equal "next"?
> 
> Since they might not have the same type, I need 
> HeterogeneousEquality. In the following attempt,
> "this", with implicit arguments, has type x ∈ (x ∷ xs),
> while "next" has type y ∈ (x ∷ xs):
> 
> this≇next : ∀ {A} {x y : A} {xs}
>           → (y∈xs : y ∈ xs)
>           → this {x = x} {xs} ≇ next {x = x} {y} {xs} y∈xs
> this≇next y∈xs ()
> 
> This attempt fails, however. Agda reports the error:
> 
> Failed to solve the following constraints:
>   Is empty: this ≅ next y∈xs
> 
> How do I convince Agda that "this" is not "next"?
> 
> The Agda version is 2.6.1. I have attached the 
> simple test file below.
> 
> Thank you!
> 
> sincerely,
> Shin
> 
> 
> <HEqTest.agda>
> 
> _______________________________________________
> Agda mailing list
> Agda at lists.chalmers.se
> https://lists.chalmers.se/mailman/listinfo/agda



More information about the Agda mailing list