Infinis et dénombrement

[Liet Kynes]

bonjour , une petite réflexion sur ce qui s'est dit en maths:

Voir : Tous les ensembles infinis sont dénombrables (futura-sciences.com), en particulier le cas 4 et plus spécifiquement Intuition et intuitionisme - Jean Largeault - Google Livres

des idées sont développées et ouvre sur une réflexion mais je pense que je ne comprends pas les mots dénombrables et indénombrables.

-> Si un nombre représente toujours une valeur numérique que l'on peut comparer à un autre alors il est soit inférieur soit supérieur soit égal à l'objet de la comparaison.

Expérience de pensée: une partie de carte se déroule selon les règles de la bataille à cela de près que l'on ne prends pas la carte de l'adversaire,à chaque donne après comparaison les joueurs notent sur le dos de la carte le numéro de la donne et chacun repose sa carte sur un tas, un joueur a pour cartes les nombres de l'ensemble N l'autre ceux de l'ensemble R.

N est dénombrable et pas R d'après ce que j'ai compris/lu (surement mal) mais les deux tas formés lors de la partie sont rigoureusement les nombres de l'ensemble N.

Donc je me demande cela veut dire quoi dénombrable et indénombrable ?
-----

[gg0]

Les tas formés sont de même taille, mais à la fin (infinie) de la partie l'un a épuisé ses cartes, pas l'autre. Rien de plus.

[ThM55]

Bonjour. Un ensemble infini est dit dénombrable s'il est en bijection avec . Il est non dénombrable sinon. Par exemple, l'ensemble des parties de est non dénombrable. La démonstration de Cantor est très simple et bien connue, c'est pourquoi je ne la reproduirai pas ici, sauf si tu le demandes.

[Liet Kynes]

J'ai bien l'idée que dans un R entre deux nombres, je ne peux pas calculer combien il y a de nombres, je connais la diagonale de cantor mais c'est mon idée d'attribuer un nombre à chaque carte qui doit être mauvaise, quand je fais cela je ne fait qu'énumérer les entiers.

Au final c'est la bijection que je ne dois pas encore comprendre et les applications.

[A voir en vidéo sur Futura]

[Liet Kynes]

L'opération que fait chaque joueur à chaque tour c'est de prendre la valeur du nombre de la carte, la divisée par elle-même, ajouter la valeur obtenue (donc 1) à la valeur écrite sur le dos de la carte du tour d'avant et la noter sur le dos de la carte en cours : ce n'est pas une application telle qu'on peux l'entendre dans le sens de la définition formelle d'une application ?

[Deedee81]

Salut,

J'ai bien l'idée que dans un R entre deux nombres, je ne peux pas calculer combien il y a de nombres, je connais la diagonale de cantor mais c'est mon idée d'attribuer un nombre à chaque carte qui doit être mauvaise, quand je fais cela je ne fait qu'énumérer les entiers.

C'est clair qu'il y a un soucis. Les nombres qu'on peut écrire (on peut aussi les noter comme "pi", ou sous forme de formules) sont finis en écriture et donc forcément dénombrable : on en rate (ça porte un nom, mais qui m'échappe, "nombres descriptibles" ???)

Mais on n'est pas obligé de noter. Et la bonne explication est celle de gg0.

Et oui, ce que tu fais est une application mais évidemment pas une bijection.

La bijection ou plutôt son absence, ce n'est pas difficile à comprendre sur le principe (une bijection c'est quand même un truc élémentaire). Et si c'est "pourquoi y en a pas" il est sans doute mieux d'éplucher la (courte) démonstration formelle (sans "diagonale" au sens habituel avec les développements décimaux) :
https://fr.wikipedia.org/wiki/Th%C3%...3%A9n%C3%A9ral

Elle est très parlante et assez facile.

Concernant les raisonnements du type jeu de carte ou autres approches "imagées", attention, ça peut être assez piégeux. Dans le même genre (là aussi il y a un argument diagonal) : le théorème de l'arrêt de Turing. J'avais imaginé une machine très astucieuse capable de résoudre le problème de l'arrêt....... et il m'a fallu un moment avant de voir la faille !!!!!

[Deedee81]

C'est clair qu'il y a un soucis. Les nombres qu'on peut écrire (on peut aussi les noter comme "pi", ou sous forme de formules) sont finis en écriture et donc forcément dénombrable : on en rate (ça porte un nom, mais qui m'échappe, "nombres descriptibles" ???)

Bon, me souviens pas du nom.

Il est à noter que l'ensemble dénombrable ainsi construit dépend des règles de construction des formules.
Mais on montre facilement que la réunion de tous ces ensembles est lui-même dénombrable (à condition que lorsqu'on utilise une dénomination d'un nombre donné comme pi on puisse le calculer ou bien que l'alphabet complet soit fini).

Et on peut définir (sans pouvoir les calculer) des nombres réels non calculables. Chaitin (améliorés même par d'autres) l'a fait avec le "nombre oméga".

Qu'il y ait des nombres réels impossibles de déterminer (calculer), c'est assez contre-intuitif (surtout si on ne les construit pas avec du hasard, un tirage à pile ou face des décimales par exemple), faut bien l'avouer.

Et c'est lié à la possibilité de définir des fonctions non calculables (ça aussi c'est peu intuitif, il y a eut un article de Delahaye là-dessus)

[pm42]

Qu'il y ait des nombres réels impossibles de déterminer (calculer), c'est assez contre-intuitif (surtout si on ne les construit pas avec du hasard, un tirage à pile ou face des décimales par exemple), faut bien l'avouer.

Et c'est lié à la possibilité de définir des fonctions non calculables (ça aussi c'est peu intuitif, il y a eut un article de Delahaye là-dessus)

Et sur les nombres non-calculables, il y a pire : les Omega de Solovay dont on ne peut connaitre aucun chiffre :
https://www.pourlascience.fr/sd/math...omega-4725.php
https://publimath.univ-irem.fr/glossaire/OM005.htm

Et dans le même genre, cela s'applique aussi aux démonstrations : https://www.pourlascience.fr/sd/math...dable-5938.php

[Liet Kynes]

Qu'il y ait des nombres réels impossibles de déterminer (calculer), c'est assez contre-intuitif (surtout si on ne les construit pas avec du hasard, un tirage à pile ou face des décimales par exemple), faut bien l'avouer.

Et c'est lié à la possibilité de définir des fonctions non calculables (ça aussi c'est peu intuitif, il y a eut un article de Delahaye là-dessus)

Du coup l'un des jeux de cartes ne peut pas être R, faut que je me replonge la dedans..

[Deedee81]

Et sur les nombres non-calculables, il y a pire : les Omega de Solovay dont on ne peut connaitre aucun chiffre :

Merci, c'est bien ces améiiorations que j'évoquais (mais je ne me souvenais pas du nom).

Chaitin a aussi montré qu'il existait des équations diophantiennes pour lesquelles il est impossible d'écrire un algorithme donnant toutes les solutions (enfin, les dénombrer aussi loin qu'on veut, ça peut être infini évidemment)

[Deedee81]

Du coup l'un des jeux de cartes ne peut pas être R, faut que je me replonge la dedans..

En "expérience de pensée" on peut imaginer un peu ce qu'on veut, et même un paquet de cartes de cardinal aleph 5 (évidemment, ce n'est pas un paquet qu'on peut vider entièrement en retirant les cartes une à une )

[Liet Kynes]

Dans l'idée il y a des nombres "approchables" et des nombres que l'on sais exister mais pour lesquels il n'est pas possible de déterminer entre quels entiers ils sont compris ?
J'ai téléchargé les articles de PLS, pas encore lu..

[Deedee81]

des nombres que l'on sais exister mais pour lesquels il n'est pas possible de déterminer entre quels entiers ils sont compris ?

Ca j'en suis certain. Prend le nombre Omega de Solovay. Aucune de ses décimales ne sont calculables. Prend le même nombre multiplié par disons cent.
Il reste totalement non calculable. Et il est compris entre 0 et 100 mais entre quels entiers exactement ? Mystère.

Voir plus haut ou https://www.cs.auckland.ac.nz/~cristian/delahaye.pdf

Peut on en faire un dont on ne pourrait dire entre quels entiers il se trouve de 0 à l'infini, je ne sais pas. Et là je me méfie de mon intuition, tu t'en doutes bien

[pm42]

ne pourrait dire entre quels entiers il se trouve de 0 à l'infini, je ne sais pas. Et là je me méfie de mon intuition, tu t'en doutes bien

1 / ( Omega de Solovay + 0,1)

Le 0,1 est là au cas ou le dit Omega sera nul mais à mon avis pas nécessaire.

[Deedee81]

Pm42, très bien vu ça

Ah bien y regarder, l'ensemble R est sacrément bizarre
Il y a longtemps un truc m'avait interpellé : comment se fait-il que l'existence de sous-ensembles de R ne pouvant être mis en bijection ni avec N ni R soit un indécidable de ZF alors que la définition de R est claire et rigoureuse.
C'est Médiat qui m'avait expliqué à l'époque (et en substance ça revient à ce qu'on discute ici, ce n'est pas parce que R est rigoureusement défini qu'on peut tout savoir sur tous ses éléments)

[gg0]

Bonjour Deedee81 : "ce n'est pas parce que R est rigoureusement défini qu'on peut tout savoir sur tous ses éléments"
Oui, c'est la classique illusion du matheux qui croit tout savoir parce qu'il a une définition rigoureuse. On la retrouve ailleurs :
* en statistiques : La "population française" peut être parfaitement définie pour un recensement, on rate toujours des gens (sans compter que certains apparaîtront deux fois)
* en géographie : le continent antarctique est parfaitement défini, mais très mal connu. Idem pour la zone des abysses (en dessous de -3000).
On peut facilement trouver d'autres exemples.

Cordialement.

[pm42]

On peut facilement trouver d'autres exemples.

Mes favorites données il y a longtemps par un prof de spé :
- les fonctions de R sont un espace vectoriel, trouvez en une base
- si je vous donne une partie de N et que je vous demande une méthode pour en extraire 1 élément, vous pouvez prendre le plus petit. Si c'est Z ou Q, idem en les indexant par N. Faites la même chose pour R : trouvez une méthode qui permet d'extraire 1 élément de toute partie donc je vous donne une définition.

[Deedee81]

On peut facilement trouver d'autres exemples.

Oh oui, j'avais même un exemple en proba (que j'avais inventé) qui m'a sacrément laissé perplexe à l'époque. Mais bon, je vais pas revenir sur cet exemple, là on s'éloigne trop du sujet.

: trouvez une méthode qui permet d'extraire 1 élément de toute partie donc je vous donne une définition.

Un grand classique. "Yaka" avoir un ensemble bien ordonné (et chose amusant ça revient à l'axiome du choix)

[pm42]

et chose amusant ça revient à l'axiome du choix

Exactement et ça permet de comprendre pourquoi il n'est pas évident. D'un coté, si tu me décris une partie de R, je vais pouvoir t'en donner un élément. Mais je ne peux pas te donner une méthode générale.
Je trouve cela perturbant et beau à la fois.

[Deedee81]

Je trouve cela perturbant et beau à la fois.

Je dirais même que c'est le coté contre-intuitif (perturbant) que rend ces résultats assez fabuleux (beau). Ce n'est que mon avis.

[Liet Kynes]

Mes favorites données il y a longtemps par un prof de spé :
- les fonctions de R sont un espace vectoriel, trouvez en une base
- si je vous donne une partie de N et que je vous demande une méthode pour en extraire 1 élément, vous pouvez prendre le plus petit. Si c'est Z ou Q, idem en les indexant par N. Faites la même chose pour R : trouvez une méthode qui permet d'extraire 1 élément de toute partie donc je vous donne une définition.

Du coup on est capable de donner une telle définition ?

[Médiat]

Un exemple que je trouve éclaircissant :

Soit la relation sur définie par :
C'est trivialement une relation d'équivalence et tout aussi trivialement, on peut trouver un représentant pour chaque classe d'équivalence :

Si dans la définition de on fait une légère modification : , cela devient impossible (essayez)

[ThM55]

Qu'est ce que cela veut dire? Tout réel x est bien évidemment un représentant de sa classe d'équivalence définie par . Non? Qu'est ce que je n'ai pas compris?

[Médiat]

Le problème est de trouver UN représentant (unique). Dans l'exemple que j'ai donné, si , le représentant trouvé pour est le même que celui trouvé pour .

Dans votre exemple , comment choisir un représentant pour chacune de ces classes ?

[Liet Kynes]

J'ai soumis à BING:
"
si nous modifions la définition de pour que , alors chaque classe d’équivalence contient une infinité non dénombrable de nombres réels, et il n’est pas possible de choisir un représentant unique pour chaque classe d’équivalence"

[Deedee81]

J'ai soumis à BING:

T'as pas pensé à lui demander "pourquoi" ? Moi c'est ce que j'aimerais bien savoir (car j'ai un peu de mal)
Parce que là il ne fait que répéter ce qu'a dit Médiat

[Médiat]

Soit R la relation sur définie par , chaque classe d’équivalence contient une infinité non dénombrable de nombres réels et les représentants peuvent parfaitement être choisis, 1 et -1 par exemple.

La justification de BING est donc fausse.

[pm42]

La justification de BING est donc fausse

Ce qui était attendu : il n'y a aucun intérêt à poser ce genre de question à des outils comme Bing de nos jours.

[Deedee81]

Ce qui était attendu : il n'y a aucun intérêt à poser ce genre de question à des outils comme Bing de nos jours.

J'avais failli rappeler qu'en science ces outils, dès qu'il s'agit de faire des raisonnements, sont souvent fautifs. Ils vont une analyse statistique des textes existant et ont peu de chance de "tomber juste" dès que la demande est un peu pointue. S'il s'agit de donner des définitions, des références, etc.... là par contre ils marchent assez bien.

[Médiat]

J'ai été trop gentil avec BING : chaque classe contient un nombre dénombrable d'éléments ! Donc tout est faux dans sa réponse.