[Agda] slightly wrong sized datatype definition leads to proof of False

Vlad Rusu Vlad.Rusu at inria.fr
Sat Oct 17 23:38:09 CEST 2020


The following code shows how a slightly wrong use of sized types in a 
definition of natural numbers leads to a proof of  ⊥.

--------------{-# OPTIONS --sized --safe  #-}
open import Relation.Binary.PropositionalEquality as Eq
open import Data.Empty using (⊥; ⊥-elim)
open import Size


-------------- auxiliary--------------
→-elim : ∀ {A B : Set}  → (A → B)  → A  → B
→-elim L M = L M
-- a trick found on the Web_
data [Size<_] (i : Size) : Set where
   box : Size< i → [Size< i ]
unbox : ∀ {i} → [Size< i ] → Size< i
unbox (box j) = j

--size eliminators
size-elim :  (P : Size → Set) → (∀ i → ((j : [Size< i ]) → P (unbox j)) 
→ P i) →  ∀ i → P i
size-elim P Hind i = Hind _ λ { (box j) → size-elim P Hind j }
size-elimproved : (P : Size → Set) → (∀ i → ((j : (Size< i)) → P j ) → P 
i) →  ∀ i → P i
size-elimproved P Hind i = →-elim (λ {Hind' → size-elim P Hind' i })
                         λ {i' Hind' → Hind i' (λ { j' → Hind' (box j')  
}) }
------------ end auxiliary-----------

-- one might think that the following is a definition natural numbers 
using some Size arguments
data ℕ  {s : Size} :  Set where
  zero :  ℕ
  suc : ({s' : Size< s} → ℕ {s'}) → ℕ {s}

-- the definition is slightly wrong ("suc" should not contain 
()-parentheses) and leads to a proof of ⊥

-- introducing foo, a certain natural number
foo : ℕ
foo = size-elimproved (λ s → ℕ{s}) (λ _ H → suc λ { {j} → H j } ) _

-- foo is a successor to itself
bar : foo ≡ suc foo
bar = refl

-- which is forbidden
baz : ∀ (n : ℕ) → (n ≡ suc λ { _ } → n   ) → ⊥
baz _ ()

--hence...
zut : ⊥
zut = baz foo bar



More information about the Agda mailing list