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?
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.