• Istituto
    • Chi Siamo
    • La nostra storia
  • Magazine
    • Agenda
    • Atlante
    • Il Faro
    • Il Chiasmo
    • Diritto
    • Il Tascabile
    • Le Parole Valgono
    • Lingua italiana
    • WebTv
  • Catalogo
    • Le Opere
    • Bottega Treccani
    • Gli Ebook
    • Le Nostre Sedi
  • Scuola e Formazione
    • Portale Treccani Scuola
    • Formazione Digitale
    • Formazione Master
    • Scuola del Tascabile
  • Libri
    • Vai al portale
  • Arte
    • Vai al portale
  • Treccani Cultura
    • Chi Siamo
    • Come Aderire
    • Progetti
    • Iniziative Cultura
    • Eventi Sala Igea
  • ACQUISTA SU EMPORIUM
    • Arte
    • Cartoleria
    • Design & Alto Artigianato
    • Editoria
    • Idee
    • Marchi e Selezioni
  • Accedi
    • Modifica Profilo
    • Treccani X

Godel, numero di

Enciclopedia della Matematica (2013)
  • Condividi

Godel, numero di


Gödel, numero di numero naturale associato a ciascuna formula di un sistema formale S secondo un procedimento dovuto a K. Gödel e detto pertanto gödelizzazione. Lo stesso procedimento permette anche di associare in modo univoco un numero naturale a ogni asserzione logica che coinvolga le formule in S. Poiché l’aritmetica è esprimibile in termini assiomatici come particolare sistema formale (→ aritmetica, sistema formale per la), è possibile rappresentare ogni affermazione espressa sui numeri naturali attraverso i numeri naturali stessi. Ciò si può esprimere dicendo che, con la gödelizzazione, l’aritmetica può “parlare di sé stessa” analogamente a quanto avviene in un libro di grammatica che spiega le regole della lingua italiana usando, a tale scopo, proprio la lingua italiana (funzione metalinguistica). Il procedimento di gödelizzazione si basa sulla definizione di una funzione, indicata con la lettera g, che associa a ogni formula aritmetica un numero naturale. Per far ciò bisogna innanzitutto associare a ciascun simbolo che può comparire in una formula aritmetica un numero naturale che costituisce il numero di Gödel di quel simbolo. In particolare, si può costruire una funzione g che associa:

• al simbolo 0 il numero naturale 3, in simboli g(0) = 3;

• al simbolo ′ il numero naturale 5, in simboli g(′) = 5;

• al simbolo ( il numero naturale 7, in simboli g(() = 7;

• al simbolo ) il numero naturale 9, in simboli g()) = 9;

• al simbolo + il numero naturale 11, in simboli g(+) = 11;

• al simbolo · il numero naturale 13, in simboli g(·) = 13;

• al simbolo = il numero naturale 15, in simboli g(=) = 15;

• al simbolo xi il numero naturale 15 + 2i dove xi è la i-esima variabile del linguaggio (per esempio g(x1) = 15 + 2 = 17, g(x2) = 15 + 4 = 19).

Si noti che a ogni simbolo dell’aritmetica viene così associato un numero dispari; la scelta dei numeri dispari viene operata per distinguere i simboli dalle formule. Infatti a ogni formula costituita da una stringa di simboli si attribuisce un numero naturale secondo la regola seguente: alla formula a1a2 ... an dove a1, a2, ..., an sono i simboli che compaiono in essa, si associa il numero

formula

