\( %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Mes commandes %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand{\multirows}[3]{\multirow{#1}{#2}{$#3$}}%pour rester en mode math \renewcommand{\arraystretch}{1.3}%pour augmenter la taille des case \newcommand{\point}[1]{\marginnote{\small\vspace*{-1em} #1}}%pour indiquer les points ou le temps \newcommand{\dpl}[1]{\displaystyle{#1}}%megamode \newcommand{\A}{\mathscr{A}} \newcommand{\LN}{\mathscr{N}} \newcommand{\LL}{\mathscr{L}} \newcommand{\K}{\mathbb{K}} \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\M}{\mathcal{M}} \newcommand{\D}{\mathbb{D}} \newcommand{\E}{\mathcal{E}} \renewcommand{\P}{\mathcal{P}} \newcommand{\G}{\mathcal{G}} \newcommand{\Kk}{\mathcal{K}} \newcommand{\Cc}{\mathcal{C}} \newcommand{\Zz}{\mathcal{Z}} \newcommand{\Ss}{\mathcal{S}} \newcommand{\B}{\mathbb{B}} \newcommand{\inde}{\bot\!\!\!\bot} \newcommand{\Proba}{\mathbb{P}} \newcommand{\Esp}[1]{\dpl{\mathbb{E}\left(#1\right)}} \newcommand{\Var}[1]{\dpl{\mathbb{V}\left(#1\right)}} \newcommand{\Cov}[1]{\dpl{Cov\left(#1\right)}} \newcommand{\base}{\mathcal{B}} \newcommand{\Som}{\textbf{Som}} \newcommand{\Chain}{\textbf{Chain}} \newcommand{\Ar}{\textbf{Ar}} \newcommand{\Arc}{\textbf{Arc}} \newcommand{\Min}{\text{Min}} \newcommand{\Max}{\text{Max}} \newcommand{\Ker}{\text{Ker}} \renewcommand{\Im}{\text{Im}} \newcommand{\Sup}{\text{Sup}} \newcommand{\Inf}{\text{Inf}} \renewcommand{\det}{\texttt{det}} \newcommand{\GL}{\text{GL}} \newcommand{\crossmark}{\text{\ding{55}}} \renewcommand{\checkmark}{\text{\ding{51}}} \newcommand{\Card}{\sharp} \newcommand{\Surligne}[2]{\text{\colorbox{#1}{ #2 }}} \newcommand{\SurligneMM}[2]{\text{\colorbox{#1}{ #2 }}} \newcommand{\norm}[1]{\left\lVert#1\right\rVert} \renewcommand{\lim}[1]{\underset{#1}{lim}\,} \newcommand{\nonor}[1]{\left|#1\right|} \newcommand{\Un}{1\!\!1} \newcommand{\sepon}{\setlength{\columnseprule}{0.5pt}} \newcommand{\sepoff}{\setlength{\columnseprule}{0pt}} \newcommand{\flux}{Flux} \newcommand{\Cpp}{\texttt{C++\ }} \newcommand{\Python}{\texttt{Python\ }} %\newcommand{\comb}[2]{\begin{pmatrix} #1\\ #2\end{pmatrix}} \newcommand{\comb}[2]{C_{#1}^{#2}} \newcommand{\arrang}[2]{A_{#1}^{#2}} \newcommand{\supp}[1]{Supp\left(#1\right)} \newcommand{\BB}{\mathcal{B}} \newcommand{\arc}[1]{\overset{\rotatebox{90}{)}}{#1}} \newcommand{\modpi}{\equiv_{2\pi}} \renewcommand{\Re}{Re} \renewcommand{\Im}{Im} \renewcommand{\bar}[1]{\overline{#1}} \newcommand{\mat}{\mathcal{M}} \newcommand{\und}[1]{{\mathbf{\color{red}\underline{#1}}}} \newcommand{\rdots}{\text{\reflectbox{$\ddots$}}} \newcommand{\Compa}{Compa} \newcommand{\dint}{\dpl{\int}} \newcommand{\intEFF}[2]{\left[\!\left[#1 ; #2\right]\!\right]} \newcommand{\intEFO}[2]{\left[\!\left[#1 ; #2\right[\!\right[} \newcommand{\intEOF}[2]{\left]\!\left]#1 ; #2\right]\!\right]} \newcommand{\intEOO}[2]{\left]\!\left]#1 ; #2\right[\!\right[} \newcommand{\ou}{\vee} \newcommand{\et}{\wedge} \newcommand{\non}{\neg} \newcommand{\implique}{\Rightarrow} \newcommand{\equivalent}{\Leftrightarrow} \newcommand{\Ab}{\overline{A}} \newcommand{\Bb}{\overline{B}} \newcommand{\Cb}{\overline{C}} \newcommand{\Cl}{\texttt{Cl}} \newcommand{\ab}{\overline{a}} \newcommand{\bb}{\overline{b}} \newcommand{\cb}{\overline{c}} \newcommand{\Rel}{\mathcal{R}} \newcommand{\superepsilon}{\varepsilon\!\!\varepsilon} \newcommand{\supere}{e\!\!e} \makeatletter \newenvironment{console}{\noindent\color{white}\begin{lrbox}{\@tempboxa}\begin{minipage}{\columnwidth} \ttfamily \bfseries\vspace*{0.5cm}} {\vspace*{0.5cm}\end{minipage}\end{lrbox}\colorbox{black}{\usebox{\@tempboxa}} } \makeatother \def\ie{\textit{i.e. }} \def\cf{\textit{c.f. }} \def\vide{ { $ {\text{ }} $ } } %Commande pour les vecteurs \newcommand{\grad}{\overrightarrow{Grad}} \newcommand{\Vv}{\overrightarrow{v}} \newcommand{\Vu}{\overrightarrow{u}} \newcommand{\Vw}{\overrightarrow{w}} \newcommand{\Vup}{\overrightarrow{u'}} \newcommand{\Zero}{\overrightarrow{0}} \newcommand{\Vx}{\overrightarrow{x}} \newcommand{\Vy}{\overrightarrow{y}} \newcommand{\Vz}{\overrightarrow{z}} \newcommand{\Vt}{\overrightarrow{t}} \newcommand{\Va}{\overrightarrow{a}} \newcommand{\Vb}{\overrightarrow{b}} \newcommand{\Vc}{\overrightarrow{c}} \newcommand{\Vd}{\overrightarrow{d}} \newcommand{\Ve}[1]{\overrightarrow{e_{#1}}} \newcommand{\Vf}[1]{\overrightarrow{f_{#1}}} \newcommand{\Vn}{\overrightarrow{0}} \newcommand{\Mat}{Mat} \newcommand{\Pass}{Pass} \newcommand{\mkF}{\mathfrak{F}} \renewcommand{\sp}{Sp} \newcommand{\Co}{Co} \newcommand{\vect}[1]{\texttt{Vect}\dpl{\left( #1\right)}} \newcommand{\prodscal}[2]{\dpl{\left\langle #1\left|\vphantom{#1 #2}\right. #2\right\rangle}} \newcommand{\trans}[1]{{\vphantom{#1}}^{t}{#1}} \newcommand{\ortho}[1]{{#1}^{\bot}} \newcommand{\oplusbot}{\overset{\bot}{\oplus}} \SelectTips{cm}{12}%Change le bout des flèches dans un xymatrix \newcommand{\pourDES}[8]{ \begin{itemize} \item Pour la ligne : le premier et dernier caractère forment $#1#2$ soit $#4$ en base 10. \item Pour la colonne : les autres caractères du bloc forment $#3$ soit $#5$ en base 10. \item A l'intersection de la ligne $#4+1$ et de la colonne $#5+1$ de $S_{#8}$ se trouve l'entier $#6$ qui, codé sur $4$ bits, est \textbf{\texttt{$#7$}}. \end{itemize} } \)

Ensembles de cardinalité finie

Axiomes

Un ensemble est une boite avec des trucs dedans. Telle est la version simpliste et suffisante d'un ensemble. Suffisante pendant un temps, et les mathématiciens faisaient à peu près n'importe quoi avec. Arriva un jour ou cette notion enfantine devint beaucoup trop problématique et on s'aperçut finalement que pour faire bien on ne pouvait pas faire n'importe quoi. Le célèbre Paradoxe du barbier de Bertran RUSSELL en est l'exemple emblématique :

Dans une ville, un barbier rase (uniquement) tous les hommes qui ne se rasent pas eux-même. Qui rase le barbier ?

Pour formaliser la notion d'ensemble (et ainsi esquiver les paradoxes), plusieurs tentatives d'axiomatisation ont été proposées. La plus connue, celle que nous adopteront, est la théorie ZFC pour Zermelo, Frenkel avec l'axiome du Choix.

Définition

Un ensemble $ X$ est une collection d'élément. Un élément $ x$ appartenant à $ X$ est noté \[x\in X\] Les ensembles sont soumis aux axiomes suivants :

Axiome d'extentionnalité.: Deux ensembles avec les même éléments sont égaux.
Axiome de l'ensemble vide.: Il existe un ensemble sans élément appellé l'ensemble vide et généralement noté $ \varnothing$ .
Axiome de la paire.: Si $ X$ et $ Y$ sont deux ensembles, il existe un ensemble avec ces deux ensembles comme élément. On le note $ \{X,Y\}$ .
Axiome de la réunion.: On vera plus tard.
Axiome de l'ensemble des parties.: On vera plus tard.
Axiome de l'infini.: Il existe un ensemble $ X$ tel que $ \varnothing\in X$ et tel que si $ x\in X$ alors $ x$ et les éléments de $ x$ sont des éléments de $ X$ .
Schéma d'axiomes de compréhension.: On vera plus tard.
Axiome du choix.: Étant donné un ensemble $ X$ non vide d'ensemble non vide, il existe un ensemble, appelé ensemble de choix, contenant exactement un élément de chaque élément de $ X$ .

Plusieurs axiomes sont laissés pour plus tard. Nous les détaillerons dans la suite de ce cours. Mais la majorité de ces axiomes sont très naturels, dans le sens où ils ne sont pas contre nature à la logique classique. L'axiome du choix est beaucoup plus problématique : dans une version simple il stipule qu'étant donné plein d'ensemble, on peut choisir un élément dans chaque ensemble. Ce qui est formellement facile lorsqu'on dispose d'un nombre fini d'ensemble mais est plus compliqué à imaginer avec une infinité. Cela donne naissance à des "paradoxes" qui n'en sont pas. Comme par exemple le paradoxe de Banach-Tarski qui utilise l'axiome du choix : il existe un moyen de découper une boule en 5 morceaux de tel manière qu'un réassemblement de ces morceaux permette d'obtenir deux boules strictement identique à la première. Ce résultat contre nature n'en reste pas moins un théorème c'est à dire un énoncé démontré par un raisonnement logique, donc indiscutablement vrai. Dans le cœur de la preuve il y a l'axiome du choix qui permet de choisir des éléments dans un ensemble sans forcement maitriser ces choix. Ainsi même si l'énoncé du paradoxe semble faire croire que l'axiome du choix est faux, un œil bienfaisant sur la démonstration permet de comprendre que c'est "mathématiquement" possible mais irréalisable dans la pratique. Cela suffit à certain pour considérer l'axiome du choix et donc la théorie ZFC. D'autre par contre ne vont pas l'admettre et travailler avec la théorie ZF... Quoiqu'il en soit c'est avec ces axiomes et uniquement eux que l'on construit les ensembles classiques. Partons du commencement avec $ \varnothing$ , l'ensemble vide (qui ne contient aucun élément). En utilisant l'axiome de la paire, on construit alors l'ensemble $ \{\varnothing\}$ qui est donc un ensemble composé d'un élément qui est l'ensemble vide. En utilisant encore l'axiome de la paire on construit l'ensemble $ \{\varnothing,\{\varnothing\}\}$ . En continuant de la sorte jusqu'à l'infini, ce qui est possible d'après l'axiome de l'infini on construit un ensemble \[\left\{ \underbrace{\varnothing}_{0}, \underbrace{\{\varnothing\}}_{1}, \underbrace{\{\varnothing,\{\varnothing\}\}}_{2}, \underbrace{\{\varnothing,\{\varnothing\},\{\varnothing,\{\varnothing\}\}\}}_{3},\ldots \right\}\] Cet ensemble est communément noté $ \N$ . Ainsi le nombre $ 3$ manipulé depuis toujours est en fait l'ensemble $ \{\varnothing,\{\varnothing\},\{\varnothing,\{\varnothing\}\}\}$ . Dans la pratique que nous ferons de la théorie des ensembles nous considérons toujours un référentiel, c'est un dire un ensemble de base dont l'existence et la construction sont admises. On le notera dans la pratique $ \E$ . Toutes les définitions et notations seront relatives à ce référentiel. En particulier tous les ensembles que nous manipulerons seront des sous-ensembles de $ \E$ .

Définition

On dira que $ A$ est un sous-ensemble de $ B$ si tous les éléments de $ A$ sont des éléments de $ B$ . On note \[A\subseteq B\]

Par exemple $ \N$ est un sous-ensemble de $ \Z$ , lui même un sous-ensemble de $ \Q$ , lui même un sous-ensemble de $ \R$ , lui même un sous-ensemble de $ \C$ , lui même un sous-ensemble de $ \mathbb{H}$ .

Représentation

L'outil de prédilection en théorie des ensembles est le diagramme de Venn¹. Il consiste à placer les différents ensembles que l'on souhaite combiner comme des patates². Il faut cependant faire attention, il faut, en générale, représenter tous les cas de figure possible.

Bon diagramme de Venn

Mauvais diagramme de Venn

Proposition

Un diagramme de Venn faisant intervenir $ n$ ensembles différents, découpe le référentiel en $ 2^n$ zone.

Démonstration

Ce résultat se démontre par récurrence sur $ n$ ce qui n'est pas le lieu ici.

Deux ensembles partagent $ \E$ en $ 4$ zones

Trois ensembles partagent $ \E$ en $ 8$ zones

Peut-être que les curieux pourraient s'intéresser à Newroz... Le calcul avec les diagrammes de Venn, permet assez souvent de représenter des configurations d'ensembles et d'observer des résultats. Il existe deux manières de définir/utiliser les ensembles :

en extension.

Dans cette configuration, on décrit l'ensemble par les éléments qui le compose, entre accolade, comme dans l'exemple suivant : \[A=\left\{a, 1, "bonjour", \pi\right\}\] Il y a deux règles a respecter dans ce cas :

L'ordre des éléments ne compte pas (c'est en fait l'axiome d'extentionnalité). \[\left\{a, 1, "bonjour", \pi\right\}=\left\{1, a, "bonjour", \pi\right\}\]
On ne répète pas le même éléments. \[\left\{a, 1, 1, 1, "bonjour", \pi\right\}=\left\{a, 1, "bonjour", \pi\right\}\]

en compréhension.

Cela est une conséquence de l'axiome du schéma d'axiomes en compréhension. On défini un ensemble par la propriété qui le caractérise (qui permet de le comprendre). \[B=\left\{x\in \R\Big|x+1{<}0\right\}\] Nous donnerons plus de détails sur les ensembles en compréhension dans le chapitre sur les prédicats.

Opérations

Il existe trois opérations élémentaires sur les ensembles. On peut en définir également d'autre mais elles se ramènes souvent à s'interpréter avec ces trois suivantes. On fixe un référentiel $ \E$ . C'est entre autre l'axiome de la réunion qui justifie la première définition. Les autres découlent de celle-ci.

Définition

L'union de deux ensembles $ A$ et $ B$ , notée \[A\cup B\] est le sous-ensemble de $ \E$ formé des éléments qui appartiennent soit à $ A$ soit à $ B$ .

Définition

L'intersection de deux ensembles $ A$ et $ B$ , notée \[A\cap B\] est le sous-ensemble de $ \E$ formé des éléments qui appartiennent à la fois à $ A$ et à $ B$ .

Définition

Le complémentaire de $ A$ , noté \[\Ab\] est le sous-ensemble de $ \E$ formé des éléments qui ne sont pas dans $ A$ .

Le complémentaire est toujours relatif au référentiel. Il est parfois nécessaire de le préciser. On note alors $ \complement_\E A$ (nous pourrons nous passer de cette notation).

CANDIMATICA\copyright

Il peut être parfois fastidieux de faire des diagrammes de Venn. Par exemple le diagramme de Venn à 5 ensembles est d'une part assez difficile à construire et d'autre part, un tel diagramme est assez peu élégant. On peut travailler avec les ensembles en s'appuyant sur des résultats bien connus, résumés dans l'acronyme CANDIMATICA. On fixe 3 trois ensembles $ A$ , $ B$ et $ C$ d'un même référentiel $ \E$ .

Théorème [CANDIMATICA]

Commutativité.: $ A\cup B=B\cup A$ et $ A\cap B=B\cap A$ .
Associativité.: $ (A\cup B)\cup C=A\cup (B\cup C)$ et $ (A\cap B)\cap C=A\cap (B\cap C)$ .
Neutralité.: $ A\cup\varnothing=A$ et $ A\cap\E=A$ .
Distributivité.: $ \A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$ et $ A\cap(B\cup C)=(A\cap B)\cup (A\cap C)$ .
Idempotence.: $ A\cup A=A$ et $ A\cap A=A$ .
Morgan.: $ \overline{A\cup B}=\Ab\cap \Bb$ et $ \overline{A\cap B}=\Ab\cup \Bb$ .
Absorption 1.: $ A\cup \E=\E$ et $ A\cap\varnothing = \varnothing$ .
Tiers exclus.: $ A\cup\Ab=\E$ .
Involution.: $ \overline{\Ab}=A$ .
Contradiction.: $ A\cap\Ab=\varnothing$ .
Absoption 2.: $ A\cup(A\cap B)=A$ et $ A\cap(A\cup B)=A$ .

Démonstration

On peut par exemple comparer les diagrammes de Venn et vérifier qu'ils couvrent les même zones. Vérifions une des propriétés de Morgan. Voici le diagramme de $ A\cup B$

Le complémentaire est donc

Colorons $ \Ab$ (en bleue) et $ \Bb$ (en rouge).

On observe alors que l'intersection de ces deux ensembles est bien $ \overline{A\cup B}$ .

Ensemble des parties

L'axiome de l'ensemble des parties justifie la définition suivante.

Définition

Pour un ensemble $ A$ , on note $ \P(A)$ l'ensemble de tous les sous-ensembles de $ A$ . \[\P(A)=\{X\subseteq A\}\]

Par exemple si $ A=\{a, b\}$ alors \[\P(A)=\left\{\varnothing, \{a\}, \{b\}, \{a, b\}\right\}.\] Si $ A=\{\alpha, \beta,\gamma\}$ alors \[\P(A)=\left\{\varnothing, \{\alpha\}, \{\beta\}, \{\gamma\}, \{\alpha, \beta\}, \{\alpha, \gamma\}, \{\beta, \gamma\}, \{\alpha, \beta, \gamma\}\right\}\]

Cardinalité

Définition

La cardinalité d'un ensemble $ A$ , noté $ \Card A$ (ou parfois $ |A|$ ou $ Card(A)$ ) est le nombre d'élément de $ A$ .

Ainsi, si $ A=\{a, b, c\}$ alors $ \Card A=3$ .

Proposition

Soient $ A$ et $ B$ deux ensembles. \[\Card(A\cup B)=\Card A+\Card B-\Card(A\cap B)\]

Démonstration

Si on compte $ \Card A+\Card B$ les éléments de $ A\cap B$ on été compté deux fois (une fois dans $ A$ et une fois dans $ B$ ) de sorte que $ \Card A+\Card B-\Card(A\cap B)$ compte le nombre d'élément de $ A\cup B$ .

Proposition

Soit $ A$ un ensemble. \[\Card\P(A)=2^{\Card A}\]

Démonstration

Il s'agit de raisonner par récurrence sur $ \Card A$ .

¹John Venn (1834-1923) est un mathématicien britannique.
²On parle d'ailleurs de patatoïdes.