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

Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica
Riga 3:
== Definizioni preliminari ==
 
{{Definizione|
* Sia <math>S=\langle \mathcal{L},Ax,\mathcal{R} \rangle</math> un [[Logica/Sistemi formali|sistema formale]] costruito su un linguaggio del primo ordine <math>\mathcal{L=\langle A,F \rangle}</math>, dove <math>Ax</math> è l'insieme degli assiomi di <math>S</math> e <math>\mathcal{R}</math> è l'insieme delle sue regole d'inferenza; <math>\mathcal{A}</math> è l'alfabeto di <math>\mathcal{L}</math> e <math>\mathcal{F}</math> l'insieme delle sue formule ben formate.
* Sia <math>c \in D</math>, il simbolo che lo denota in <math>\mathcal{L}</math> è rappresentato da <math>\overline{c} \in \mathcal{A}</math>, dove <math>\mathcal{A}</math> è l'alfabeto di <math>\mathcal{L}</math>.
* Sia <math>R \subseteq D^k</math> una relazione <math>k</math>-aria. In [[Logica/Insiemi|teoria degli insiemi]], essa è definita come l'insieme delle liste numerate <math>\langle c_1,...,c_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(c_1,...,c_k)</math>. <math>D</math> è il dominio degli elementi <math>c_1,...,c_k</math>, cioè <math>c_i \in D</math>, per ogni <math>i=1,...,k </math>.
* Sia <math>f:D^k \mapsto D</math> una funzione <math>k</math>-aria.
}}
 
=== Rappresentabilità ===
Line 12 ⟶ 14:
==== Relazione rappresentabile ====
 
{{Definizione|
<math>R</math> è ''rappresentabile'' in <math>S</math> sse esiste una formula <math>\alpha[x_1,...,x_k] \in \mathcal{F}</math>, contenente esattamente <math>k</math> variabili libere <math>x_1,...,x_k </math>, tale che, per ogni <math>k</math>-upla di elementi <math>\langle c_1,...,c_k \rangle</math>:
 
Line 18 ⟶ 21:
 
Dove <math>\alpha[\overline{c_1}/x_1,...,\overline{c_k}/x_k]</math> indica la sostituzione di ogni variabile <math>x_i</math> con il simbolo <math>\overline{c_i}</math>, per ogni <math>i=1,...,k</math>. Si dice allora che la formula ''rappresenta'' la relazione <math>R</math>.
}}
 
==== Relazione semi-rappresentabile ====
{{Definizione|
<math>R</math> è ''semi-rappresentabile'' (o ''debolmente rappresentabile'') in <math>S</math> sse esiste una formula <math>\alpha[x_1,...,x_k] \in \mathcal{F}</math>, contenente esattamente <math>k</math> variabili libere <math>x_1,...,x_k </math>, tale che, per ogni <math>k</math>-upla di elementi <math>\langle c_1,...,c_k \rangle</math>, <math>\langle c_1,...,c_k \rangle \in R</math> sse <math>\vdash_S\alpha[\overline{c_1}/x_1,...,\overline{c_k}/x_k]</math>.
}}
 
==== Funzione rappresentabile ====
{{Definizione|
<math>f</math> è rappresentabile in <math>S</math> sse esiste una formula <math>\alpha[x_1,...,x_k,x_{k+1}] \in \mathcal{F}</math>, contenente esattamente <math>k+1</math> variabili libere <math>x_1,...,x_k,x_{k+1} </math>, tale che, per ogni <math>(k+1)</math>-upla di elementi <math>\langle c_1,...,c_k,c_{k+1} \rangle</math>, se <math>f(c_1,...,c_k)=c_{k+1}</math>, allora:
 
Line 28 ⟶ 35:
# <math>\vdash_S \forall x_1,...,x_k \exists x_{k+1}\forall y
(\alpha[x_1,...,x_k,y] \leftrightarrow y=x_{k+1})</math>.
}}
 
=== Ricorsività ===
Line 48 ⟶ 56:
A partire da questa funzione, possiamo ora definire una relazione (<math>Dim_S(m,n)</math>) e una funzione sui numeri naturali (<math>sost(x,y,z)</math>), a loro volta ricorsive:
 
{{Definizione|
* la relazione <math>Dim_S(m,n) \subseteq \N^2</math> è definita come <math>Dim_S(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_S</math> codifica la relazione "<math>(d=\langle \alpha_1,...,\alpha_k \rangle) \vdash_S \alpha</math>", cioè, vale sse <math>d</math> dimostra <math>\alpha</math>, ovvero, sse <math>d</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 libera di gödeliano <math>y</math>. In sostanza, la funzione <math>sost</math> aritmetizza la sostituzione di un numerale al posto di una variabile libera in una formula.
}}
 
<math>Dim_S</math> e <math>sost</math> sono ricorsive, essendo definite a partire da funzioni o insiemi ricorsivi, quali <math>g</math>, <math>g^{-1}</math>, <math>\text{DIM}</math> e <math>\mathcal{F}</math>, e non contenendo quantificatori nelle loro definizioni.
 
=== ω-coerenza ===
{{Definizione|
Un sistema formale <math>S</math> è ω-coerente sse non esiste una formula <math>\alpha[x] \in \mathcal{F}</math> tale per cui <math>\vdash_S \exists x\alpha[x]</math> e, per ogni <math>n \in \N</math>, <math>\vdash_S \neg\alpha[\overline{n}/x]</math>.
}}
 
==== Lemma di coerenza ====