Wikibooks

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

Naviga nella cronologia in modo interattivo
← Differenza precedenteDifferenza successiva →
Contenuto cancellato Contenuto aggiunto
VisualeWikitesto
Nessun oggetto della modifica
Riga 38:
:Sia <math>Ax</math> l'insieme degli assiomi di <math>S</math> e <math>\mathcal{R}</math> l'insieme delle sue regole d'inferenza. L'insieme <math>\text{DIM}</math> è così definito:
 
# se <math>\langle \alpha \rangle \in Ax\text{DIM}</math>, allorasse <math>\langle \alpha \rangle \in \text{DIM}Ax</math>;
# se<math>\langle \alpha_1,...,\alpha_n, \alpha_{n+1} \rangle \in \text{DIM}</math> sse <math>(l=\langle \alpha_1,...,\alpha_n \rangle) \in \text{DIM}</math> e <math>\alpha_{n+1} \in Ax</math>, oppure <math>\alpha_{n+1}</math> è conseguenza diretta di qualche <math>j</math>-upla <math>\langle \alpha_1,...,\alpha_j \rangle</math> (sottolista di <math>l</math>) per qualche <math>R_i \in \mathcal{R}</math>, allora <math>\langle \alpha_1,...,\alpha_n, \alpha_{n+1} \rangle \in \text{DIM}</math>.
 
==== Numeri di Gödel ====
Sia ora <math>g:(\mathcal{A} \cup \mathcal{F} \cup \mathrm{SEQ})
\mapsto \N</math> una funzione ricorsiva e iniettiva, chiamata ''numero di Gödel'' (in onore al grande logico). La funzione non fa altro che assegnare univocamente ad ogni stringa di <math>\mathcal{L=\langle A,F \rangle}</math>, e ad ogni sua sequenza di stringhe costituente una dimostrazione (l'insieme <math>\text{SEQ}</math>), uno ed un solo numero naturale, detto appunto ''numero di Gödel'' o g''ödeliano''. Essendo <math>g</math> una funzione iniettiva, essa è invertibile, dunque esiste <math>g^{-1}: \N \mapsto
(\mathcal{A} \cup \mathcal{F} \cup \mathrm{SEQ})</math>. Supponiamo che anche <math>g^{-1}</math> sia ricorsiva.
 
A partire da questa funzione, possiamo ora definire una relazione (<math>Dim(m,n)</math>) e una funzione sui numeri naturali (<math>sost(x,y,z)</math>), anch'essea loro volta ricorsive:
 
* la relazione <math>Dim(m,n) \subseteq \N^2</math> è definita come <math>Dim(m,n) =\{\langle m,n \rangle|
g^{-1}(m)=\langle \alpha_1,...,\alpha_k \rangle, g^{-1}(m) \in \text{DIM}, \alpha_k=g^{-1}(n)\}</math>. In sostanza, il predicato <math>Dim(m,n)</math> codifica la relazione "<math>(l=\langle \alpha_1,...,\alpha_k \rangle) \vdash_S \alpha</math>", cioè, vale sse <math>l</math> dimostra <math>\alpha</math>, ovvero, sse <math>l</math> è una dimostrazione in <math>S</math> e <math>\alpha=\alpha_k</math>.
* la funzione <math>sost:\N^3 \mapsto \N</math> è definita come <math>sost(x,y,z)=g(g^{-1}(x)[\overline{z}/g^{-1}(y)])</math>, cioè, la funzione <math>sost</math> restituisce il g''ödeliano'' della formula ottenuta sostituendo nella formula di g''ödeliano'' <math>x</math> il simbolo (numerale) di <math>z</math> al posto della variabile di g''ödeliano'' <math>y</math>. In sostanza, la funzione aritmetizza la sostituzione.
 
<math>Dim</math> e <math>sost</math> sono ricorsive, essendo definite a partire da <math>g</math>, <math>g^{-1}</math>, <math>\text{DIM}</math> e <math>\mathcal{F}</math> e non contenendo quantificatori nelle loro definizioni.
 
== Primo Teorema di incompletezza ==
Estratto da "https://it.wikibooks.org/wiki/Logica_matematica/Incompletezza/Teoremi_di_incompletezza_di_Gödel"