Logica matematica/Incompletezza/Teoremi di incompletezza di Gödel: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Pagina sostituita con 'In logica matematica, i teoremi di incompletezza di Gödel sono due famosi teoremi dimostrati da Kurt Gödel nel 1931. Essi fanno parte dei teoremi limit...' Etichette: Sostituito Modifica visuale |
|||
Riga 1:
In logica matematica, i teoremi di incompletezza di Gödel sono due famosi teoremi dimostrati da [[w:Kurt Gödel|Kurt Gödel]] nel 1931. Essi fanno parte dei teoremi limitativi, che precisano cioè le proprietà che i sistemi formali non possono avere.
== Definizioni preliminari ==
* 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_0,...,n_{k-1} \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_0,...,n_{k-1})</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_0,...,n_{k-1}</math>, cioè <math>n_i \in \N</math>, per ogni <math>0 \leq i < k </math>.
Sia ora <math>\mathcal{S}</math> un sistema formale.
=== Rappresentabilità ===
==== Relazione rappresentabile ====
<math>R</math> si definisce rappresentabile in <math>\mathcal{S}</math> sse esiste una formula <math>\alpha[x_0,...,x_{k-1}] \in \mathcal{S}</math>, contenente esattamente <math>k</math> variabili libere <math>x_0,...,x_{k-1} </math>, tale che, per ogni <math>k</math>-upla di numeri <math>\langle n_0,...,n_{k-1} \rangle</math>:
# se <math>\langle n_0,...,n_{k-1} \rangle \in R</math>, allora <math>\vdash_\mathcal{S} \alpha[\overline{n_0}/x_0,...,\overline{n_{k-1}}/x_{k-1}]</math>;
# se <math>\langle n_0,...,n_{k-1} \rangle \not\in R</math>, allora <math>\vdash_\mathcal{S} \neg\alpha[\overline{n_0}/x_0,...,\overline{n_{k-1}}/x_{k-1}]</math>.
Dove <math>\alpha[\overline{n_0}/x_0,...,\overline{n_{k-1}}/x_{k-1}]</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 < k </math>.
== Primo Teorema di incompletezza ==
| |||