$\mathbb{R}$ admet, lit-on, la propriété de la borne sup, dans quelle logique?

Peut-on démontrer la propriété de la borne supérieure dans une logique du premier ordre avec une construction n'admettant aucun axiome de choix?
Les mathématiques ne sont pas vraies, elles sont commodes.
Henri Poincaré
«13

Réponses

  • L'axiome du choix n'a strictement rien à voir avec la propriété de la borne sup. Heureusement !
  • AlainLyon
    Modifié (23 Jun)
    Martial a dit :
    L'axiome du choix n'a strictement rien à voir avec la propriété de la borne sup. Heureusement !

    Comment démontre-t-on la propriété de la borne supérieure avec la logique classique du premier ordre? A celle ou celui qui répond par la complétion de $\mathbb{R}$ je lui en demanderai une preuve!
    Les mathématiques ne sont pas vraies, elles sont commodes.
    Henri Poincaré
  • Cela se démontre directement à partir de la définition de $\R$.
    A toi de nous dire quelle définition de $\R$ tu prends (coupures, suites de Cauchy, etc.)
  • @Cyrano Je ne comprends pas du tout comment en définissant $\mathbb{R}$ par les suites de Cauchy on peut trouver la limite de n'importe qu'elle suite de Cauchy de nombres réels dans une logique du premier ordre sans utiliser un axiome de choix. Comment ferai tu (dans les grandes lignes)?
    Les mathématiques ne sont pas vraies, elles sont commodes.
    Henri Poincaré
  • Bonjour, 
    Je suis novice en la matière… mais avec les suites de Cauchy, on établit une relation d’équivalence. Pas d’axiome du choix, me semble-t-il. 
  • AlainLyon
    Modifié (23 Jun)
    Dom a dit :
    Bonjour, 
    Je suis novice en la matière… mais avec les suites de Cauchy, on établit une relation d’équivalence. Pas d’axiome du choix, me semble-t-il. 

    Bin si puisqu'il est question d'associer à toute suite de Cauchy de l'anneau R défini comme quotient sa limite. Implicitement j'y vois là un axiome du choix.
    Post Scriptum : je connais personnellement trois axiomes de choix et j'appelle axiome du choix général ce que d'aucuns désignent par l'axiome du choix)

    Les mathématiques ne sont pas vraies, elles sont commodes.
    Henri Poincaré
  • Médiat_Suprème
    Modifié (23 Jun)
    Voir : report.dvi (mq.edu.au) qui présente une construction originale de $\mathbb R$ (j'avais posté un pdf) avec toutes les démonstrations.

    Les quasi-endomorphismes à la page 73
    Il ne faut pas respirer la compote, ça fait tousser.

    J'affirme péremptoirement que toute affirmation péremptoire est fausse
  • AlainLyon
    Modifié (23 Jun)
    @Médiat_Suprème Cette définition me convient, Ben Hodger a prouvé avec elle la propriété de la borne supérieure sans axiome de choix (voir fichier en anglais). La complétion vient alors en montrant qu'une union dénombrable de segments fermés emboîtés dont le diamètre tend vers $0$ a pour intersection un singleton.

    Il reste à prouver de manière constructive que les compacts sont les fermés bornés pour la topologie de la valeur absolue! J'ai de vagues souvenirs de preuve consistant à recouvrir un fermé borné par des boules de rayon $\epsilon$ suivit d'un procédé d'extraction pour n'importe quel recouvrement ouvert, mais je sais plus si cette preuve plutôt difficile utilise un axiome de choix!
    Les mathématiques ne sont pas vraies, elles sont commodes.
    Henri Poincaré
  • Congru
    Modifié (23 Jun)
    J'ai un commentaire à rajouter, mais j'ai besoin de faire un arbre au plus binaire, comment fait-on ?
    Ce serait ça mon arbre: $[ ∀ x [ → [ ∧ [ ¬ [ ∃ a [ ∧ [ ∀ b [ ↔ [ b ε a ][ ⊥ ]]][ a ε x ]]]][ ∀ y [ ∀ z [ → [ ∧ [ ¬ [ y ∼ z ]][ ∧ [ y ε x ][ z ε x ]]][ ∀ a [ → [ ∧ [ a ε y ][ a ε z ]][ ⊥ ]]]]]]][ ∃ w [ ∀ y [ → [ y ε x ][ ∃ z [ ∀ a [ ↔ [ a ∼ z ][ ∧ [ a ε w ][ a ε y ]]]]]]]]]]$
    Bref, c'est ça l'axiome du chois @AlainLyon, et c'est équivalent à dire que si un ensemble $a$ n'a aucun élément vide alors il existe une fonction $f$ (fonction choix) de domaine $a$ telle que $\forall x(x\in a\implies f(x)\in x)$. Même si tu admets la négation de l'axiome du choix, il y aura des ensembles $a$ qui auront des fonctions choix. Donc, le fait qu'il y ait une fonction choix n'a pas toujours besoin qu'on utilise l'axiome du choix. 

    Mathématiques divines
  • C'est de la polonaise ?

    Sinon, pour fabriquer un arbre, l'algorithme du shunting yard est très facile à programmer et remarquablement efficace.
    Il ne faut pas respirer la compote, ça fait tousser.

    J'affirme péremptoirement que toute affirmation péremptoire est fausse
  • J'ai connu une polonaise qui en prenait au petit déjeuner.
  • Congru
    Modifié (23 Jun)
    @Médiat_Suprème oui, et c'est aussi comme cela que les arbres sont codés dans mon logiciel de traitement de texte.
    Mathématiques divines
  • Si on part de $\R$ comme l'espace quotient des $\Q$ suites de Cauchy par les suites qui $\Q$ convergent vers 0 alors j'arrive à montrer que toute partie non vide majorée admet une borne supérieure en ayant recours à l'axiome du choix dépendant (plus faible que l'axiome du choix). Est-ce là la question ?
  • @troisqua je penses que tu pourrais démontrer cela par dichotomie sans utiliser l'axiome du choix ou un quelconque affaiblissement de celui ci.
    Mathématiques divines
  • troisqua
    Modifié (25 Jun)
    C'est justement la dichotomie qui me fait choisir à chaque étape (il faut bien prendre un terme dans $A$ majoré non vide et un terme majorant pour construire la suite non ?)
    Je pense que sans l'axiome du choix dépendant on ne peut pas faire grand chose en analyse.
  • @troisqua il y a deux suites que tu peux construire sans utiliser l'axiome du choix, les bornes des intervalles successifs.
    Mathématiques divines
  • troisqua
    Modifié (25 Jun)
    Je n'utilise pas l'axiome du choix. Pour construire la suite des bornes j'ai juste besoin du choix dépendant. Mais sinon peut-être que tu peux préciser ta construction par récurrence n'utilisant pas le choix dépendant. Je suis curieux.
  • Oui, mais pour la suite des bornes, t'as besoin de rien.
    Mathématiques divines
  • Moi j'en ai besoin pour la suite des bornes. Comment fais-tu s'il te plaît ?
  • Congru
    Modifié (25 Jun)
    1.T'as un ensemble non vide $A\in \mathcal P \mathbb R$, s'il a un maximum alors c'est bon.
    2. Supposons que $A$ n'a pas de maximum et qu'il est majoré:
    a.On choisit $a\in A$ et un majorant $m$ de $A$, 
    b. Ensuite on pose $u_0:=a$ et $v_0:=m$
    c. Ensuite, si $\bigcap \{A;[(a+m)/2;m] \}\not = \emptyset $ alors on posera $u_1=(a+m)/2$ et $v_1=m$
    d. si $\bigcap \{A;[(a+m)/2;m] \} = \emptyset $ alors on posera $u_1=a$ et $v_1=(a+m)/2$
    e. ainsi de suite ...





    Mathématiques divines
  • Foys
    Modifié (25 Jun)
    Ci dessous, on démontre sans axiome du choix la propriété de la borne supérieure pour $\R$ vu comme quotient de l'ensemble de suites de Cauchy de $\Q$ (pour la relation d'équivalence := la différence des suites tend vers $0$).

    Soit $X$ une partie non vide et majorée de $\R$ défini comme quotient des suites de Cauchy de $\Q$. Soit $m$ un majorant de $X$. Pour tout entier $n$ soit $D_n$ l'ensemble des (classes d'équivalence de) suites rationnelles constantes de la forme $k \mapsto \frac {a}{10^n}$ où $a\in \Z$. Il est clair que $D_n\subseteq D_{n+1}$ pour tout entier $n$. Pour tout entier $n\in \N$ soit $X_n$ l'ensemble des $u\in D_n$ tels qu'il existe $v\in X$ tel que $u \leq v$. Alors pour tout entier $n$, $X_n$ est majoré par $m$ et possède donc un plus grand élément $u_n$ (ordonné par l'ordre induit, $D_n$ est isomorphe à $\Z$). Alors $n \mapsto u_n$ est une suite de Cauchy de $\Q$ ($u_n \leq u_{n+1} \leq u_n + \frac 1 {10^n}$ pour tout $n$). On vérifie routinièrement que sa classe $\overline u$ est la borne supérieure de $X$ (pour tout entier $n$, $\frac 1 {10^n} + u_n$ majore $X$ et les classes d'équivalence de $(u_n)_{n \in \N}$ et de $\left (  \frac 1 {10^n} + u_n \right)_{n \in \N}$ sont identiques ce qui montre que $\overline u$ majore $X$, de plus pour tout entier $n$, $\left ]\overline u - \frac 2 {10^n}, \overline u \right ]$ contient $u_n$ et donc aussi un élément de $X$ et donc $\overline u$ est le plus petit majorant de $X$).



    Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
  • troisqua
    Modifié (25 Jun)
    @Congru : Le "ainsi de suite" nécessite le choix dépendant.
  • Congru
    Modifié (25 Jun)
    C'est un cas classique de définition par récursion transfinie.
    Mathématiques divines
  • Merci Foys.
  • Par quel axiome justifies-tu l'existence de ta suite définie par récurrence de ta suite de tes bornes et nécessitant à chaque étape le choix dans un ensemble défini grâce aux termes précédemment fabriqués ?
  • @troisqua T'as compirs pourquoi le "ainsi de suite" ne nécessite pas de "choix dépendant" ?
    Mathématiques divines
  • Non, pas avec ce que tu as écrit, puisqu'à chaque étape tu utilises le caractère non vide d'un ensemble construit à l'étape précédente, dans lequel tu pioches sans dire comment.
  • Congru
    Modifié (25 Jun)
    troisqua a dit :
    Par quel axiome justifies-tu l'existence de ta suite définie par récurrence de ta suite de tes bornes et nécessitant à chaque étape le choix dans un ensemble défini grâce aux termes précédemment fabriqués ?


    @troisqua c'est grace à mon théorème préféré: le théorème de récursion transfinie.
    Mathématiques divines
  • Je crois avoir appris que l'axiome du choix dépendant est la variante la moins puissante de l'axiome du choix nécessaire à montrer l'existence d'une suite construite par une récursion transfinie de longueur dénombrable et dans laquelle il faut faire un choix à chaque étape.
  • Congru
    Modifié (25 Jun)
    troisqua a dit :
    Non, pas avec ce que tu as écrit, puisqu'à chaque étape tu utilises le caractère non vide d'un ensemble construit à l'étape précédente, dans lequel tu pioches sans dire comment.
    Si, je dis comment, je divise l'intervalle en deux et je regarde si du côté droit il y a quelque chose, si oui alors les deux nouveaux termes des suites respectives seront les bornes de l'intervalle de droite, si non alors ce sera les bornes de l'intervalle de gauche.


    Mathématiques divines
  • troisqua a dit :
    Je crois avoir appris que l'axiome du choix dépendant est la variante la moins puissante de l'axiome du choix nécessaire à montrer l'existence d'une suite construite par une récursion transfinie de longueur dénombrable et dans laquelle il faut faire un choix à chaque étape.
    On t'a menti, le théorème de récursion transfinie n'a aucunement besoin d'axiome du choix, peu importe l'affaiblissement apporté.

    Mathématiques divines
  • Et parle moi de l'intervalle de gauche.
  • Vu qu'on écrit plus ou moins en même temps...as-tu vu mon dernier commentaire ?
    Mathématiques divines
  • troisqua
    Modifié (25 Jun)
    J'ai vu tous tes commentaires. Au lieu de planquer une récurrence dans des points de suspension et d'un laconique "ainsi de suite", rédige tout proprement stp.
    D'autre part, si tu dis vrai il faut corriger les wikipedia sur l'axiome du choix dépendant.
    The axiom DC   is the fragment of AC  that is required to show the existence of a sequence constructed by transfinite recursion of countable length, if it is necessary to make a choice at each step and if some of those choices cannot be made independently of previous choices.

    Tu auras remarqué les précautions prises par Foys dans sa preuve pour éviter cet écueil, merci à lui.


  • troisqua a dit :
    J'ai vu tous tes commentaires. Au lieu de planquer une récurrence dans des points de suspension et d'un laconique "ainsi de suite", rédige tout proprement stp.

    désolé, j'essayais de faire vite, à rédiger proprement ça risquerait de me prendre un peu plus de temps.
    Mathématiques divines
  • troisqua a dit :
    J'ai vu tous tes commentaires. Au lieu de planquer une récurrence dans des points de suspension et d'un laconique "ainsi de suite", rédige tout proprement stp.
    D'autre part, si tu dis vrai il faut corriger les wikipedia sur l'axiome du choix dépendant.
    The axiom  displaystyle mathsf DC is the fragment of  displaystyle mathsf AC that is required to show the existence of a sequence constructed by transfinite recursion of countable length, if it is necessary to make a choice at each step and if some of those choices cannot be made independently of previous choices.





    Wikipedia est un menteur (parfois) :D
    Mathématiques divines
  • troisqua
    Modifié (25 Jun)
    Et il ment dans toutes les langues. Il ne te reste qu'à démontrer ce que tu dis. Pour l'instant j'ai des affirmations péremptoires et une preuve, identique à la mienne, par dichotomie, mais qui ne construit la suite des bornes que modulo DC.
  • Congru
    Modifié (25 Jun)
    @troisqua Pour avoir personnellement démontré par moi même le théorème de récursion transfinie pour les relations bienfondée-setlike, je peux te confirmer qu'il n'y a nul besoin de choix dépendant pour démontrer ce théorème.
    Après, il te reste à toi d'aller voir une démonstration du théorème de récursion transfinie si tu souhaites vérifier ce que je dis. Sinon tu peux toujours juste te conformer à ce que dit wikipedia, mais comme t'es un matheux je sais quelle voie tu vas prendre et je sais qu'elle me donnera raison.
    Mathématiques divines
  • troisqua
    Modifié (25 Jun)
    Détaille juste ta preuve. Applique ta récursion transfinie en disant proprement quel ensemble bien ordonné tu utilises et va au bout. Ça ne peut pas être si long que tout ce que tu as déjà tapé.
    Wikipedia (enfin les matheux qui ont rédigé cette partie) dit beaucoup plus de choses que ce que j'ai copié avant :
    For example, a construction by transfinite recursion frequently will not specify a unique value for Aα+1, given the sequence up to α, but will specify only a condition that Aα+1 must satisfy, and argue that there is at least one set satisfying this condition. If it is not possible to define a unique example of such a set at each stage, then it may be necessary to invoke (some form of) the axiom of choice to select one such at each step. For inductions and recursions of countable length, the weaker axiom of dependent choice is sufficient. Because there are models of Zermelo–Fraenkel set theory of interest to set theorists that satisfy the axiom of dependent choice but not the full axiom of choice, the knowledge that a particular proof only requires dependent choice can be useful.

  • @troisqua si tu as déjà trouvé un truc que j'ai écrit sur ce forum "trop formel", alors ma preuve te paraitra venir d'un autre monde.
    Mathématiques divines
  • troisqua
    Modifié (25 Jun)
    Tu devrais alors demander (ou produire) une correction de l'ensemble des pages wikipedia sur la récursion transfinie, les axiomes du choix et en particulier DC (en version anglaise, française et espagnole pour ce que j'ai lu et compris) et proposer tes propres résultats. En attendant je veux bien lire ta preuve d'un autre monde.
  • Bon rappelons déjà ce qu'est le théorème de récursion transfinie:
    Mathématiques divines
  • Congru
    Modifié (26 Jun)
    Je ne vais rédiger le théorème que dans le cas ensembliste:
    Soit $(C;R)$ une relation bienfondée ensembliste, soit $G:=(F;(x;y;z))$ une formule fonctionnelle, alors il existe une unique application surjective $f$ de domain $C$ telle que $\forall x(x\in C\implies G(x;f\restriction _{R^{-1}x};f(x)))$

    Mathématiques divines
  • Et donc ?
  • Congru
    Modifié (25 Jun)
    C'est ça le théorème pour les bienfondés ensemblistes. Je l'ai rédigé. Je ne parlais pas de rédiger une démonstration, j'ai déjà fait ça dans un cadre plus général et je ne compte pas le mettre sur le forum. Mais juste pour que tu saches ce dont on parle, je t'ai donné le théorème dans le cas ensembliste (suffisant ici).
    Mathématiques divines
  • troisqua
    Modifié (25 Jun)
    A quel ensemble bien ordonné appliques-tu ta récurrence transfinie ? Actuellement, il ne manque "que" de la rigueur à ta preuve  par dichotomie pour être valable. Malheureusement tu cites un théorème général sans dire comment précisément tu l'appliques dans le cadre qui nous intéresse. Tu n'as donc rien prouvé en l'état.
    Au fait, le théorème de Baire dans les espaces complets est équivalent à l'axiome du choix dépendant.
  • Congru
    Modifié (25 Jun)
    $(\mathbb N ; \{(a;b)\vert  (b\in \mathbb N)\wedge (a\in b) \} )$

    Mathématiques divines
  • Congru
    Modifié (25 Jun)
    troisqua a dit :
    A quel ensemble bien ordonné appliques-tu ta récurrence transfinie ? Actuellement, il ne manque "que" de la rigueur à ta preuve  par dichotomie pour être valable. Malheureusement tu cites un théorème général sans dire comment précisément tu l'appliques dans le cadre qui nous intéresse. Tu n'as donc rien prouvé en l'état.
    Au fait, le théorème de Baire dans les espaces complets est équivalent à l'axiome du choix dépendant.

    En fait il s'agit de construire deux suites de Cauchy dont la différence tend vars $0$. Il n'y a pas besoins de $AC$ pour montrer qu'une suite de Cauchy dans $\mathbb R$ converge (du moins je crois), qu'on me corrige si je me trompes.
    Aussi, en réalité, j'ai dit oui quand tu disais que je n'avais pas rédigé rigoureusement ma construction, mais il y a déjà tout de façon informel, ça ne correspond pas au niveau formel que je trouve acceptable, mais bon j'ai expliqué en mots simples sur mes commentaires. Là je dois aller faire un peu de sport.
    Mathématiques divines
  • troisqua
    Modifié (25 Jun)
    @Congru: si ton argument fonctionnait, alors la démonstration du théorème de Baire dans les complets (qui singe exactement ta construction dichotomique pour fabriquer une suite de proche en proche) pourrait se faire sans choix dépendant. Or, il est assez facile de montrer que Baire dans les complets implique le choix dépendant.
    Donc je ne crois pas à l'existence de ta preuve sans utilisation du choix dépendant, d'ailleurs tu n'as pas encore fourni de preuve.
    D'autre part, précédemment, le choix dépendant, on ne l'a pas utilisé pas pour prouver qu'une suite tendait vers 0. On l'a utilisé pour montrer l'existence des deux suites constituant les bornes des intervalles (tu les fabriques par choix dépendant, et si tu veux faire une récurrence transfinie pour contourner le problème il faudra bien préciser comment tu l'appliques pour ne pas tomber dans le piège classique rappelé en gras dans l'extrait Wikipedia ci-dessus).
  • Congru
    Modifié (25 Jun)
    Preuve de quoi ? Du théorème de récursion transfinie ou qu'une suite de Cauchy de réels converge ?
    Au fait tu es libre de croire ce que tu veux croire, si quelqu'un d'autre a une preuve du théorème de récursion transfinie, je lui prie de fournir cette preuve à @troisqua. Je ne compte pas mettre ma preuve sur ce forum.
    Mathématiques divines
Connectez-vous ou Inscrivez-vous pour répondre.