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 =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 \subset g(Y \setminus $. 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.
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 =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 \subset g(Y \setminus $. 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.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
S'aider d'un schéma !
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.
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é.
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.
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.$
C'était mon quart d'heure philosophique...
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 !)
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).
Montrer que la fonction $b : X \rightarrow Y$ est une bijection est très facile.
$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 ?
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.
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 ?
Le cas fini est trivial, pas besoin de Cantor dans ce cas-là. Ce Monsieur s'intéressait essentiellement à l'infini.
C'est trivial avec les cardinaux pour les ensembles finis.
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.