Définition d'un ensemble transitif

PierreCap
PierreCap
dans Fondements et Logique
Bonjour c'est encore moi. En fait, plus j'avance dans l'apprentissage des ordinaux, et plus je me pose des questions basiques (avancé-je vraiment ?) Bref, voilà ce qui m'amène. La définition d'un ensemble transitif est : $$\forall x \in X , x\subseteq X \qquad (1)$$
Jusque là c'est bon. Le problème est que dans Wikipédia ils disent que cette définition est équivalente à la suivante :
$$\cup X \subseteq X \qquad (2)$$
Je comprends le sens $(1) \Rightarrow (2)$, par contre pour $(2) \Rightarrow (1)$ je crois que c'est pas vrai. Par exemple si :
    $X=\{X_1, X_2, X_3\}$ avec $X_1 \subset X_3$ et $X_2 \subset X_3$
alors on a $\cup X = X_3 \subset X$ mais pourtant $X$ n'est pas transitif puisque $X_3$ est le seul élément à être aussi une partie. Je me trompe ?
«1

Réponses

  • Poirot
    Poirot
    Bah non, qu'est-ce qui te dit que $X_3 \subset X$ ?
  • PierreCap
    PierreCap
    Et avec $X=\{X_1, X_2, X_3, \{X_3\} \}$ ?
  • Maxtimax
    Maxtimax
    Relis la remarque de Poirot
  • PierreCap
    PierreCap
    Oui maintenant on a $\cup X=\{ X_3 \cup \{X_3\} \}$ c'est pas mieux. Je suis convaincu. Mais alors comment démontre-t-on le sens $(2) \Rightarrow (1)$ ?
  • bisam
    bisam
    Commence naturellement : Soit $x\in X$ et $y\in x$. Alors $y\in \cup X$ et donc par hypothèse sur $X$, $y\in X$. Ainsi $x\subset X$.
  • PierreCap
    PierreCap
    Merci beaucoup bisam pour tes lumières. C'est simple quand on sait :-)
  • PierreCap
    PierreCap
    J'aurais une question subsidiaire, dans la même veine. Par définition, un ordinal est un ensemble transitif bien ordonné par la relation d'appartenance $\in$. Je suppose donc qu'il existe des ensembles bien ordonnés par $\in$ qui ne sont pas transitifs. Auriez-vous un exemple ?
  • christophe c
    christophe c
    N'importe quel singleton (sauf 1 que je te laisse trouver)
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • PierreCap
    PierreCap
    Bonjour Christophe. J'essaye de comprendre voilà mon raisonnement.
    Soit $X \neq \emptyset $ et soit $\le$ une relation d'ordre définie sur $\{ X \}$. On a donc $X\le X$.
    Les parties de $\{ X \}$, qui sont $\emptyset$ et $X$, ont toutes deux un plus petit élément donc $(\{ X \} , \le)$ est bien ordonné.
    Tout singleton est donc bien ordonné ? Je suppose que le singleton $\{ \emptyset \}$ échappe à la règle mais pourquoi ?
    Pour la relation d'appartenance il faut prendre la relation élargie "$\in ou =$"
  • christophe c
    christophe c
    C'est l'ORDINAL 1
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • PierreCap
    PierreCap
    D'accord, donc il est transitif, contrairement aux autres singletons.
    Sinon peux-tu me confirmer si tout singleton est bien ordonné ? Je l'ignorais.
  • Poirot
    Poirot
    Ça ne veut rien dire en soi. Par contre, si on met l'unique ordre possible sur un singleton, effectivement un tel singleton est alors bien ordonné. Ça a l'air de t'étonner ?
  • PierreCap
    PierreCap
    En fait je pense que c'est juste une conséquence des définitions non ? et que par conséquent il est bon de le savoir
  • christophe c
    christophe c
    Tu as même qu'un ensemble est bien ordonné par tout ordre ssi il est bien ordonné par = ssi il contient au plus un élément :-D
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • PierreCap
    PierreCap
    Tu voulais écrire je pense "Tu as même qu'un ensemble est bien ordonné par tout ordre ssi il est bien ordonné par = ssi il contient au plus un élément" ? :-)
  • Math Coss
    Math Coss
    L'égalité est une relation d'ordre total sur les singletons et uniquement sur les singletons (et l'ensemble vide) ; dans ces cas, c'est un bon ordre.
  • Poirot
    Poirot
    Il n'y a pas de problème dans la réponse de CC.
  • PierreCap
    PierreCap
    Ah d'accord, l'égalité peut être une relation d'ordre ! Je n'avais pas envisagé cette option :-)
  • PierreCap
    PierreCap
    Pour en revenir à ma question (je demandais si quelqu'un connaît un exemple d'ensemble bien ordonné par la relation $\in$ qui ne soit pas transitif). Christophe a proposé les singletons. Je crois que j'ai trouvé un autre exemple, ce sont les ensembles $a_i$, pour $i\ge 2$, construits de la manière suivante :
      $a_0 \neq \emptyset$ $a_1 = \{ a_0\}$ $a_2 = \{ a_0, a_1\}$ $a_3 = \{ a_0, a_1,a_2\}$ etc
    Ils sont construits comme des ordinaux, sauf que le 1er ensemble n'est pas $\emptyset$, donc n'est pas une partie de $a_i$.
  • christophe c
    christophe c
    Il te faut l'axiome de fondation. Un ensemble r tel que r={0; r} est transitif par exemple
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • GG
    GG
    @cc, dans l'exemple de PierreCap, en prenant a0 = 1, les ai (i > 0) et l'ensemble des ai ne sont-ils pas bien ordonnés par $\in $ et non transitifs, sans besoin de AF ?
  • christophe c
    christophe c
    Si mais la ça devient très ton exemple du fait que tu as précisé a0
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • PierreCap
    PierreCap
    Bonjour Christophe. Un ordinal est, par définition, un ensemble transitif strictement bien ordonné par la relation $\in$. J'aurais donc du dire que je cherchais un ensemble dans lequel $\in$ est un bon ordre strict et qui n'est pas transitif. Dans ce cas l'axiome de fondation n'est pas nécessaire puisque la relation d'ordre étant antiréflexive on n'aura jamais $a_i \in a_i$. C'est mieux ?
  • christophe c
    christophe c
    Ce que je voulais dire est qu'il est "nécessaire" pour que TON EXEMPLE général marche, pas pour TROUVER des exemples qui marche.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • PierreCap
    PierreCap
    Je ne comprends pas ce que tu veux dire. Mon exemple général marche puisqu'il est strictement bien ordonné par la relation $\in$ et qu'il n'est pas transitif. J'avais juste mal rédigé l'énoncé initial, je l'ai corrigé et disant que la relation d'ordre est stricte.
  • Poirot
    Poirot
    Justement, pour affirmer que ton ensemble est strictement bien ordonné, tu as besoin de l'axiome de fondation.
  • PierreCap
    PierreCap
    Ah bon ? Je ne cherche pas à démontrer que mon $a_i$ est strictement bien ordonné, je l'affirme, par définition.

    Je fais comme pour la définition d'un ordinal : elle ne nécessite pas AF (d'après ce que j'ai lu par exemple chez JL Krivine) et pourtant un ordinal est par définition strictement bien ordonné. C'est écrit par exemple ici.
  • christophe c
    christophe c
    "je fais comme". Mais ça ne marche pas. Je te le redis si r = {0;r} la partie {r} de r n'a pas de minimum si même si tu voulais définir ton ordre par "x dans y ET x différent de y" je mettrai juste un peu plus de secondes à te taper un graphe 3 cyclique de mon téléphone.

    Ce genre de confusion est d'ailleurs UNE DES RAISONS qui m'ont amené à te proposer une AUTRE définition bien plus simple et n'évoquant aucune idée d'ordre du mot ordinal. Tu n'es pas le premier qui "tourne bourrique" avec la definition usine à gaz de l'Académie.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • christophe c
    christophe c
    Cela dit ton idée est tout à fait respectable et respectée. On construit des tas de choses avec ce genre d'idées qui ont donné de célèbres théorèmes de consistance relative.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • PierreCap
    PierreCap
    Je te crois sur parole Christophe je l'enregistre dans une case mémoire. Malheureusement je ne suis pas à la hauteur pour comprendre tes arguments. Par exemple cet ensemble qui se définit par r = {0 ; r} ? Un jour j'espère ... :-)
  • christophe c
    christophe c
    Je ne l'ai pas défini je l'ai supposé. Bon courage et bravo pour ta patience.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • GG
    GG
    @cc, à propos de ta définition personnelle, il est clair qu'un ordinal la vérifie et que réciproquement un ensemble A la vérifiant coïncide avec le plus petit ordinal qui n'appartient pas à A. Par contre, j'ai passé un bon moment à chercher à montrer directement que $\subset $ est une relation de bon ordre sur A, et à ma grande honte (je plaisante), je n'y suis pas parvenu (tes habituelles fameuses trois lignes de l'autre fil où tu en parles !). Par exemple, si P est une partie non vide de A, $\bigcap $ P est bien un minorant de P, élément de A, mais je ne vois pas ce qui le contraint à être aussi un élément de P.
    Ça doit sans doute crever les yeux, mais je doute fortement que PierreCap trouvera ta définition "bien plus simple" que l'officielle (sans compter qu'on ne peut décemment pas en faire l'impasse) !
  • christophe c
    christophe c
    C'est plus simple, tu n'as même pas besoin de A. Si X n'est pas vide l'intersection e des éléments de X qui est évidemment l'ensemble de ses parties transitives avec un doute juste pour e lui même est le minimum de X (sauf si e est dans e).

    Tu es donc juste ramené à prouver qu'aucun ordinal ne se contient lui même comme élément. Et il suffit même de prouver qu'aucun ordinal ne contient de vice. Mais l'ensemble r des éléments d'un ordinal s qui ne contiennent pas de vice est transitif et si r n'est pas s il est dans s et tu as la contradiction que r est dans r.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • christophe c
    christophe c
    Vice abrège ensemble x tel que x dans x.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • christophe c
    christophe c
    Pour le confort de tous, je rappelle la définition:
    $<<x$ est un ordinal $>>$

    est une abréviation de
    $<<$ pour tout $y: ([y\in x]$ si et seulement si $[y\subset (x \cap P(y))$ et $y\neq x])>>$
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • GG
    GG
    Excuse-moi cc, je suis un peu bouché. J'ai un ordinal A (selon ta définition).
    Je prends une partie non vide quelconque P de A, et je veux montrer qu'il y a dans P un élément qui est inclus dans tous les éléments de P.
    Peux-tu refaire la démonstration, en utilisant mes lettres, stp ?
  • christophe c
    christophe c
    J'écris un pdf pour faire une V2 d'un article je te mettrai un lien. Avec ma définition il est plus long de prouver qu'un élément d'un ordinal est un ordinal (enfin plus long est un bien grand mot).

    Donc ta volonté est artificiellement rallongeante puisqu'il est plus élégant de prouver d'abord qu'un ensemble d'ordinaux a un minimum PUIS ensuite de prouver que ça implique que les ordinaux sont bien ordonnés CAR leurs éléments sont des ordinaux.

    De mon téléphone
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • GG
    GG
    Ah, OK, merci.
  • christophe c
    christophe c
    D'un pc.

    $x$ est un pordi abrégera $x$ est élément d'au moins un ordinal

    $x$ est un vice abrégera $\exists y\in x: y\in y$

    Comme déjà dit plus haut: il est "évident" (trivial et rapide) que:

    1/ Tout ensemble d'ordinal a un minimum pour $\subset$ (ou est vide), et que pour deux ordinaux $a,b: a\in b$ ou $a=b$ ou $b\in a$.

    2/ Aucun pordi n'est un vice.

    3/ Soit $a$ le plus petit des ordinaux tel que $b:=a\cap ON \neq a$.

    4/ $b$ est une partie transitive de $a$ car un élément de $b$ est un ordinal qui ne contient que des ordinaux de $a$, donc de $b$.

    5/ Donc $b\in a$. Soit $c$ tel que $c\neq b$ et $c$ est transitif et $c\subseteq b$. Soit $d$ un ordinal de $b\setminus c$.

    6/ Alors $c\subset d$

    7/ donc $c=d$ ou $c\in d$. Dans tous les cas, $c\in b$.

    8/ Donc $b$ est un ordinal

    9/ Donc $b\in b$.

    Au cas où tu t'étonnerais de cette apparente longueur de preuve (bon, je l'ai rallongée en numérotant), je peux te proposer (c'est assez long et technique) une preuve d'une formalisation de l'énoncé suivant:

    Il sera toujours dur de prouver que 2 ordinaux sont comparables ou dur de prouver qu'un ordinal ne contient que des ordinaux.

    La raison à ça est que sinon, il y aurait un jeu borélien non déterminé assez facile à deviner, or on sait prouver (Harvey Friedman et Tony Martin) que tous les heux boréliens sont déterminés ET que prouver ça est dur "forcément dur".
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • GG
    GG
    OK, merci. J'en resterai à la définition standard qui me semble beaucoup plus intuitive et simple pour mon petit cerveau ! :-)
  • christophe c
    christophe c
    Oui de toute façon quand ça devient du par coeur, tout ça c'est pareil, tu ne le prouves qu'un fois. Par contre avec mes définitions, la théorie s'enseigne en une page, toute preuve donnée alors qu'avec l'approche usuelle, il faut 5 à 10 fois plus.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • christophe c
    christophe c
    En fait il y a plus simple!
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • christophe c
    christophe c
    On peut procéder comme suit, et tout devient trivial, mais en plus court.

    $<<x$ est un prodinal$>>$ abrège $<<x$ est l'ensemble de ses parties transitives autres que lui-même$>>$.

    Autrement dit, je reprends la définition que j'ai donnée du mot "ordinal" en l'appelant "prodinal".

    Puis: $<<x$ est un ordinal$>> :=<<x$ est un prodinal qui ne contient que des prodinaux$>>$.

    Les preuves sont alors encore raccourcies au point de devenir quasiment des constats évidents (sauf erreur).
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • PierreCap
    PierreCap
    Excusez-moi, je reviens à mes petits problèmes avec une nouvelle question, concernant les ensembles transitifs :
      Soit $X$ un ensemble d'ordinaux tel que $\forall x,y \in X \ , \ x \in y \Rightarrow x \subset y$
    Comment démontrer que $X$ est transitif (sans supposer que $X$ a un plus grand élément) ?

    Je pense avoir trouvé une méthode en posant $Y= X \cup \{ X \}$. Un élément de $Y$ est soit un élément de $X$, soit égal à $X$, qui est maintenant le plus grand élément de $Y$. La formule ci-dessus peut donc s'étendre à $Y$ :
      $\forall x,y \in Y \ , \ x \in y \Rightarrow x \subset y$
    En donnant à $y$ la valeur $X$ (et donc à $x$ une valeur dans $X$), on obtient :
      $\forall x \in X \ , \ x \in X \Rightarrow x \subset X$
    Ou plus simplement :
      $\forall x \in X \ , \ x \subset X$
    Cette démonstration est-elle correcte ? Je la trouve un peu tirée par les cheveux, il n'y a pas plus simple ?
  • GG
    GG
    @cc, excuse-moi, je suis lent à comprendre ! Tu as écrit plus haut :

    Tu es donc juste ramené à prouver qu'aucun ordinal ne se contient lui même comme élément. Et il suffit même de prouver qu'aucun ordinal ne contient de vice. Mais l'ensemble r des éléments d'un ordinal s qui ne contiennent pas de vice est transitif et si ...

    Qu'est-ce qui empêcherait la partie r de ton ordinal s (selon ta définition) d'avoir par exemple { { $ \alpha, \varnothing $ } } comme élément, avec $\alpha $ = {$\alpha $}, auquel cas r ne serait pas transitive ?
  • christophe c
    christophe c
    L'élément que tu cites n'est lui même pas transitif donc pas dans s donc pas dans r.
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • GG
    GG
    Ah oui, merci. En fait, je pensais à {$ \varnothing, \alpha $, {$ \varnothing, \alpha $ } } qui est bien élément de s, mais plus de r !
  • christophe c
    christophe c
    Les éléments de S étant transitifs ceux de r aussi et si un élément d'un élément de r contient un vice l'élément de r aussi donc r est transitif
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • PierreCap
    PierreCap
    Oubliez ma question, c'était un faux problème. La question était plutôt :
      Soit $X$ un ensemble tel que $\forall x,y,z \in X \ , \ (x \in y \ \text{ et } \ y\in z) \Rightarrow x \in z$
    Comment démontrer que $X$ est transitif ? Mais j'ai trouvé une démonstration donc la question est close.
  • christophe c
    christophe c
    Ton théorème étant faux, si ta preuve ne contient pas d'erreur (vérifie bien quand meme avant) tu vas devenir le scientifique et même l'homme le plus célèbre de tous les temps. Prends ton temps. Mais vérifie!
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
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 15

CidrolinDomHeuristiqueSnbiguine_equationmanustfj +8 Invités