Let $W$ be a subset of $\mathbb{N} \times \mathbb{N}$. Suppose $W$ is the Godel universal enumerable set (for the class of all enumerable subsets of $\mathbb{N}$, i.e. for any enumerable set $V$ subset of $\mathbb{N} \times \mathbb{N}$ there exists a total computable function $s:\mathbb{N} \rightarrow \mathbb{N}$ s.t. $\langle n,x \rangle \in V \iff \langle s(n),x \rangle \in W$.

  1. Prove that there exists a number $x \in \mathbb{N}$ in s.t. $W_x=\{x\}$.
  2. Prove that for $y$ not equal to $x$ s.t. $W_x=\{y\}$ and $W_y=\{x\}$.

My argument for the first is that since $W$ is a Godel universal set, there must be some natural number $x$ s.t. $W_x=\{x\}$, using the fact that there exist a total computable function, and any total computable function have a total computable extension s.t. $a=b$ iff $W_a=W_b$.

Do you think this is correct?

How can I use this argument for the second part?


closed as unclear what you're asking by chi, Evil, David Richerby, Raphael Oct 5 '17 at 10:21

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ You should state explicitly that $W$ is a Gödel universal set when you introduce it in the first line of the text. What is a Gödel universal set? $\endgroup$ – Andrej Bauer Oct 3 '17 at 12:34
  • 1
    $\begingroup$ Why is this tagged complexity theory? Anyway, you should really provide the required definitions. As it is, I believe the question can not be answered. $\endgroup$ – chi Oct 3 '17 at 18:03
  • $\begingroup$ If you are not sure whether your argument is correct, that probably means that it is incorrect. A correct argument will be "clearly" or "obviously" correct. Use the definitions to logically deduce what you are asked to prove. $\endgroup$ – Yuval Filmus Oct 5 '17 at 9:48
  • $\begingroup$ @Yuval Filmus, I'm indeed trying to make logical deductions based on definitions, but I'm very new and inexperienced in this field. $\endgroup$ – FunnyBuzer Oct 5 '17 at 10:20
  • 1
    $\begingroup$ This smells like "use the fixed-point theorem" for a well-chosen function. $\endgroup$ – Raphael Oct 5 '17 at 10:22

Browse other questions tagged or ask your own question.