1

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?

Carl Mummert
  • 81,604
user3285532
  • 15
  • Do you have at your fingertips the number of indices that any particular computable function will have? – Carl Mummert Jan 22 '18 at 12:04
  • 3
    One good reason to not see a connection between infinity and extensionality is if there isn't one in fact - try showing that the answer to this question is "no." – Noah Schweber Jan 22 '18 at 12:24

1 Answers1

1

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.

Geid
  • 48