Degré d'infinité ...

[invite0f31cf4c]

Bonsoir !
Je lisais mon cour sur les intégrales sur un intervalle non compact, et je me suis posé une question.
Est-ce qu'il existe une théorie qui expliquerais différents degrés d'infinité ... Je m'explique. Si on prend le cardinal de l'ensemble des nombres entiers, il est égal à l'infini et si on prend le cardinal des nombres rééls (Je sais pas vraiment si on le droit de dire ça ...), il est aussi égal à l'infini.
Pourtant, il y a ... "Plus" d'élements dans l'ensemble des rééls que dans les entiers ... Si on prend un segment quelconque dans les rééls, on va trouver une infinité d'élement alors que dans les entiers, bah il y a une quantité finie.
De même, exp(x) tend vers l'infini quand x tend vers l'infini, tout comme ln(x). Pourtant, exp(x)/ln(x) tend vers l'infini, donc l'expontentiel l'emporte, donc il tend vers un infini d'ordre superieur ...
Donc je suppose que l'on peut définir un ordre ou un degré d'infinité ... Mais est-ce qu'il existe quelque chose de tel là dessus, ou je vais être obliger de l'inventer ?
Merci de vos réponses !
++ !
L.S.
-----

[Quinto]

Oui bien sur qu'il existe plusieurs infinis.
La théorie des ensembles de Cantor met un peu ca en lumière.
D'une manière générale on dit que card(A)>=card(B) s'il existe une surjection de A dans B.

[invite6b1e2c2e]

De plus, on peut d&#233;finir la relation (entre ensemble)A < B ssi il existe une injection de A dans B, le th&#233;or&#232;me de Cantor Bernstein te dit que si A<B et si B< A, alors il existe une bijection de A sur B.
C'est un excellent exercice de le d&#233;montrer, quand on est, disons, en sup.
Du coup, tu as les infinis d&#233;nombrables, qui sont les plus petits infinis, ie ceux en bijection avec N, puis tu as les autres, dont on pense (conjecture ? Sans doute un logicien peut d&#233;tailler &#231;a mieux que moi) qu'ils sont de cardinal au moins R.

__
rvz

[martini_bird]

Salut,

puis tu as les autres, dont on pense (conjecture ? Sans doute un logicien peut détailler ça mieux que moi) qu'ils sont de cardinal au moins R.

Ca s'appelle l'hypothèse du continu et c'est indécidable (Cohen, 1963).

Cordialement.

[A voir en vidéo sur Futura]

[invite6b1e2c2e]

Ah oui, je me disais bien que c'&#233;tait un truc comme &#231;a.
En tout cas, merci pour cette pr&#233;cision.

__
rvz

[GuYem]

Salut,

Ca s'appelle l'hypothèse du continu et c'est indécidable (Cohen, 1963).

Cordialement.

J'ai jamais vu des trucs indécidables. Enfin si à l'instant, mais en fait je ne sais pas ce que ça veut dire, et je n'ai aucune idée de comment ça se démontre.

Tu peux développer un peu Martini ?

[matthias]

J'ai jamais vu des trucs indécidables.

Tu es sûr ?
L'axiome des parallèles, l'axiome du choix ...
Si en ajoutant un axiome ou son contraire à un système d'axiomes tu obtiens dans les deux cas un nouveau système consitant, c'est bien que c'était un indécidable de l'ancien système non ?

[Quinto]

Moi je reprendrai bien la remarque de Guyem:
Je ne sais pas ce que c'est et j'aimerai savoir comment ca se d&#233;montre.
Apr&#232;s je comprendrai la r&#233;ponse de Matthias

[GuYem]

Moi je reprendrai bien la remarque de Guyem:
Je ne sais pas ce que c'est et j'aimerai savoir comment ca se démontre.
Après je comprendrai la réponse de Matthias

Idem !

En fait je ne sais pas ce que c'est un système d'axiomes consistant.

