Last active
November 29, 2025 14:52
-
-
Save jake-87/7fdcd1dce1ef61b3c3ddbd14755887b1 to your computer and use it in GitHub Desktop.
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
| open import Relation.Binary.PropositionalEquality | |
| open import Data.Product | |
| open import Data.Bool | |
| open import Relation.Nullary.Negation | |
| open import Data.Sum | |
| open import Data.Empty | |
| postulate LEM : ∀ {ℓ} (A : Set ℓ) → A ⊎ (¬ A) | |
| postulate funext : ∀ {ℓ} {A B : Set ℓ} {f g : A → B} → (∀ x → f x ≡ g x) → f ≡ g | |
| only-one : (A : Set) → Set | |
| only-one A = Σ (A → A) λ f → (x : A) → ¬ (f x ≡ x) | |
| only-one-bool : only-one Bool | |
| only-one-bool = not , h | |
| where | |
| h : (x : Bool) → not x ≡ x → ⊥ | |
| h false () | |
| h true () | |
| must-be-not : (f : Bool → Bool) → ¬ (f true ≡ true) → ¬ (f false ≡ false) → f ≡ not | |
| must-be-not f a b = funext h | |
| where | |
| other : ∀ (g : Bool → Bool) b → ¬ (g b ≡ b) → g b ≡ not b | |
| other g false x with g false | |
| ... | false = ⊥-elim (x refl) | |
| ... | true = refl | |
| other g true x with g true | |
| ... | false = refl | |
| ... | true = ⊥-elim (x refl) | |
| h : (x : Bool) → f x ≡ not x | |
| h false = other f false b | |
| h true = other f true a | |
| only-one-bool-unique : ∀ (x : only-one Bool) → only-one-bool ≡ x | |
| only-one-bool-unique (fst , snd) with snd true | snd false | |
| ... | p | q with must-be-not fst p q | |
| ... | refl = refl | |
| unique-LEM : ∀ {ℓ} (A : Set ℓ) → (x : A) → (∀ (y : A) → x ≡ y) → LEM A ≡ inj₁ x | |
| unique-LEM A x x₁ with LEM A | |
| ... | inj₂ y = ⊥-elim (y x) | |
| ... | inj₁ x₂ with x₁ x₂ | |
| ... | refl = refl | |
| bad : (B : Set) → B → B | |
| bad B x with LEM (only-one B) | |
| ... | inj₁ (f , _) = f x | |
| ... | inj₂ _ = x | |
| id : (A : Set) → A → A | |
| id A x = x | |
| -- Parametricity is not true with LEM. | |
| is-bad : ∀ x → ¬ (bad Bool x ≡ id Bool x) | |
| is-bad x f with unique-LEM (only-one _) only-one-bool only-one-bool-unique | |
| ... | p rewrite p with x | f | |
| ... | false | () | |
| ... | true | () | |
| parametricity-id : Set₁ | |
| parametricity-id = (f g : (A : Set) → A → A) → f ≡ g | |
| not-parametric : ¬ parametricity-id | |
| not-parametric x = is-bad true (cong-app (cong-app (x bad id) Bool) true) | |
| -- or | |
| -- not-parametric : ¬ parametricity-id | |
| -- not-parametric x with x bad id | |
| -- ... | p with cong-app (cong-app p Bool) true | |
| -- ... | k with is-bad true | |
| -- ... | f = ⊥-elim (f k) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment