[Teoria] Capire se una proprietà è estensionale

[TacTech]

Salve a tutti, ho molta difficoltà nel riuscire a classificare gli insiemi. Ad esempio l'insieme $ A ={i |n !in cod(varphi _i)} $ con n fissato, non è finito, quindi non è banalmente ricorsivo. Cerco di capire se è estensionale. Per definizione, una proprietà è estensionale se sostituendo $varphi _i$ con una $varphi _j$ che calcola la stessa cosa, la proprietà continua a valere. In questo caso però non riesco a pensare a come vedere se la proprietà che definisce l'insieme continua a valere. Qualcuno sa aiutarmi?

[MarcoChampion]

Ciao TacTech ti rispondo anche se ormai è passato più di un mese dalla tua domanda sperando di esserti d'aiuto
Allora dalla definizione, una proprietà è estensionale se presi due indici x,y qualsiasi di funzione, le due funzioni danno gli stessi identici risultati (input-output) e la funzione con indice x appartiene alla proprietà allora anche y deve appartenere alla proprietà. Intuitivamente se le due funzioni calcolano esattamente la stessa cosa allora devono appartenere entrambe alla proprietà, in questo caso si parla di proprietà estensionale. Per cui una proprietà è estensionale quando questa parla di cosa calcolano le funzioni e non di come lo fanno.
Ora tu hai scritto che non essendo l'insieme finito allora non è ricorsivo ma è sbagliato in quanto esistono insiemi infiniti ricorsivi (come l'insieme di tutti i numeri naturali). Guardando bene l'insieme del tuo esercizio puoi notare che sicuramente se due funzioni calcolano la stessa e hanno n nel loro codominio, allora apparterranno all'insieme, per cui quell'insieme rappresenta una proprietà estensionale.
Come puoi vedere quella proprietà parla di cosa calcolano le funzioni (in quel caso se daranno mai come output n) per cui sicuramente è una proprietà estensionale.
Le proprietà non estensionali sono facili da individuare in quanto parlano di come sono fatte le funzioni quindi si tratta di proprietà sintattiche. Ad esempio l'insieme contenenti tutti gli indici di programmi di lunghezza inferiore a 10 , non è estensionale in quanto anche se due programmi calcolano la stessa cosa potrebbero essere scritti da istruzioni diverse e quindi con una lunghezza diversa.