Proposition indécidable

[kalish]

Bonjour, suite à une discussion plus qu'enrichissante, j'ai appris qu'un système axiomatique d'une théorie se devait d'être essentiellement générateur. (et libre on s'en moque), car si deux axiomatiques donnaient des théorèmes différents, il s'agissait de deux théories différentes.

Du coup, est-ce que ça signifie que n'importe quelle proposition vraie dans une théorie, est indécidable dans une autre, et que si une proposition est indécidable dans une théorie, elle l'est dans une autre? Ca me chiffonne un peu car normalement les propositions sont indécidables si elles sont formulables avec le vocabulaire/les outils de la théorie, cad que ce sont des propositions qui appartiennent à la théorie. Or peut-on imaginer deux théories totalement différentes ayant exactement le même vocabulaire?

Je remercierais les gens qui savent de ne pas me traiter de crétin ou d'inculte quand je pose une question, puisque ils ne le font pas du tout avec les autres, les illuminés de ne pas voir le messie en moi et dans chacune de mes phrases, (surtout quand c'est pour changer d'avis comme de chemise), et de laisser toute remarque psychologique ou morale au vestiaire, la morale n'est pas démontrée mathématiquement, ni ses bienfaits ne le sont.
-----

[Médiat]

Or peut-on imaginer deux théories totalement différentes ayant exactement le même vocabulaire

Dans la théorie des groupes, la commutativité est indécidable, pas dans la théorie des groupes abélien.

La théorie des ordres (avec toutes ses variantes) utilise le même vocabulaire que les relation de préordre (où certains indécidables sont des axiomes pour les ordres) ou même que les relations d'équivalence.

Je remercierais les gens qui savent de ne pas me traiter de crétin ou d'inculte quand je pose une question, puisque ils ne le font pas du tout avec les autres, les illuminés de ne pas voir le messie en moi et dans chacune de mes phrases, (surtout quand c'est pour changer d'avis comme de chemise), et de laisser toute remarque psychologique ou morale au vestiaire, la morale n'est pas démontrée mathématiquement, ni ses bienfaits ne le sont.

Merci de ne pas me remercier !

[kalish]

Ok.

Au passage, lors d'une discussion avec un étudiant allemand en informatique théorique fasciné par le théorème de Godel, je lui ai demandé si les propositions indécidables en question étaient les axiomes (car c'est ce que j'imaginais), il m'a dit oui mais pas seulement. De là venait ma conviction, j'admets que c'est un peu faible, mais sans correction, pas de progrès.

Il faut donc que vous me trouviez des fréquentations vraiment brillantes pour que je ne divague pas.

[kalish]

