Scribd Logo
Importer

Bienvenue sur Scribd !

  • 19 vues

    Cours L1 18

    Transféré par

    Abd Essamad
    Ce document mathématique présente des théorèmes sur les cardinaux d'ensembles finis. Il démontre des formules sur les cardinaux d'unions, intersections et produits cartésiens d'ensembles finis.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd

    Cours L1 18

    Transféré par

    Abd Essamad
    19 vues1 page
    Ce document mathématique présente des théorèmes sur les cardinaux d'ensembles finis. Il démontre des formules sur les cardinaux d'unions, intersections et produits cartésiens d'ensembles finis.

    Titre original

    Cours-L1-18

    Copyright

    © © All Rights Reserved

    Formats disponibles

    PDF, TXT ou lisez en ligne sur Scribd

    Avez-vous trouvé ce document utile ?

    Ce contenu est-il inapproprié ?

    Ce document mathématique présente des théorèmes sur les cardinaux d'ensembles finis. Il démontre des formules sur les cardinaux d'unions, intersections et produits cartésiens d'ensembles finis.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    19 vues1 page

    Cours L1 18

    Transféré par

    Abd Essamad
    Ce document mathématique présente des théorèmes sur les cardinaux d'ensembles finis. Il démontre des formules sur les cardinaux d'unions, intersections et produits cartésiens d'ensembles finis.

    Droits d'auteur :

    © All Rights Reserved
    Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
    Télécharger au format pdf ou txt
    sur 1

    f est injective.

    On conclut que (ii) équivaut à (iii) ; par ailleurs (i) équivaut par définition
    à (ii) et (iii) d’où le théorème.

    Remarque : On voit en particulier que si x ∈ E et E est fini alors E \ {x} n’est pas
    en bijection avec E. Ceci est une caractérisation des ensembles finis.
    Une autre application simple des ensembles finis est le principe des tiroirs ; “si on range
    n + 1 chaussettes dans n tiroirs, l’un (au moins) des tiroirs contiendra deux chaussettes”
    (on laisse la preuve en exercice).
    Il est naturel, sachant qu’une ensemble est fini de chercher à déterminer son cardi-
    nal (un entier naturel). On appelle combinatoire cette partie des mathématiques. Voici
    quelques résultats utiles.

    THÉORÈME: Soient E et F des ensembles finis de cardinaux m et n respectivement,


    alors :
    (i) card(E) + card(F ) = card(E ∩ F ) + card(E ∪ F )
    (ii) card(E × F ) = mn
    (iii) Soit F(E, F ) l’ensemble des applications de E vers F alors card(F(E, F )) = nm .
    En particulier card(P(E)) = 2m .
    (iv) Le nombre d’injection de E dans F est 0 si m > n et n(n−1)(n−2) . . . (n−m+1)
    si m ≤ n.
    (v) L’ensemble des bijections de F vers F a pour cardinal n! = n(n − 1)(n − 2) . . . 2.1

    Démonstration: (i) Commençons par observer que dans le cas plus facile où E ∩F = ∅,
    la formule est évidente ; en effet si X = A ∪ B avec A ∩ B = ∅ alors card(X) = card(A) +
    card(B). Revenons au cas général et posons E 0 := E \ (E ∩ F ), alors E ∪ F est union
    disjointe de F et E 0 donc card(E ∪ F ) = card(F ) + card(E 0 ). Mais E est union disjointe
    de E 0 et E ∩ F donc on a aussi : card(E) = card(E 0 ) + card(E ∩ F ) et on tire de ces deux
    égalités la formule : card(E) + card(F ) = card(E ∩ F ) + card(E ∪ F )
    (ii) On peutPécrire E × F = ∪x∈E {x} × F ; or ces ensembles sont disjoints donc on a
    card(E × F ) = x∈E card({x} × F ). Mais F est en bijection avec chacun des P ensembles
    {x} × F par l’application y 7→ (x, y) donc card({x} × F ) = n et card(E × F ) = x∈E n =
    mn.
    (iii) Pour construire une fonction de E = {a1 , a2 , . . . , am } vers F il faut choisir f (a1 )
    (il y a n choix possibles), f (a2 ) (il y a n choix possibles),. . . etc. Il y a donc n×n . . . n = nm
    fonctions de E vers F .
    Soit A un sous-ensemble de E, on lui associe la fonction fA : E → {0, 1} définie par
    fA (x) = 1 si x ∈ A et fA (x) = 0 si x ∈ / A (la fonction fA s’appelle la fonction caractéristique
    de A). On obtient ainsi une bijection entre P(E) et F(E, {0, 1}) (la bijection réciproque est
    donnée par f 7→ {x ∈ E | f (x) = 1}). On conclut que card(P(E)) = card({0, 1})m = 2m .
    (iv) Tout d’abord, il est clair que si card(E) > card(F ) il n’existe aucune injection de
    E dans F . Si maintenant E = {a1 , a2 , . . . , am } et m ≤ n, pour construire une application
    injective de E dans F on doit choisir f (a1 ) ∈ F (il y a n choix possibles) puis f (a2 ) ∈
    F \ {f (a1 )} (il y a n − 1 choix possibles) puis f (a3 ) ∈ F \ {f (a1 ), f (a2 )} (il y a n − 2 choix
    possibles) et ainsi de suite. On obtient donc bien en tout n(n − 1)(n − 2) . . . (n − m + 1)
    injections.

    18

    Vous aimerez peut-être aussi