PS : ma question ne s'applique pas uniquement à cet exemple, mais en toute généralité, quand on montre qu'un ensemble E est non vide puis qu'on dit "soit x un élément de E", utilise-t-on implicitement l'axiome du choix?

Fractal

Salut !


non, tu n'as pas bessoin de l'axiom du choix pour choisir un elements dans un ensemble non vide. (c'est pour cela que l'axiom de choix ce contente de dire que "un produit d'ensemble non vide est non vide")


tu as bessoin de l'axiom du choix quand tu dois faire une infinité de choix non discernable.


note que l'équivalence entre l'énoncé que tu ecrit t l'axiom du choix est trivial en partant de ceci :

la définition du produit des Xi, c'est l'ensemble des application de I dans l'union disjointes des Xi telle que pour tous i f(i) est dasn Xi.

(on appelle Union disjointe d'une famille l'ensemble : union pour i dans I des Xi*{i}, ou * désigne le produit cartésien : si les Xi sont effectivement disjoint c'est équivalent à l'union standart, si il ne le sont pas on "met plusieur fois" les elements qui sont dans plusieur Xi...)

en fait si tu essai de comprendre précisement ce qui requière l'axiom du choix (et que tu as du temps à perdre ^^ ) je te conseillerai de réfléchir à l'exercice suivant :

on considere les trois enoncé :
AC : un produit d'ensemble non vide est non vide. (axiome du choix)
ACD : soit R une relation binaire sur X, telle que pour tous x il existe y telle que xRy, alors il existe une suite xn telle que xn R x(n+1) pour tous n. (axiome des choix dépendants)
ACden : tous produit dénombrable d'ensemble non vide est non vide (Axiome du choix dénombrable)