dove pn è l’ennesimo numero primo. Il numero così ottenuto è, quindi, un numero pari, prodotto dei primi n numeri primi, ciascuno elevato al numero di Gödel associato al simbolo che occupa il posto corrispondente. La successione dei numeri primi 2, 3, 5, 7, ... indica il posto che il simbolo (codificato al suo esponente) occupa nella stringa a1a2 ... an. Per esempio, al numero naturale 4 che nella formalizzazione dell’aritmetica è scritto come stringa 0'''', essendo 5 = succ(succ(succ(succ(0)))) corrisponde il numero di Gödel g(4) = 3995822442167325000 che è il prodotto

formula

Se invece si considera, per esempio, la formula x1 + x2 = 0, il suo numero di Gödel sarà

formula

essendo

formula

Seguendo questa procedura, ogni formula è, quindi, codificata da un numero pari, essendo il primo fattore una potenza di 2. Il numero di Gödel di ogni simbolo dell’alfabeto è invece, per la definizione data della corrispondenza g, un numero dispari; ciò esclude la possibilità di confondere simboli e formule. Inoltre il numero attribuito a una formula è unico perché unica è la scomposizione in fattori primi di un numero naturale (in base al teorema fondamentale dell’aritmetica): è dunque possibile risalire dal numero di Gödel alla formula da cui tale numero proviene. Si possono codificare in modo analogo anche le sequenze di formule; a una sequenza di espressioni formali e1, e2, e3, ..., en si associa il numero di Gödel

formula

Non è possibile che tale numero sia confuso con il numero di Gödel di una semplice formula: infatti, poiché g(e1) è sicuramente un numero pari, gli esponenti del numero di Gödel di una sequenza di formule sono tutti pari, mentre quelli di una singola formula sono tutti dispari. Nella codifica così costruita si ha, quindi, che: a un simbolo è associato un numero di Gödel dispari; a una formula un numero pari che, scomposto in fattori primi, ha tutti i fattori con esponente dispari; a una sequenza di formule un numero pari che, scomposto in fattori primi, ha tutti i fattori con esponente dispari.

Come si vede anche negli esempi precedenti, i numeri di Gödel sono molto grandi anche in corrispondenza di formule elementari; tuttavia, l’importanza della codifica introdotta da Gödel non risiede nel calcolo effettivo dei numeri di Gödel, ma nella possibilità di scrivere una stringa di un linguaggio formale o anche una sequenza di stringhe come numero naturale in modo univoco (due formule diverse o due sequenze diverse di formule non possono infatti avere lo stesso numero di Gödel). In particolare, come nell’insieme delle stringhe di un linguaggio si distingue l’insieme L delle formule ben formate, così tra i numeri naturali si distinguono i numeri di Gödel relativi a formule ben formate; se è decidibile la proprietà di appartenenza a L, lo è anche quella di essere un numero di Gödel di una formula ben formata e viceversa.

Vedi anche
autoreferenza Nelle scienze sociali, all’interno della teoria dei sistemi, la proprietà che avrebbero alcuni sistemi di riferirsi a sé stessi, cioè di determinare i propri stati internamente, mediante un processo di interazione circolare tra gli elementi che li costituiscono e in modo essenzialmente indipendente dall’ambiente ... Kurt Gödel Matematico e filosofo (Brno 1906 - Princeton 1978). Libero docente di matematica all'univ. di Vienna (1933-38), fu uno degli studiosi che si riunivano attorno a M. Schlick nel Verein Ernst Mach, poi (1929) denominato Wiener Kreis. Dopo il 1938 emigrò negli USA, di cui prese la cittadinanza nel 1948. ... lògica matemàtica Branca della logica, che utilizza un linguaggio simbolico e adotta un sistema di calcolo di tipo algebrico per esaminare le espressioni di un discorso deduttivo. Queste ultime possono essere considerate formalmente come oggetti grafici combinabili tra loro (sintassi) o in relazione al loro significato ... aritmetica Matematica Parte della matematica che riguarda lo studio dei numeri, in particolare dei numeri interi. Il termine fu usato per la prima volta dai pitagorici, per indicare la scienza astratta dei numeri, contrapposto a λογιστική (logistica), che era invece la parte pratica del calcolo numerico: ma nell’uso ...
Tag
  • SCOMPOSIZIONE IN FATTORI PRIMI
  • LINGUAGGIO FORMALE
  • NUMERO NATURALE
  • SISTEMA FORMALE
  • GÖDELIZZAZIONE
Altri risultati per Godel, numero di
  • godelizzazione
    Dizionario delle Scienze Fisiche (1996)
    gödelizzazióne 〈g✄ödël-〉 [Dal cognome di K. Gödel] [ALG] [FAF] Tecnica in uso nella logica matematica, consistente nell'associare un numero intero (numero di Gödel) a ogni espressione di un sistema formale del primo ordine. Il criterio per eseguire questo collegamento è, per lo più, il seguente. Si ...
Vocabolario
nùmero
numero nùmero s. m. [dal lat. numĕrus; cfr. novero]. – 1. Ciascuno degli enti astratti che rappresentano insiemi di unità, ordinati in una successione infinita (serie naturale dei n.) nella quale ogni elemento conta un’unità in più rispetto...
godeliano
godeliano ‹ġö-› agg. – Relativo al matematico Kurt Gödel (1906-1978) e alla sua opera: teoremi g., o prove di Gödel, le dimostrazioni, da lui formulate, dell’incompletezza di qualsiasi assiomatizzazione della teoria dei numeri, dell’impossibilità...
  • Istituto
    • Chi Siamo
    • La nostra storia
  • Magazine
    • Agenda
    • Atlante
    • Il Faro
    • Il Chiasmo
    • Diritto
    • Il Tascabile
    • Le Parole Valgono
    • Lingua italiana
    • WebTv
  • Catalogo
    • Le Opere
    • Bottega Treccani
    • Gli Ebook
    • Le Nostre Sedi
  • Scuola e Formazione
    • Portale Treccani Scuola
    • Formazione Digitale
    • Formazione Master
    • Scuola del Tascabile
  • Libri
    • Vai al portale
  • Arte
    • Vai al portale
  • Treccani Cultura
    • Chi Siamo
    • Come Aderire
    • Progetti
    • Iniziative Cultura
    • Eventi Sala Igea
  • ACQUISTA SU EMPORIUM
    • Arte
    • Cartoleria
    • Design & Alto Artigianato
    • Editoria
    • Idee
    • Marchi e Selezioni
  • Accedi
    • Modifica Profilo
    • Treccani X
  • Ricerca
    • Enciclopedia
    • Vocabolario
    • Sinonimi
    • Biografico
    • Indice Alfabetico

Istituto della Enciclopedia Italiana fondata da Giovanni Treccani S.p.A. © Tutti i diritti riservati

Partita Iva 00892411000

  • facebook
  • twitter
  • youtube
  • instagram
  • Contatti
  • Redazione
  • Termini e Condizioni generali
  • Condizioni di utilizzo dei Servizi
  • Informazioni sui Cookie
  • Trattamento dei dati personali