Logique du premier ordre et complétude
La logique du premier ordre est le langage formel des énoncés quantifiés sur les objets et les relations, et le théorème de complétude de Gödel démontre que son système de preuve saisit précisément les énoncés vrais dans toutes les interprétations.
Definition
La logique du premier ordre étend la logique propositionnelle avec des quantificateurs portant sur un domaine d'objets, ainsi que des symboles de relation, de fonction et de constante ; le théorème de complétude stipule qu'un énoncé est dérivable dans son système de preuve précisément lorsqu'il est une conséquence logique des axiomes supposés.
Scope
Ce sujet aborde la syntaxe des langages du premier ordre, les termes, les formules et les énoncés, la sémantique des structures et de la satisfaction, les notions de validité et de conséquence logique, un système déductif pour la logique du premier ordre, ainsi que les théorèmes de correction (soundness) et de complétude reliant la prouvabilité à la vérité.
Core questions
- Quelle est la syntaxe et la sémantique précises de la logique du premier ordre ?
- Que signifie pour un énoncé d'être une conséquence logique d'une théorie ?
- Pourquoi tout énoncé valide est-il formellement prouvable ?
- Comment la complétude relie-t-elle le système de preuve à la classe de tous les modèles ?
Key theories
- Théorème de correction
- Tout énoncé dérivable dans le système de preuve est vrai dans tout modèle des prémisses ; ainsi, le système déductif ne prouve jamais de conséquences fausses.
- Théorème de complétude de Gödel
- Réciproquement, tout énoncé qui est vrai dans tous les modèles d'une théorie en est dérivable ; ainsi, la prouvabilité et la conséquence logique coïncident pour la logique du premier ordre.
- Construction de Henkin
- La complétude est prouvée en construisant un modèle directement à partir d'un ensemble maximal cohérent d'énoncés avec des témoins pour les énoncés existentiels, offrant ainsi une recette syntaxique pour la construction de modèles.
Clinical relevance
La logique du premier ordre constitue le cadre standard pour la formalisation des théories mathématiques, et la complétude garantit que toute vérité sémantique commune à tous les modèles peut en principe être prouvée, ce qui soutient la preuve automatique de théorèmes et l'adéquation fondamentale des systèmes axiomatiques.
History
La logique du premier ordre a émergé de la Begriffsschrift de Frege et a été isolée comme un système distinct par Hilbert et Ackermann. Gödel a prouvé la complétude dans sa thèse de doctorat de 1929, et la construction de Henkin de 1949 a fourni la preuve simplifiée utilisant des ensembles cohérents maximaux, qui est aujourd'hui standard.
Key figures
- Gottlob Frege
- Kurt Goedel
- Leon Henkin
- Alfred Tarski
Related topics
Seminal works
- enderton2001
- marker2002
- shoenfield1967
Frequently asked questions
- En quoi la complétude diffère-t-elle des théorèmes d'incomplétude de Gödel ?
- La complétude concerne la conséquence logique : tout énoncé vrai dans tous les modèles d'une théorie est prouvable. L'incomplétude concerne une théorie spécifique : une théorie cohérente suffisamment forte contient des énoncés vrais dans son modèle visé qu'elle ne peut pas prouver. Les deux notions sont distinctes et ne sont pas en conflit.
- Pourquoi la logique du premier ordre est-elle le choix standard ?
- Elle est suffisamment expressive pour formaliser la plupart des mathématiques tout en bénéficiant de la complétude et de la compacité, propriétés qui font défaut aux logiques plus fortes telles que la logique du second ordre. Cet équilibre entre expressivité et bonnes propriétés métathéoriques en fait le cadre logique par défaut.