Logica matematica/Incompletezza/Teoremi di incompletezza di Gödel: differenze tra le versioni

* Sia <math>n \in \N</math>, il suo simbolo numerale è rappresentato da <math>\overline{n}</math>.

* Sia <math>R</math> una relazione <math>k</math>-aria <math>R \subseteq \N^k</math>. In [[Logica/Insiemi|teoria degli insiemi]], essa è definita come l'insieme delle liste numerate <math>\langle n_0n_1,...,n_{k-1}n_k \rangle</math> di lunghezza <math>k</math> (<math>k</math>-uple), tali che esse siano in grado di soddisfare una determinata proprietà <math>R(n_0n_1,...,n_{k-1}n_k)</math>. <math>\N^k</math> è la potenza cartesiana di ordine <math>k</math> di <math>\N</math>, che è l'insieme dei numeri naturali. In questo caso, <math>\N</math> assume la connotazione di universo degli elementi <math>n_0n_1,...,n_{k-1}n_k</math>, cioè <math>n_i \in \N</math>, per ogni <math>0 \leq i < =1,...,k </math>.

<math>R</math> si definisce rappresentabile in <math>\mathcal{S}</math> sse esiste una formula <math>\alpha[x_0x_1,...,x_{k-1}x_k] \in \mathcal{S}</math>, contenente esattamente <math>k</math> variabili libere <math>x_0x_1,...,x_{k-1}x_k </math>, tale che, per ogni <math>k</math>-upla di numeri <math>\langle n_0n_1,...,n_{k-1}n_k \rangle</math>:

# se <math>\langle n_0n_1,...,n_{k-1}n_k \rangle \in R</math>, allora <math>\vdash_\mathcal{S} \alpha[\overline{n_0n_1}/x_0x_1,...,\overline{n_{k-1}n_k}/x_{k-1}x_k]</math>;

# se <math>\langle n_0n_1,...,n_{k-1}n_k \rangle \not\in R</math>, allora <math>\vdash_\mathcal{S} \neg\alpha[\overline{n_0n_1}/x_0x_1,...,\overline{n_{k-1}n_k}/x_{k-1}x_k]</math>.

Dove <math>\alpha[\overline{n_0n_1}/x_0x_1,...,\overline{n_{k-1}n_k}/x_{k-1}x_k]</math> indica la sostituzione di ogni variabile <math>x_i</math> con il numerale <math>\overline{n_i}</math>, per ogni <math>0 \leq i < =1,...,k </math>.