Skip to content

Sized types allow a type which is both inductive and coinductive in an inconsistent way #1946

@andreasabel

Description

@andreasabel

AIM XXIII, with Nisse and Andrea:

open import Common.Size

data SizeLt (i : Size) : Set where
  size : (j : Size< i)  SizeLt i

-- Legal again in 2.5.1
getSize : {i}  SizeLt i  Size
getSize (size j) = j

-- Structurally inductive (c), coinductive via sizes.
data U (i : Size) : Set where
  c : ((s : SizeLt i)  U (getSize s))  U i

data  : Set where

empty : U ∞  ⊥
empty (c f) = empty (f (size ∞))  -- f x <= f < c f

-- If U is a data type this should not be possible:
inh :  i  U i
inh i = c λ{ (size j)  inh j }

absurd : ⊥
absurd = empty (inh ∞)

Metadata

Metadata

Assignees

No one assigned

    Labels

    coinductionCoinductive records, musical coinductionfalseProof of the empty type which checks without known-unsafe flags (e.g. without --type-in-type)infinity-less-than-infinityBugs relating to the ∞ < ∞ rulesized typesSized types, termination checking with sized types, size inferencetype: bugIssues and pull requests about actual bugs

    Type

    No type

    Projects

    No projects

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions