Une utilisation surprenante de l'axiome du choix !

[Médiat]

Bonjour,

Le cadre est ZFC, ce qui est normal pour parler de l’axiome du choix.

Supposons que nous disposions de 100 fonctions et d’une fonction de choix sur une certaine famille d’ensembles (j’aurais l’occasion d’en dire plus, si des questions se font jour), cette fonction de choix est totalement indépendante des fonctions .

Supposons que nous connaissions parfaitement 99 des 100 fonctions ainsi que la fonction de choix (le résultat suivant s'appuyant sur cette fonction de choix, il n'est donc pas vraiment constructif) et que nous ayons l’occasion de connaître la 100^ième fonction (qui peut être n’importe laquelle choisie parmi les 100 ) pour toutes les valeurs de sauf un nombre fini (à notre convenance), alors il est possible, en choisissant bien les entiers dont nous ne connaissons pas les images, de prévoir l’image d’un nombre arbitraire (fixé à l’avance) d’entre eux, par cette 100^ième fonction, avec une probabilité de réussite au moins de 99%.

Je précise que « probabilité de réussite au moins de 99% » ne veut pas dire que si on prévoit 100 images, au moins 99 seront justes, mais que si on applique la même stratégie à chacune des 100 fonctions, dans au moins 99 cas on aura fait une prédiction parfaite.

Étonnant, non ?
-----

[Médiat]

Afin d'établir le côté surprenant de ce résultat : certains ont cru y voir une raison valable de rejeter définitivement l'axiome du choix !

[invite4ef352d8]

Bonjour !

Que signifie "totalement indépendante " ?

[Médiat]

Bonjour !

Que signifie "totalement indépendante " ?

Bonjour,
Que la fonction de choix n'est pas choisie en fonction des U_i.
Que l'on peut refaire "l'expérience" avec d'autres U_i tout en gardant la même fonction de choix.

Je sens que vous connaissez ce résultat .

[A voir en vidéo sur Futura]

[invite4ef352d8]

non je ne connais pas ce résultat et j'avoue que je suis assez intrigué (et que j'ai un peu de mal à comprendre son sens précis aussi ^^)

sur qu'elle famille d'ensemble prend ton cette fonction de choix ?

[invitec317278e]

Salut Médiat,

Pourrais tu développer ?
Je ne vois pas où intervient la fonction de choix, dans cette histoire (d'ailleurs, je ne sais même pas ce qu'on entend par fonction de choix, mais ça, je peux sans doute le trouver tout seul)

[Médiat]

non je ne connais pas ce résultat

Je disais cela car la fonction de choix a quand même un rapport avec les suites (mais pas particulièrement les U_i), cf. infra.

je ne sais même pas ce qu'on entend par fonction de choix

Une fonction de choix, est une fonction capable de "choisir" un élément dans chacun des ensembles d'une famille infinie d'ensembles non vides.

sur qu'elle famille d'ensemble prend ton cette fonction de choix

Sur l'ensemble des classes d'équivalence pour une relation bien choisie entre suites à valeurs réelles (comme les Ui).

Je ne vois pas où intervient la fonction de choix

C'est elle qui permet de choisir les images que l'on peut deviner.

J'en dirai plus au fur et à mesure des questions.

[invite6754323456711]

Bonjour,

La réponse me semble être dans l'énoncé L'une quelconque des 99 (voir même 100) fonctions faits l'affaire.

Je précise que « probabilité de réussite au moins de 99% » ne veut pas dire que si on prévoit 100 images, au moins 99 seront justes, mais que si on applique la même stratégie à chacune des 100 fonctions, dans au moins 99 cas on aura fait une prédiction parfaite.

Patrick

[invite4ef352d8]

et le nombres de valeur qu'on va essayer de deviner est fixé à l'avance ? (avant de construire la fonction de choix ?)

[Médiat]

et le nombres de valeur qu'on va essayer de deviner est fixé à l'avance ? (avant de construire la fonction de choix ?)

Oui, et la fonction de choix est indépendante du reste du problème donc en particulier de ce nombre.

[Médiat]

Bonjour,

La réponse me semble être dans l'énoncé L'une quelconque des 99 (voir même 100) fonctions faits l'affaire.

La réponse est forcément dans l'énoncé, sinon ce ne serait pas des mathématiques .
Par contre je ne vois pas ce que vous voulez dire par la partie en gras, la question est de déterminé l'image par l'une des fonctions d'un nombre fini fixé à l'avance d'entiers, indépendament de cette valeur bien sur (sans l'utiliser) !

[invitec317278e]

Je suis en train de me demander quelle relation d'équivalence on pourrait choisir, déjà.
Je me dis que si c'est pas trop compliqué, c'est sans doute un truc du genre :
équivaut à lorsque , ou alors lorsque ces ensembles ne diffèrent que d'un nombre fini d'éléments...Mais je ne vois pas ce qu'on pourrait tirer de ça...
alors je me dis que c'est sans doute une relation d'ordre compliquée ou tombée du ciel, que j'ai aucune chance de trouver

[Médiat]

équivaut à lorsque , ou alors lorsque ces ensembles ne diffèrent que d'un nombre fini d'éléments...

Je ne suis pas sur de comprendre vos notations, voulez-vous dire que la différence symétrique des images est finie ? Si oui, ce n'est pas cela, mais vous êtes dans la bonne direction ... (en fait c'est plus simple et plus naturel)

[invite6754323456711]

Par contre je ne vois pas ce que vous voulez dire par la partie en gras, la question est de déterminé l'image par l'une des fonctions d'un nombre fini fixé à l'avance d'entiers, indépendament de cette valeur bien sur (sans l'utiliser) !

J'étais partie trop rapidement sur l'hypothèse ou les images des 100 fonctions étaient, en plus d'être dénombrable, identiques tel que l'ensemble des réels calculables.

Donc la solution est pour moi

Patrick

[invitec317278e]

Oui, ce que j'avais en tête était la finitude de la différence symétrique.
Hélas, les possibilités sont nombreuses, yen a des tas, des relations d'équivalence Et vu que je ne vois pas comment tout se goupillera après avoir choisi la relation d'équivalence, j'ai du mal à procéder autrement que "considérer une à une toutes les relations possibles et voir si par miracle, yen aurait pas une qui ferait que le problème devient alors évident"
(là je teste : u_n équivaut à v_n si {n tq u_n =/= v_n } est fini)


Concernant l'axiome du choix (puisqu'on doit s'en servir) , puis-je savoir si la phrase suivante est correcte (ou du moins à peu près, ça m'aiderait déjà de savoir à quoi il faudra ensuite appliquer la fonction de choix) ? :
"lorsque l'on considère l'image d'un ensemble par la fonction de choix, on ne se sert pas réellement de l'axiome du choix. En revanche, lorsque l'on considère l'image d'une infinité d'ensembles par la fonction de choix, on se sert de l'axiome du choix."

[Médiat]

(là je teste : u_n équivaut à v_n si {n tq u_n =/= v_n } est fini)

. Elle est assez naturelle, mais faites l'expérience de pensée qui consiste à choisir un élément (une suite) dans chaque classe ...

Concernant l'axiome du choix (puisqu'on doit s'en servir) , puis-je savoir si la phrase suivante est correcte (ou du moins à peu près, ça m'aiderait déjà de savoir à quoi il faudra ensuite appliquer la fonction de choix) ? :
"lorsque l'on considère l'image d'un ensemble par la fonction de choix, on ne se sert pas réellement de l'axiome du choix. En revanche, lorsque l'on considère l'image d'une infinité d'ensembles par la fonction de choix, on se sert de l'axiome du choix."

Votre phrase est ambigüe, mais si vous voulez dire que si vous devez choisir une élément dans un ensemble, l'axiome du choix n'est pas nécessaire, vous avez raison, pour affirmer qu'une fonction existe toujours quand il y a une infinité d'ensembles, l'axiome du choix est nécessaire ; malgré tout sans axiome du choix, on peut créer une fonction de choix explicitement sans AC ; si cela vous intéresse je vous donnerai un exemple ou AC n'est pas nécessaire.

[invitec317278e]

Elle est assez naturelle, mais faites l'expérience de pensée qui consiste à choisir un élément (une suite) dans chaque classe ...

Je ne vois pas où vous voulez en venir : de toute façon, si l'AC est nécessaire pour établir une fonction de choix sur la partition induite par cette relation, je ne peux pas imaginer de méthode pour choisir un élément dans chaque case, non ? Ou alors, voulez vous dire que l'AC n'est justement pas nécessaire dans le cas de cette relation ?

[Médiat]

Je ne vois pas où vous voulez en venir : de toute façon, si l'AC est nécessaire pour établir une fonction de choix sur la partition induite par cette relation, je ne peux pas imaginer de méthode pour choisir un élément dans chaque case, non ? Ou alors, voulez vous dire que l'AC n'est justement pas nécessaire dans le cas de cette relation ?

AC est bien nécessaire, c'est justement pourquoi, si vous essayer de faire ce choix vous-même, vous allez vous préparer un mal de tête historique , mais c'est bien d'essayer, cela permet de toucher du bout des neurones, pourquoi AC est nécessaire.

[invitec317278e]

Donc, il faut que je trouve une relation d'ordre simple et naturelle, telle que AC soit nécessaire pour pouvoir choisir un élément de chaque classe ; et je dois aussi trouver un ensemble infini de de classes d'équivalence auxquelles appliquer la fonction de choix (car si on n'applique pas la fonction de choix à une infinité de classes d'équivalence, on se sert de la restriction de la fonction de choix à un ensemble fini, et donc, on n'utilise pas l'AC).
Est-ce correct ?


Dans la démonstration, est-ce que les 99 premières suites interviennent ? Est-ce que le procédé utilisé pour deviner les images de la 100ième suite dépend des 99 premières suites ?

[Médiat]

Donc, il faut que je trouve une relation d'ordre simple et naturelle, telle que AC soit nécessaire pour pouvoir choisir un élément de chaque classe ; et je dois aussi trouver un ensemble infini de de classes d'équivalence

