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

[Médiat]

Non, absolument pas, c'est un théorème de ZFC + HC et son contraire est un théorème de ZFC + Non HC
-----

[andretou]

Mais cela ne revient-il pas à décréter que l'hypothèse du continu est vraie dans une théorie où l'on déclare qu'elle est vraie (ZFC + HC), et fausse dans une théorie où l'on déclare qu'elle est fausse (ZFC + non HC) ?!...

[Médiat]

Comme pour tous les axiomes ; la commutativité est "fausse" dans la théorie des groupes non commutatifs et "vraie" dans la théorie des groupes commutatifs !

Il y a aussi des cas où un axiome supplémentaire peut transformer un indécidable en théorème, mais cela ne change pas grand-chose.

[andretou]

Finalement, il suffit de bien choisir ses axiomes pour pouvoir démontrer tout et son contraire et avoir toujours raison !?
Le choix des axiomes peut-il être purement arbitraire ? Ou doit-il obéir à des règles ?

[Médiat]

Finalement, il suffit de bien choisir ses axiomes pour pouvoir démontrer tout et son contraire et avoir toujours raison !?

Ca tombe bien les mathématiques ne s'occupent pas de vérité !

Le choix des axiomes peut-il être purement arbitraire ? Ou doit-il obéir à des règles ?

Chacun est libre de choisir les axiomes qu'il veut, puis de "prouver" à la communauté que ce choix a un intérêt quelconque.

[andretou]

Ok !
Pour en revenir à HC, le seul et unique moyen de résoudre l'indécidabilité consiste à faire de HC elle-même (ou de non HC) un axiome ?
Ou existe-t-il d'autres moyens de résoudre cette indécidabilité ?

[Médiat]

Par exemple choisir un axiome A tel que ou

[andretou]

Un tel axiome A existe-t-il nécessairement ?

[Médiat]

Oui, par exemple ou [/QUOTE]

[gg0]

Finalement, il suffit de bien choisir ses axiomes pour pouvoir démontrer tout et son contraire et avoir toujours raison !?
Le choix des axiomes peut-il être purement arbitraire ? Ou doit-il obéir à des règles ?

Pour pouvoir tout démontrer, il suffit de prendre deux axiomes contraires. Mais bien entendu, ça n'a plus d'intérêt. Donc quand on choisit des axiomes pour avancer, on essaie qu'ils ne soient pas contradictoires.

Cordialement.

[andretou]

Mais existe-t-il nécessairement un axiome A différent de HC tel que ou ?
Ou cette question est-elle à son tour indécidable ???...

[Médiat]

Je ne vois ni où vous voulez en venir, ni l'intérêt, si vous y tenez A = HGC, et il y en a des tonnes d'autres (moins évidentes que celle-ci), par exemple A = "IR est égal à l'union d'une famille croissante d'ensembles dénombrables"

[andretou]

Je ne vois ni où vous voulez en venir, ni l'intérêt

J'essaie simplement de comprendre l'indécidabilité et ses implications...
Je vous remercie pour vos explications et pour votre patience.

[Médiat]

Bonjour,

Alors j'en profite pour tenter de tordre le cou à certaines incompréhensions qui entourent la notion d'indécidable :

1) Les théorèmes d'incomplétude signeraient la mort des mathématiques (j'ai lu cela !) en ce sens que l'on ne pourra jamais "tout savoir", non seulement un tel argument s'applique sans problème à toutes les formes de connaissance, ce qui devrait montrer l'inanité de cet argument, mais surtout, les théorèmes d'incomplétude assurent, aux mathématiciens, du travail sans limite, la vie éternelle des mathématiques !

2) Il y aurait, pour chaque théorie, en particulier l'arithmétique ou la théorie des ensembles, une "vérité" supra mathématique(*) que les mathématiques essayent d'approcher (on peut faire un parallèle avec la physique qui essaye d'approcher "la réalité"), la présence d'un indécidable montrant que cette "vérité" n'est pas accessible (et ne le sera jamais dans le cas des 2 théories que je viens de citer), alors qu'il "suffit" d'ajouter un axiome pour qu'un indécidable ne le soit plus.

3) J'ai entendu Cédric Villani dire que face à une conjecture, on pouvait "soit la démontrer, soit démontrer son contraire, soit démontrer son indécidabilité ce qui serait une mauvaise nouvelle"(**) ; on pourrait dire qu'au contraire, c'est une bonne nouvelle puisque l'on a le choix !

4) Un exemple d'indécidable qui s'est révélé être extrêmement fructueux est le fameux cinquième postulat(***) d'Euclide (qui est bien indécidable dans la théorie constituée des autres axiomes), puisque deux formules incompatibles avec ce postulat donneront naissance au 19ième siècle aux géométries elliptique et hyperbolique (en plus de l'euclidienne).

5) Même une théorie complète peut avoir plusieurs modèles non isomorphes (pas besoin d'indécidable pour ne pas pouvoir tout dire à propos d'un tel objet mathématique à partir de la théorie)

