Last active
May 12, 2026 19:03
-
-
Save TOTBWF/b3dbe1fb1b62018fe40870163a72e532 to your computer and use it in GitHub Desktop.
A proof of false in Agda 2.9.0
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| {-# OPTIONS -vtc.pos:30 #-} | |
| -- Credit to Naïm Favier for the idea that | |
| -- 'if b then Set else (Set → Set)' might trick | |
| -- the positivity checker. | |
| module PositivelyFalse where | |
| -------------------------------------------------------------------------------- | |
| -- Prelude | |
| data ⊥ : Set where | |
| -- Unit sans eta | |
| data ⊤ : Set where | |
| tt : ⊤ | |
| ⊤-rec : ∀ {ℓ} {A : Set ℓ} → ⊤ → A → A | |
| ⊤-rec tt x = x | |
| -------------------------------------------------------------------------------- | |
| -- False | |
| Negate : (tt : ⊤) → ⊤-rec tt (Set → Set) | |
| Negate tt X = (X → ⊥) | |
| mutual | |
| -- This tricks the positivity checker, which doesn't add | |
| -- an edge from the second argument of P to Negate. | |
| P : (tt : ⊤) → ⊤-rec tt (Set → Set) | |
| P = Negate | |
| -- This in turn breaks positivity checking for FixP | |
| data FixP : Set where | |
| wrap : P tt FixP → FixP | |
| no-fixp : FixP → ⊥ | |
| no-fixp (wrap x) = x (wrap x) | |
| yet-fixp : FixP | |
| yet-fixp = wrap no-fixp | |
| bang : ⊥ | |
| bang = no-fixp yet-fixp |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment