Rappresentabilità (logica matematica)
Da Wikipedia, l'enciclopedia libera.
Nella logica matematica il concetto di rappresentabilità di una funzione o di un predicato è relativo alle teorie formali dell'aritmetica, ovvero alle teorie del primo ordine che hanno come linguaggio il linguaggio dell'aritmetica del primo ordine e che quindi ammettono come modello la struttura dei numeri naturali. Esempi di tali teorie sono l'aritmetica di Peano e l'aritmetica di Robinson.
L'idea di un insieme rappresentabile da una teoria aritmetica T è quella di un insieme per il quale
- esiste una formula che esprime l'insieme nel linguaggio di T
- dato un qualunque numero è possibile "farsi dire" dalla teoria T se questo appartiene o no all'insieme.
Un discorso analogo vale per le funzioni rappresentabili.
[modifica] Definizioni
Nel linguaggio dell'aritmetica del primo ordine esistono dei termini "standard" per denotare i numeri naturali chiamati numerali:
- 0 è il numerale del numero zero
- S(0) è il numerale del numero 1
- S(S(0)) è il numerale del numero 2
- ...e così via...
Se indichiamo con Sn(0) il termine S(S(S(...(((0)))...))) in cui il simbolo S compare n volte possiamo dire che Sn(0) è il numerale del numero n.
Consideriamo un sottoinsieme U dell'insieme N dei numeri naturali. Diremo che U è rappresentabile in T se
- esiste una formula ben formata φ(x) con una variabile libera che lo esprime;
- per ogni numero naturale n si ha che
- se
allora φ(Sn(0)) è dimostrabile in T - se
allora 
φ(Sn(0)) è dimostrabile in T
- se
La nozione di rappresentabilità si può estendere anche a sottoinsiemi di Nk e quindi a relazioni a k argomenti. In tal caso la formula che le rappresenta dovrà avere k variabili libere.
[modifica] Rappresentare funzioni
Per una funzione
ci sono due nozioni di rappresentabilità:
La funzione f si dice debolmente rappresentabile nella teoria aritmetica T se
- esiste una formula ben formata φ(y,x) con 2 variabili libere che la esprime;
- per ogni numero naturale n si ha che
- se n = f(m) allora φ(Sn(0),Sm(0)) è dimostrabile in T
- se
allora φ(Sn(0),Sm(0)) è dimostrabile in T.
Se assieme alle condizioni precedenti si ha anche che
- per ogni numero m in T è dimostrabile la formula
allora f si dice fortemente rappresentabile in T o rappresentabile come funzione. La formula traduce il fatto che la relazione y=f(x) espressa dalla formula φ(y,x) si comporta sul numero m come una funzione, cioè dato l'elemento m del dominio esiste un unico elemento y del codominio che è in relazione con m.
Le nozioni di rappresentabilità appena esposte si generalizzano facilmente a funzioni definite su Nk anziché su N.
