4
$\begingroup$

Can one create such function in Agda ?

ℕ→ℕ-undecidable : ¬ ( (f g :  ℕ → ℕ ) → Dec (f ≡ g)) 
ℕ→ℕ-undecidable = ?

I am particularly interested in proof using cubical Agda.

$\endgroup$
5
$\begingroup$

ℕ→ℕ-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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.