complétude

Cet article est extrait de l'ouvrage Larousse « Dictionnaire de la philosophie ».

Logique

1. Au sens fonctionnel (ou au sens expressif), propriété satisfaite par un système de connecteurs propositionnels assez riche pour exprimer toutes les fonctions de vérité ; ainsi, la négation et la disjonction, prises ensemble, constituent un système complet de connecteurs ; ce n'est pas le cas du système constitué de l'implication et de la disjonction, car aucune formule écrite avec ces deux seuls connecteurs n'est logiquement fausse. – 2. Au sens sémantique, propriété satisfaite par une présentation axiomatique d'une partie de la logique, lorsque toutes les formules logiquement valides qui y sont exprimables y sont prouvables ; ainsi, les axiomatiques usuelles pour le calcul propositionnel et pour le calcul des prédicats du premier ordre sont sémantiquement complètes ; par contre, la logique du second ordre ne possède aucune axiomatisation sémantiquement complète. – 3. Au sens syntaxique (ou au sens déductif, ou encore au sens « des théories »), propriété d'une théorie mathématique consistante dans laquelle tout énoncé du langage de la théorie est ou bien prouvable, ou bien réfutable ; ainsi, la théorie de la seule multiplication des entiers naturels est syntaxiquement complète ; en revanche, l'arithmétique de Peano, pas plus qu'aucune de ses extensions, n'est syntaxiquement complète, car si ces théories sont consistantes, elles contiennent toujours des énoncés indécidables, c'est-à-dire ni prouvables ni réfutables.

Jacques Dubucs

→ arithmétique, consistance, décidabilité, effectivité, Gödel (théorème de), machine (logique, de Turing)