Clôture transitive

Congru
Modifié (October 2023) dans Fondements et Logique
Bonjour
On appellera relation binaire tout ensemble de couples.
On appellera relation transitive tout ensemble de couples qui vérifie la propriété de transitivité (que je ne rappelles pas)
Comment définit-on alors la cloture transitive d'une relation binaire.

Réponses

  • Cyrano
    Modifié (October 2023)
    On peut définir de manière générale la clôture transitive de n'importe quel ensemble. 

    Soit $x$ un ensemble. On définit une suite $(x_n)_{n\in \omega}$ par récurrence sur $n$ en posant $x_0 = x,$ et $x_{n+1} = \cup x_n .$ On pose alors $\text{cl}(x) = \bigcup_{n\in \omega} x_n$. 
  • Médiat_Suprème
    Modifié (October 2023)
    Bonjour
    Intuitivement, on ajoute tous les couples nécessaires et on itère (union sur la longueur du chemin à partir de la relation initiale). Sinon, on prend la plus petite relation transitive contenant la relation de départ
    Il ne faut pas respirer la compote, ça fait tousser.

    J'affirme péremptoirement que toute affirmation péremptoire est fausse
  • Merci @Cyrano, mais il y a un quiproquo, je parle de relations transitives, pas d'ensembles transitifs. J'ai du manquer de clarté et je m'en excuse.
  • @Médiat_Suprème, belle trouvaille pour la première définition, je n'y avais pas pensé, elle marche bien. Par contre je m'attendais à la seconde définition, et elle est problématique (c'est le piège 😅)
  • L'intersection doit marcher à la place de plus petite (du coup, je ne vois pas le problème)
    Il ne faut pas respirer la compote, ça fait tousser.

    J'affirme péremptoirement que toute affirmation péremptoire est fausse
  • Ah oui pardon.
    De toute façon l'idée de Médiat_Suprème est assez similaire. :smile:
  • Congru
    Modifié (October 2023)
    Le problème avec "plus petit" c'est qu'il faut prouver qu'un plus petit existe et la classe des transitifs qui contiennent une relation binaire donné n'est pas un ensemble.
    L'intersection marche bien, mais il faut préciser l'intersection de quel (type d') objet on prend.

    N.B: désolé pour les fautes, mon smartphone a cette manie de vouloir corriger mon orthographe.
    Edit. Généralement on justifie l'utilisation "plus petit" en disant que la propriété est stable par intersection d'ensemble non-vide dont chaque élément vérifie la propriété, mais cette justification ne marche pas ici.
    Edit2. Je viens de me relire, je m'étais mal exprimé, c'est corrigé.
  • Oui @Cyrano, d'ailleurs la clôture transitive d'un ensemble, c'est son segment initial par la clôture transitive de $\in$.
  • Congru
    Modifié (October 2023)
    Sinon l'exemple de la clôture transitive est un peu triviale pour illustrer ce que je dis, car on peut facilement contourner l'utilisation de classes ici, mais bon le but ici est de parler de l'intersection d'une classe d'ensembles.
    Et plutôt que de parler de propriétés stables par intersection non vide, on pourrait s'intéresser aux propriétés stables par intersection de classes non vides.
    Cordialement.
  • On traduit l'énoncé souhaité en langage purement ensembliste ci-dessous, le mot entier voulant alors dire "ordinal fini".
    On dit que deux objets $x,y$ appartiennent à la cloture transitive d'une relation binaire $R$ (formule à deux variables libres $a,b$ ici) lorsqu'il existe un entier $n \neq 0$ et une fonction $f$ de domaine $n+1$  $(=n \cup \{n\})$ telle que $f(0) = x$, $f(n) =y$ et pour tout $i\in n$, $R[a:= f(i), b:= f(i+1)]$. L'écriture  d'un tel énoncé en formule du premier ordre est alors immédiate.
    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$.
  • Bonjour @Congru , 2 manières de s'y prendre.
    1) On passe par l'intersection. Une relation binaire existe sur un ensemble $E$, au pire tu prends l'union des éléments de tes couples. Dès lors, en travaillant avec l'ensemble des relations binaires sur $E$, tu peux définir la plus petite comme l'intersection de toutes les relations binaires transitives sur $E$ contenant ta relation de base.
    2) Appelons $\rightarrow$ ta relation sur un ensemble $E$. La clôture transitive de $\rightarrow$ est la relation $\rightarrow^+$ définie par $x \rightarrow^+ y$ ssi il existe une suite finie $x_0,x_1,...,x_n$ (avec $n > 0$) tel que $x_0 = x$, $x_n = y$ et $\forall i, x_i \rightarrow x_{i+1}$. Je te laisse vérifier que $\rightarrow^+$ fait le travail.
  • Congru
    Modifié (October 2023)
    Bonjour,
    Merci @Foys, je crois que c'est la définition la plus naturelle (de la clôture d'une relation binaire) que tu as donnée.
    Merci @Heuristique, ta première définition est la raison pour laquelle j'ai regretté d'avoir pris l'exemple de la clôture transitive, car cette définition est parfaitement valide et elle permet de contourner le passage par les classes. Ta deuxième définition est aussi parfaitement valide et elle est à rapprocher de celle de @Foys qui l'utilise pour définir la clôture transitive d'un symbole de relation binaire.
    Merci à vous deux.
  • Georges Abitbol
    Modifié (October 2023)
    Ou sinon, soit $R$ un ensemble de couples. Soit $X$ un ensemble contenant tous les membres des couples contenus dans $R$ (il en existe un par l'axiome de remplacement, je me trompe ?). Alors la clôture transitive de $R$ est le plus petit sous-ensemble de $X\times X$ qui contient $R$ comme sous-ensemble, et qui est transitive.
    EDIT : Oups, pardon, il est trop tôt et je n'avais pas lu la réponse d'Heuristique.
Connectez-vous ou Inscrivez-vous pour répondre.