Est-ce que ça a un sens de dire que la théorie des groupes abéliens est incluse dans la théorie des groupes, ou bien faut il considérer qu'il s'agit de deux théories différentes (l'un n'empêchant pas l'autre non plus au final).

[A voir en vidéo sur Futura]

[Tryss]

Au passage, lors d'une discussion avec un étudiant allemand en informatique théorique fasciné par le théorème de Godel, je lui ai demandé si les propositions indécidables en question étaient les axiomes (car c'est ce que j'imaginais), il m'a dit oui mais pas seulement.

Soit vous l'avez mal compris, soit il a raconté une bêtise plus grosse que lui : un axiome d'une théorie ne peut pas être indécidable dans cette théorie.

D'une part parce qu'il existe, dans cette théorie, une démonstration triviale de cet axiome.

D'autre part, puisqu'il n'existe pas de modèle de cette théorie ou l'axiome est faux (puisqu'alors ce ne serrait pas un modèle de cette théorie)

[kalish]

non, non,je l'ai bien compris, mais peut-être lui m'a-t-il mal compris, puisque c'était moi qui lui posait la question, il n'a juste pas réfuté. Malheureusement, je ne suis pas enregistré ni filmé partout, tout au plus a-t-on pris dans ma vie de moi des photographies compromettantes...

D'une part parce qu'il existe, dans cette théorie, une démonstration triviale de cet axiome.

D'autre part, puisqu'il n'existe pas de modèle de cette théorie ou l'axiome est faux (puisque alors ce ne serrait pas un modèle de cette théorie)

Ok pour la première.
En quoi la deuxième invalide son indécidabilité.
Indécidable ce n'est ni vrai, ni faux, ou en tout cas,on ne peut pas dire si ça l'est, et on ne pourra jamais (dans une théorie donnée).

D'ailleurs à ce propos, puisque HC est indécidable dans ZFC.

Est-ce qu'on peut réellement créer une théorie cohérente où un ensemble a un cardinal compris entre celui des entiers naturels et celui des réels?

Si on ne le pouvait pas, cela n'invaliderait-il pas l'indécidabilité de HC dans zfc puisqu'il ne pourrait y avoir d'hypothèses supplémentaire réalisant son inclusion? CAD l'indécidabilité dans une théorie s'accompagne-t-elle forcément d'une décidabilité dans une autre?

(j'imagine que des théories à une seule hypothèse n'ont pas le statut de théorie, mais c'est peut-être faux).
Existe-t-il forcément une théorie incluant HC? Ce n'est pas ce que je lis sur wikipedia, j'y lis que c'est encore un sujet de recherche.


Autre question, dans le cas de HC, hypothèse et conjecture se confondent un peu il me semble. Les résultats utilisant l'hypothèse du continu vrai dans zfc ont ils autant de valeurs que des résultats utilisant HC faux dans zfc (cad aucune?), en tant que conjecture?

Jusqu'à ce qu'on PROUVE que c'était indécidable, l'hypothèse semblait très plausible pour beaucoup de gens.

[Tryss]

Indécidable ce n'est ni vrai, ni faux, ou en tout cas,on ne peut pas dire si ça l'est, et on ne pourra jamais (dans une théorie donnée).

On peut montrer qu'une proposition est indécidable dans une théorie si il existe des modèles ou cette proposition est vraie, et des modèles ou cette proposition est fausse.

Est-ce qu'on peut réellement créer une théorie cohérente où un ensemble a un cardinal compris entre celui des entiers naturels et celui des réels?

Oui, à l'aide de la méthode du Forcing :

https://fr.wikipedia.org/wiki/Forcing

[Mocassins]

@kalish: La théorie des ensembles et la théorie des modèles sont des domaines dont l'investigation fait rapidement apparaître des subtilités. Tu ferais mieux d'étudier un bouquin avec définitions, propriétés de base, que de poser les questions comme elles te viennent en avançant avec une idée intuitive de ce qu'est une théorie, un modèle, la vérité en mathématique, ZFC...

[Matmat]

Ok.

Au passage, lors d'une discussion avec un étudiant allemand en informatique théorique fasciné par le théorème de Godel, je lui ai demandé si les propositions indécidables en question étaient les axiomes (car c'est ce que j'imaginais), il m'a dit oui mais pas seulement. De là venait ma conviction, j'admets que c'est un peu faible, mais sans correction, pas de progrès.

Il faut donc que vous me trouviez des fréquentations vraiment brillantes pour que je ne divague pas.

Chaque axiome d'un système d'axiome cohérent est un indécidable du système d'axiome amputé de cet axiome.

[Médiat]

Chaque axiome d'un système d'axiome cohérent est un indécidable du système d'axiome amputé de cet axiome.

Bonsoir,

Ceci n'est pas tout à fait exact (c'est souhaitable mais pas obligatoire), un bon exemple est ZF.

[Matmat]

A cause de l'axiome de la paire ?

[Médiat]

Ou le schéma d'axiomes de compréhension qui peut se déduire du schéma de remplacement, ou l'axiome de l'ensemble vide etc.

De plus, à partir du moment où il y a un schéma d'axiomes, il y a de fortes chances qu'il y ait de nombreuses redondances

[kalish]

La théorie des ensembles et la théorie des modèles sont des domaines dont l'investigation fait rapidement apparaître des subtilités. Tu ferais mieux d'étudier un bouquin avec définitions, propriétés de base, que de poser les questions comme elles te viennent en avançant avec une idée intuitive de ce qu'est une théorie, un modèle, la vérité en mathématique, ZFC...

désolé mais je n'ai pas accès à ces bouquins, et je n'ai pas les moyens de les acheter.

En plus, remarque annexe, il me semble qu'on en apprend énormément en posant des questions.

Au passage, les termes de la logique semblent donner naissance à des discussions plutôt confuses y compris parmi la communauté, http://www.les-mathematiques.net/pho...,397421,397421

Chaque axiome d'un système d'axiome cohérent est un indécidable du système d'axiome amputé de cet axiome.

Ceci n'est pas tout à fait exact (c'est souhaitable mais pas obligatoire), un bon exemple est ZF.

Je suppose que c'est ce que vous vouliez dire quand vous parliez de système axiomatique libre.

Mais si deux axiomes ne sont pas "libres", n'est il pas forcément possible de créer des systèmes incohérents? (où par exemple, si chacun des axiomes est vrai, alors il implique que l'autre soit faux en partie?), dès lors on aurait prouvé un énoncé indémontrable, ce qui n'est pas possible dans une théorie cohérente, donc la théorie n'est pas cohérente.
C'est surprenant de ne pas pouvoir prouver qu'une théorie est cohérente mais de pouvoir prouver qu'elle est incohérente.


