Math'O Man : le Blog des Maths

Exercices théorie des ensembles


Se marier avec quelqu'un qu'on aime


Comment trouver l'amour de sa vie ? Comment se caser ? Comment former un bon couple ? Ce type de questions préoccupe beaucoup de gens. Voici une version matheux de ce problème fondamentale.

Le problème de mariage ou le problème de former les bons couples

Supposons que nous avons n femmes et n hommes, tous célibataires et prêts à se marier ; pour tout entier k dans [1,n] et tout choix de k femmes, l'ensemble des hommes qui sont aimés par au moins une de ces femmes contient au moins k éléments.
Démontrer qu'on peut organiser des mariages tels que chaque femme se marie avec un époux qu'elle aime.

Pourquoi ne pas lire aussi :


A la recherche des mathématiques perdues

Quand les maths influencent la litérature française

Un amour de Swann, le deuxième livre autonome de la trilogie Du côté de chez Swann de Marcel Proust, est paru en 1913. A cette époque la théorie des ensembles et la théorie des groupes venaient d'être inventées et connaissaient un grand essor.
Je m'imagine bien l'écrivain Proust lors d'une réception un dimanche après-midi chez un représentant de la nomenklatura scientifique parisienne, disons chez le grand mathématicien Henri Poincaré ; on y joue des arrangements pour violon et piano des opéras de Wagner, on parle de poésie ou d'art chinois. Proust, le snob, s'isole dans le salon à côté et trouve sur la table une revue scientifique avec la dernière publication de son hôte. Il l'ouvre sur la première page, commence à lire et n'y comprend pas grand'chose — mais les mots et formulations lui plaisent...

Bon, vous direz que j'ai trop d'imagination ! Alors jugez par vous-même... voici la phrase avec laquelle commence Un amour de Swann :

Pour faire partie du « petit noyau », du « petit groupe », du « petit clan » des Verdurin, une condition était suffisante mais elle était nécessaire [...]

 

UVSQ - 2011/2012

Sur cette page des remarques et documents destinés aux étudiants qui suivent mes cours et TD à l'UVSQ en 2011/2012.

Probabilités — L2 économie

  • Polycopié — Cours, exercices & corrigés (mise à jour le 02/02/2012)
    Il est possible que vous devez ré-actualiser la page (touche F5).
     
  • Contrôle continu 1 : 22 février 2012 dans votre groupe de TD (carte d'étudiant)
     
  • Contrôle continu 2 : 28 mars 2012 de 18h30 à 20h dans l'amphi 1 (carte d'étudiant)
     
  • Toute absence non-justifiée par un certificat médical donne lieu à la note 0.
    Note globale = (moyenne des notes de CC + note de partiel) / 2
    La note globale doit être au moins 10 pour que la matière soit validée.
    En session 2, la moyenne des notes de CC intervient seulement si elle est supérieure à la note du partiel session 2.

Théorie des groupes — L2 chimie

Quelques blagues pour matheux

Ajourd'hui quelques lignes pour illustrer que le cerveau n'est pas le seul organe actif des matheux...

Comment "le font"-ils ?
  • Les topologistes le font discrètement.
  • Les topologistes le font de manière ouverte.
  • Les topologistes le font avec du caoutchouc.
  • Les couples de topologistes le font en se rendant connexes.
  • (les logiciens le font) ou NON (les logiciens le font).
  • Les algébristes le font en groupe ou en anneau.
  • Les algébristes le font avec leur corps.
  • Les algébristes le font associativement.
  • Les algébristes le font en s'inversant.
  • Les algébristes le font en se multipliant.
  • Les analystes le font continûment.
  • Les analystes le font sur un support compact.
  • Les experts en théorie de la mesure le font presque partout.
  • Les experts en équations différentielles le font suivant les conditions initiales.
  • Les experts en théorie des ensembles le font avec application.
  • Les experts en combinatoire le font de toutes les manières possibles.
  • Les mathématiciens le font une infinité de fois s'il peuvent le faire une fois et ensuite une fois de plus.
Comment "le faisaient" les grands ?
  • Cantor le faisait en diagonale.
  • Fermat essayait de le faire dans la marge mais n'avait pas assez de place.
  • Galois l'a fait la nuit juste avant.
  • Möbius le faisait toujours du même côté.
  • Klein l'avait simultanément dedans et dehors.
  • Cauchy le faisait avec un ami (Schwarz, Lipschitz, Riemann).
  • Markov le faisait à la chaîne.
  • Archimède le faisait dans sa baignoire.
  • Newton tomba dans les pommes.
  • Bourbaki le faisait dans un cas particulier du théorème 10.2.5 en utilisant subtilement le lemme 7.3.2.

Deux contrepèteries

  • Nul n'est jamais assez fort pour ce calcul !
  • Mon prof de maths a montré Bézout.

Une réciproque
The duchess: "Excuse me that I am late, but I was so fucking busy and vice versa."

Recommandation bibilographique : Ces blagues m'ont été envoyées par email au fil des années. Mais il existe même des livres sur ce sujet. Le lecteur qui souhaite s'y approfondir se plonger avec profit dans l'ouvrage de référence Je fais des maths comme un(e) cochon(ne) de Gérard-Olivier Maitry publié en 2008.

Un exercice théorique sur les groupes

La théorie des groupes semble contenir une infinité de questions de colle qui ont l'apparence élémentaires mais qui sont en fait plutôt difficiles. En voici une que vient de m'envoyer un ami:

Soient G un groupe fini d’ordre n et f :G →G un automorphisme de G. On note

E := \{x \in G \;|\; f (x) = x^{-1}\}

et l’on suppose que le cardinal de E est minoré par n/2. Prouver que f est une involution.

Exercice d'arithmétique

Après une longue absence je viens de faire un peu le ménage dans les commentaires du billet précédent sur les exercices de la liste de Vladimir Arnol'd et je me suis rendu compte que PB y a posé un petit problème que toute le monde a oublié dans la déferlante de solutions (dues pour la plupart à JLT). Le voilà, dans un billet à lui tout seul !

Exercice de PB : calculer la signature de la (multiplication par 541 modulo 1223).

SO(3) e(s)t l'espace projectif à 3 dimensions

Quelques fois on garde un souvenir très complet d'une démonstration mathématique, et ce souvenir inclût également des accessoires absurdes et inutiles comme par exemple le numéro de la page du livre où on l'a apprise ou la couleur de la chemise du professeur qui l'a expliquée...

Ci-dessous j'explique, en forme d'exercice corrigé, pourquoi le groupe SO(3) de rotations dans l'espace peut être identifié à l'espace projectif réel \mathbb{P}^3. Et je me rappelle que c'était un collègue d'études qui m'a raconté cette preuve par la méthode de hand waving sous le soleil d'été dans une piscine plein air à Bonn!

Un bel énoncé géométrie et topologie
Le but de l'exercice est de montrer que \;SO(2)\:\simeq\: \mathbb{P}^1\;\; et \;\;SO(3)\:\simeq\:\mathbb{P}^3\,.

Notations
Dans un premier temps — dont nous nous contentons ici — le symbole \:\simeq\: signifie simplement qu'il existe une bijection entre les ensembles concernés; c'est clairement une relation d'équivalence.
Comme d'habitude \mathbb{P}^n dénote l'espace projectif réel de dimension n, c'est-à-dire l'ensemble des droites vectorielles dans \mathbb{R}^{n+1}. Fixons aussi les notations pour trois sous-ensembles importants de \mathbb{R}^{n+1}\::
  • la boule \;\mathbb{B}^{n+1}=\{x\in\mathbb{R}^{n+1} \:|\: x_1^2+\cdots+x_{n+1}^2\leq1\}\,,
    \:
  • la sphère \;\mathbb{S}^{n}=\{x\in\mathbb{R}^{n+1} \:|\: x_1^2+\cdots+x_{n+1}^2=1\}\,,
    \:
  • l'hémisphère nord \;\mathbb{S}^{n}_+=\{x\in\mathbb{S}^{n} \:|\: x_{n+1}^2\geq0\}\,.
    \:
Le bord de la boule \mathbb{B}^{n+1} est la sphère \mathbb{S}^n. Chaque point x sur ce bord possède un antipode, à savoir le point —x.
Si on ``recolle'' \mathbb{B}^{n+1} par identification des antipodes sur son bord, alors on obtient un nouvel ensemble que nous notons \mathbb{B}^{n+1}/\!\sim\,. Ca, c'est du handwaving. De manière ensembliste on pourra écrire

