[Agda] nontermination and Sized types
Andrew M. Pitts
amp12 at cam.ac.uk
Fri Oct 2 15:52:58 CEST 2020
> On 2 Oct 2020, at 13:36, vlad <Vlad.Rusu at inria.fr> wrote:
>
> Looking at (V2) one can notice that nonterminating' looks like a well-founded induction principle for the _<_ relation on Size, defined by j < i iff (t : Size< i). Which is strange since _<_ is *not* well founded, as ∞ < ∞ holds. Indeed, if nonterminating' were accepted then it could be used to prove that _<_ is well founded: just take P s = "there is no infinite <-decreasing sequance starting at s". So, I believe the Agda termination checker rightfully rejects the definition (V2).
I believe issue #3026 is still open and that at the moment (v2.6.1) Agda allows one to prove _<_ for Size is well-founded and hence derive a logical inconsistency. :-)
Andy
More information about the Agda
mailing list