Du coup j'ai de nouveaux une foule de questions. Si il existe TOUJOURS des propositions indécidables dans une théorie arithmétique etc etc..., ET qu'il suffit de rajouter des axiomes, ou des hypothèses pour inclure la proposition indécidable dans une théorie cohérente, (qui donc possèdera de nouveaux énoncés indécidables), toutes les théories sont extensibles à l'infini, et il existe donc des théories cohérentes avec une infinité d'axiomes. (voire une infinité de théories cohérentes avec une infinité d'axiomes).

A-t-on une possibilité de quantifier le nombre de propositions indécidables par rapport au nombre d'axiomes libres (et minimaux), ou existe-t-il une infinité de propositions indécidables dans chaque théorie cohérente?

[Médiat]

Mais si deux axiomes ne sont pas "libres", n'est il pas forcément possible de créer des systèmes incohérents? (où par exemple, si chacun des axiomes est vrai, alors il implique que l'autre soit faux en partie?), dès lors on aurait prouvé un énoncé indémontrable, ce qui n'est pas possible dans une théorie cohérente, donc la théorie n'est pas cohérente.

Dire qu'un système de 2 axiomes n'est pas "libre" cela veut dire que l'un implique l'autre, ou le contraire de l'autre, donc si a => non b, il est clair que {a, b} est inconsistant, par contre si a => b, on ne peut rien conclure.

C'est surprenant de ne pas pouvoir prouver qu'une théorie est cohérente mais de pouvoir prouver qu'elle est incohérente.

Peut-être pour vous, mais pas pour tout le monde

Si il existe TOUJOURS des propositions indécidables dans une théorie arithmétique etc etc..., ET qu'il suffit de rajouter des axiomes, ou des hypothèses pour inclure la proposition indécidable dans une théorie cohérente, (qui donc possèdera de nouveaux énoncés indécidables), toutes les théories sont extensibles à l'infini, et il existe donc des théories cohérentes avec une infinité d'axiomes. (voire une infinité de théories cohérentes avec une infinité d'axiomes).

AP, ZF etc. ne sont pas finiment axiomatisable, et il existe des théories beaucoup plus simple comme la théorie des groupes sans torsion

A-t-on une possibilité de quantifier le nombre de propositions indécidables par rapport au nombre d'axiomes libres (et minimaux), ou existe-t-il une infinité de propositions indécidables dans chaque théorie cohérente?

Il existe des théories consistantes (finiment axiomatisable ou non) sans aucune formule indécidable.

[kalish]

Peut-être pour vous, mais pas pour tout le monde

Et ça ne m'étonne pas, être étonné n'est ni synonyme de ne rien comprendre, ni synonyme de tout comprendre, ni synonyme de ne comprendre qu'une partie, en fait ça n'est synonyme que de ne pas être étonné (ou équivalent, on dirait qu'on retombe dans la tautologie).

Il existe probablement plus de gens que ça n'étonne pas que de gens qui comprennent...donc.

Savoir qui appartient à quel ensemble n'est pas le sujet de la discussion, c'est bien trop souvent le cas dans les discussions humaines, alors qu'un forum est un lieu d'échanges.

Il existe des théories consistantes (finiment axiomatisable ou non) sans aucune formule indécidable.

S'agit-il de théorie complexes? S'agit-il de théories utilisant l'arithmétique, car énoncée telle quelle votre phrase laisse penser le contraire de ce que dit le théorème de godel (et je ne peux que citer wikipedia):

Le premier théorème établit qu'une théorie suffisante pour y démontrer les théorèmes de base de l'arithmétique est nécessairement incomplète, au sens où il existe des énoncés qui n'y sont ni démontrables, ni réfutables (un énoncé est démontrable si on peut le déduire des axiomes de la théorie, il est réfutable si on peut déduire sa négation). On parle alors d'énoncés indécidables dans la théorie.

Est-ce que le problème est que la question est imprécise ou bien ce que dit wikipédia est faux? Si oui, en quoi?

[Médiat]

La première fois que je vous ai répondu que vous citiez mal le théorème de Gödel, vous m'avez répondu, avec amabilité et gentillesse :

Ce qui est inexact, c'est votre compréhension de ce que j'écris et votre a priori qui à l'évidence vous rend cassant

Donc cette fois-ci, ne voulant pas réitérer cette faute immonde, vous vous débrouillerez sans moi ; mais je ne suis pas mécontent de constater, une fois de plus, que le mauvais usage de ce théorème amène à écrire les pires bêtises concernant les mathématiques !

[kalish]

On peut essayer d'être organisé.

1) qu'est-ce que ça apporte comme réponse à part être cassant? Quel est l'intérêt de répondre que vous n'allez pas répondre?