[matthias]

En fait je ne sais pas ce que c'est un système d'axiomes consistant.

J'aurais du dire "cohérent" ou "non contradictoire", consistant étant le mot anglais. C'est donc un système d'axiomes à partir duquel il est impossible de démontrer une proposition et son contraire.

[GuYem]

Ok.

Donc si j'ai bien compris, on prend un système d'axiome. Si on veut montrer qu'un truc est un indécidable de ce système on procède de la manière suivante :
-On le rajoute en tant qu'axiome et on regarde si le nouveau système d'axiomes est consistant.
-On rajoute son contraire en tant qu'axiome et on regarde à nouveau si le système d'axiome est consistant.

Si les deux systèmes sont consistants alors le truc était indécidable. Ce ne parait pas complètement bète comme façon de voir les choses !

Mais alors, comment faire pour voir si un système d'axiome est consistant ?

[matthias]

Mais alors, comment faire pour voir si un système d'axiome est consistant ?

Je ne sais pas comment on fait pour des axiomes genre axiome du choix ou hypothèse du continu, mais pour l'axiome des parallèles, on peut montrer qu'il n'y a pas de contradiction en calquant un modèle sur le système axiomatique (genre remplacer droite par un grand cercle sur une sphère, etc). Tu déduis alors la cohérence du système de la cohérence d'un autre. Mais bon je doute que toutes les démonstrations soient aussi simples

[matthias]

J'ai trouvé ce doc qui explique un peu la méthode sans entrer dans les détails :
http://www.math.unicaen.fr/~dehornoy/Surveys/Dgy.pdf
Je ne sais pas trop ce que ça vaut.

[spi100]

Ok.

Donc si j'ai bien compris, on prend un système d'axiome. Si on veut montrer qu'un truc est un indécidable de ce système on procède de la manière suivante :
-On le rajoute en tant qu'axiome et on regarde si le nouveau système d'axiomes est consistant.
-On rajoute son contraire en tant qu'axiome et on regarde à nouveau si le système d'axiome est consistant.

Pas tout à fait.

Dans un système axiomatique consistant M, une proposition P est indécidable si les axiomes de M permettent de prouver que P et Non P sont vraies.
Dans ce cas tu peux alors construire un nouveau système M' consistant, en rajoutant P aux axiomes de M.

[matthias]

Dans un système axiomatique consistant M, une proposition P est indécidable si les axiomes de M permettent de prouver que P et Non P sont vraies.

Non dans ce cas tu as prouvé que ton système d'axiomes n'était pas consistant.

[spi100]

Non dans ce cas tu as prouvé que ton système d'axiomes n'était pas consistant.

Je ne crois pas, inconsistant ça serait plutot que deux axiomes se contredisent.

Dans le cas que je décris aucun des axiomes de M n'est en contradiction avec P.

[matthias]

Dans le cas que tu décris, les axiomes permettent de prouver P et non P, donc ils se contredisent.

[spi100]

Oui, je vois ce que tu veux dire. Si j'ajoute P à la liste des axiomes de M, c'est que je décide de tenir P pour vrai. Mais si les autres axiomes de M permettent de montrer non P, alors il y a contradiction.
Je regarde dans le littérature que j'ai sous le coude et je reviens ...

[matthias]

Si j'ajoute P à la liste des axiomes de M, c'est que je décide de tenir P pour vrai. Mais si les autres axiomes de M permettent de montrer non P, alors il y a contradiction.

En fait dans ton cas on se moque même de rajouter P puisqu'on peut le prouver à partir des axiomes (donc déjà P est un théorème et donc pas un indécidable et n'a pas besoin d'être ajouté aux axiomes). Si en plus non P est aussi un théorème, cela prouve la non consistance du système M.
C'est même comme cela que l'on définit la consistance: il n'existe aucune proposition P telle que P et non P soient tous les deux des théorèmes.

