Résultats fondamentaux en logique mathématique

Study Notes

Résultats fondamentaux en logique mathématique

La décennie 1930 est marquée par des avancées significatives en logique mathématique, notamment le théorème de complétude du calcul des prédicats du premier ordre démontré par Gödel.
Ce théorème stipule que toute démonstration mathématique peut être représentée dans le formalisme du calcul des prédicats, indiquant sa complétude.
L'ensemble des théorèmes du calcul des prédicats n'est pas calculable, ce qui signifie qu'il n'existe pas d'algorithme capable de vérifier si une formule donnée est prouvable ou non.
Malgré cela, il existe un algorithme qui, étant donné une formule du premier ordre, peut en trouver une preuve en un temps fini si elle existe, sinon il continue indéfiniment.
L'ensemble des formules du premier ordre prouvables est considéré comme "récursivement énumérable" ou "semi-décidable".
Le second théorème d'incomplétude de Gödel établit que la cohérence (non-contradiction) d'une théorie, incluant des axiomes qui formalisent l'arithmétique (comme les axiomes de Peano), n'est pas une conséquence de ces axiomes seuls.
La propriété de la sous-formule, découlant du théorème d'élimination des coupures en calcul des séquents de Gentzen, stipule que tout théorème purement logique peut être démontré en utilisant uniquement des propositions qui sont des sous-formules de son énoncé.
Cette propriété implique la cohérence de la logique, car elle interdit la dérivation de la formule vide, associée à l'absurdité.
L'indépendance de l'hypothèse du continu par rapport aux autres axiomes de la théorie des ensembles (ZF) a été prouvée en 1963 par Cohen.
La théorie de la calculabilité a considérablement progressé au cours de la deuxième moitié du XXe siècle.
La correspondance de Curry-Howard, établie vers le début des années 1980, identifie la simplification des démonstrations et les programmes, créant ainsi un lien entre les mathématiques et l'informatique.
Cette correspondance a été étendue à la logique classique en 1990.
Des théorèmes mathématiques importants, tels que le théorème des quatre couleurs et le théorème de Feit-Thompson, ont été entièrement formalisés et mécanisés.
Le XXIe siècle a vu l'émergence de nouvelles branches prometteuses de la logique, comme la théorie homotopique des types.

Système logique

Un système logique (ou logique) est un système formel auquel on associe une sémantique.
Un système formel se compose de deux éléments :
- Une syntaxe (ou langage) définie par un ensemble de symboles utilisés pour construire des formules. Dans les systèmes de logique classique ou intuitionniste, les formules représentent des énoncés mathématiques exprimés formellement. De plus, un ensemble de règles de construction de formules est défini, permettant de créer des formules par des moyens combinatoires, telles que des suites de symboles, des arbres étiquetés, des graphes, etc.
- Un système de déduction (ou système d'inférence, ou encore calcul) qui possède un ensemble d'axiomes et de règles d'inférence. Les déductions sont également définies par des moyens combinatoires. Une déduction permet de dériver des formules (les formules prouvables ou théorèmes) à partir de formules de départ (les axiomes) en utilisant des règles (les règles d'inférence).
La sémantique sert à attribuer un sens, voire une valeur de vérité, à chaque formule construite à partir d'un système formel.
Cette attribution se fait par le biais d'une interprétation (ou valuation) des formules, une fonction qui associe à chaque formule un objet dans une structure abstraite appelée modèle.
La sémantique permet de définir la validité des formules et d'interpréter les formules d'un système formel dans un contexte donné.
Dans le contexte de la logique classique, il s'agit d'attribuer à chaque formule la valeur Vrai ou la valeur Faux, pouvant être identifiées respectivement aux valeurs 1 ou 0 (voir Algèbre de Boole).
Il arrive que la syntaxe soit définie comme étant le système de déduction lui-même, et que l'on désigne le système formel complet (voire le système logique complet) par le terme "calcul".
Par conséquent, il est courant d'utiliser le terme "calcul des propositions" pour désigner ce que l'on devrait appeler "logique des propositions", de même que l'on peut confondre "calcul des prédicats" et "logique des prédicats".

Syntaxe et sémantique

Les formules et les déductions sont caractérisées par leur nature finie.
De plus, chaque ensemble de formules et de déductions est récursif, c'est-à-dire qu'il existe un algorithme qui détermine si un objet donné est une formule correcte ou une déduction correcte du système.
L'étude de la logique du point de vue des formules et des expressions est appelée la syntaxe.
La sémantique, au contraire, s'écarte de la combinatoire en utilisant (généralement) des objets infinis. Elle...

Description

Ce quiz explore les réalisations clés en logique mathématique des années 1930, notamment le théorème de complétude de Gödel. Vous découvrirez des concepts tels que la récursivité et l'énumérabilité des formules du premier ordre, ainsi que les implications du second théorème d'incomplétude. Testez vos connaissances sur ces avancées significatives.