title: Rappresentabilità
text: # Rappresentabilità
  
  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
  
  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 $S^n(0)$ il termine S(S(S(...S(S(0)))...))) in cui il simbolo S compare n volte possiamo dire che $S^n(0)$ è il numerale del numero n.
  
  Possiamo ora dare la seguente definizione:
  
  Dato 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 $n\in U$ allora $φ(S^n(0))$ è dimostrabile in T
     * se $n\notin U$ allora $\neg$$φ(S^n(0))$ è dimostrabile in T
  
  La nozione di rappresentabilità si può estendere anche a sottoinsiemi di $N^k$ e quindi a relazioni a k argomenti. In tal caso la formula che le rappresenta dovrà avere k variabili libere.
  
  ### Esempi
  
  * L'insieme U={0} costituito dal solo numero 0 è esprimibile mediante la formula
  
      $\varphi (x):\equiv (x=0)$
      e mediante tale formula è anche rappresentabile nell'Aritmetica di Robinson, infatti se n∈U cioè n=0 allora la formula
         $\varphi (0)\equiv (0=0)$
      è dimostrabile essendo una istanza degli assiomi per l'uguaglianza, se invece n≠0 allora la formula
         $\neg \varphi (S^{n}(0))\equiv \neg (S^{n}(0)=0)\equiv \neg (S(S(...S(0)...))=0)$
      è 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.
  * Si può dimostrare che qualsiasi insieme ricorsivo è rappresentabile nell'Aritmetica di Robinson e quindi anche nell'Aritmetica di Peano.
  
  ## Rappresentare funzioni
  
  Per una funzione
  
      $f:\mathbb {N} \to \mathbb {N}$
  
  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 esprime la relazione y=f(x);
  * per ogni coppia di numeri naturali n e m si ha che
     * se n=f(m) allora $φ(S^n(0),S^m(0))$ è dimostrabile in T
     * se n≠f(m) allora $\neg$$φ(S^n(0),S^m(0))$ è dimostrabile in T.
  
  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:
  
  * per ogni numero naturale m è dimostrabile in T la formula
  
         $\exists y(\varphi (y,S^{m}(0))\land \forall z(\varphi (y,S^{m}(0))\to (z=y)))$
  
  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 $N^k$ anziché su N.
  
  