Applications entre ensembles — Les-mathematiques.net The most powerful custom community solution in the world

Applications entre ensembles

Bonjour,

Je bute sur l'exercice suivant. Soit $X$ et $Y$ des ensembles non vides, $f$ une application de $X$ dans $Y$ et $g$ une application de $Y$ dans $X$. Montrer qu'il existe une partie $A$ de $X$ telle que $g(Y \setminus B)=X \setminus A$ (avec $f(A)=B$).

En raisonnant par analyse-synthèse, j'ai montré que si $A$ et $B$ existent, on a alors $g^{-1}(A) \subset f(A)$ et $f^{-1}(Y \setminus B) \subset g(Y \setminus B)$. Cela n'avance pas.

On peut partir aussi de : si $f$ est surjective, alors $A=X$ convient, et si $g$ est surjective, alors $A=\emptyset$ convient, et enlever ou ajouter des éléments à $A$.

Une indication serait bienvenue. Merci d'avance.

Réponses

  • @JP : si une telle partie $A$ existe telle que $f(A)=B$, il est clair que l'application $h:A\to{}B$ qui coïncide avec $f$ sur $A$, est canoniquement surjective. Peut-être est-ce une piste ? A voir.

    S'aider d'un schéma !
  • Une indication : considérer l'ensemble $\mathcal{A}:=\{E\subset X\mid X\setminus E\subset g(Y \setminus f(E)) \}$.

    Montrer que $\mathcal{A}$ est non-vide et qu'on peut obtenir $A$ à partir de $\mathcal{A}$.


    PS. Mon idée à l'air de marcher mais il faut détailler pour en être sûr... donc à voir.
  • Merci à vous.

    TP, il me semble que ça ne va pas marcher, car on ne peut pas oblitérer $Y \setminus B$. Oui, les schémas aident beaucoup !

    raoul.S, j'imaginais quelque chose comme ça, car on ne peut pas ajouter ou enlever des éléments un par un, à un ensemble pour en obtenir un autre vérifiant une certaine propriété, cela suppose implicitement que les ensembles sont finis ou dénombrables ?
    $\cal A$ est non vide ($X \in \cal A$). A l'autre bout, si $g$ est surjective, $\emptyset$ convient. Il faut diminuer $X$ jusqu'à obtenir un ensemble qui convient. Une technique est de considérer $A=\bigcap_{E \in \cal A} E$ et de vérifier que $A$ appartient encore à $\cal A$ :
    $X \setminus \bigcap_{E \in \cal A} E = \bigcup_{E \in \cal A} X \setminus E = \ldots$, je vais vérifier.
    On aura alors le plus petit qui vérifie l'inclusion.
    Avec $A$ le plus petit qui vérifie $X \setminus A \subset g (Y \setminus f(A))$, il faut alors montrer l'égalité.
  • @Julia Paule oui c'est ça. Il me semble qu'on devrait bien obtenir $X \setminus A = g (Y \setminus f(A))$ à la fin.
  • Oui merci. L'intersection $A$ appartient bien à $\cal A$. Alors si $X \setminus A \ne g(Y \setminus f(A))$, alors $\exists x \in g(Y \setminus f(A)), x \notin X \setminus A $, i.e. $x \in A$.

    Alors $X \setminus (A \setminus \{x \})=(X \setminus A) \cup \{x \} \not \subset g(Y \setminus f(A \setminus \{x \}))=g(Y \setminus f(A)) \cup g(f(x))$ ou $g(Y \setminus f(A))$, ce qui est impossible dans les 2 cas.

    Merci beaucoup.
  • Lemme (Knaster-Tarski) : Une application $h : \mathcal{P} (X) \rightarrow \mathcal{P}(X) $ croissante pour l'inclusion possède un point fixe.

    Soit $K = \{ x \in \mathcal {P} (X) \mid x \subset h(x) \} $ et soit $ s = \bigcup K $ la borne supérieure de $K$.

    Pour tout $x$ dans $K$, on a $ x \subset s $ et $ x \subset h(x) \subset h(s) $. Ainsi $h(s) $ est un majorant de $K$ et $s \subset h(s)$. Mais comme $ h(s) \subset h(h(s)),\ h(s) $ est dans $ K ,$ d'où $ h(s) \subset s $ et finalement, $ h(s) = s. $ $ \square $

    L'application de $\mathcal{P}(X) $ dans $ \mathcal{P}(X) : U \mapsto X\setminus g(Y\setminus f(U)) $ est croissante (pour l'inclusion) en tant que composée de quatre applications, deux croissantes et deux décroissantes. Elle a donc un point fixe $ A = X\setminus g(Y\setminus f(A)) $ et l'on a $ X\setminus A = g(Y\setminus f(A)). $

    Lorsque $f$ et $g$ sont injectives, c'est le théorème de Cantor-Bernstein : la bijection cherchée est $b(x) = f(x)$ pour $x$ dans $A$ et $ b(x) = g ^{-1} (x) $ pour $x$ dans $X\setminus A.$
  • @GG : je connaissais ce résultat sous le nom de "théorème du point fixe". J'ignorais qu'il était dû à Knaster-Tarski.
  • @GG : le lemme dont tu parles (et la preuve de Cantor-Bernstein qui suit) rejoint une discussion qu'on a eue avec CC et Maxtimax il y a quelques semaines (mois ?). Sur les 3 preuves de Cantor-Bernstein que je connais, celle-ci est conceptuellement la plus difficile à appréhender, mais elle présente sur les deux autres l'énorme avantage de ne pas avoir besoin de la connaissance de $\omega$.

    C'était mon quart d'heure philosophique...
  • @Martial, oui, disons que c'est la preuve du lemme qui n'est pas évidente. Quand je l'avais cherchée par mes propres moyens, j'avais considéré la chaîne $\emptyset \subset h(\emptyset) \subset h(h((\emptyset)) \subset ...$ et pensé naïvement et à tort que sa réunion était un point fixe. J'étais resté bloqué. L'astuce, c'est de prendre la réunion de TOUS les ensembles inclus dans leur image. C'est d'ailleurs plus clair visuellement dans la formulation originelle du lemme en termes de treillis complet.

    Quant à son emploi dans la question de Julia Paule, il est plus que naturel.
    On part d'un ensemble $A$, on construit successivement $f(A), Y\setminus f(A), g(Y\setminus f(A))$, et on se demande si ce dernier ensemble est complémentaire de $A$. La première idée qui vient à l'esprit, c'est de faire plusieurs essais avec différentes valeurs de $A$, et l'on voit que lorsque $A$ croît de $\emptyset$ à $X, g(Y\setminus f(A))$ décroît de $g(Y)$ non complémentaire de $\emptyset$ à $g(Y\setminus f(X))$ inclus dans $X$.
    De là à introduire un complément supplémentaire et à chercher un point fixe, il n'y a qu'un pas !

    (Merci AD pour la correction. Ce "setminus" est plus joli en effet !)
  • Ok GG pour ta démonstration. C'est assez général. On peut prendre aussi la fonction $U \mapsto g(Y\setminus f(X \setminus U))$.
    Je vais regarder la démonstration du théorème de Cantor-Bernstein qui en découle, qui parait du coup très simple, avec ta fonction (la mienne ne marche peut-être pas).
  • Merci beaucoup GG. Peu importe la fonction utilisée pour la démonstration de l'existence de $A$.

    Montrer que la fonction $b : X \rightarrow Y$ est une bijection est très facile.
  • De rien ! :-)
  • Cette démonstration du théorème de Cantor-Bernstein est intéressante. J'ai essayé d'en comprendre l'idée.

    $f : X \rightarrow Y$ injective, donc $f$ fournit une bijection : $X \rightarrow f(X)$.
    Reste à atteindre $Y \setminus f(X)$. On peut le faire par $g^{-1}$. Mais il faut se placer sur $g(Y)$.
    $g : Y \rightarrow X$ injective, donc $g^{-1}$ fournit une bijection : $g(Y) \rightarrow Y$.
    On peut restreindre $g^{-1}$ à $ g(Y\setminus f(X))$ pour atteindre $Y \setminus f(X)$.
    Alors $g^{-1}$ fournit une bijection : $g(Y \setminus f(X)) \rightarrow Y \setminus f(X)$.
    Par ces deux applications injectives $f$ et $g^{-1}$, on atteint $f(X) \cup Y \setminus f(X)= Y$.
    Mais il y a redondance : $g(Y \setminus f(X)) \subset X$.
    On peut prendre $X$ plus petit.
    En partant d'une partie $A$ de $X$, $f$ et $g^{-1}$ fournissent encore les injections : $A \rightarrow f(A)$ et $g(Y \setminus f(A)) \rightarrow Y \setminus f(A)$, qui atteignent $f(A) \cup Y \setminus f(A)= Y$.
    Alors s'il existe $A \subset X$ telle que $X \setminus A = g(Y \setminus f(A))$, on a gagné.
    Pour $A=\emptyset$, on a $X \setminus A \supset g(Y \setminus f(A))$.
    Pour $A=X$, on a $X \setminus A \subset g(Y \setminus f(A))$.
    On se doute qu'en partant d'une de ces deux extrémités, on a des chances d'obtenir une égalité.
    C'est ce qu'on a fait dans les messages précédents.

    Martial, en quel sens trouves-tu cette démonstration plus difficile à appréhender que les autres démonstrations du théorème de Cantor-Bernstein ?
  • @Julia : celle avec les danseurs et les danseuses est facile à comprendre, même par quelqu'un qui n'a jamais fait de maths.
    Celle avec les ancêtres est pour ainsi dire triviale.
    Dans la démonstration ci-dessus il faut faire preuve de davantage d'abstraction, et penser au théorème du point fixe.

    Mais ce n'est que mon point de vue, et on peut penser différemment.
  • Martial, c'est vrai que dans cette démonstration, on a du mal à imaginer, avec le théorème du point fixe, comment on peut obtenir une égalité à coup sûr (un $A$ qui fait l'égalité).
    Si on imagine qu'on ajoute au fur à mesure des éléments au membre de gauche, on en ajoute aussi au membre de droite, mais qui ne vont pas forcément appartenir à l'image de $g$, donc on n'aura plus l'inclusion pendant un certain temps, mais on n'aura pas non plus à ce moment-là l'inclusion inverse, juste une non-inclusion dans les deux sens. Enfin il me semble. Au fur et à mesure qu'on continue à ajouter des éléments à gauche, on ajoute des éléments à droite, qui eux vont finir par tous appartenir à gauche. Mais on ne voit pas bien où se fait le basculement.

    Cela se comprend un peu mieux avec la solution de raoul.S, en prenant l'intersection $A$ de toutes les parties qui vérifient l'inclusion : membre de gauche $\subset$ membre de droite. C'est la plus petite partie qui vérifie l'inclusion. Toute partie plus petite ne la vérifie pas. On peut alors imaginer que $A$ vérifie l'égalité.

    Les autres démonstrations, vues dans Wiki : https://fr.wikipedia.org/wiki/Théorème_de_Cantor-Bernstein, font appel à une suite infinie. La 3ème démonstration est celle des ancêtres. J'imagine que celle avec les danseurs et les danseuses est la 1ère ? Ces deux démonstrations restent-elles valables dans le cas où les ensembles sont finis ?
  • Oui c'est cela. J'ai simplement remplacé les spectateurs et les places par des danseurs et des danseuses, ça fait plus romantique, lol.

    Le cas fini est trivial, pas besoin de Cantor dans ce cas-là. Ce Monsieur s'intéressait essentiellement à l'infini.
  • Ok merci Martial. Mais ces démonstrations ne me paraissent pas faciles à comprendre par quelqu'un qui n'a jamais fait de maths, il faut déjà comprendre une bijection d'un ensemble dans une partie propre (que deviennent les autres éléments, ceux qui ne sont pas dans la partie propre ? ou bien : la partie propre parait trop petite pour accueillir tout le monde). Je veux dire qu'on n'a pas naturellement l'esprit préparé à comprendre l'infini.

    C'est trivial avec les cardinaux pour les ensembles finis.
  • Bonjour,

    La fin d'un exo me pose problème.
    $E$ et $F$ sont deux ensembles et on suppose qu'on a une injection $f: E\to F$ et une injection $g: F\to E$.

    On a posé : $X = \{A\in P(E)\mid g(F\setminus f(A)) \subset E\setminus A\}$.

    J'ai prouvé dans les premières questions que $X$ est non vide et que $B=\cup_{A\in X} A$ est le plus grand élément de $X$.
    Puis que $B = E\setminus g(F\setminus f(B))$.

    On veut maintenant définir une bijection de $E$ dans $F$.

    Merci pur votre aide.
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!