Numeri di Gödel
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
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
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.