Are all infinite sets of indices of computable functions extensional?

178 Views Asked by At

Let $I$ be any set of indices of computable functions. Let $\Phi_i$ denote the $i-th$ computable function. A set of indices of computable functions is extensional if for all $i, j$: $$\text{if } i \in I \wedge \Phi_i \backsimeq \Phi_j \text{ then } j \in I $$

Is "I is infinite if and only if I is extensional" true?

As you might have guessed, I'm studying for an exam and have no clue on how to perform this exercise. I don't see any connection between infinity and extensionality. Could anybody provide any guidance?

1

There are 1 best solutions below

0
On BEST ANSWER

My guess is:

$ \rightarrow$: Set $ \{i|$I is odd$\}$ is not an extensional set, but it is an infinite set nonetheless, therefore this side of the implication does not hold.

$\leftarrow $: I am having difficulties with this one: because of the padding lemma, every recursive function has infinitely many indices, so the moment the set contains a function, there will be infinitely many equivalent ones. But if the set is empty, is it extensional? How can we find an empty extensional set?

Edit:Rice's Theorem states a property is trivial if it holds for no computable function, so an empty set is extensional, but I cannot think of such a property.

Hope somebody can answer.

PS: good luck, see you tomorrow.