Combinatoire et dénombrement

mpsi_quatre · December 2017

Salut,

Je profite de Noël pour réviser les chapitres du début d'année et notamment celui que j'ai trouvé le plus dur et où j'ai eu ma seule mauvaise note en devoir pour le moment : "COMBINATOIRE ET DÉNOMBREMENT". Ce dernier se trouve dans la partie "Fondements" de notre cours donc c'est pour ça que je l'ai mis ici. J'ai décidé de reprendre tout le cours et de vraiment comprendre les démonstrations qui n'ont pas été totales dans ce cours, nous avons juste parfois lancé les idées par manque de temps parfois.

L'outil principal est la construction du cardinal et le premier théorème (et peut-être plus important du cours ?) est celui-là : l'unicité du cardinal d'un ensemble. Pour rappel, on dit que deux ensembles $E$ et $F$ ont même cardinal s'il existe une bijection de $E$ sur $F$. On note $|E|=|F|$. Un ensemble $E$ est dit fini s'il existe $n\in\mathbb N$ et une bijection $f:[|1,n|]\rightarrow E$. Dans ce cas, on dit que $E$ est de cardinal $n$ et on note $|E|=n$.

Voilà comment je rédigerais le plus proprement possible la preuve du théorème. D'abord un lemme : soit $(n,m)\in\mathbb N^2$ tel que $n\neq m$. Alors il n'existe pas de bijection de $[|1,n|]$ dans $[|1,m|]$. Preuve du lemme : montrons le résultat par récurrence sur $n\in\mathbb N$. On note $\mathcal P(n)$ la propriété : "$\forall m\in\mathbb N$ tel que $n\neq m$, il n'existe pas de bijection de $[|1,n|]$ dans $[|1,m|]$".
Si $n=0$ alors pour tout $m\neq n$, on a $m\geq 1$ et les applications de $[|1,n|]=\emptyset$ dans $[|1,m|]\neq\emptyset$ sont non surjectives. Donc $\mathcal P(0)$ est vraie.
Soit $n\in\mathbb N$ tel que $\mathcal P(n)$ soit vraie. Soit $m\in\mathbb N$ tel que $n+1\neq m$ (*). Supposons par l'absurde qu'il existe une bijection $f:[|1,n+1|]\rightarrow [|1,m|]$, ce qui impose $m\geq 1$. Alors $f$ induit une bijection $\overline f$ de $[|1,n|]$ dans $[|1,m|]\backslash\{f(n+1)\}$, lui-même en bijection avec $[|1,m-1|]$, via $g:[|1,m|]\backslash\{f(n+1)\}\rightarrow [|1,m-1|]$ définie par $g(x)=x$ si $x<f(n+1)$ et $g(x)=x-1$ si $x>f(n+1)$. Donc $g\circ\overline f$ est une bijection de $[|1,n|]$ dans $[|1,m-1|]$, ce qui oblige, parce que $\mathcal P(n)$ est vraie, que $n=m-1$, contredisant (*). Donc $\mathcal P(n+1)$ est vraie.

Maintenant la preuve du théorème :
Soit $E$ un ensemble. S'il existe $(n,m)\in\mathbb N^2$ tel que $E$ soit en bijection avec $[|1,n|]$ et $[|1,m|]$ via $f:[|1,n|]\rightarrow E$ et $g:E\rightarrow [|1,m|]$. Alors $[|1,n|]$ et $[|1,m|]$ sont en bijection via $g\circ f$, ce qui impose, d'après le lemme, que $n=m$, entier que l'on note $|E|$.

J'aurai plein d'autres questions sur la suite du cours mais déjà là, on a juste montré l'unicité du cardinal pour un ensemble fini non ? On peut en déduire facilement que l'unicité du cardinal est également vraie pour un ensemble infini ?

AD · December 2017

Bonsoir, juste pour le pinaillage.

mpsi_quatre a écrit:

Soit $m\in\mathbb N$ tel que $~\cdots~$ lui-même en bijection avec $[|1,m-1|]$,

Que veut dire $m-1$ si $m=0\in\mathbb N$ ?
Alain

