Une proposition (on dit aussi énoncé) est dite décidable dans une théorie axiomatique, si on peut la démontrer ou démontrer sa négation dans le cadre de cette théorie. Un énoncé mathématique est donc indécidable dans une théorie s’il est impossible de le déduire, ou de déduire sa négation, à partir des axiomes. Pour distinguer cette notion d’indécidabilité de la notion d’indécidabilité algorithmique (voir ci-dessous), on dit aussi que l’énoncé est indépendant du système d’axiomes.

En termes plus concrets, cela veut dire qu’on demande au système de fournir une conclusion sans lui avoir fourni suffisamment d’hypothèses. Ainsi, l’âge du capitaine d’un bateau est indécidable en fonction du tonnage et de la vitesse du navire.

En logique classique, d’après le théorème de complétude, une proposition est indécidable dans une théorie s’il existe des modèles de la théorie où la proposition est fausse et des modèles où elle est vraie. On utilise souvent des modèles, pour montrer qu’un énoncé est indépendant d’un système d’axiomes (dans ce cadre on préfère employer indépendant qu’indécidable). La propriété utilisée dans ce cas n’est pas le théorème de complétude mais sa réciproque, très immédiate, appelée parfois fidélité. Probablement est-ce là d’ailleurs la première apparition de la notion de modèle, avec la construction au XIXème siècle de modèles des géométries non classiques, ne vérifiant pas l’axiome des parallèles. Si l’on admet le fait assez intuitif que la géométrie euclidienne est cohérente — la négation de l’axiome des parallèles ne se déduit pas des autres axiomes — l’axiome des parallèles est bien alors indépendant des autres axiomes de la géométrie, ou encore indécidable dans le système formé des axiomes restant.

Une théorie mathématique pour laquelle tout énoncé est décidable est dite complète, sinon elle est dite incomplète. Beaucoup de théories mathématiques sont naturellement incomplètes, parce qu’il y a évidemment des énoncés qui ne sont pas déterminés par les axiomes (théorie des groupes, des anneaux, ...) . Certaines théories, comme la théorie des corps algébriquement clos, celle des corps réels clos, ou encore l’arithmétique de Presburger sont complètes. Le théorème d’incomplétude de Gödel nous garantit que toute théorie axiomatique cohérente, et suffisamment puissante pour représenter l’arithmétique de Peano (l’arithmétique usuelle), est incomplète, pourvu qu’elle soit axiomatisée de façon que l’on puisse décider au sens algorithmique (voir ci-dessous) si un énoncé est ou non un axiome. Cette dernière hypothèse qui semble un peu compliquée à énoncer est très naturelle et vérifiée par les théories axiomatiques usuelles en mathématiques.