Logica matematica/Incompletezza/Teoremi di incompletezza di Gödel: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Riga 3:
== Definizioni preliminari ==
* Sia <math>S</math> un sistema formale costruito su un linguaggio
* 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. 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>U</math> è l'insieme universo degli elementi <math>c_1,...,c_k</math>, cioè <math>c_i \in U</math>, per ogni <math>i=1,...,k </math>.
* Sia <math>f:U^k \mapsto U</math> una funzione <math>k</math>-aria.
=== Rappresentabilità ===
Line 11 ⟶ 12:
==== Relazione rappresentabile ====
<math>R</math>
# se <math>\langle c_1,...,c_k \rangle \in R</math>, allora <math>\vdash_S\alpha[\overline{c_1}/x_1,...,\overline{c_k}/x_k]</math>;
Line 19 ⟶ 20:
==== Relazione semi-rappresentabile ====
<math>R</math>
==== Funzione rappresentabile ====
<math>f</math> è rappresentabile in <math>S</math> sse esiste una formula <math>\alpha[x_1,...,x_k,x_{k+1}] \in \mathcal{L}</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:
# <math>\vdash_S\alpha[\overline{c_1}/x_1,...,\overline{c_k}/x_k,\overline{c_{k+1}}/x_{k+1}]</math>;
# <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>.
== Primo Teorema di incompletezza ==
| |||