mpsi_quatre · December 2017

Sauf erreur, le cas $m=0$ ne peut pas se produire parce que sinon $[|1,m|]=\emptyset$ et l'application $f:[|1,n+1|]\rightarrow [|1,m|]$ ne peut pas être bijective.

AD · December 2017

Alors dans ce cas, quand tu définis $m$, limite le à $\mathbb N^*$. :-)
Alain

mpsi_quatre · January 2018

Voilà j'ai édité. Et pour ma question à la fin du message ?

Maxtimax · January 2018

Ta dernière question n'a de sens que si tu précises ce que tu appelles "l'unicité du cardinal pour les ensembles infinis". Puisqu'elle n'a pas de sens en ce moment, ce qui suit n'est pas précis; mais a priori la réponse sera non.

christophe c · January 2018

Je confirme que ça n'a pas de sens (que veut dire unicité). Peut-être veux-tu parler de transitivité de l'équipotence.

D'autre part, il est préférable (tu sauras peut-être un jour pourquoi) de prendre $\{0;1;2;3;...;n-1\}$, car c'est "la définition officielle (toute controverse respectée, mais mise à part) de $n$ qui est .. de cardinal $n$.

Par ailleurs, sache que le thème présent est assez mal présenté par l'académisme dans le sens qu'on démontre souvent du vent. Voici pourquoi:

1) En fait, les noms donnés aux différents ensembles sont déjà "bien choisis" pour que tout aille bien. Par exemple, $a\times b:=\{(x,y)\mid x\in a$ et $y\in b\}$ ou encore $a^b:=\{f\mid f$ est une application de $b$ dans $a\}$. On pourrait varier les exemples. Ces ensembles ont des cardinaux, mais surtout peuvent être considérés comme des noms (que l'on peut utiliser tels quels) de leurs cardinaux (après tout un objet peut avoir plusieurs noms) de sorte que seul le signe "=" est à toucher à la fin (à remplacer par disons $==$ qui abrège "sont en bijection).

2) Par exemple***, $a\times b==b\times a$ et la bijection est $(x,y)\mapsto (y,x)$ ou encore $a\times (b+c) == (a\times b)+(a\times c)$ ou encore [small]a^{u+v} == (a^u)+(a^v)[/small] $a^{u+v} == (a^u)\times (a^v)$

3) Aucune considération de finitude n'est ici utile. Ca vaut pour les ensembles infinis tout aussi bien. Mais attention, ce n'est pas du tout une réponse à ta question finale "peut-on en déduire?"

4) Pour la combinatoire, je dois avouer que les notations sont moins plaquantes puisqu'on la notation $S(E)$ pour l'ensemble des bijections de $E$ dans lui-même alors que son cardinal est noté $E!$. Mais il n'est pas très difficile de s'y retrouver non plus faut dire.

5) Comme il n'y a pas spécialement de notations ensemblistes robustes pour $\{x\mid x\subset E$ et $card(x)=a\}$, tu peux aller faire un holp up non risqué du côté des notations cardinales et la reprendre en disant que cet ensemble s'appelle $\binom{E}{a}$ (je ne sais plus lequel on met en bas, pardon si erreur). De même que tu peux prendre (je ne sais pas quelle est la notation moderne) $A^E_a$ pour désigner $\{x\mid x$ est une injection de $a$ dans $E\}$

6) Je ne sais pas trop pourquoi les "nombre de surjections telles que", etc n'ont pas reçus de noms aussi stables, mais ça, ton prof te le dira peut-être

7) Les raisonnements par récurrence dans ce genre de chapitre sont moralement fautifs. Par exemple, prétendre définir par récurrence que $2^n$ signifie $ if $n=0$ then $1$ else $2\times (2^{n-1})$, bien que "pas faux" est relativement peu respectueux des sincérités qui ont conduit à s'y intéresser de près.

*** tu peux poser la convention (relativement connue et acceptée) que $a+b:=\{(i,x) \mid (i=0$ et $x\in a)$ ou
$(i=1$ et $x\in b)\}$, même si elle contient une sorte de maladresse congénitale.