Forum de mathématiques - Bibm@th.net

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.

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

AAlex

Membre

Inscription : 13-11-2017

Messages : 9

Re : Ensembles et Bijections

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)

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\}$)

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] ?

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)

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.