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

Contenuto cancellato Contenuto aggiunto
correggo template e categoria
Riga 6:
 
{{Definizione|
* Sia <math>S=\langle \mathcal{L},Ax,\mathcal{R} \rangle</math> un [[Logica matematica/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 matematica/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.
}}
Riga 41:
=== Ricorsività ===
{{Definizione|
Una funzione <math>f</math> è detta ricorsiva sse essa è esprimibile mediante la [[Logica matematica/Computabilità/Ricorsività|teoria della ricorsività]]. Una relazione (o un insieme) <math>R</math> è ricorsiva sse la sua [[Logica matematica/Insiemi#Funzione caratteristica|funzione caratteristica]] è ricorsiva.
 
* L'insieme <math>\mathcal{F}</math> delle formule ben formate di un sistema formale <math>S</math>, essendo definito induttivamente, è ricorsivo.