# If $W$ is a Godel universal set there exists a number $x$ s.t. $Wx=x$ [closed]

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?

• 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? – Andrej Bauer Oct 3 '17 at 12:34
• 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. – chi Oct 3 '17 at 18:03
• 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. – Yuval Filmus Oct 5 '17 at 9:48
• @Yuval Filmus, I'm indeed trying to make logical deductions based on definitions, but I'm very new and inexperienced in this field. – FunnyBuzer Oct 5 '17 at 10:20
• This smells like "use the fixed-point theorem" for a well-chosen function. – Raphael Oct 5 '17 at 10:22