Comment by cionx

I don’t understand this argument. Just because functional extensionality is undecidable for arbitrary functions doesn’t mean that it is undecidable for every class of functions.

In the specific situation, let’s say that by an array we mean a finite, ordered list whose entries are indexed by the numbers 0, 1, …, n - 1 for some natural number n. Let’s also say that two arrays are equal if they have the same length and the same value at each position (in other words, they have “the same elements in the same order”).

If we now want to represent a function f as an array arr such that f(i) = arr[i] for every possible input i of f, then this will only be possible for some very specific functions: those whose domain are the set {0, 1, …, n - 1} for some natural number n. But for any two such functions f, g : {0, 1, …, n - 1} → t, their extensional equality is logically equivalent to the equality of the corresponding arrays: you really can check that f and g are extensionally equal by checking that they are represented by equal arrays.