Récurrence sur R

[Eogan]

Bonjour, après avoir découvert la toute puissance des démonstrations par récurrence sur N je me demandais s'il n'existait pas un équivalent sur R.
Peut-être dans le style: Montrer H0 vraie puis que Hx vraie implique Hx+e vraie avec e qui tend vers 0.
-----

[Coincoin]

Salut,
Pas à ma connaissance...
Et jouer avec des limites, ça pose le problème de la continuité : ce n'est pas parce que H_x est vraie pour x tendant vers x₀ que H_x0 est vraie.

[GuYem]

Pareil que Coincoin : jamais entendu parler de récurrence sur R.

Je crois que le caractère dénombrable de N est indispensable à ce genre de raisonnement.

[Eogan]

C'est bien dommage, car ça permettrait de démontrer facilement un grand nombre de propriétés!

[A voir en vidéo sur Futura]

[Quinto]

Moi j'ai entendu le contraire, mais je n'ai jamais vraiment vu à quoi ca ressemblait.

[martini_bird]

Salut,

je vois difficilement quelle pourrait être la notion d'hérédité qui permette d'aboutir à la véracité d'une proposition P(x) pour un ensemble non-dénombrable de x...

Cordialement.

[Quinto]

C'est un de mes profs de logique et combinatoire qui m'avait dit ceci. Comme je l'ai dit, je n'ai jamais vu ni entendu vraiment de quoi il était question.
Je suis évidemment moi même curieux, mais il parlait de récurrence transfinie ou de quelque chose de ce genre, si quelqu'un en a entendu parler...

[martini_bird]

Salut,

en effet, puisque le théorème de Zermelo assure un bon ordre sur un ensemble arbitraire, on peut théoriquement disposer d'une récurrence sur R. Reste qu'en pratique, un tel bon ordre n'est pas disponible... (à ma connaissance en tout cas)

Cordialement.

[moijdikssékool]

Montrer H0 vraie puis que Hx vraie implique Hx+e vraie avec e qui tend vers 0

ce n'est pas tout à fait la définition d'une récurrence

C'est bien dommage, car ça permettrait de démontrer facilement un grand nombre de propriétés!

lesquelles?

Si le monde n'a absolument aucun sens, qui nous empêche d'en inventer un?

moi, mais ca n'aurait aucun sens

[doryphore]

Tiens c'est quoi le lien entre l'existence d'un bon ordre et l'existence d'une notion de récurrence?
Etant donné que je ne connais que les récurrences sur N et assimilés, je suis curieux...

[martini_bird]

Salut,

la démonstration du principe de récurrence s'appuie sur le fait que tout partie de IN admet un élément minimal. Or un ensemble muni d'un bon ordre est précisément un ensemble totalement ordonné dont toute partie admet un élément minimal.

Cordialement.

[matthias]

la démonstration du principe de récurrence s'appuie sur le fait que tout partie de IN admet un élément minimal. Or un ensemble muni d'un bon ordre est précisément un ensemble totalement ordonné dont toute partie admet un élément minimal.