\;\;\;\;\;\mathbb{B}^{n+1}/\!\sim~\;\,=\;\,\left(\mathbb{B}^{n+1}\backslash\mathbb{S}^n\right)\:\dot{\bigcup}\:<br />\big\{\{x,-x\}\,|\,x\in\mathbb{S}^n\big\}\,.<br />


Questions
  1. Expliquer par des mots de quelles formes sont la boule \mathbb{B}^n et son bord \mathbb{S}^{n-1} dans les cas n=1,2,3.
  2. Démontrer que \;\mathbb{S}^n_+ \:\simeq\: \mathbb{B}^n\,.
    \,
  3. Démontrer que \;\mathbb{B}^n/\!\sim~\;\simeq\:\mathbb{P}^n\,.
    \,
  4. Démontrer que \;SO(2)~\simeq~\mathbb{P}^1\,.
    \,
  5. Démontrer que \;SO(3)~\simeq~\mathbb{P}^3\,.
    \,
Cliquez pour lire la Solution.

Règle pour apprendre à conjuguer

Dans un post récent mon collègue bloggeur PB a constaté qu'une trop grande partie de ses élèves en prépa ne savent pas conjuguer correctement les verbes du premier groupe au passé composé et qu'ils écrivent souvent « on a montrer que… » dans leurs copies.

Je pense que la compréhension de la structure grammaticale d'une langue est fondamentale pour l'apprentissage des mathématiques. Je la situerais au même niveau que la théorie des ensembles, c'est-à-dire une structure fondamentale à connaître pour ne pas écrire de bêtises. Malheureusement l'enseignement scolaire actuel ne transmet plus cette hygiène de base, de sorte que de telles lacunes se prolongent jusqu'aux classes préparatoires...