Vous avez la relation d'équivalence, donc les classes d'équivalence, et la fonction de choix nécessaire (et fournie) est celle qui à chaque classe associe un représentant, pas besoin de relation d'ordre.

Donc cela dépend bien de l'ensemble des suites réelles, mais pas des 100 qui ont été fournies.

Dans la démonstration, est-ce que les 99 premières suites interviennent ? Est-ce que le procédé utilisé pour deviner les images de la 100ième suite dépend des 99 premières suites ?

Oui, c'est parce qu'il y a 100 suites que l'on a 99 chances sur 100 de réussite ...

[invitec317278e]

Ah, j'avais cru que la relation d'équivalence que j'ai énoncé plus haut était mauvaise
(les mots "relations d'ordre" de mon dernier message sont un lapsus, je voulais dire relation d'équivalence).

J'ai donc la fonction de choix, c'est déjà un début. Maintenant faut essayer de l'utiliser et surtout de trouver à quoi l'appliquer

[Médiat]

J'ai donc la fonction de choix, c'est déjà un début. Maintenant faut essayer de l'utiliser et surtout de trouver à quoi l'appliquer

Le plus dur est fait.

[invite6754323456711]

J'ai donc la fonction de choix, c'est déjà un début. Maintenant faut essayer de l'utiliser et surtout de trouver à quoi l'appliquer

Vous avez donné la clé pour résoudre de l'énigme pourquoi ne pas aller plus loin ?

Je me permet un spolier

 Cliquez pour afficher

Il me semble qu'Il faut juste l'utiliser pour partiionner l'ensemble des 100 fonctions. Comme une relation d'équivalence est réflexive il y aura une partition ne contenant que des éléments de la 100ieme fonction.

Cela permet de trouver le nombre fini d'élément vérifiant la propriété énoncé

Car j'aurais une question sur AC. Comment juste en postulant AC cela infère t-il qu'il l'on soit toujours possible de trouver une fonction de choix ? Autrement dit, si j'ai bien compris, que tous ensemble soit bien ordonné ?

Patrick

[invite4ef352d8]

le fait que tout ensemble admet un bon ordre est une conséquence assez facile du Lemme de Zorn, qui est un énoncé équivalent à l'axiome du choix, mais "un peu plus adapté" aux utilisations pratique.

pour montrer que Zorn => tout ensemble admet un bon ordre, considère l'ensemble (inductif), des partie de X munie d'un bon ordre la relation d'ordre etant l'inclusion et la compatibilité des relation d'ordre...

la preuve que l'axiome du choix implique le lemme de zorn est un peu delicate, apparement elle est présenté sous sa forme classique sur la page wikipédia que j'ai mis en lien.

[invite6754323456711]

/wiki/Lemme_de_Zorn"]Lemme de Zorn[/URL], qui est un énoncé équivalent à l'axiome du choix, mais "un peu plus adapté" aux utilisations pratique.

Pourrait-il remplacer l'axiome du choix ? c'est à dire Zorn => axiome du choix ?

Patrick

[invite4ef352d8]

comme je l'ai dit, et comme c'est expliqué sur Wiki ,Lemme Zorn<=> axiome du choix.

c'est aussi équivalent aux th de Zermelo qui dit que "tout ensemble admet un bon ordre".

donc remplacer l'axiome du choix par le lemme de zorn ne change absolument rien.

[Médiat]

 Cliquez pour afficher

Il me semble qu'Il faut juste l'utiliser pour partiionner l'ensemble des 100 fonctions. Comme une relation d'équivalence est réflexive il y aura une partition ne contenant que des éléments de la 100ieme fonction.

Cela permet de trouver le nombre fini d'élément vérifiant la propriété énoncé

Je ne comprends ni ce que vous voulez faire, ni en quoi cela résout le problème

Car j'aurais une question sur AC. Comment juste en postulant AC cela infère t-il qu'il l'on soit toujours possible de trouver une fonction de choix ?

Dans la mesure où AC est justement là pour dire qu'elle existe ...

Autrement dit, si j'ai bien compris, que tous ensemble soit bien ordonné ?

cf. les réponses de Ksilver.

Et j'ajoute la citation de Bona que j'ai rappelé dans un autre post :

L'axiome du choix est évidemment vrai, le principe du bon ordre est évidemment faux, et le lemme de Zorn personne n'en sait rien

[invite6754323456711]

Je ne comprends ni ce que vous voulez faire.

Je suis alors tout comme une restriction de la citation de Jerry Bona en ce qui concerne le lemme de Zorn.

Patrick

[invite6754323456711]

Dans la mesure où AC est justement là pour dire qu'elle existe ...

Que l'on affirme qu'elle existe, mais nous n'avons pas trouvé d'incohérence à cette affirmation non ?

Patrick

[Médiat]

Que l'on affirme qu'elle existe, mais nous n'avons pas trouvé d'incohérence à cette affirmation non ?

Désolé, mais je ne vois pas ce que vous voulez dire ; est que vous sous-entendez que l'on n'a pas démontré que ZFC est contradictoire ?