Indécidabilité et incomplétude.

[Onneritpas]

Incomplétude et indécidabilité en logique mathématique.
 
Indécidabilité et incomplétude sont deux  notions totalement différentes.
 
Indécidabilité.
Juste un exemple :
Rappelons tout d’abord ce que l’on appelle « cardinal » d’un ensemble.
Si un ensemble contient n éléments, son cardinal est n.
Le cardinal des nombres entiers est appelé « ﬡ0 »  (aleph0)
Le cardinal de l’ensemble des nombres entre compris entre 0 et 1 est appelé « ﬡ1 » (aleph1). (On a  ﬡ1 beaucoup plus grand que ﬡ0)
ﬡ0 concerne les ensembles « dénombrables » alors que ﬡ1 désigne des ensembles ayant la puissance du continu. Par exemple l’ensemble des points d’un segment de droite ou l »ensemble des nombres entre0 et 1 ce qui revient au même !
 
Exemple : Hypothèse du continu :
Existe-t-il un ﬡ entre ﬡ0  et ﬡ1 ?
Il a été démontré qu’il n’existe pas,  et qu’il ne peut y avoir, de démonstration pour décider s’il en existe une ou non.
Ce problème est donc appelé : indécidable.
Un autre exemple, plus technique démontre l’indécidabilité du problème des mots dans les semi-groupes de Thue.
 
Incomplétude.
On dit qu’un système d’axiomes est incomplet s’il existe des propositions vraies non démontrables dans ce système d’axiomes.
C’est le cas de l’arithmétique qui contient des propositions vraies mais indémontrables.
Bien sûr, on pourrait croire qu’il suffirait d’ajouter comme axiomes ces propositions et le tout est joué !
Hélas, le théorème de Gödel est à ce point puissant qu’il démontre en plus que le nouveau système d’axiomes ne pourrait, lui aussi  démontrer d’autres propositions vraies et ainsi de suite jusqu’à l’infini.
Il est évident qu’il est impossible de définir un système infini d’axiomes !
Donc l’arithmétique est incomplète.