il faut alors prouver que AC => ACD => ACden (et surtous pas ACden => ACD par contre, meme si ca peut 'avoir l'air vrai', et quand trichant un peu on à vite fait de le prouver par accident... )
(c'est un résultat tres classique)

la preuve n'est pas difficile, à partir du moment ou on a bien compris à quoi sert l'axiome du choix.

je te dit ca, parceque cette exos fait intervenir quasiemet toute les subtilité de l'axiomes du choix, et il me semble bien que c'est en le faisant que j'ai compris comment ca fonctionait ^^

D'accord
Mais est-ce qu'il y a un axiome précis qui l'autorise?
Parce que cela me semble quand même aussi peu constructif que l'axiome du choix et autant contestable par un intuitionniste, non?

Fractal

Posts croisés.
Je finis mon DM de physique et je m'y met

Fractal

Mais est-ce qu'il y a un axiome précis qui l'autorise? >>> oui et non.


la définition de l'ensemble vide c'est :


"pour tous x, x n'appartiens pas à vide"
(l'existence de cette ensemble est un axiom )

donc V différent de vide, s'ecrit donc :

"il existe x telle que x appartiens a V".


apres si passer de "il existe x telle que" à "soit x telle que" te pose probleme, c'est un poil plus embetant ... parceque je connait pas de facon de justifier que ceci à bien un sens sans introduire la notion de language et de démonstration formelle. donc j'espère que tu trouvera que cela est acceptable pour un intuitioniste ^^ (ceci dit je me trompe peut-etre sur ce dernier point, j'ai pas encore terminé le cours de logique ...)

J'ai un petit doute, est-ce qu'en logique intuitionniste on a "non(pour tout x, P(x))" qui est équivalent à "il existe x tel que non P(x)"?

Fractal

oui, en ce qui me concerne (I mean, dans le cour que j'ai eu...) c'était la définition du quantificateur "il existe"

En logique classique, d'accord, mais je pense pas que ce soit encore le cas en logique intuitionniste.
Sur wiki en anglais : (partie  "Universal versus existential quantification") la flèche ne va que dans l'autre sens, ce qui sous-entendrait que c'est pas vrai dans l'autre sens.

Fractal

D'ailleurs, dans ces mêmes propriétés, on remarque qu'aucune flèche ne va vers un "il existe", ce qui voudrait dire qu'on ne peut pas déduire l'existence de quelque chose autrement qu'en le construisant explicitement (en c'est d'ailleurs tout à fait cohérent avec l'idée qu'on peut se faire de l'intuitionnisme)

Fractal

Alors, pour en revenir à ton exercice, déjà pour la première implication je bloque un peu.

Ma première réaction a été de dire, soit , on choisit tel que , puis tel que et ainsi de suite par récurrence.
Bon, je me doute bien que ça ne marche pas vu que je ne me sers même pas de l'axiome du choix, mais même là je ne vois pas bien pourquoi.
Le principe de récurrence est une conséquence de l'axiome du choix?

Sinon, je suis aussi parti comme ça :
Pour tout , on pose .
Maintenant, d'après l'axiome du choix il existe telle que pour tout , c'est à dire que pour tout .
Mais ensuite je ne vois pas bien comment conclure, mis à part en utilisant de nouveau une récurrence.
Ou alors on posant définie par , alors si x₀ est un élément quelconque de X, la suite vérifie les conditions demandées.
Mais là encore j'ai l'impression de contourner le problème en faisant des trucs interdits...

Fractal

hum désolé, je pensais que tu utilisait le therme "intuisioniste" au sens de "théorie naives". (par oposition a une théorie formelle ou ce genre de question n'as pas lieux d'etre...). la javoue que je ne connait absolument ien sur la logique intuitioniste !


pour les exos je te réponds dans le prochain postes.

la remiere idée est effectivement fausse !


en fait de cette facon tu peut prouver que "pour tous n il existe une suite fini x1,x2..xn" telel que xi R xi+1. mais pas de passer à une suite infinit.




mais la deuxieme démonstraon est en effet corecte. tu n'utilise rien d'interdit. e fait d'avoir une fonction f te permet de définir une suite précise Xn = g^n(x).
(le ^n sgnifiant itérern fois).

tu comprend bien la distintion ?

la récurence n'est jammais interdite. comme je te l'ai dit dans un autre poste c'est une propriété fondamental de N. si tu peut parler d'entier alors tu peut parler de récurence.

mais dans le premier cas tu prouve exactement que "pour tous n il existe une suite finit x1,x2...xn telle que pour tous i<n  xi R x(i+1)". si tu es pas d'accord, essai de montrer qu'il exste une telle suite (Xn)n appartenant a N par récurence. tous ce que tu pourra faire c'est montrer par récurence que pour tous n, un telle suite est définit par k<n...

Ah voui, je crois que je vois un peu mieux ce que tu veux dire.
Vu qu'on veut démontrer qu'il existe une suite infinie vérifiant telle propriété, il n'y a en fait aucun entier sur lequel faire une récurrence, donc ça tombe à l'eau direct ^^

Pour la deuxième implication, on considère une famille dénombrable d'ensembles et muni de la relation pour un certain naturel i.
Alors, d'après l'axiome des choix dépendants, il existe une suite d'éléments commençant par un élément de X₀ et tel que l'on ait exactement un élément de chaque X_i.
L'axiome du choix dénombrable est donc impliqué par l'axiome des choix dépendants.

Est-ce correct?

Fractal

dans l'esprit c'est tous a fait corecte.

y a deux petite amélioration mais d'ordre plutot technique :


1) ce que tu dis est faux si les Xi ne sont pas disjoint. (par exemples si il existe a qui est a la fois dans Xo et dans X1 tu peut construire la suite constante égal à a...).
Il faut donc forcer les Xi a etre disjoint en prenant X = l'union des Xi * {i}

et R la reation sur X définit par (x,a) R (y,b) si et seulement si b=a+1...


2) techniquement, rien ne t'autorise à choisir xo dans Xo (meme si on pourrait changer l'énoncé de ACD en permettant de choisir xo et le résultat global serait le meme - apres je sais pas si les deux énoncé sont vraiment équivalent - )
pour régler ce probleme tu construit ta suite, tu as xo dans un certain Xp. et tu construit "à la main" une suite d'élement ao dans Xo... jusqu'a ap dans Xp, ce que tu peut faire par récurence, ou juste n invoquant qu'un produit finit d'ensemble non vide est finit (meme sans l'axiom du choix...) et en construisant la suite (ao...ap,x0,x1...,xn....)


mais c'est deux point sont plus de l'ordre du détail je trouve.

Oki

Pour le premier point, en effet j'avais pas pensé à ce genre de petites complications.
Pour le deuxième point, je me suis effectivement posé la question, mais vu que dans la démo de l'axiome des choix dépendants le point de départ pouvait être quelconque, je me suis dit que là aussi, mais effectivement c'est pas tout à fait vrai.

_{PS : On fait de ce genre de trucs à Ulm?
PS2 : Tu khôlles pas à LLG par hasard?}

Fractal

PS : On fait de ce genre de trucs à Ulm? >>> oui, si on décide de suire le cours de logique

PS2 : Tu khôlles pas à LLG par hasard?>>> non, mais il y a effectivement des gens de ma promo qui kholle à LLG... et j'avoue que certain pourait etre tenté de donner ce genre de chose en kholle :p

non plutot en Spé tous de meme, et normalement à condition que le prof ai décidé de parler d'axiom du choix en cours. (quoique... ca peut ne pas arreter tous le monde ca ^^  ... en sup on m'avait donné une khole qui parlait de filtre et d'ultrafiltre ... on est quand meme relativement loin du programe de prépa la :p)

Les filtres et ultra filtres, pourquoi pas, du moment qu'on te donne la définition c'est pas plus compliqué qu'autre chose (enfin je crois, j'en ai jamais manipulé ), mais avec l'axiome du choix c'est quand même des raisonnements assez différents il me semble, puisqu'on touche aux fondements mêmes des mathématiques.

En tous cas, merci pour ton aide
A bientôt.

Fractal