patternModerate
Proof that type does not have decidable equality in Agda
Viewed 0 times
equalityagdatypedecidablethatdoesnothaveproof
Problem
Can one create such function in Agda ?
I am particularly interested in proof using cubical Agda.
ℕ→ℕ-undecidable : ¬ ( (f g : ℕ → ℕ ) → Dec (f ≡ g))
ℕ→ℕ-undecidable = ?I am particularly interested in proof using cubical Agda.
Solution
ℕ→ℕ-undecidable is not provable in Agda. If we postulate the law of excluded middle (LEM), it follows that equality on every set is decidable, contradicting ℕ→ℕ-undecidable. Since Agda is consistent with LEM, it follows that ℕ→ℕ-undecidable is not provable in base Agda. This holds the same for cubical and vanilla Agda.Context
StackExchange Computer Science Q#107195, answer score: 11
Revisions (0)
No revisions yet.