Récurrence généralisée

mehdi

Bonjour

Quelle est la définition de principe de
Récurrence généralisée sur une famille pas nécessairement suite ?
Dans quel cas peux-je utiliser cette méthode de démonstration ?
Merci beaucoup

Médiat

Vous voulez parler de récurrence transfinie ?

mehdi

Merci
C'est exactement ça

Médiat

Alors : https://fr.wikipedia.org/wiki/Récurrence_transfinie#Définition_par_récurrence_transfinie

Poirot

Dans ce cas tu remplaces simplement les entiers naturels par des ordinaux, et il faut ajouter une clause de stabilité quand on passe à un ordinal limite.

mehdi

Merci pour tous
Soit X un ensemble et P(X) l'ensemble des parties de X
Si on a Une propriété dépendant de A partie de X.
Si cette propriété est vraie pour A égal le vide et si pour A fixé, la propriété est vraie pour tout B strictement continue dans A implique que la propriété est vraie pour A.
Est-ce qu'on peut conclure par récurrence transfinie que la propriété vraie pour toutes les parties de X ?

Merci

Foys

@medhi: non car on pourrait montrer comme ça que dans un ensemble (même infini) toute partie dudit ensemble est finie.

mehdi

@Foys, merci
1) Je n'ai pas compris pourquoi je ne peux pas appliquer le théorème de démonstration par récurrence transfinie dans mon exemple.
2) Si je remplace dans mon exemple propriété par égalité ou formule dépendant de A partie de X, est-ce que je peux conclure que la formule ou l'égalité est vraie pour toute partie A de X ?
Merci.

Poirot

$\mathcal P(X)$ n'est pas bien ordonné pour l'inclusion, donc ce n'est pas le cadre pour appliquer une récurrence (transfinie).

Martial

Il n'est même pas totalement ordonné, donc on est vraiment mal barrés...

mehdi

Merci à tous

Palabra

En fait l'ordre partiel $(\mathcal{P}(X),\subset)$ est bien fondé (edit: non, voir plus bas), donc on peut effectivement montrer des choses sur les parties de $X$ par induction bien fondée. Pour cela, pas besoin de vérifier qu'une propriété est satisfaite pour l'ensemble vide car c'est déjà impliqué par la clause d'hérédité:

$\forall A \in \mathcal{P}(X), (\forall B,B\subset A \Longrightarrow \varphi(B)) \Longrightarrow \varphi(A)$.

Dans ce que propose Foys, à savoir par exemple $\varphi(A):=$"$A$ est fini" et $X=\mathbb{N}$, l'hérédité n'est pas satisfaite justement pour $A= \mathbb{N}$.

Foys

Palabra a écrit:

En fait l'ordre partiel $(\mathcal P (X),\subset)$ est bien fondé,

La suite $n\mapsto \{k\in \N \mid k \geq n\}$ est strictement décroissante et non stationnaire dans $\mathcal P(\N)$.

Pour tout $X$, si $(\mathcal P (X),\subset)$ est bien fondé, $X$ est fini.

Poirot

C'est même la définition de la finitude par Tarski qui est en fait équivalente à la définition usuelle (sans le moindre axiome du choix).

Palabra

haha, oui tout à fait, mea culpa!