# Prove that <Z> is not a element of NOT-SELF

I know this has been a question but based on a past experience, i thought i would rewrite it so i can get input and ask questions faster.

Suppose we have $$\text{NOT-SELF}=\{\langle M\rangle \mid M \text{ is a Turing machine that does not accept }\langle M\rangle\}$$ the set of all machines that don't accept their own coding.

Let $Z$ be a TM such that $L(Z)$ is a subset of $\text{NOT-SELF}$. Prove that $\langle Z\rangle$ is an element of $\text{NOT-SELF}$.

My answer so far is very broad and I'm trying to improve it.

If $\langle Z\rangle$ is not an element of $\text{NOT-SELF}$, than $\langle Z\rangle$ can’t be an element in $L(Z)$. Since there’s a condition that $L(Z)$ is a subset of $\text{NOT-SELF}$, this contradicts so $\langle Z\rangle$ must be an element of $\text{NOT-SELF}$.

• Z only accepts TMs that do not accept themselves (being a subset of NOT-SELF). Therefore it doesn't accept itself and is in NOT-SELF. – avakar Nov 12 '13 at 23:31
• So you deliberately posted a duplicate? – Raphael Jan 15 '14 at 8:30

Assume (i) $L(Z) \subseteq \text{NOT-SELF}$ and assume towards contradiction that (ii) $\langle Z \rangle \notin \text{NOT-SELF}$.
Because of (ii) and (i) we get that $\langle Z \rangle \notin L(Z)$.
(if it was in $L(Z)$ and $L(Z)$ is a subset of $\text{NOT-SELF}$, it must also be in $\text{NOT-SELF})$.
Thus, $Z$ does not accepts its own encoding. Thus, by the definition of $\text{NOT-SELF}$ it should be that $\langle Z \rangle \in \text{NOT-SELF}$, which is a contradiction.