Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 15-11-2017 17:15:24

AAlex
Membre
Inscription : 13-11-2017
Messages : 9

Ensembles et Bijections

Bonjour,

On cherche à démontrer de manière ensembliste que l'ensemble des bijections entre 2 ensembles à n est n! :

on note EnsBij(A, B) l’ensemble des bijections d’un ensemble A dans un ensemble B
et on remarque que, pour tout a ∈ A et b ∈ B, on a :
            #EnsBij(A, B) = #B ∗ #EnsBij(A \ {a}, B \ {b})


Premièrement on cherche une égalité ensembliste qui relie EnsBij(A, B) et EnsBij(A \ {a}, B \ {b}), ainsi que sa preuve ensembliste.
     -> Sur ce point je ne vois vraiment pas comment faire surtout qu'on parle d'ensembles différents (A et A \ {a}) ?!?

Puis à partir du résultat précédent une démonstration récurrence que #EnsBij(A, B) = #A!
     -> Ici je pense qu'il n'y a pas trop de difficultés si on connais le résultat précédent.

Hors ligne

#2 15-11-2017 21:59:01

Yassine
Membre
Inscription : 09-04-2013
Messages : 1 090

Re : Ensembles et Bijections

Bonsoir,
Je ne pense pas que tu trouveras une égalité ensembliste entre EnsBij(A,B) et EnsBij(A\{a},B\{b}), les éléments n'ont rien à voir entre eux.
Par contre, tu peux trouver une relation qui lie leur cardinal.
L'idée générale est la suivante pour compter les bijections :
Pour construire une bijection de A vers B, je prends un élément a de A et j'essaie de lui trouver une image dans B : j'ai #B possibilités.
Une fois que je fais un choix, disons b, je suis face au même problème, sur des ensembles différents : A\{a} et B\{b}.

C'est ce qui donne la relation que tu cherches


L'ennui dans ce monde c'est que les idiots sont sûrs d'eux et les gens sensés pleins de doutes. B. Russel

Hors ligne

#3 15-11-2017 22:07:39

AAlex
Membre
Inscription : 13-11-2017
Messages : 9

Re : Ensembles et Bijections

Yassine a écrit :

Je ne pense pas que tu trouveras une égalité ensembliste entre EnsBij(A,B) et EnsBij(A\{a},B\{b}), les éléments n'ont rien à voir entre eux.

La dessus je suis entièrement d'accords et c'est ce qui me bloque mais l'énoncé demande pourtant "une égalité ensembliste qui relie EnsBij(A, B) et EnsBij(A \ {a}, B \ {b})" ....
Peut-être que cela signifie plutôt une transformation sur EnsBij(A, B) pour arriver à EnsBij(A \ {a}, B \ {b}) mais du coup c'est pas clair. Du coup ce que tu décris me parait correct, merci.

Dernière modification par AAlex (15-11-2017 22:09:41)

Hors ligne

#4 16-11-2017 09:07:12

Yassine
Membre
Inscription : 09-04-2013
Messages : 1 090

Re : Ensembles et Bijections

Bonjour,
Dans ce cas tu peux alors montrer que l'ensemble $EnsBij(A,B)$ est bijectif avec l'ensemble  $B \times EnsBij(A\setminus\{a\},B\setminus\{b\})$. Ce sera peu ou prou la même démarche  : une bijection $f$ de $A \to B$ est entièrement déterminée si je connais l'image $b=f(a)$ d'un élément quelconque $a$ et que je connais la bijection  $f|_{A\setminus\{a\}}: A\setminus\{a\} \to B\setminus\{b\}$ (restriction de $f$ à $A\setminus\{a\}$)


L'ennui dans ce monde c'est que les idiots sont sûrs d'eux et les gens sensés pleins de doutes. B. Russel

Hors ligne

#5 16-11-2017 15:12:49

AAlex
Membre
Inscription : 13-11-2017
Messages : 9

