Comment démontre-t-on l'indécidabilité d'une proposition mathématique ?

[Médiat]

Même en imaginant une machine capable de lister indéfiniment tous les sous-ensembles ?
Qu'est-ce qui permet d'affirmer qu'une telle machine est inconcevable ?

Bonjour,

Ce n'est pas une question de machine mais de cardinal, vous ne pouvez écrire qu'une quantité dénombrable d'algorithmes (puisque c'est une suite finie d'instructions), alors même en leur associant un nombre fini de paramètres entiers, cela ne fait toujours que du dénombrable !
-----

[Deedee81]

Salut,

Même en imaginant une machine capable de lister indéfiniment tous les sous-ensembles ?
Qu'est-ce qui permet d'affirmer qu'une telle machine est inconcevable ?

C'est toujours ce bon vieux Cantor "dénombrable versus non dénombrable"

Si tu as du mal à comprendre, tu peux regarder https://fr.wikipedia.org/wiki/Argume...nale_de_Cantor
Ce n'est pas ma méthode préférée (je préfère celle que j'ai pointé plus haut) mais elle a l'avantage d'être fort simple a comprendre.

Et ça peut s'adapter de manière élémentaire aux sous-ensemble (par exemple en utilisant le lien que Médiat a donné plus haut entre sous-ensemble de N et nombre réels).

A noter que ce procédé permet aussi de démontrer d'autres choses sympathique comme le fait que tout nombre ou toute suite de nombre n'est pas nécessairement calculable (au sens de Turing) ou pour démontrer que le problème de l'arrêt est un indécidable (ici le cadre est les machines de Turing) ce qui retombe dans le sujet. Ca a des implications pratiques assez étonnante. Par exemple, supposons que je désire écrire un programme CTRL qui va prendre un programme quelconque P et qui doit déterminer s'il peut provoquer une division par zéro. Je dispose d'une mémoire illimitée. Et bien on démontre "à la Turing" qu'un tel programme CTRL est .... impossible à écrire !!!! Evidemment, je peux en écrire un qui va détecter certains cas flagrant (par exemple s'il est écrit xxx / 0 en toute lettre) ou qui va marcher sur un certain nombre de programmes. Mais pour pour tous les cas possibles pour n'importe quel programme P, tintin, c'est impossible. J'avais vu ça en potassant la théorie des compilateurs et j'avais trouvé ça à la fois étonnant et décevant.

[andretou]

ok, merci à tous de m'avoir éclairé !

[gg0]

Avec de l'indéfiniment, on n'obtient que du fini, et à la limite (temps infini, si ça avait un sens), du dénombrable. Et l'ensemble des sous-ensembles de N n'est pas dénombrable.

Cordialement.

NB : Une petite formation sur la théorie des ensembles te ferait le plus grand bien.

[Gondolin]

Le premier théorème d'incomplétude de Gödel est en fait facile à démontrer une fois que l'on a saisi l'idée (c'est là le génie de Gödel):
1) Une théorie T qui contient assez d'arithmétique[*] permet d'encoder la démonstrabilité d'une proposition dans la théorie T elle-même (ie de manière interne à la théorie).
2) Via un argument diagonal on peut construire des énoncés qui font référence à eux-mêmes (de même manière qu'on peut écrire des programmes qui affichent leur propre code source, voire toute la théorie des quines sur wikipédia)

L'énoncé de Gödel est alors l'énoncé G qui dit "l'énoncé G n'est pas démontrable". Alors l'énoncé G est vrai (preuve par l'absurde: s'il était faux, alors G serait démontrable, donc vrai, absurde; contrairement à ce que l'on pourrait penser ce n'est pas un raisonnement circulaire), donc G n'est pas démontrable (par T)! Exercice amusant: l'énoncé H qui dit "l'énoncé H est démontrable" est lui aussi vrai, donc H est démontrable.
[*] Il faut une théorie \sigma_1-sound contenant RCA0 (en fait techniquement pour Gödel il faut même qu'elle soit omega-consistante mais il y a une variante du à Rosser qui n'a besoin que de la \sigma_1-soudness).