Combinatoire axiomatique / rigoureuse

julien__
julien__
dans Combinatoire et Graphes
Bonjour,
Plusieurs axiomatisations de la géométrie ont été proposées et ont permis de donner un sens rigoureux à des notions intuitives telles celle de droite, carrés, etc. Grâce à ces axiomatiques, on peut démontrer des théorèmes et faire vérifier ses preuves par un ordinateur, par exemple dans un logiciel de preuve formelle tel COQ.

Existe-t-il une axiomatique de la combinatoire et du dénombrement ?
Je pose la question pour plusieurs raisons, et en particulier parce qu'avec une telle axiomatique il serait simple de vérifier ses preuves et d'identifier d'où vient ses erreurs.

Voici un exemple :

Pour démontrer que $\sum\limits_{k=1}^{n} \binom{n}{k} = 2^n$, on peut compter de deux façons différentes le nombre d'éléments dans $P(E)$ lorsque $E$ est un ensemble à $n$ éléments.
Je voudrais appliquer une suite de règles/transitions qui permettent de faire exactement cette preuve, mais en appliquant des théorèmes et en utilisant des axiomes.
Autrement dit, je ne parle pas d'utiliser un autre type de preuve (récurrence), mais bien de formaliser une preuve combinatoire.

(Edit) Autre exemple :
Comment démontrer "rigoureusement" (au sens "indiscutable") que le nombre de permutations d'un ensemble à $n$ élément est $n!$ ? Faudrait-il en faire un axiome de la théorie ?

Bien cordialement,
Julien

(Edit) Éléments de recherche :
http://math.stackexchange.com/questions/1083562/are-there-rigorous-formulation-and-proof-of-the-pigeonhole-principle

Réponses

  • christophe c
    christophe c
    Existe-t-il une axiomatique de la combinatoire et du dénombrement ?

    oui ZF sans l'axiome de l'infini. Mais je ne sais pas s'il existe des logiciels qui l'implémentent. Mais écris déjà ta preuve dans ZF_fini, le reste est un peu matériel. (Elle n'est pas si longue que tu crois).
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • bisam
    bisam
    Pour faire de la combinatoire, il faut compter le nombre d'éléments de plusieurs ensembles, et ce, de plusieurs façons différentes, bien souvent.
    il faut donc définir le cardinal d'un ensemble.
    La notion de "cardinal" en maths est intimement liée à celles d'injection, surjection et bijection.
    Connais-tu ces notions ?

    Si c'est le cas, tu devrais sans problème pouvoir faire toi-même l'axiomatique nécessaire.
    Sinon, il me semble difficile d'aborder ces notions "rigoureusement" comme tu le souhaites.
  • christophe c
    christophe c
    Sinon, il me semble difficile d'aborder ces notions "rigoureusement" comme tu le souhaites

    Si si, c'est possible et praticable

    Exemple: $C_n^p$ est le cardinal de $D_n^p:=\{X\subseteq n \mid card(X)=p\}$. De plus $P(n)=\cup_{p\leq n} D_n^p$. L'union précédente est disjointe. Donc $2^n = card(P(n)) = \sum_{p\leq n} C_n^p$.

    Ce n'est qu'un exemple. Mais c'est déjà très formel. On peut tout écrire avec $\in,\to, \forall$ en quelques lignes (je ne le ferai pas).
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • bisam
    bisam
    Je m'inquiétais surtout pour la définition du "cardinal", justement.
  • julien__
    julien__
    Bonjour Christophe C,
    Je suppose que tu parles de la Théorie des ensembles de Zermelo-Fraenkel ? Je ne suis pas du tout familier avec et il me semblait que c'était assez compliqué comme axiomatique ? Il faut que je regarde plus en détail. Aurais-tu des ressources pédagogiques à me conseiller ?
    Existe-t-il déjà un dictionnaire de correspondances entre le vocabulaire de la combinatoire et celui de cette théorie ?

    Bonjour bisam,
    Je connais les notions d'applications injectives, surjectives, bijectives... Ainsi que le programme de prépa MP/MPSI.
    Un exemple de preuve plus rigoureuse pour montrer l'égalité en exemple serait de dire que $P(E) = \bigcup X_{i}$ où $ X_i = \{ F \in P(E) ~|~ card(F) = i \}$ et que cette réunion est constituée d'éléments disjoints, donc que l'on peut appliquer le "principe d'additivité". Mais là encore, il faut définir beaucoup de choses : principe d'additivité, $ card~P(E) = 2^n $, donner un sens précis (rigoureux, donc) au nombre $ \binom{n}{k} $, etc...

    (Edit : ma réponse a croisé celle de Christophe C)
  • christophe c
    christophe c
    Je m'inquiétais surtout pour la définition du "cardinal", justement.

    $card(E):=$ le plus petit entier $n$ tel que $E$ et $n$ sont équipotents (ici cadre fini)
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • bisam
    bisam
    @julien__ : Je te dirais bien d'aller piocher dans mon cours sur le dénombrement... mais c'est un des rares chapitres que je n'ai pas encore tapés.
    Cependant, on trouve les preuves des fondements du dénombrement dans de nombreux bouquins niveau L1.

    Une des preuves les plus difficiles est de montrer l'unicité du cardinal, autrement dit de montrer que pour tout couple d'entiers $p$ et $q$ les ensembles $\{0,1,...,p-1\}$ et $\{0,1,...,q-1\}$ ne sont équipotents que si $p=q$.

    Ensuite, de nombreuses preuves passent par l'établissement de bijections classiques, et on utilise très souvent le fait que l'équipotence est une relation d'équivalence.
  • christophe c
    christophe c
    Une des preuves les plus difficiles est de montrer l'unicité du cardinal

    Je pense que ça doit dépendre des gouts et des couleurs. Pour ton truc, il suffit de prouver qu'il n'y a pas de surjection de $n$ sur $n+1$
    Aide les autres comme toi-même car ils sont toi, ils sont vraiment toi
  • bisam
    bisam
    Je me suis un peu emballé... mais ce n'est quand même pas trivial. Et par conséquent, il faut l'expliquer à Coq.
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 11

AmadouCongruPoirot +8 Invités