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
Riga 4:
 
* 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 UD</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 UD^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>UD</math> è l'insiemeil universodominio degli elementi <math>c_1,...,c_k</math>, cioè <math>c_i \in UD</math>, per ogni <math>i=1,...,k </math>.
* Sia <math>f:UD^k \mapsto UD</math> una funzione <math>k</math>-aria.
 
=== Rappresentabilità ===
Riga 65:
 
== Primo Teorema di incompletezza ==
Sia <math>S</math> un sistema formale in grado di rappresentare le funzioni ricorsive, allora esiste una formula <math>\gamma</math> tale per cui:
 
# se <math>S</math> è coerente, allora <math>\nvdash_S \gamma</math>;
# se <math>S</math> è ω-coerente, allora <math>\nvdash_S \neg\gamma</math>.
 
Dunque, se esiste tale formula, <math>S</math> è sintatticamente incompleto.
 
=== Dimostrazione ===
Essendo <math>S</math> in grado di rappresentare funzioni ricorsive, esso può esprimere la relazione <math>Dim_S</math> e le funzioni <math>sost</math> e <math>g</math> all'interno del suo linguaggio <math>\mathcal{L}</math>, che conterrà i simboli di predicato e di funzione <math>\text{Dim}_S</math>, <math>\text{sost}</math> e <math>\text {g}</math>.
 
Consideriamo la formula <math>\gamma(y)</math> di <math>S</math>, contenente libera la variabile <math>y</math>:<blockquote><math>\gamma(y):\neg\exists x
\text{Dim}_S(x,\text{sost}(y,\overline{\text{g}(y)},y))</math></blockquote>
 
== Secondo Teorema di incompletezza ==
Estratto da "https://it.wikibooks.org/wiki/Logica_matematica/Incompletezza/Teoremi_di_incompletezza_di_Gödel"