[spi100]

Tu peux aussi voir les choses un peu autrement. Si les axiomes de M permettent de montrer à la fois P et non P, alors P est complètement indépendant des axiomes de M car ils ne permettent pas de décider de la vérité de P.

Ca ne me semble pas en contradiction avec ce qui est dit dans la wikipedia

http://fr.wikipedia.org/wiki/Ind%C3%A9cidable

Une proposition indécidable, ou sa négation, peut être ajoutée à un système cohérent pour former un autre système cohérent. C'est ainsi que l'on ajoute souvent l'axiome du choix aux axiomes de Zermelo-Fraenkel (ZF) pour former le système ZFC.

Maintenant surement que la manière que je propose pour démontrer l'indécidabilité est trop naïve. De ce que j'ai compris du théorème d'incomplétude de Goedel, pour tout système d'axiomes M compatible avec l'arithmétique, on peut fabriquer un théorème P de M, énoncant: "P n'est pas un théorème de M". Dans ce cas, effectivement P est indécidable car si P est vrai alors il est faux, et s'il est faux alors il est vrai.

Je pensais que c'était équivalent à montrer que P et non P sont tous deux des théorèmes de M. Ca doit être là que je me trompe ?

[erik]

Si les axiomes de M permettent de montrer à la fois P et non P, alors P est complètement indépendant des axiomes de M car ils ne permettent pas de décider de la vérité de P.

Non si tu peux montrer P et non P à partir des axiomes M, c'est que tes axiomes sont inconsistant. Et ça c'est très génant : cela signifie que pour n'importe quelle proposition Q, si tu montre que Q est vrai alors non Q est vrai également.
Bref cela veux dire qu'a partir de M on déduit absolument n'importe quoi.

[spi100]

Oui, en lisant ça

http://www.eleves.ens.fr/home/ollivi...el/goedel.html

je comprends mon erreur.

En fait P est indécidable dans M, si ni P ni non P ne sont des théorèmes de M, et c'est bien le cas si l'on montre que P => non P. Effectivement ce n'est pas du tout la même chose que de dire que P et non P sont des théorèmes de M.

[matthias]

Tu peux aussi voir les choses un peu autrement. Si les axiomes de M permettent de montrer à la fois P et non P, alors P est complètement indépendant des axiomes de M car ils ne permettent pas de décider de la vérité de P.

Comment veux-tu qu'il y ait une quelconque indépendance si tu peux PROUVER P à partir des axiomes ?
Et toi ça ne te gène pas de pouvoir démontrer à la fois une chose et son contraire ? A partir de là on pourrait démontrer n'importe quoi ensuite ...
Pour qu'une proposition soit indécidable il faut que ni elle ni son contraire ne soit démontrable.

De ce que j'ai compris du théorème d'incomplétude de Goedel, pour tout système d'axiomes M compatible avec l'arithmétique, on peut fabriquer un théorème P de M, énoncant: "P n'est pas un théorème de M".

Non. On peut énoncer une proposition P de ce type, pas un théorème. Un théorème c'est une proposition qui peut être démontrée à partir des axiomes. Or là c'est justement indémontrable.

Dans ce cas, effectivement P est indécidable car si P est vrai alors il est faux, et s'il est faux alors il est vrai.

Non plus. Si tu savais énoncer une proposition qui donne ce résultat, tu démontrerais encore la non consistance du système d'axiomes.
Il ne faut pas confondre VRAI/FAUX avec démontrable/indémontrable.

[EDIT: grillé]

[spi100]

[EDIT: grillé]

Je te trouve bien agressif vis à vis de quelqu'un qui reconnait aisement ses erreurs [EDIT:lit mon poste un peu plus haut]. C'est un forum pas un ring de boxe.

[matthias]

Cela signifie juste que le temps que je poste mon message, quelqu'un avait déjà répondu (dont toi) ...
Aucune agressivité de ma part.