Product Design, Manufacturing & Innovation Resources
Casa » Numeri di Gödel

Numeri di Gödel

1931
  • Kurt Gödel
Tecnica di numerazione di Gödel nella logica matematica con numeri naturali unici.

(Immagine generata a solo scopo illustrativo)

La numerazione di Gödel è una tecnica fondamentale che assegna un numero naturale unico (un numero di Gödel) a ogni simbolo, formula e prova in un linguaggio formale. Questa aritmetizzazione della sintassi consente di codificare le affermazioni metamatematiche su un sistema formale (ad esempio, ‘questa formula è dimostrabile’) come affermazioni aritmetiche sui numeri, che possono quindi essere ragionate all'interno del sistema stesso.

La numerazione di Gödel è l'ingegnoso meccanismo che colma il divario tra la sintassi (la struttura simbolica di un linguaggio formale) e la teoria dei numeri (le proprietà dei numeri interi). Il processo consente di tradurre le affermazioni sulla logica in affermazioni sui numeri. Il metodo funziona assegnando prima un numero intero unico a ogni simbolo di base del linguaggio formale (per esempio, ‘¬’ → 1, ‘∨’ → 2, ‘∀’ → 3, ‘x’ → 4, ecc.).

A formula, which is a sequence of these symbols, can then be assigned its own unique number. Gödel’s original method used prime factorization. For a sequence of symbols with numbers [latex]s_1, s_2, …, s_k[/latex], the formula’s Gödel number would be [latex]2^{s_1} \cdot 3^{s_2} \cdot 5^{s_3} \cdot \dots \cdot p_k^{s_k}[/latex], where [latex]p_k[/latex] is the k-th prime number. Due to the fundamental theorem of arithmetic (unique prime factorization), this mapping is injective; every formula gets a unique number, and from any such number, the original formula can be uniquely recovered.

Infine, una prova, che è una sequenza di formule, può essere codificata nello stesso modo, prendendo i numeri di Gödel delle formule che la compongono e applicando nuovamente la codifica prime-power. Questa completa aritmetizzazione significa che proprietà metamatematiche complesse, come ‘la sequenza F è una prova valida della formula P’, diventano predicati puramente aritmetici che coinvolgono i numeri di Gödel di F e P. Questo ha permesso a Gödel di costruire una formula che si riferisce alla propria dimostrabilità, il passo chiave della sua prova di incompletezza.

UNESCO Nomenclature: 1201
– Matematica pura

Tipo

Sistema astratto

Interruzione

Sostanziale

Utilizzo

Concettuale/Teorico

Precursori

  • geometria analitica (la mappatura di Cartesio della geometria all'algebra)
  • Il concetto di ‘characteristica universalis’ di Leibniz’
  • il teorema fondamentale dell'aritmetica (fattorizzazione unica dei numeri primi)
  • formalizzazione dei linguaggi nella logica di Frege e Russell
  • Il lavoro di Cantor sulle mappature tra insiemi

Applicazioni

  • teoria della computabilità (rappresentazione delle macchine di Turing e dei programmi come numeri)
  • informatica (il principio secondo cui il codice è dato)
  • teoria dell'informazione
  • crittografia
  • teoria del linguaggio formale
  • dimostrazioni di indecidibilità, come il problema dell'arresto

Brevetti:

NA

Idee e potenziali innovazioni

A causa dell'eliminazione del traffico generato dai bot, che attualmente supera i 40.000 al giorno, questo contenuto è riservato ai membri della community.
> Accedi O > Registrati L'accesso a questo contenuto, così come a tutti gli altri contenuti e strumenti riservati, è (100% gratuito).

Correlato a: Numero di Gödel, aritmetizzazione, sintassi, metamatematica, codifica, linguaggio formale, teoria delle prove, computabilità, autoreferenzialità, fattorizzazione dei primi.

Contesto storico

Numeri di Gödel

1924
1925
1930
1931
1939
1940
1950
1922
1925
1928
1930
1936
1940
1943
1950

(se la data è sconosciuta o non rilevante, ad esempio "meccanica dei fluidi", viene fornita una stima approssimativa della sua notevole comparsa)

Invenzioni, innovazioni e principi tecnici correlati

Le immagini a grandezza naturale e i download sono disponibili, 100% gratuitamente, solo per i membri registrati.

> Login <