Re : Ensembles et Bijections

Ok merci beaucoup, mais du coup comment peut-on définir une telle application et montrer proprement qu' elle est bijective, [tex]\forall[/tex] [tex] Card(A) \in [1;n] [/tex] ?

Hors ligne

#6 16-11-2017 17:47:49

Yassine
Membre
Inscription : 09-04-2013
Messages : 1 090

Re : Ensembles et Bijections

Bonsoir,
Je vais un peu simplifier les notation pour que ce soit propre.
Je note $\Gamma$ l'ensemble des bijections de $A \to B$ et $\Gamma_{ab}$ l'ensemble des bijections de $A\setminus\{a\} \to B\setminus\{b\}$ pour $(a,b) \in A\times B$ quelconque.
Je vais montrer qu'on peut construite une injection de $\Gamma \to B \times \Gamma_{ab}$ et une injection de $B\times \Gamma_{ab}\to \Gamma$, ce qui montrera que les deux ensembles sont en bijection (Théorème de Cantor-Bernstein).

Pour une application $F: \Gamma \to B \times \Gamma_{ab}$, je vais noter $F(f)=(F_1(f), F_2(f))$ les composantes de l'image de $F(f)$ (on a donc $F_1(f) \in B$ et $F_2(f) \in \Gamma_{ab}$).

Soit $\gamma \in \Gamma$. Je définis alors $F_1$ et $F_2$ comme suit :
1) $F_1(\gamma) = \gamma(a)$
2) $F_2(\gamma): A\setminus\{a\} \to B\setminus\{b\}$ telle que $\forall x \in A\setminus\{a\}$, $F_2(\gamma)(x) =
  \begin{cases}
    \gamma(x)       & \quad \text{si } x \neq \gamma^{-1}(b)\\
    \gamma(a)  & \quad \text{si } x = \gamma^{-1}(b)
  \end{cases}$

Tu peux alors montrer que $F$ ainsi définie est injective.

L'injection dans l'autre sens est plus simple. Soit $(b',\sigma) \in B \times \Gamma_{ab}$, je définis alors $G(b',\sigma) \in \Gamma$ par :
1) $G(b',\sigma)(a) = b'$
2) $\forall x \neq a$, $G(b',\sigma)(x) = \begin{cases}
    \sigma(x)       & \quad \text{si } \sigma(x) \neq b'\\
    b  & \quad \text{si } \sigma(x) = b'
  \end{cases}$
Ici, c'est encore plus simple de montrer l'injectivité.

Une fois qu'on montre que $F$ et $G$ sont injectives, on peut conclure que $\Gamma \simeq B \times \Gamma_{ab}$

[EDIT]
Pour être complet, il faudrait également montrer que $F$ et $G$ sont bien définies et qu'en particulier, $F_2(\gamma)$ est bien un élément de $\Gamma_{ab}$, ce qui ne pose pas de difficulté particulière.

[EDIT2]
L'expression de $G$ était incorrecte. J'étais allé un peu vite en besogne !
by the way, tu peux également montrer que $G=F^{-1}$

Dernière modification par Yassine (18-11-2017 08:02:48)


L'ennui dans ce monde c'est que les idiots sont sûrs d'eux et les gens sensés pleins de doutes. B. Russel

Hors ligne

#7 16-11-2017 18:46:23

AAlex
Membre
Inscription : 13-11-2017
Messages : 9

Re : Ensembles et Bijections

Bonsoir,
un grand merci, les explications sont très clairs. Je me penche maintenant sur les démonstrations d'injections.
Bonne soirée.

Hors ligne

Réponse rapide

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quel est le résultat de l'opération suivante (donner le résultat en chiffres)?
soixante dix-sept plus trente deux
Système anti-bot

Faites glisser le curseur de gauche à droite pour activer le bouton de confirmation.

Attention : Vous devez activer Javascript dans votre navigateur pour utiliser le système anti-bot.

Pied de page des forums