Récurrence généralisée

mehdi
mehdi
dans Fondements et Logique
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

Réponses

  • Médiat
    Médiat
    Vous voulez parler de récurrence transfinie ?
  • mehdi
    mehdi
    Merci
    C'est exactement ça
  • Médiat
    Médiat
    Alors : https://fr.wikipedia.org/wiki/Récurrence_transfinie#Définition_par_récurrence_transfinie
  • Poirot
    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
    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
    Foys
    @medhi: non car on pourrait montrer comme ça que dans un ensemble (même infini) toute partie dudit ensemble est finie.
    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$.
  • mehdi
    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
    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
    Martial
    Il n'est même pas totalement ordonné, donc on est vraiment mal barrés...
  • mehdi
    mehdi
    Merci à tous
  • Palabra
    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
    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.
    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$.
  • Poirot
    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
    Palabra
    haha, oui tout à fait, mea culpa!
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 28

HéhéhéJLTOShinebiguine_equationbisamnicolas.patroisvlad69 +21 Invités