Preuves
Bonjour
En bossant un cours sur les groupes symétriques un de mes problèmes récurrents s'est à nouveau posé.
En effet, j'essayais de redémontrer les propositions et théorèmes pour m'assurer d'avoir bien assimilé.
Je me suis donc retrouvé à démontrer la propriété qui dit que le cardinal de l'ensemble des bijections d'un ensemble de $n$ éléments est $n!$.
J'ai donc fait ma démo par récurrence en voyant que le cas $n=1$ est trivial et pour l'hérédité j'ai dit que la manière de créer nos nouvelles bijections c'est de récupérer les $(n-1)!$ bijections déjà existantes et de se rendre compte, comme elles sont chacune composé de $n-1$ éléments, qu'il y a $n$ façons d'intercaler notre nouvel élément n et donc (n-1)! * n = n!
Il se trouve que le cours procède bien par récurrence mais ne procède pas de la même manière pour l'hérédité.
Au delà de savoir si la preuve présentée ci-dessus est valide ou non, je suis en quête de conseils. Il m'arrive régulièrement de chercher un exercice ou une preuve simple et de ne pas avancer tout à fait les même arguments que la correction.
J'aimerais donc savoir si vous avez des conseils pour "auto-vérifier" sa preuve. J'ai assez peu confiance quand je ne peux pas vérifier cette dernière et donc j'ai vite l'impression de raconter n'importe quoi ou que les arguments présentés constituent plus une observation approfondie du problème qu'une preuve rigoureuse (j'ai conscience que ma question n'a pas de réponse toute faite mais ce n'est pas la première fois que ça m'arrive donc autant la poser (:D))
Merci de vos conseils avisés.
En bossant un cours sur les groupes symétriques un de mes problèmes récurrents s'est à nouveau posé.
En effet, j'essayais de redémontrer les propositions et théorèmes pour m'assurer d'avoir bien assimilé.
Je me suis donc retrouvé à démontrer la propriété qui dit que le cardinal de l'ensemble des bijections d'un ensemble de $n$ éléments est $n!$.
J'ai donc fait ma démo par récurrence en voyant que le cas $n=1$ est trivial et pour l'hérédité j'ai dit que la manière de créer nos nouvelles bijections c'est de récupérer les $(n-1)!$ bijections déjà existantes et de se rendre compte, comme elles sont chacune composé de $n-1$ éléments, qu'il y a $n$ façons d'intercaler notre nouvel élément n et donc (n-1)! * n = n!
Il se trouve que le cours procède bien par récurrence mais ne procède pas de la même manière pour l'hérédité.
Au delà de savoir si la preuve présentée ci-dessus est valide ou non, je suis en quête de conseils. Il m'arrive régulièrement de chercher un exercice ou une preuve simple et de ne pas avancer tout à fait les même arguments que la correction.
J'aimerais donc savoir si vous avez des conseils pour "auto-vérifier" sa preuve. J'ai assez peu confiance quand je ne peux pas vérifier cette dernière et donc j'ai vite l'impression de raconter n'importe quoi ou que les arguments présentés constituent plus une observation approfondie du problème qu'une preuve rigoureuse (j'ai conscience que ma question n'a pas de réponse toute faite mais ce n'est pas la première fois que ça m'arrive donc autant la poser (:D))
Merci de vos conseils avisés.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
je dois avouer que je ne comprends pas ta preuve, elle n'est absolument pas formalisée; je connais des preuves qui marchent comme tu le dis, mais qui éclaircissent d'où vient le $(n-1)!$. Comme tu parles de bijections "existantes" (?? les autres n'existent pas ?) tu as une idée en tête que je ne comprends pas.
Peux-tu rédiger ta méthode ?
Cordialement.
J'ai procédé par récurrence pour démontrer que $card(Gn) = n!$ (Avec Gn l'ensemble des bijections de $n$ dans $n$ )
Initialistation : $n=1$ , la seule bijection possible est 1 sur lui même donc $card(G1)= 1! =1$
Hérédité: On suppose un n>= 2 tq $card(G(n-1)) = (n-1)! $
Je dit ensuite que pour "créer" toutes les bijections de Gn il suffit de prendre celle de (G(n-1)) et d'observer qu'il suffit d'intercaler notre élément n dans tous les emplacements possibles soit n emplacements.
$(n-1)!$ bijections par n emplacement on a $card(Gn) = n!$
J'espère avoir été assez précis pour que tu puisse comprendre mon idée gerard0 .
Ton message me permet d'appuyer un peu plus ma question .Comment peut-on considérer la validité d'une preuve ? Certains considère qu'elle suffit et d'autre qu'elle n'est pas assez formalisée . Comment trouver un juste milieu et analyser quand une preuve est "prête" où mérite d'être approfondi ?
Tu ne formalises pas assez. C'est pas interdit d'être vague mais il faut alors assumer le risque de rejet.
Sache que je peux témoigner que j'ai voulu transposer la preuve de l'existence d'une nombre infini de nombres premiers en exploitant justement l'ensemblisme fini (et donc je n'ai pas parlé de $n!$ qui n'a même pas de définition simple dans Peano en plus) et donc cet ensemble (dont je sais par coeur son cardinal) et bien ça m'a un peu découragé. Des choses simples peuvent se révéler très profondes et inextricables quand on entre dans le détail. "Intercaler" (sur une table en bois pendant que tu y es???) ne vaut pas preuve.
La tienne l'est insuffisamment, car tu parles "d'emplacements" à propos de bijections. Je vois l'idée, ce qui fait que je suis capable de rectifier, mais si tu parles de bijections, alors tu as des bijections d'un ensemble à n-1 éléments dans, disons lui-même. Et tu dois montrer que les bijections d'un ensemble à n éléments sont n fois plus nombreuses. Il tre faut donc définir ces bijections. Tu ne l'as pas fait.
C'est en ça qu'un lecteur un peu exigeant te dira "ce n'est pas une preuve". Quand tu rédiges, tu dois à la fois éviter de t'étendre sur ce qui est évident pour le niveau où tu te places, et donner clairement toutes les étapes de calcul/raisonnement qui sont convaincantes. pas te contenter, comme ici, d'idées vagues.
Et tu t'apercevras, en faisant ce travail, que ce qui te semblait simple se révèle parfois ardu (les propriétés "évidentes" sont souvent les plus difficiles à démontrer), voire (ça arrive) fausses !!
Cordialement.
La décorporation semble peu évitable, il "te faut" deux ensembles et non pas un. Tu l'as senti avec ta table en bois où on pose les jetons et intercale. Mais pas de table en bois dans les preuves de maths :-D
Il me reste donc pas mal de boulot alors pour traduire mes "idées" en véritables preuves de manière intuitive mais je pense apercevoir le but vers lequel il faut tendre.
christophe je ne comprends pas pourquoi mon énoncé ne serait pas démontrable , pourrais-tu me détailler ce que tu as voulu dire ?
En tous cas merci , j'essayerai de remballer ma planche en bois pour mes prochaines preuves ;-)
Vrai pour tout G,H de cardinal n-1 = > vrai pour tous G,H de cardinal n
Dans une récurrence la plupart du temps, pour prouver $(\forall t:(R(x,t))\to (\forall t: R(x+1,t))$; partant de $R(x+1,t)$ qu'on cherche à avoir, on le déduit de $R(x,f(t))$ et $R(x,g(t))$ par exemple et non pas bisounoursement de $R(x,t)$.
J’ai cru au début que ton « n » de l’hérédité avait le droit d’être égal à $1$ et donc j’ai failli dire que c’était faux car ce serait considérer « n-1 » qui vaut alors 0 et qui n’est pas un cas de l’initialisation.
Or tu as bien choisi dans ta preuve détaillée un n supérieur ou égal à 2 dans l’hérédité.
Les petits détails parfois sont primordiaux.
Remarque : on peut très bien traiter le cas n=0, c’est un autre débat.
Là ça n’est pas fait et on s’en fiche dans la discussion.
Hérédité : soit G un truc de cardinal « n+1 » alors en enlevant un élément j’obtiens un truc de cardinal « n » et hop...
J’ai loupé un truc ?
Tu partitionnes en $n$ sous-ensembles de $(n-1)!$ éléments tes bijections, mais ces ensembles sont des ensembles de bijections qui vont d'un ensemble dans un ensemble différent. FORMELLEMENT le testeur de preuves serait impitoyable et répondrait
STOP, moi robot je vous dis que vous n'avez pas supposé qu'il y a $(n-1)!$ bijections de $E\setminus \{3\}$ dans $E\setminus \{84\}$. FATAL ERROR.
Par le principe des bergers, on obtient N = n . (n-1)!
**********************************
Ci-dessous on propose un traitement du nombre d'éléments du groupe symétrique.
$\newcommand{\perm}[1]{\mathfrak S \left (#1 \right )}$
Si $F$ est un ensemble on note ci-dessous $\perm F$ l'ensemble des bijections de $F$ dans lui-même.
On abrègera lorsque $n$ est un entier naturel, $\perm{\{1,...,n\}}$ par $\mathfrak S_n$ (et donc $\mathfrak S_0= \perm{\emptyset}$).
I) 1°)Soient $E$ un ensemble et $u$ n'appartenant pas à $E$. Pour tout $x,y$ de $E$, appelons $\mathfrak T^E_{x,y}$ l'ensemble des éléments de $\perm E$ envoyant $x$ sur $y$.
Soit pour tout $y,z\in E$, $\tau_{y,z}$ l'application (qui est un élément de $\perm{E}$) envoyant $x\in E$ sur
-$z$ si $x=y$
-$y$ si $x=z$
-$x$ si $x\notin\{y,z\}$.
Bref $\tau_{y,z}$ est la permutation qui échange $y$ et $z$ et laisse le reste inchangé.
Soient $p,q,r\in E$; $f\in \mathfrak T^E_{p,q}$, alors $\tau_{q,r} \circ f \in \mathfrak T^E_{p,r}$. L'application qui à $g\in \mathfrak T^E_{p,q}$ fait correspondre $\tau_{q,r} \circ g \in \mathfrak T^E_{p,r}$ est bijective (de bijection réciproque $h \in \mathfrak T^E_{q,r} \mapsto \tau_{r,q} \circ h \in \mathfrak T^E_{p,q}$ vu que $\tau_{r,q} \circ \tau_{q,r} = \tau_{q,r} \circ \tau_{q,r} = Id$).
De plus pour tout $p\in E$, les ensembles $(\mathfrak T^E_{p,q})_{q\in E}$ sont deux à deux disjoints et leur réunion est égale à $\perm E$.
2°) Soit $F$ un ensemble et $a$ n'appartenant pas à $F$. Alors $\perm F$ est en bijection avec $\mathfrak T^{F \cup \{a\}}_{a,a}$ via l'application $\xi$ qui à $k\in \perm F$ fait correspondre $x \mapsto k(x)$ si $x\in F$ et $\xi(k)(a):=a$.
Par suite, comme $\perm {F \cup \{a\}}$ est la réunion disjointe des $\mathfrak T^{F \cup \{a\}}_{a,s}$ quand $s$ parcourt $F\cup \{a\}$, on en déduit que $\left ( F \cup \{a\}\right ) \times \perm F$ est en bijection avec $\perm{F\cup \{a\}}$ par l'application qui à $(x,f)\in \left ( F\cup \{a\}\right )\times \perm F$ fait correspondre $\tau_{a,x} \circ \xi (f)$
3°) L'application de 2°) au cas où $F=\{1,...,n\}$ avec $n\in \N$ et $a:=n+1$, donne l'équipotence entre $\{1,...,n+1\}\times \mathfrak S_n$ et $\mathfrak S_{n+1}$ ainsi que l'égalité entre cardinaux: $$(n+1) \times \text{card}\left ( \mathfrak S_n\right ) = \text{card}\left ( \mathfrak S_{n+1}\right ) \tag{*}$$.
4°) Puisque $\emptyset$ est la seule application de $\emptyset$ dans lui-même et que cette application est très clairement bijective (elle est injective et surjective: les définitions de ces propriétés commencent par des "quel(s) que soi(en)t"), on en déduit que $\text{card}\left (\mathfrak S_0 \right )=1$. Il vient aussitôt $\text{card}\left (\mathfrak S_n \right )=n!$ par récurrence sur $n$ et ce qui précède.
Comme j'ai la désagréable impression que ma démonstration penche plutôt du mauvais côté de la frontière aux yeux de certains, je me sens moralement tenu de me justifier. :-)
Je note [n, m] l'intervalle fermé de N pour deux entiers naturels n, m, avec naturellement [n, m] = $\varnothing$ pour n > m,
et f | A la restriction de f à une partie A de dom f.
Soit n un entier naturel non nul, et $\varphi$ l'application de $\mathfrak S_n $ dans $\mathfrak S $([2, n]) : p $\mapsto$ ( (12 .. p(1)) o p ) | [2, n]
a) cette application $\varphi$ est correctement définie : la composée de p avec le cycle (12 .. p(1)) possède 1 comme point fixe. Sa restriction à [2, n] est donc bien une permutation de [2, n].
b) $\varphi$ est surjective et les images réciproques $\varphi$-1(q) ont exactement n éléments pour toute permutation q de [2, n], à savoir, pour chaque k dans [1, n], la permutation (12 .. k)-1 o q' où q' est le prolongement de q à [1, n] avec q'(1) = 1.
c) D'après le principe des bergers, on a card ($\mathfrak S_n$ ) = n . card ($\mathfrak S$([2, n]) = n . card ($\mathfrak S_{n-1}$) et l'on conclut par récurrence.
Je crois que foys a pas mal d'heures de vol sur COQ (le vérifieur parmi les plus prisés actuellement) et que, sans le dire, il rédige pour le forum des preuves parfaites (ie des REtraductions en langue humaine de celles qui ferait valider par COQ). Là est le danger de se faire du mal et de stresser ses neurones.
Par exemple quand tu dis "machin est bien défini", c'est mort pour le logiciel, c'est une incantation intime destinée à vérifier que personne ne parle maintenant ou se taise à jamais. Un validateur logiciel te dira "je ne comprends pas", parce que sinon, tu n'aurais éprouvé le besoin d'ajouter "c'est bien défini".
C'est une des difficultés des maths pour les profs. Ils ont tellement fait de choses difficiles dans leur vie, que seul les vérifieurs automatiques peut les ramener sur des routines acceptables.
Si tu n'as pas auparavant par exemple, prouvé l'injectivité de $\circ$, un vérifieur sera intraitable si tu relèves le défi de n'avoir qu'un $E$ et non pas $E,F$ (par exemple).
De même, le fait d'utiliser des opérations, le vérifieur peut se montrer très méchant s'il a été implémenté pour se méfier de toute opération (les opérations créent les existences d'objets sans le dire).
Non, c'est juste une tournure de phrase qui signale que si je définis l'application par f : A $\rightarrow$ B, p $\mapsto$ T(p) où T(x) est un terme fonctionnel à une variable libre, alors on a le théorème $\forall x $ $ (x \in A \Rightarrow T(x) \in
Soit $\mathfrak S_n$ l'ensemble des permutations de $\{1,\ldots,n\}$.
Pour tout $k\in\{1,\ldots,n+1\}$, on définit $\varphi_k:\mathfrak S_n\to \mathfrak S_{n+1}$ par :
$\forall x\in \{1,\ldots,n\}$,
$(\varphi_k(\sigma))(x)=\sigma(x)$ si $x<k$,
$(\varphi_k(\sigma))(k)=n+1$,
$(\varphi_k(\sigma))(x)=\sigma(x-1)$ si $x>k$.
On montre alors successivement :
1) Pour tout $k$, et tout $\sigma\in \mathfrak S_n$, $\ \varphi_k(\sigma)\in \mathfrak S_{n+1}$.
2) Pour tout $k$, $\varphi_k:\mathfrak S_n\to \mathfrak S_{n+1}$ est injective.
3) Les images des $\varphi_k$ sont deux à deux disjointes.
4) $\mathfrak S_{n+1}$ est la réunion des images des $\varphi_k$.
Je ne détaille pas les preuves des points 1--4 mais si on doit les détailler ça prend encore un peu de temps. Maintenant, la question est de savoir si on doit le faire. La réponse dépend du contexte.
Pour un étudiant en mathématiques, il est bon d'apprendre à rédiger de manière formelle, au moins au début, pour se convaincre que dans des situations analogues on serait capable de détailler la preuve si nécessaire.
Pour discuter entre mathématiciens expérimentés, une explication du genre "pour permuter $n+1$ objets je permute les $n$ premiers puis j'intercale le dernier dans l'un des $n+1$ emplacements" suffit, car le mathématicien expérimenté sait qu'il serait capable de produire une preuve formelle à partir de cette idée.
Pour répondre à une question d'examen ou de concours il n'est pas toujours évident de savoir jusqu'à quel niveau de détail on doit aller. Il faut détailler assez pour convaincre le correcteur qu'on a compris, mais pas trop pour ne pas perdre un temps excessif. Personnellement je rédigerais comme j'ai fait ci-dessus, c'est-à-dire en formalisant mais sans donner les preuves de 1--4, mais ça ne veut pas dire que j'ai nécessairement raison.
Les logiciels vérifieurs sont quand-même sévères mais c'est vrai que c'est une bonne chose de s'entrainer à passer leur filtre (je crois que sur le forum, Foys s'est fait un devoir d'acquérir ça avec COQ, en pluss d'en faire profiter le forum, ce serait bien qu'il trouve un débouché à ces nouveaux réflexes).
Dans la vie réelle, je ne connais guère que JLKrivine (qui est encore "pire" que foys, à croire qu'il a été élevé par des logiciels vérifieurs :-D ) qui semble assez terriblement posséder ces réflexes (à moins de passer 1000 ans à écrire chaque livre qu'il écrit sinon). Une vraie preuve rédigée de JLK ça vaut le détour :-D
Mais dans sa démonstration détaillée, le lièvre était levé.