Autement dit, avec ce bon ordre on a un minimum sur R, et tout élément admet un "successeur" immédiat (minimum de l'ensemble des éléments strictement supérieurs à l'élément donn&#233 ?
La récurrence consisterait donc à démontrer une propriété pour le minimum et pour le successeur de tout élément vérifiant la propriété, comme sur N ?

J'avoue que j'ai du mal à imaginer un bon ordre sur un ensemble non dénombrable.

[martini_bird]

Autement dit, avec ce bon ordre on a un minimum sur R, et tout élément admet un "successeur" immédiat (minimum de l'ensemble des éléments strictement supérieurs à l'élément donn&#233 ?
La récurrence consisterait donc à démontrer une propriété pour le minimum et pour le successeur de tout élément vérifiant la propriété, comme sur N ?

J'avoue que j'ai du mal à imaginer un bon ordre sur un ensemble non dénombrable.

Oui, c'est bien ça.

Mais comme tu le dis ce n'est pas effectif: le théorème de Zermelo (équivalent à AC) assure l'existence d'un bon ordre, mais ne donne aucun moyen de le construire.

Avec l'axiome du choix, on se retrouve à nouveau avec des objets que l'on ne sait pas construire.

C'est un peu comme dans le paradoxe de Banach-Tarski, où on montre l'existence d'un découpage de la sphère pour en former deux autres: on a aucune information sur le découpage en question.

[matthias]

En fait, passe encore qu'on puisse trouver un bon ordre sur un ensemble arbitraire (équivalent à l'axiome du choix si j'ai bien compris), par contre pour la récurrence comme je l'ai écrit ça ne doit pas être ça.
Je ne crois pas que l'on puisse en déduire que la propriété serait vraie pour tous les éléments, sinon on se retrouve avec un équivalent des axiomes de Peano ...

Quelqu'un aurait plus de détails, parce que là je m'embrouille ?

[EDIT: croisement avec martini, mais si tu as plus d'explications quand-même, n'hésite pas ]

[doryphore]

Ok, je vois où se situe la problématique maintenant...
Donc accepter Zermelo nous oblige d'accepter l'existence d'une relation de bon ordre sur R (entre autres) sans pouvoir en faire une construction mentale (pour l'instant).
C'est marrant, ça permet de définir de nouveaux réels.

Le cinquième successeur de 1 par exemple...notons le (1;5).

On a (1;5)+(2;3)=(3;8), 2*(1;7)=(2;14), (3;7)*(2;4)=(6;26) si vous n'y voyez pas n'inconvénient.

En revanche, pour deux réels x et y quelconques construits autrement, on a toujours y=(x;+-)

[invité576543]

Bonjour,

Je m'immisce dans cette discussion pour la dériver un petit peu... En prenant le problème dans l'autre sens, par les ordinaux. La récurrence est définie sur N, c'est à dire sur l'ordinal , mais si je prends un ordinal transfini, comme par exemple , une récurrence ne peut pas se présenter à partir d'une notion de "successeur immédiat", comme le présente Matthias par exemple.

Quelqu'un pourrait-il développer la notion de récurrence sur un ordinal transfini? Je pense que cela aiderait à comprendre de quoi on parle sur ce fil...

En particulier, la question d'une récurrence sur l'ordinal pourrait se révéler utile, non?

Cordialement,

[doryphore]

Oubliez la moitié de ce que j'ai dit hier soir, j'avais une conception assez limitée d'une relation d'ordre: aucune raison pour que deux réels quelconques construits d'une autre manière ne soit pas successeurs l'un de l'autre...

[Sylvestre]

Quelqu'un pourrait-il développer la notion de récurrence sur un ordinal transfini? Je pense que cela aiderait à comprendre de quoi on parle sur ce fil...

En particulier, la question d'une récurrence sur l'ordinal pourrait se révéler utile, non?
Cordialement,

Salut,

J'entre dans cette discussion très intéressante. Pour définir la récurrence transfinie, on fait comme cela. Tout d'abord la propriété essentielle pour la récurrence c'est le bon ordre d'un ordinal. Un bon ordre est un ordre avec la propriété supplémentaire que toute partie A de l'ensemble ordonné E possède un plus petit élément qui est lui même dans A.
Par exemple, cela est vrai sur IN. Par exemple, le plus petit élément de {3,5,7,23} est 3. Mais cela marche aussi pour les parties infinies.

Ce qui est étonnant est que l'on peut étendre cela à des ordres différents de celui de IN (que l'on appele . Par exemple possède un bon ordre ou les entiers sont ordonnés comme dans IN (qui est ) et où est plus grand que tous les autres. On montre facilement que cela est un bon ordre.

Ensuite, on va plus loin, on peut définir pour tout entier n. En tant qu'ensemble, . La relation d'ordre est que . On montre que c'est un bon ordre.

En fait, étant donné un ordinal x, on peut toujours construire x+1, en posant et en étendant l'ordre de x, en posant que .

Bon, avant d'aller plus loin (c'est-à-dire, avant de monter jusqu'à ), je vais présenter la récurrence transfinie.

On définit une section commençante d'un ordinal X, en posant que c'est une partie A de X telle que on a . Par exemple, les sections commençantes de IN sont {0}, {0,1}, {0,1,2},etc...
Une section commençante de est . Une autre est . Il faut remarquer qu'une section commençante n'a pas forcément de plus grand élément, c'est le cas du dernier exemple.

On peut maintenant définir la récurrence transfinie. Soit X, un ordinal (qui est donc bien ordonn&#233 et P une propriété sur les éléments de X telle que pour toute section commençante A, on ait : Si P est vraie pour tout a\in A, alors P est vraie pour le plus petit élément de X-A (qui existe par la propriété de bon ordre). Dans ce cas, la propriété est vraie pour tout .

Bon, c'est assez pour ce message, je continuerai plus tard.

[Sylvestre]

Resalut,

Bon, j'ai oublié de dire que lorsque l'on parle de récurrence transfinie, la propriété essentielle n'est pas que tout entier a un successeur, c'est plutôt le fait que pour toute partie strictement bornée supérieurement d'un ensemble ordonné X , l'ensemble des bornes possède un plus petit élément. En symbole,cela se dit telle que , l'ensemble des b qui conviennent possède un plus petit élément.

Par exemple,ceci n'est pas vrai sur IR avec l'ordre usuel. En effet, l'ensemble ]0,1] est borné supérieurement, par 2 par exemple, mais il ne l'ensemble de ses bornes supérieures strictes est qui ne possède pas de plus petit élément.

Mais cela est vrai pour tous les ordinaux, car, grâce à la propriété de bon ordre, toute partie possède un plus petit élément.

[matthias]

si je prends un ordinal transfini, comme par exemple , une récurrence ne peut pas se présenter à partir d'une notion de "successeur immédiat", comme le présente Matthias par exemple.

lorsque l'on parle de récurrence transfinie, la propriété essentielle n'est pas que tout entier a un successeur

Oui, on est bien d'accord pour dire qu'une récurrence s'appuyant sur la notion de successeur ne va pas fonctionner dans le cas non dénombrable, c'était le sens de la remarque:

par contre pour la récurrence comme je l'ai écrit ça ne doit pas être ça.
Je ne crois pas que l'on puisse en déduire que la propriété serait vraie pour tous les éléments, sinon on se retrouve avec un équivalent des axiomes de Peano ...

On peut maintenant définir la récurrence transfinie. Soit X, un ordinal (qui est donc bien ordonné) et P une propriété sur les éléments de X telle que pour toute section commençante A, on ait : Si P est vraie pour tout , alors P est vraie pour le plus petit élément de X-A (qui existe par la propriété de bon ordre). Dans ce cas, la propriété est vraie pour tout .

Il ne manque pas une condition d'initialisation ?

[Sylvestre]

Il ne manque pas une condition d'initialisation ?

En fait, non, car est une section commençante et P est vraie pour tout élément de .

Sinon, concernant le fait que IR est non dénombrable, si on accepte l'axiome du choix, alors tout ensemble peut être bien ordonné donc IR en particulier. Il existe donc un ordinal muni d'un bon ordre qui est en bijection avec IR. Evidemment cet ordre n'a rien à voir avec l'ordre usuel. Pour faire de la récurrence sur IR, il faut réussir à comprendre suffisament cet ordre pour pouvoir l'utiliser. Le problème est que l'on peut montrer qu'il n'est pas possible d'exhiber cet ordre explicitement. Cela a un rapport étroit avec le fait que la théorie des ensembles avec l'axiome du choix est aussi cohérente que la théorie des ensemble avec sa négation.

[doryphore]

J'ai vu quelque part que l'on mettait le concept de limite sur le même plan que celui de successeur dans la reccursion sur des ordinaux quelconques: peut-on m'en dire davantage ?
successseur-limite et hérédité-continuité joueraient-ils des rôles similaires ?

[invite2ec8adb6]

pour une récurrence sur R, je pense que si il existe un a>0 tel que si la propriété est vraie en x, alors elle est vraie sur l'intervalle (x,x+a)
alors si on arrive à démontrer la propriété par récurrence sur une suite (xn) de réèls bien choisis, on la démontre sur R

[matthias]

pour une récurrence sur R, je pense que si il existe un a>0 tel que si la propriété est vraie en x, alors elle est vraie sur l'intervalle (x,x+a)
alors si on arrive à démontrer la propriété par récurrence sur une suite (xn) de réèls bien choisis, on la démontre sur R

Il faudrait que ta suite ne soit pas minorée.
Si tu avais un réel a>0 tel que si la propriété est vraie en x alors elle est vraie sur [x-a;x+a], il suffit que la propriété soit vraie pour un réel pour être vraie sur R.
Mais ce n'est pas vraiment une récurrence sur R, là on est encore dans le cas dénombrable (en fait tu vas démontrer par une récurrence classique que si ta propriété est vraie pour x alors elle est vraie sur [x-na;x+na]).

[Sylvestre]

pour une récurrence sur R, je pense que si il existe un a>0 tel que si la propriété est vraie en x, alors elle est vraie sur l'intervalle (x,x+a)
alors si on arrive à démontrer la propriété par récurrence sur une suite (xn) de réèls bien choisis, on la démontre sur R

En fait, il suffit que pour tout x, il existe un a vérifiant la propriété que tu dis. Le a pouvant dépendre de x.

Cela ressemble beaucoup à un type de démonstration où l'on montre que l'ensemble des points tels que la propriété est vérifiée est ouvert et fermé et qu'il contient 0. Comme les seuls parties de IR qui soient fermées et ouvertes sont l'ensemble vide et IR tout entier, on a le résultat. Les ensembles ouverts de IR sont les réunions d'intervalles ouverts.

En pratique, on montre que si la propriété est vraie sur [0,x], alors on montre qu'il existe un tel que la propriété est vraie sur [tex] [0,x+\epsilon[. Il faut aussi montrer que si la propriété est vraie sur un ensemble de points convergeants vers x, comme par exemple [0,x[, alors elle est vraie pour x. Si l'on prouve ces deux choses, on a prouvé que la propriété est vraie sur tout .

[invite2ec8adb6]

je n'ai pas compris le système
une fois que la propriété est vraie au voisinage de epsilon, elle l'est pour epsilon,et tu réapplique le premier lemme à x+epsilon, ce qui te donne un epsilon' et tu continue comme ça jusqu'à l'infini?
mais qu'est-ce qui te prouve que la série des epsilon tend vers l'infini?

[matthias]

Ce que montre Sylvestre c'est que l'ensemble des x vérifiant la propriété va être à la fois un ouvert et un fermé de R+, donc sera R+ tout entier (R+ étant connexe).

Sinon, tu peux raisonner par l'absurde. Considère l'ensemble des réels x tels que la propriété soit vraie sur [0;x]. Suppose qu'il est majoré, il admet donc une borne supérieure A. La propriété est donc vraie pour une suite convergeant vers A, et par hypothèse A appartiendra alors à l'ensemble. Mais si la propriété est vraie sur [0;A] alors il existe epsilon tel qu'elle soit vraie sur [0;A+epsilon[ donc A n'est pas la borne supérieure.