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.