Product Design, Manufacturing & Innovation Resources
Maison » Nombres de Gödel

Nombres de Gödel

1931
  • Kurt Gödel
Technique de numérotation de Gödel en logique mathématique avec des nombres naturels uniques.

(Image générée à titre d'illustration uniquement)

La numérotation de Gödel est une technique fondamentale qui attribue un nombre naturel unique (un nombre de Gödel) à chaque symbole, formule et preuve dans un langage formel. Cette arithmétique de la syntaxe permet d'encoder des énoncés métamathematiques sur un système formel (par exemple, ‘ cette formule est démontrable ’) sous forme d'énoncés arithmétiques sur des nombres, qui peuvent ensuite être raisonnés au sein du système lui-même.

La numérotation de Gödel est un mécanisme ingénieux qui comble le fossé entre la syntaxe (la structure symbolique d'un langage formel) et la théorie des nombres (les propriétés des nombres entiers). Ce processus permet de traduire des énoncés logiques en énoncés numériques. La méthode consiste à attribuer d'abord un entier unique à chaque symbole de base du langage formel (par exemple, ‘ ¬ ’ → 1, ‘ ∨ ’ → 2, ‘ ∀ ’ → 3, ‘ x ’ → 4, etc.).

Une formule, qui est une séquence de ces symboles, peut alors se voir attribuer son propre numéro unique. La méthode originale de Gödel utilisait la factorisation en nombres premiers. Pour une séquence de symboles avec les nombres [latex]s_1, s_2, …, s_k[/latex], le nombre de Gödel de la formule serait [latex]2^{s_1} \cdot 3^{s_2} \cdot 5^{s_3} \cdot \dots \cdot p_k^{s_k}[/latex], où [latex]p_k[/latex] est le k-ième nombre premier. En raison du théorème fondamental de l'arithmétique (décomposition unique en facteurs premiers), cette correspondance est injective ; chaque formule reçoit un nombre unique, et à partir de n'importe quel nombre, la formule originale peut être récupérée de manière unique.

Enfin, une preuve, qui est une séquence de formules, peut être encodée de la même manière, en prenant les nombres de Gödel de ses formules constitutives et en appliquant à nouveau l'encodage par puissance première. Cette arithmétique complète signifie que les propriétés métamathematiques complexes, telles que ‘ la séquence F est une preuve valide de la formule P ’, deviennent des prédicats purement arithmétiques impliquant les nombres de Gödel de F et P. Cela a permis à Gödel de construire une formule qui fait référence à sa propre prouvabilité, étape clé de sa preuve d'incomplétude.

UNESCO Nomenclature: 1201
– Mathématiques pures

Taper

Système abstrait

Perturbation

Substantiel

Usage

Conceptuelle/théorique

Précurseurs

  • géométrie analytique (mise en correspondance de la géométrie et de l'algèbre par Descartes)
  • Le concept de ‘ characteristica universalis ’ de Leibniz’
  • le théorème fondamental de l'arithmétique (factorisation première unique)
  • formalisation des langages en logique par Frege et Russell
  • Les travaux de Cantor sur les applications entre ensembles

Applications

  • théorie de la calculabilité (représentation des machines de Turing et des programmes sous forme de nombres)
  • l'informatique (le principe selon lequel le code est une donnée)
  • théorie de l'information
  • cryptographie
  • théorie formelle du langage
  • preuves d'indécidabilité, comme le problème de l'arrêt

Brevets:

NA

Idées d'innovations potentielles

En raison du trafic généré par les robots de scraping, actuellement supérieur à 40 000 par jour, ce contenu est réservé aux membres de la communauté.
> Connexion < ou > Registre < (100% gratuit) pour y accéder, ainsi qu'à tous les autres contenus et outils à accès restreint.

En rapport avec : nombre de Gödel, arithmétique, syntaxe, métamathematique, codage, langage formel, théorie de la démonstration, calculabilité, autoréférence, factorisation en nombres premiers.

Contexte historique

Nombres de Gödel

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

(si la date est inconnue ou non pertinente, par exemple « mécanique des fluides », une estimation arrondie de son émergence notable est fournie)

Inventions, innovations et principes techniques connexes

Les images en pleine résolution et les téléchargements sont uniquement disponibles, et 100% gratuits, pour les membres inscrits.