Insiemi produttivi

[CUCU]

Fissata una enumerazione F0, F1, F2... delle funzioni parziali ricorsive,
definiamo Wi= DOM(Fi), ossia Wi è l'insieme di tutti gli elementi per cui Fi è definita, dove Fi è l'i-esima funzione parziale ricorsiva.

Un insieme A è produttivo se e solo se esiste una funzione parziale ricorsiva f tale che se Wi è incluso in A allora f(i) è definita e f(i) appartiene a A - Wi (l'insieme degli elementi che appartengono ad A ma non a Wi).
f è detta essere la funzione produttiva di A.



Dimostrare le susseguenti affermazioni:

1) NONTOT={ i | Fi è non totale } è un insieme produttivo.
2) TOT={ i | Fi è totale } è un insieme produttivo.
3) Se A è un insieme produttivo P= { i | Wi è incluso in A } è un insieme produttivo.

Per alcuni di questi esercizi è utile utilizzare il metodo suggerito da Cantor per mettere in corrispondenza N con NxN, che abbiamo discusso in un altro thread.

NOTA: Un insieme si dice creativo se è ricorsivamente enumerabile e il suo complemento è produttivo. Così TOT e NONTOT sono insiemi produttivi che non hanno un complemento creativo (come invece spesso accade). Infatti segue immediatamente dalla definizione che un insieme produttivo non può essere ricorsivamente enumerabile.