complétude

En logique mathématique et métalogique, un système formel est dit complet par rapport à une propriété particulière si chaque formule possédant cette propriété peut être prouvée par une démonstration formelle à l'aide de ce système, c'est-à-dire par l'un de ses théorèmes ; autrement, le système est dit incomplet. Le terme « complet » est également utilisé sans qualification, avec des significations différentes selon le contexte, la plupart du temps se référant à la propriété de la validité sémantique. Intuitivement, dans ce sens particulier, un système est dit complet si toute formule vraie y est démontrable. Kurt Gödel, et ont tous publié des preuves de complétude. (Voir la thèse de Church-Turing.)