Voici donc une «recette» permettant d'éviter l'erreur la plus fréquente : la confusion entre les terminaisons -er, , -ez. On peut l'appliquer sans vraiment comprendre ce que c'est un infinitif, un participe composé et une deuxième personne au pluriel (de toutes manières ceux qui comprennent ces notions ne font probablement pas d'erreurs).

L'idée est simple : remplacer le verbe du premier groupe par un autre verbe, puis se fier à la prononciation. Par exemple on a les correspondances suivantes.

montrer/apprendre/voir,    montrez/apprenez/voyez,    montré/appris/vu.

Il suffit alors de procéder par analogie. Au lieu du verbe montrer utilisez l'autre verbe (apprendre, voir, etc.), puis testez laquelle est la bonne conjuguaison en lisant à haute voix.

Quelques règles de grammaire pour les nuls

FAUX
CORRECT
DONC PAR ANALOGIE
on a apprendre que... on a appris que... on a montrer montré que...
vous devez apprenez... vous devez apprendre... vous devez montrez montrer...
je viens de vu que... je viens de voir que... je viens de montré montrer que...
le lemme qu'on a voir le lemme qu'on a vu le lemme qu'on a montrer montré
ce qu'il devait compris ce qu'il devait comprendre ce qu'il devait montré montrer
Quel lemme voir-vous ? Quel lemme voyez-vous ? Quelle femme aimer aimez-vous ?

C'est bizarre, je ne suis pas français mais je crois que je fais moins d'erreurs de conjuguaison que la moyenne des bacheliers français. Je fais des fautes sur les prépositions (par exemple je ne sais pas si on dit j'aide un élève à faire ses devoirs j'aide un élève de faire ses devois ou j'aide un élève faire ses devois) et parfois je n'utilise pas le passé correct (dans ma langue maternelle, l'allemand, on utilise de manière indifférente l'imparfait et le passé composé), mais jamais ça ne me viendrait à l'esprit d'écrire « on a montrer que… »

Concevoir la notion d'application

Je me rappelle qu'au début de mes études de mathématiques, parfois une simple question de formalisme pouvait me poser des problèmes. Par exemple, j'avais du mal à jongler entre différents points de vue d'une notion a priori simple comme celle d'application. Voici quelques lignes qui pourraient sembler bêtes aux initiés, mais comme les livres expliquent rarement ce genre de choses en détail elles peuvent être utiles à ceux qui y sont confrontés pour la première fois — et notamment aux élèves et étudiants d'aujourd'hui qui, lors de leur parcours scolaire, ne rencontrent plus assez de théorie des ensembles.


Considérons une application (synonyme de fonction) d'un ensemble X dans un ensemble Y.

f\;:\; X \;\longrightarrow \;Y\,,\;\; x \; \longrightarrow\;f(x)\,.

(Désolé, la deuxième flèche devrait commencer par un pied mais mon plug-in LaTeX ne le permet pas.)

Si vous venez de passer le bac, vous avez déjà une notion intuitive de ce que c'est une application. Mais les mathématiciens possèdent plusieurs autres points de vue pour concevoir cet objet — et chacun a sa raison d'être.

  1. Point de vue y en fonction de x.
    C'est le point de vue habituellement enseigné au collège et au lycée. On conçoit x comme variable et y comme l'image qui change en fonction de x.
    Le schéma mental est le suivant.

    dessiner le graphe d'une fonction, comprendre les fonctions

    L'ensemble de départ X est représenté horizontalement, l'ensemble d'arrivée Y est représenté verticalement. La donnée de l'application f revient à la donnée de son graphe \Gamma \subset X\times Y constitué des couples (x,f(x)), où x parcourt X.
    En disant x parcourt X, on adopte donc bien l'idée que la variable est x.
     
  2. Point de vue collection d'éléments de Y.
    On peut aussi écrire l'application f en forme de famille (f(x))_{x\in X}. On oublie donc de spécifier l'ensemble d'arrivée Y.
    En général, une famille (y_j)_{j\in J} dans Y n'est rien d'autre qu'une application

    y\;:\; J \;\longrightarrow \;Y\,,\;\; j \; \longrightarrow\;y_j\,,

     
    où l'ensemble de départ J est appellé l'ensemble d'indices ; très souvent il n'a pas d'importance et peut être remplacé par un autre ensemble de même cardinal. Ce qui compte dans ce point de vue c'est simplement la collection des images de l'application.
    Dans certaines situations un bon choix de l'ensemble d'indices peut raccourcir les écritures. Par exemple, si (b_j)_{j\in J} est une base d'un K-espace vectoriel E, alors tout vecteur v de E se décompose comme combinaison linéaire

    v=\sum_{j\in J} \lambda_j\, b_j\:,

    (\lambda_j)_{j\in J} est une famille de scalaires presque tous nuls (c'est-à-dire l'application \lambda\;:\; J \;\longrightarrow \;K\, est nulle sauf en un nombre fini de points ; cela est nécessaire pour pouvoir prendre la somme). Mais si on conçoit la base non comme une famille de vecteurs mais comme un sous-ensemble B de l'espace E, alors on peut la prendre elle-même comme ensemble d'indices et écrire simplement

    v=\sum_{b\in B} \lambda_b\, b\:.


     
  3. Point de vue les fibres en fonction de y.
    Pour chaque y dans Y on appelle fibre de f en y (ou ensemble de niveau y) l'ensemble de tous les antécédents de y, noté
     
    f_y\;=\;f^{-1}(\{y\:\})\:=\:\{\:x\in X\; :\; f(x)=y\:\} \,.

     
    Connaître une application revient à connaître la collection de ses fibres. C'est donc y qu'on considére comme variable. On s'aide du schéma mental suivant.
     

    représenter une fonction graphiquement, comprendre une fonction


    L'espace de départ est projeté sur l'espace d'arrivée. L'application est injective (resp. surjective resp. bijective) si et seulement si chaque fibre possède au plus (resp. au moins resp. précisément) un élément.
     
Une conséquence naturelle du point de vue des fibres est la factorisation canonique, que nous allons expliquer ci-dessus et dont la quintessence se résume ainsi :
L'ensemble des fibres non-vides d'une application est une partition de l'ensemble de départ et a le même cardinal que l'image de l'application.

Factorisation canonique

Nous nous proposons de montrer que toute application est la composée d'une surjection, d'une bijection et d'une injection. Soit donc f une application de X vers Y. On considère son image

\tilde{Y} = f(X)\:\subset\:Y

et l'espace des fibres

\tilde{X} = \{\,f^{-1}(\{y\})\:|\: y\in \tilde{Y}\,\}\:\subset\:{\scr P}(X).

Ainsi l'espace des fibres est le quotient de X par la relation d'équivalence  ~  qui est définie par  x ~ x'  si et seulement si f(x) = f(x'). Il est clair que \tilde{X} et \tilde{Y} sont en bijection. Plus précisément il existe une surjection \pi, une bijection \tilde{f} et une injection j tel que le diagramme suivant commute.

Factorisation canonique d'une fonction, comment comprendre les applications

En effet, il suffit de prendre pour \pi la projection canonique sur le quotient X/~, c'est-à-dire l'application qui à chaque x dans X associe la fibre de f en f(x) ; puis pour j l'injection naturelle, et enfin pour \tilde{f} l'application qui envoie une fibre sur l'unique élément dans Y qui est son image par f. Il est alors évident que f est la composée

f= j\circ \tilde{f}\circ \pi.

Un avant-goût de la suite

Concevoir une application comme la collection de ses fibres est très fréquent en topologie, géométrie algébriques et théorie des singularités. On fait varier un point dans l'espace d'arrivée pour observer, dans l'espace de départ, la manière dont varie la fibre au-dessus de ce point. Un exemple très basique est l'application

f\;:\; \mathbb{R}^3 \;\longrightarrow \;\mathbb{R}\,,\;\; (x,y,z) \; \longrightarrow\;ax+by+cz\,,

 
a,b,c sont des réels fixés non tous nuls. La collection des fibres est constituée de plans parallèles. Il s'agit donc d'un feuilletage de l'espace \mathbb{R}^3 par plans (comme un feuilleté). Les fibres se ressemblent toutes ; on a même ce qu'on appelle une fibration globalement triviale.

Plus généralement, si f est une fonction différentiable et si on fait varier le point dans l'espace d'arrivée sans toucher les valeurs critiques, alors localement les fibres se ressemblent toutes (fibration localement triviale). En revanche, si on passe par une valeur critique alors la nature des fibres peut changer. Par exemple si on traverse la valeur critique 0 de l'application

g\;:\; \mathbb{R}^2 \;\longrightarrow \;\mathbb{R}\,,\;\; (x,y) \; \longrightarrow\;x^2+y^2\,,

dans le sens décroissant, alors la fibre est d'abord un cercle, puis dégénère en un point et, enfin, devient vide — une catastrophe a lieu au sens de la théorie des catastrophes de René Thom.

Tout ça devient plus intéressant dans le complexe. Les fibres de

g\;:\; \mathbb{C}^2 \;\longrightarrow \;\mathbb{C}\,,\;\; (x,y) \; \longrightarrow\;x^2+y^2\,,

sont des surfaces réelles (courbes complexes ou surfaces de Riemann). Et au lieu de traverser la valeur critique 0, on peut la contourner avec un petit lacet dans le plan complexe et observer la déformation de cette surface le long du lacet. Evidemment à la fin on retrouve la même surface qu'au début du lacet, mais lors du trajet certaines caractéristiques se sont déplacés continûment et ont échangés leurs places... (monodromie).

Avis de recherche

Mon ami Laurent Kaczmarek souhaite recenser toutes les démonstrations du résultat suivant d'algèbre linéaire.
Un espace vectoriel de dimension finie sur un corps non-dénombrable n'est pas réunion dénombrable de sous-espaces vectoriels stricts.

Preuves dans les cas réel ou complexe acceptées (et même souhaitées !).

Vladimir Arnold Trivium - conclusion

Avant les vacances d'été j'avais écrit un billet avec les exercices du Trivium mathématique de Vladimir Arnold. Grâce aux efforts estivaux de certains lecteurs, notamment de JLT, presque toute question a trouvé sa solution (sauf les 27, 41, 51, 58, 68, 69, 70, 73, 74). Quelle conclusion peut-on tirer ?

D'abord ce trivium est loin d'être trivial. Il apprend de l'humilité à beaucoup parmi nous, enseignants souvent spécialisés dans certains domaines, et nous rappelle qu'on a la mémoire courte, c'est-à-dire qu'on a tendance à oublier des choses si on ne les utilise/enseigne plus. Deuxièmement, on apprend à apprécier l'outil Wikipédia pour chercher des définitions ou clarifications de certaines notions. Je crois que j'aurais fait mes études plus facilement si Wikipédia avait déjà existé ; mais il y a encore dix ans il fallait aller à la bibliothèque, passer beaucoup de temps à ne rien trouver ou encore trouver des articles et livres où la notion recherchée apparaissait englobée par 200 pages de définitions ou théorèmes...

Mais laissons le dernier mot à l'auteur du Trivium lui-même : en fait, Arnold a écrit un Mathematical Trivium bis dans lequel il résume certaines réactions à son premier Trivium. En plus il y a aussi son texte sur l'enseignement des mathématiques et la vidéo suivante sur les mathématiques expérimentales :