HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

Proof that type does not have decidable equality in Agda

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
equalityagdatypedecidablethatdoesnothaveproof

Problem

Can one create such function in 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.