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?

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