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 3:
== Definizioni preliminari ==
 
* Sia <math>n \in \NS</math>, ilun sistema formale suocostruito numeralesu èun rappresentatolinguaggio daformale <math>\overlinemathcal{nL}</math>.
* Sia <math>c \in U</math>, il simbolo che lo denota in <math>\mathcal{L}</math> è rappresentato da <math>\overline{c}</math>.
* Sia <math>R \subseteq U^k</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_1c_1,...,n_kc_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_1c_1,...,n_kc_k)</math>. <math>\N^kU</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_1c_1,...,n_kc_k</math>, cioè <math>n_ic_i \in \NU</math>, per ogni <math>i=1,...,k </math>.
 
Sia ora <math>\mathcal{S}</math> un sistema formale.
 
=== Rappresentabilità ===
Line 12 ⟶ 11:
==== Relazione rappresentabile ====
 
<math>R</math> si definisce ''rappresentabile'' in <math>\mathcal{S}</math> sse esiste una formula <math>\alpha[x_1,...,x_k] \in \mathcal{SL}</math>, contenente esattamente <math>k</math> variabili libere <math>x_1,...,x_k </math>, tale che, per ogni <math>k</math>-upla di numerielementi <math>\langle n_1c_1,...,n_kc_k \rangle</math>:
 
# se <math>\langle n_1,...,n_k \rangle \in R</math>, allora <math>\vdash_\mathcal{S} \alpha[\overline{n_1}/x_1,...,\overline{n_k}/x_k]</math>;▼
# se <math>\langle n_1,...,n_k \rangle \not\in R</math>, allora <math>\vdash_\mathcal{S} \neg\alpha[\overline{n_1}/x_1,...,\overline{n_k}/x_k]</math>.▼
 
Dove <math>\alpha[\overline{n_1}/x_1,...,\overline{n_k}/x_k]</math> indica la sostituzione di ogni variabile <math>x_i</math> con il numerale <math>\overline{n_i}</math>, per ogni <math>i=1,...,k</math>.▼
 
▲# se <math>\langle n_1c_1,...,n_kc_k \rangle \in R</math>, allora <math>\vdash_\mathcal{S} vdash_S\alpha[\overline{n_1c_1}/x_1,...,\overline{n_kc_k}/x_k]</math>;
▲# se <math>\langle n_1c_1,...,n_kc_k \rangle \not\in R</math>, allora <math>\vdash_\mathcal{S} vdash_S\neg\alpha[\overline{n_1c_1}/x_1,...,\overline{n_kc_k}/x_k]</math>.
 
▲Dove <math>\alpha[\overline{n_1c_1}/x_1,...,\overline{n_kc_k}/x_k]</math> indica la sostituzione di ogni variabile <math>x_i</math> con il numeralesimbolo <math>\overline{n_ic_i}</math>, per ogni <math>i=1,...,k</math>.
==== Relazione semi-rappresentabile ====
<math>R</math> si definisce ''semi-rappresentabile'' (o ''debolmente rappresentabile'') in <math>S</math> sse esiste una formula <math>\alpha[x_1,...,x_k] \in \mathcal{L}</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>, vale <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>.
 
== Primo Teorema di incompletezza ==
Estratto da "https://it.wikibooks.org/wiki/Logica_matematica/Incompletezza/Teoremi_di_incompletezza_di_Gödel"