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

[math]

non è un I.I.R.F.

Per definizione,
[math]
L'idea a questo punto è negare il quantificatore universale e ottenere
[math]

Allora costruisco una funzione ad-hoc:
[math]

Preso l'indice [math] ottengo

[math]

e concludo che [math]

Preso l'indice [math] (che esiste per il Padding Lemma) (e di conseguenza [math]), impongo anche che [math] e lo posso fare perché gli indici che vengono fuori dal Padding lemma sono [math][math]

[math] perché

[math]


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

Preso l'indice [math] ottengo

[math]

dato che [math] ha infiniti indici, scelgo [math] e ottengo

[math]

Quindi [math] e quindi I non è un I.I.R.F.
Pareri e correzioni sono ben accetti.