L'indecidibilità dell'Aritmetica di Robinson

In this work we prove the undecidability of Robinson Arithmetic (an arithmetic theory weaker than Peano’s one) and we use this result to conclude, through notions like interpretability, the undecidability of other theories, like the Concatenation Theory. To reach this result we start analysing some general results about decidability and interpretability of theories; then, from the axioms of Robinson Arithmetic and some subtheories, we use the results of the first chapter to prove some specific theorems about the considered arithmetic. In the end, in the third chapter, we interpret Robinson Arithmetic into the Concatenation Theory (a theory whose elements are strings), proving the undecidability of this theory.

Questo lavoro si propone di dimostrare l'indecidibilità dell'Aritmetica di Robinson (una teoria aritmetica più debole dell'Aritmetica di Peano) e di sfruttare tale risultato per concludere, attraverso nozioni come l'interpretabilità, l'indecidibilità di altre teorie, in particolare la Teoria della Concatenazione. Per ottenere questo risultato si analizzano innanzitutto alcuni risultati generali sulla decidibilità e l'interpretabilità di teorie; quindi, partendo dagli assiomi dell'Aritmetica di Robinson e da alcune sue sottoteorie, si sfruttano i risultati della prima parte per dimostrare fatti più specifici sulla teoria aritmetica considerata. Infine, nel terzo capitolo, si interpreta l'Aritmetica di Robinson all'interno della Teoria della Concatenazione (una teoria che ha come elementi le stringhe), concludendo così l'indecidibilità di quest'ultima.