Complétude

• Étant donné un ensemble E d'éléments et un sous-ensemble S de cet ensemble, on peut définir la complétude de S relativement à E par la fraction d'éléments de E se trouvant dans S. Par exemple, si E contient 12 éléments et S trois, alors la complétude est de 3/12 = 25 %. La notion est notamment utilisé dans le cadre de relevés (recensements), où l'on défini la complétude de l'échantillon constitué par la population recensée par rapport à la totalité de la population à laquelle on s'intéresse (population totale qui n'est pas nécessairement connue). La détermination de la complétude d'un échantillon est un élément important dans le cadre de l'étude d'une population : elle peut permettre par exemple d'évaluer le biais statistique de l'échantillon sur lequel se fait l'étude.
  • Exemple : soit une région constituée de dix étoiles rouges et deux étoiles jaunes. Supposons que l'ensemble des objets détectés dans cette région soit constitué de deux étoiles rouges et une jaune. La complétude générale est de 25 % (3/12), mais si on regarde par type d'étoiles, la complétude atteint 50 % parmi les jaunes et 20 % parmi les rouges. Le nombre réel d'étoiles ne serait généralement pas connu exactement mais il peut être estimé à partir de la population connue et de la détermination (typiquement à partir de tests expérimentaux ou de simulations) de la complétude, qui devient donc un paramètre important pour l'étude de la population d'objets considérée. Si l'on sait par exemple que, dans notre échantillon, on doit trouver 20 % des étoiles rouges et qu'on en a trouvé une, alors on peut estimer qu'il y en a cinq en tout. Évidemment, dans cet exemple, le faible nombre d'objets détectés (deux rouges et une jaune) augmente l'incertitude sur la taille réelle de la population totale : voir erreur statistique.

On parle de complétude en mathématiques dans des sens très différents. On dit d'un objet mathématique qu'il est complet pour exprimer que rien ne peut lui être ajouté, en un sens qu'il faut préciser dans chaque contexte. Dans le cas contraire, on parle d'incomplétude, surtout dans le contexte de la logique mathématique.

• Un espace métrique est complet quand toute suite de Cauchy d'éléments de cet espace converge, voir espace complet.
  • Plus généralement, un espace uniforme est complet quand tout filtre de Cauchy converge.
• Un espace mesuré est complet quand tout sous-ensemble d'un ensemble de mesure nulle est mesurable, voir mesure complète.
• En logique mathématique, un jeu de règles ou d'axiomes est complet quand il formalise entièrement la sémantique attendue. Cela peut se préciser de façons très différentes. On a les deux notions de complétude suivantes pour la sémantique de Tarski.
  • Un système de déduction pour une logique donnée (calcul propositionnel, ou calcul des prédicats en logique classique mais aussi en logique intuitionniste ...), est complet quand il démontre les formules valides dans tous les modèles de cette logique. Plus précisément, on dit qu'une formule se déduit sémantiquement d'une théorie quand dans tout modèle de la théorie, pour toute interprétation de ses variables libres, la formule est valide. Un système de déduction est correct, fidèle ou adéquat quand toute déduction est valide sémantiquement. Il est complet quand toutes les déductions sémantiques peuvent se dériver dans le système. On parle de théorème de complétude quand il existe un système de déduction fidèle qui est complet (le système de déduction doit être raisonnable, c’est-à-dire que l'ensemble des preuves dans le système doit être récursif).
  • Une théorie axiomatique est complète quand tout énoncé du langage de la théorie est déterminé par déduction dans la théorie : il est soit démontrable, soit de négation démontrable. Cette notion est étroitement liée à celle de théorie décidable mais ne se confond pas avec elle. Le premier théorème d'incomplétude de Gödel énonce que, sous des hypothèses raisonnables, aucune théorie arithmétique cohérente n'est complète. Il a pour conséquence qu'il n'y a pas système de déduction raisonnable qui capture entièrement la sémantique attendue, à savoir la vérité dans un modèle, celui des entiers naturels (le modèle standard de l'arithmétique).
• En calcul propositionnel, un système de connecteurs est dit complet (ou fonctionnellement complet) quand il permet de décrire toutes les fonctions de la sémantique attendue, soit dans le cas de la logique classique, quand ces connecteurs permettent de décrire toutes les fonctions booléennes.
• En théorie de la calculabilité ou en théorie de la complexité des algorithmes, un ensemble ou un problème de décision est complet dans une classe, si cet ensemble ou problème appartient à la classe, et si, pour une notion de réduction adéquate, tout ensemble ou problème de la classe se réduit à celui-ci.
  • Ainsi le problème de l'arrêt, plus exactement l'ensemble des entiers n tels que la machine de code n s'arrête pour l'entrée n, est complet dans la classe des ensembles récursivement énumérables (pour la réduction récursive).
  • La satisfaisabilité d'un ensemble de clauses du calcul propositionnel est un problème NP-complet, c’est-à-dire complet dans la classe des problèmes solubles en temps non déterministe polynomial (pour la réduction polynomiale).
• En théorie des ordres, un treillis est complet quand toute partie possède une borne supérieure et une borne inférieure, voir comme cas particulier les algèbres de Boole complètes.
• Dans le contexte de l'informatique théorique, en théorie des domaines, un ordre partiel complet (parfois abrégé cpo, de l'anglais) est un ensemble partiellement ordonné qui a un plus petit élément et dont toutes les chaînes ont une borne supérieure.
• En théorie des graphes, un graphe (ou un sous-graphe) non orienté est complet quand toute paire de sommets est reliée par une arête.