(*) Ce n'est pas la position platonicienne que je critique, mais, l'idée qu'un indécidable serait une catastrophe insoluble.
(**) Je ne cite pas verbatim, ayant entendu cette phrase à la radio, en l'entendant je me suis retrouvé collé au plafond, je n'ai donc pas pu la noter immédiatement, mais j'en garantis l'esprit.
(***) Les mathématicens Grecs faisaient la différence entre axiome (évident, par nature indémontrable (dans la vision des mathématiques d'il y a 2000 ans et plus)) et postulat (utile, mais pas encore démontré, peut-être démontrable)

[andretou]

5) Même une théorie complète peut avoir plusieurs modèles non isomorphes (pas besoin d'indécidable pour ne pas pouvoir tout dire à propos d'un tel objet mathématique à partir de la théorie)

Auriez-vous éventuellement un exemple pour nous permettre de comprendre ?

[Médiat]

Par exemple la théorie des ordres linéaires denses sans extrémums.

Cette théorie est -catégorique, c'est à dire qu'elle ne possède qu'un seul modèle de cardinal (à isomorphisme près), alors qu'elle n'est pas -catégorique, c'est à dire qu'en cardinal strictement plus grand que le dénombrable il existe plusieurs modèles non isomorphes.

Par exemple et ne sont pas isomorphe (trivial)

[andretou]

2) Il y aurait, pour chaque théorie, en particulier l'arithmétique ou la théorie des ensembles, une "vérité" supra mathématique(*) que les mathématiques essayent d'approcher (on peut faire un parallèle avec la physique qui essaye d'approcher "la réalité"), la présence d'un indécidable montrant que cette "vérité" n'est pas accessible (et ne le sera jamais dans le cas des 2 théories que je viens de citer), alors qu'il "suffit" d'ajouter un axiome pour qu'un indécidable ne le soit plus.

Je suis d'accord qu'il "suffit" d'ajouter un axiome pour qu'un indécidable ne le soit plus, mais je voudrais faire remarquer que le problème n'en est pas résolu pour autant.
Par exemple, s'il s'avérait que la conjecture de Goldbach est indécidable, alors vous poseriez comme axiome "tout nombre pair est égal à la somme de deux nombres premiers". Mais Gödel a démontré que la nouvelle théorie ainsi créée contiendrait nécessairement de nouvelles propositions indécidables !
Le fait d'axiomatiser une proposition indécidable ne fait ainsi que déplacer le problème sans le solutionner au fond...

[Médiat]

Certes, mais ce n'est en rien un problème, le but d'une théorie mathématique n'est pas de pouvoir "tout" démontrer, mais de démontrer ce dont on a besoin (quelque soit la source de ce besoin), avec les outils (axiomes) disponibles.

Ce genre d'absolu après lequel vous semblez courir n'a pas d'intérêt, pour prendre un exemple simpliste, en prenant le plus simple ensemble infini : IN, sans aucune structure (donc les théorèmes d'incomplétude de Gödel ne s'appliquent pas), vous ne pourrez pas définir "tous" ses sous-ensembles, cela n'a empêché personne de faire de l'arithmétiques depuis des millénaires ...

[andretou]

en prenant le plus simple ensemble infini : IN, sans aucune structure (donc les théorèmes d'incomplétude de Gödel ne s'appliquent pas), vous ne pourrez pas définir "tous" ses sous-ensembles...

Je ne comprends malheureusement pas ce que signifie "définir les sous-ensembles de IN"...
Pourriez-vous SVP m'expliquer ?

[Médiat]

Si on part d'un ensemble fini, par exemple {a, b, c}, il est facile de définir et de lister chacun de ses sous-ensembles (il y en a 8).

Pour un ensemble infini, IN par exemple, on peut définir un certain nombre de ses sous-ensembles (les nombres pairs, les nombres plus grand que 8769876989856987676, etc.), mais vous ne pourrez pas les définir "tous".

[Deedee81]

Salut,

Le fait d'axiomatiser une proposition indécidable ne fait ainsi que déplacer le problème sans le solutionner au fond...

J'ai l'impression de sentir une petite origine platonicienne à cette remarque.

Comme dit Mediat, il n'y a pas d'absolu et aucune proposition mathématique n'est vraie ou fausse dans l'absolu. Ce n'est jamais qu'un "paquet de symboles mathématiques".
Et la validité de la proposition est simplement une question liée à la définition de ces symboles et aux axiomes adoptés.
Il y a une très grande liberté.

mais vous ne pourrez pas les définir "tous".

Petite précision utile, Médiat, n'hésite pas à me frapper violemment si je dis une bêtise : ce problème de pas pouvoir tous les définir n'est ni une question de temps (la liste est infinie) ni même de caractère dénombrable (l'ensemble des sous-ensembles de N est non dénombrable, on ne peut donc en faire une liste séquentielle) (en fait, si, c'est là qu'est le problème, voir ci-dessous, mais le fait que l'ensemble soit non dénombrable n'est pas un problème en soi).

C'est pire que ça. Quel que soit le langage fini (phrases de longueur finies) utilisé pour définir les sous ensembles de N, il y aura toujours des sous-ensembles que l'ont ne peut pas définir avec ce langage. Tout simplement parce que ce langage ne donnant que des phrases finies, alors l'ensemble des définitions est lui dénombrable.

Ce phénomène peut être assez troublant, bien qu'assez compréhensible dès qu'on se penche un peu dessus. On peut comprendre qu'à l'époque de Cantor cela ait fait bondir plus d'un mathématicien

[andretou]

l'ensemble des sous-ensembles de N est non dénombrable

Le nombre de parties d'un ensemble de n éléments n'est-il pas 2^n ?
De ce fait, le nombre de sous-ensembles de IN n'est-il pas 2 à la puissance aleph0 ?

[Médiat]

C'est pire que ça. Quel que soit le langage fini (phrases de longueur finies) utilisé pour définir les sous ensembles de N, il y aura toujours des sous-ensembles que l'ont ne peut pas définir avec ce langage. Tout simplement parce que ce langage ne donnant que des phrases finies, alors l'ensemble des définitions est lui dénombrable.

Absolument, l'ensemble des définitions est dénombrable, même si on autorise l'usage d'un (ou de plusieurs (forcément fini)) paramètres (forcément entier(s)) ce qui renvoie à ce que Poincaré disait (il faut comprendre du texte suivant que Poincaré réfute la définition de "définition" qu'utilisait un autre mathématicien : Schoenflies (la première phrase))

En effet ce qui caractérise précisément une définition, c'est qu'elle permet de distinguer l'objet défini de tous les autres objets ; si elle s'applique a une infinité d'objets, elle ne permet pas de les discerner les uns des autres ; elle n'en définit aucun; elle n'est plus une définition.
Mais alors il n'y a pas d'autre ensemble que ceux dont tous les éléments sont définissables en un nombre fini de mots; et comme on peut leur appliquer la démonstration de M. Richard (l'ensemble E des nombres qui peuvent être définis en un nombre fini de mots est dénombrable), il semble qu'on doive conclure que tous les ensembles infinis sont dénombrables

[Médiat]

Le nombre de parties d'un ensemble de n éléments n'est-il pas 2^n ?
De ce fait, le nombre de sous-ensembles de IN n'est-il pas 2 à la puissance aleph0 ?

J'ai peur que la façon dont vous écrivez les choses ne cache une incompréhension...
Mais en tout état de cause, c'est exactement ce que sous-entend Deedee81 puisque

[Deedee81]

On a cette notation ici par exemple :
https://fr.wikipedia.org/wiki/Hypoth...8se_du_continu

[andretou]

J'ai peur que la façon dont vous écrivez les choses ne cache une incompréhension...
Mais en tout état de cause, c'est exactement ce que sous-entend Deedee81 puisque

Si encore je ne souffrais que d'une incompréhension limitée !...
Auriez-vous SVP la possibilité d'expliquer pourquoi ?

Deedee, dans l'article Wikipedia on peut lire : On montre que le cardinal de ℝ est celui de l'ensemble des parties de ℕ, que l'on note 2ℵ0
Je comprends que le cardinal de l'ensemble des parties de IN est égal à , mais comment démontre-t-on que est aussi le cardinal de IR ?

[Médiat]

Auriez-vous SVP la possibilité d'expliquer pourquoi ?

Théorème de Cantor

Je comprends que le cardinal de l'ensemble des parties de IN est égal à , mais comment démontre-t-on que est aussi le cardinal de IR ?

Pour un logicien, ce pourrait être la définition de IR, pour un mathématicien, il existe une bijection entre l'ensemble des parties de IN et [0, 1[ : l'application qui a un sous-ensemble de IN fait correspondre le nombre réel dont l'écriture en base 2 comporte des 1 à chaque position décimale qui correspond à un élément de la partie en question (pour être rigoureux, ce n'est pas exactement une bijection à cause des développements impropres, mais comme il n'y en a qu'un nombre dénombrable, ce n'est pas gênant)

[Deedee81]

Salut,

Pris de vitesse

Un petit lien, qui en plus donne la démonstration sous la forme que je préfère.

https://fr.wikipedia.org/wiki/Th%C3%...A8me_de_Cantor

Concernant les développements impropres, c'est comme par exemple 0.999... qui est égal à 1.000...
https://fr.wikipedia.org/wiki/D%C3%A...#39;unit%C3%A9

[Médiat]

Bonjour,

J'aurais pu vous diriger vers : http://forums.futura-sciences.com/ma...-internet.html

[andretou]

Quel que soit le langage fini (phrases de longueur finies) utilisé pour définir les sous ensembles de N, il y aura toujours des sous-ensembles que l'ont ne peut pas définir avec ce langage. Tout simplement parce que ce langage ne donnant que des phrases finies, alors l'ensemble des définitions est lui dénombrable.

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 ?