Extraction diagonale

Chalk
Modifié (July 2023) dans Fondements et Logique
Bonjour,

J'essaye d'éclairer la subtilité décrite ici : https://agreg-maths.fr/uploads/versions/2491/optimisation_hilbert_erratum.pdf (le gros paragraphe)
Et je suis assez perdu quand j'essaye de le poser proprement.

Supposons que j'arrive à démontrer par récurrence que :
pour tour entier $n$, il existe des suites $\phi_0,...,\phi_n$ telle que la suite $\phi_n$ est extraite de $\phi_{n-1}$ qui est extraite de etc ... jusqu'à $\phi_0$, telles que pour tout $i\leq n$ on ait la propriété $P(i,\phi_n)$. Comme dans ce fil : https://agreg-maths.fr/uploads/versions/2491/optimisation_hilbert_erratum.pdf 

Comment j'arrive ensuite, avec l'axiome du choix, à démontrer qu'il existe une suite $\phi$ telle que pour tout $n$, $\phi$ vérifie $P(n, \phi)$ ?

Déjà, est-ce le bon énoncé, et ensuite j'utilise comment l'axiome du choix (fort, pour faire simple) pour justifier cette extraction diagonale ?

Réponses

  • Quand tu fais une extraction diagonale, tu construis une suite $(\phi_n)$ d'extractrices telles que $\phi_0 \circ\cdots\circ \phi_n$ vérifie ce que tu veux (cette construction se fait avec l'axiome du choix dénombrable dépendant). 

    Ensuite tu poses $\phi(n)=\phi_0\circ\cdots\circ\phi_n(n)$ pour définir une extractrice commune. 
  • Chalk
    Modifié (July 2023)
    Oui ok mais alors en quoi est-ce plus subtil qu'invoquer l'axiome du choix dénombrable à chaque fois qu'on construit une simple suite par récurrence ?

    Je ne pense pas que l'erratum d'un livre d'agrégation expliquerait qu'il y a une grosse subtilité ici si c'était vraiment le même cas que n'importe quelle suite qu'on construit par récurrence avec l'axiome du choix dénombrable ?

    Et puis justement comme le dit l'erratum, si tu appliques la récurrence classique à ma proposition, rien ne dit que c'est les mêmes $\phi_i$ quand $n$ change. Tu tombes en plein dans le problème. Pour chaque $n$ il existe des $\phi_1,...,\phi_n$ mais $n$ est à chaque fois fixé. Quand $n$ augmente vers l'infini rien ne dit justement que tu peux construire sur les mêmes $\phi_i$. Dit plus clairement, on a démontré que pour tout $n$ il existe des $\phi_{i,n}$ tels que ... Du coup que vaut $\phi$ ?

    Bon maintenant que j'y pense on peut construire une suite par récurrence sans faire appel à l'axiome du choix, chaque élément est unique, mais ça n'enlève rien au point que je viens de soulever.
  • On peut construire toute suite finie de $\phi_i$ sans faire appel à l'axiome du choix. Mais pour construire une suite infinie, on a besoin du choix dépendant.
  • Chalk
    Modifié (July 2023)
    Et comment concrètement on utilise l'axiome du choix ?

    Pour l'instant on a juste prouvé que pour tout $n$ il existe $\phi_{0,n}$ jusqu'à $\phi_{n,n}$ tels que ... Jusque là y'a pas d'axiome du choix.

    J'indice exprès en $n$ pour bien montrer que la récurrence ne montre pas qu'on peut aller à l'infini avec les mêmes $\phi_i$. La récurrence montre que pour tout $n$ il existe des phi_i, donc les phi_i en question dépendent de $n$. C'est exactement le problème que pointe l'erratum.

    De ça comment on définit $\phi$ ou comment on la construit concrètement avec l'axiome du choix ?

    On peut presque oublier les messages précédents, je souhaite voir une démonstration rigoureuse dans ZFC de l'extraction diagonale sur des sous-suites extraites construites par récurrence par exemple.
  • SkyMtn
    Modifié (July 2023)
    Soit $\mathcal S$ l'ensemble des suites finies d'extractrices vérifiant ta propriété $P$. On définit une relation binaire $\mathcal R$ sur $\mathcal S$ par
    $$ (\phi_0,\ldots,\phi_n) \mathcal R (\psi_0,\ldots,\psi_m) \Longleftrightarrow m = n+1 \text{ et } \forall i \le n ~,~ \phi_i = \psi_i $$ L'ensemble $\mathcal S$ contient une suite de longueur $1$ et pour tout entier naturel $n$, et toute suite $(\phi_0,\ldots,\phi_n) \in \mathcal S$, il existe $\phi_{n+1}$ une extractrice telle que $(\phi_0,\ldots,\phi_n,\phi_{n+1}) \in \mathcal S$ et donc $(\phi_0,\ldots,\phi_n) \mathcal R (\phi_0,\ldots,\phi_n,\phi_{n+1})$.

    D'après l'axiome du choix dénombrable dépendant, il existe une suite $(\Phi^n)_{n\in\mathbb N}$ dans $\mathcal S$ telle que $\Phi^0 = (\phi_0)$ et $\Phi^n \mathcal R \Phi^{n+1}$ pour tout $n\in\mathbb N$. On définit ensuite $\phi_n$ comme la dernière composante de $\Phi^n$, ainsi $(\phi_0,\ldots,\phi_n) = \Phi^n$.

    La suite $(\phi_n)_{n\in\mathbb N}$ est ainsi construite.
  • Top, merci beaucoup !  B)
Connectez-vous ou Inscrivez-vous pour répondre.