Rappresentabilità

(Reindirizzamento da Funzione rappresentabile)

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 dotati delle operazioni di addizione e moltiplicazione. 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.

Definizione

modifica

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(...S(S(0)))...))) in cui il simbolo S compare n volte possiamo dire che Sn(0) è il numerale del numero n.

Possiamo ora dare la seguente definizione:

Dato un sottoinsieme   dell'insieme N dei numeri naturali diremo che   è rappresentabile 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.

  • L'insieme U={0} costituito dal solo numero 0 è esprimibile mediante la formula
     
e mediante tale formula è anche rappresentabile nell'Aritmetica di Robinson, infatti se nU cioè n=0 allora la formula
 
è dimostrabile essendo una istanza degli assiomi per l'uguaglianza, se invece n0 allora la formula
 
è dimostrabile sfruttando l'assioma (Q1) (dagli assiomi propri dell'Aritmetica di Robinson), l'assioma (L5) degli assiomi logici ed il modus ponens. Dunque per U è verificata la definizione di insieme rappresentabile nell'Aritmetica di Robinson.
  • L'insieme U=N è rappresentabile in qualsiasi teoria che includa tra i propri assiomi gli assiomi logici. Per esprimere e rappresentare l'insieme N è sufficiente una qualsiasi tautologia, infatti le tautologie sono tutte dimostrabili a mediante i soli assiomi logici.
  • L'insieme vuoto è rappresentabile in qualsiasi teoria che includa tra i propri assiomi gli assiomi logici. Per esprimere e rappresentare l'insieme vuoto è sufficiente una qualsiasi contraddizione, infatti le tautologie sono tutte dimostrabili a mediante i soli assiomi logici.

Rappresentare funzioni

modifica

Per una funzione

 

ci sono due nozioni di rappresentabilità:

La funzione f si dice debolmente rappresentabile nella teoria aritmetica T se

Dunque una funzione f è debolmente rappresentabile se il suo grafico è rappresentabile come insieme.

La funzione f si dice fortemente rappresentabile in T o rappresentabile come funzione se assieme alle condizioni precedenti vale anche la condizione aggiuntiva:

 

Tale 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.

Voci correlate

modifica