2) Je ne fais que citer, il faut bien imaginer que si vous êtes expert en la matière, c'est que d'autres ne le sont pas. En l'absence d'explications, je ne lis que des insultes, et le fait est que vos propos contredisent wikipedia, SAUF si tout ce que vous vouliez faire était d'apporter une précision permettant de dire que mon propos était forcément absurde, auquel cas vous pouvez simplement dire que dans certains cas, certaines théories sont complètes, ce que ne renie pas wikipedia.

Reste donc à savoir ce qui est vrai de ce qui est faux dans wikipedia, sans vous visiblement, ni ce qui est mal compris exactement, puisque vous ne souhaitez pas donner d'explications (et je ne crois pas mentir en disant ça).

Le théorème m'intéresse car il semble dire qu'il existe toujours une part d'arbitraire à la base d'une théorie, (ce qui parait malheureusement évident, mais difficile de savoir ce qui est vraiment évident), mais que cet arbitraire n'est pas suffisant pour éliminer tout mystère. J'avoue que c'est une motivation purement philosophique qui anime ma question.

3) La concision des réponses d'un expert et les sous entendus peuvent facilement permettre à l'expert de se hisser sur le crane des autres. La moquerie et le ridicule ne me touchent pas, je suis immaculé de gloire pour l'éternité.

Si vous connaissez une bonne utilisation du théorème, n'hésitez pas à le montrer, je ne comprends pas l'intérêt de garder ses connaissances pour soi, à part s'en sentir propriétaire et par conséquent, peut-être, imaginer qu'on "aurait pu les inventer". Ces connaissances ont été produites par d'autres en grandes parties, je ne vois pas bien ce que vous gardez de si précieux.

[kalish]

.

4)C'est assez drôle de lire un mathématicien se délecter du "mauvais usage d'un théorème" de se satisfaire que quelqu'un dise des bêtises en mathématiques, j'ai du mal à comprendre qu'on puisse écrire ça sans en avoir honte, et que ça vous procure une quelconque jouissance, enfin bon, chacun son truc.

[Médiat]

4)C'est assez drôle de lire un mathématicien se délecter du "mauvais usage d'un théorème" de se satisfaire que quelqu'un dise des bêtises en mathématiques, j'ai du mal à comprendre qu'on puisse écrire ça sans en avoir honte, et que ça vous procure une quelconque jouissance, enfin bon, chacun son truc.

Décidément, vous accumulez, après les insultes, la citation tronquée afin d'en changer le sens : je ne me délecte pas du mauvais usage d'un théorème, mais de constater que ce mauvais usage a des conséquences non négligeables sur les bêtises qu'on en déduit, d'où ma lutte permanente ne serait-ce que sur FSG, pour le bon usage des théorèmes d'incomplétude de Gödel.

[gg0]

Kalish,

pour comprendre, il faut une part d'humilité (ne pas croire que ce qui est compliqué pour les autres sera facile pour soi-même) et une part d'effort (le travail de compréhension est difficile, on ne peut pas se contenter de poser des questions). Et quand on a la chance d'avoir des réponses de professionnels, on évite de faire le kakou.
Pour l'instant, dans ce fil, je ne t'ai pas vu respecter ces règles élémentaires. Donc tu cherches autre chose que la compréhension.

Désolé !

[PlaneteF]

Bonjour,

désolé mais je n'ai pas accès à ces bouquins, et je n'ai pas les moyens de les acheter.

Tu peux trouver sur le sujet beaucoup de cours sur le net, ... et bien évidemment encore plus si tu es à l'aise en Anglais.

En Français par exemple ces cours et articles souvent cités sur FS : http://www.math.unicaen.fr/~dehornoy/surveys.html

En plus, remarque annexe, il me semble qu'on en apprend énormément en posant des questions.

Le sujet est suffisament pointu pour que cette démarche ne soit pas suffisante.


Codialement