Informateci

Sto provando a fare l'esercizio presente a pagina 2:
dimostrare che

[math]I = \{\,x \mid \varphi_x(x) = \varphi_x(x+30) \,\}

non è un I.I.R.F.

Per definizione,
[math]I \mbox{ è un I.I.R.F. se e solo se } \forall_{x,y}\mbox{. se } x\in I \mbox{ e } \varphi_x=\varphi_y \mbox{ allora } y\in I
L'idea a questo punto è negare il quantificatore universale e ottenere
[math]\exists_{x,y}\mbox{. } x\in I \mbox{ e } \varphi_x=\varphi_y \mbox{ e } y\notin I

Allora costruisco una funzione ad-hoc:
[math]\varphi_{x}(y) = \varphi_{f (x)}(y) = \psi (x, y) = \left\{ \begin{array}{ll}
42 & \mbox{se } x = 0 \vee x = 30 \\
43 & \mbox{altrimenti}
\end{array}
\right.

Preso l'indice [math]x_0=0 ottengo

[math]42 = \varphi_{0}(0) = \varphi_{0}(0+30) = 42

e concludo che [math]x_0 \in I

Preso l'indice [math]x_1 \neq x_0 (che esiste per il Padding Lemma) (e di conseguenza [math] \varphi_{x_1}=\varphi_{x_0} ), impongo anche che [math]x_1 = 30 e lo posso fare perché gli indici che vengono fuori dal Padding lemma sono [math]\#[math]N

[math]x_1 \notin I perché

[math]42 = \varphi_{30}(30) \neq \varphi_{30}(30+30) = 43


VECCHIA SOLUZIONE (errata, credo)
L'idea a questo punto è che nego la tesi, costruisco una funzione ad-hoc:

[math]\varphi_{f (x)}(y) = \psi (x, y) = \left\{ \begin{array}{ll}
42 & \mbox{se } x = 0 \vee x = 30 \\
43 & \mbox{altrimenti}
\end{array}
\right.

Preso l'indice [math]x_0=0 ottengo

[math]42 = \varphi_{0}(0) = \varphi_{0}(0+30) = 42

dato che [math]\varphi ha infiniti indici, scelgo [math]x_1=30 e ottengo

[math]42 = \varphi_{30}(30) \neq \varphi_{30}(30+30) = 43

Quindi [math]x_0 \in I \mbox{ , } x_1\notin I \mbox{ , } \varphi(x_0)=\varphi(x_1) e quindi I non è un I.I.R.F.

Pareri e correzioni sono ben accetti.