\( %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 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 en compréhension

Prédicats

L'énoncé "$ x+1{<}0$ " n'est pas une proposition, parce qu'il y a ambiguïté sur la valeur de vérité. Cependant lorsque l'on remplace $ x$ par n'importe quel nombre réel cela deviens une proposition. Cela motive la définition de prédicat.

Définition

Un prédicat sur un ensemble $ \E$ est un énoncé $ p(x)$ dépendant d'un paramètre $ x$ , de sorte qu'en remplaçant $ x$ par n'importe quelle valeurs $ a\in \E$ , $ p(a)$ est une proposition

Ainsi $ p(x)="x+1{<}0"$ est un prédicat sur $ \R$ de sorte que $ p(1)$ est faux, comme $ p(0)$ ou $ p(-1)$ mais $ p(-\pi)$ est vrai.

Définition

Soit $ p$ un prédicat sur un ensemble $ \E$ . La classe de $ p$ sur $ \E$ , noté $ \Cl_\E(p)$ est l'ensemble des valeurs de $ \E$ tel que le prédicat soit vrai. \[\Cl_\E(p)=\left\{x\in \E\Big|p(x)=\top\right\}\]

Avec notre exemple de $ p(x)="x+1{<}0"$ , on observe que $ \Cl_\R(p)=]-\infty ; -1[$ : \[]-\infty ; -1[=\left\{x\in \R\Big|"x+1{<}0"=\top\right\}\] Dans la pratique on ne note pas $ \top$ , il est sous-entendu qu'il n'y a que la valeur de vérité vraie qui nous intéresse, de sorte que l'on préfère la notation \[]-\infty ; -1[=\left\{x\in \R\Big|x+1{<}0\right\}\] Une telle notation rentre dans le cadre du schéma d'axiome en compréhension de la théorie des ensembles. Ce schéma d'axiome dis en qu'une telle considération et possible et bien construite.

Pont entre proposition et ensemble

D'un coté nous avons la théorie des propositions avec sa batterie de propriétés (candimatica) et de l'autre la théorie des ensembles avec aussi ses propriété (candimatica). Les prédicats se trouvent à l'intersection de ces deux théories et le théorème suivant en forme en quelque sorte le pont

Théorème

Soient $ p$ et $ q$ deux prédicats définis sur un ensemble $ \E$ .

$ \Cl_\E(p\ou q)=\Cl_\E(p) \cup \Cl_\E(q)$
$ \Cl_\E(p\et q)=\Cl_\E(p) \cap \Cl_\E(q)$
$ \Cl_\E(\non p)=\overline{\Cl_\E(p)}$
$ \Cl_\E(p\implique q)=\overline{\Cl_\E(p)} \cup \Cl_\E(q)$
$ \Cl_\E(p\equivalent q)=\left(\overline{\Cl_\E(p)} \cup \Cl_\E(q)\right)\cap\left(\overline{\Cl_\E(q)} \cup \Cl_\E(p)\right)$

Démonstration

C'est une conséquence triviale des définitions et constructions

Prenons pas exemple $ p(x)="x{>}0"$ et $ q(x)="x\leqslant 1"$ . D'après ce théorème : \begin{eqnarray*} \Cl_\R(p\implique q) &=&\overline{\Cl_\R(x{>}0)}\cup\Cl_\R(x\leqslant 1)\\ &=&\overline{]0 ; +\infty[}\cup ]-\infty ; 1]\\ &=&]-\infty ; 0]\cup ]-\infty ; 1]\\ &=&]-\infty ; 0] \end{eqnarray*} Cela signifie que pour tout les $ x\in ]-\infty ; 0]$ le prédicat $ "x{>}0"\implique "w\leqslant 1"$ est vrai. En particulier, si $ x=-12$ (la première proposition de cette implication est fausse, donc l'implication est vrai).

Quantificateurs

Il existe un outil permettant de transformer les prédicats en propositions. Il s'agit des quantificateurs. Comme leur nom l'indique, ils vont quantifier les prédicats. Il s'agit donc de savoir si cette quantification est vraie ou fausse ; on a donc une proposition. Il existe deux quantificateurs : l'universel et l'existentiel.

Définition

Soit $ p$ un prédicat sur un ensemble $ \E$ . Le quantificateur universel, noté $ \forall$ (prononcer quelque soit ou pour tout), transforme un prédicat $ p(x)$ en proposition $ \forall x, p(x)$ . De plus \[\left(\forall x, p(x)\right)=\top \qquad\Longleftrightarrow\qquad \Cl_\E(p)= \E\]

Ainsi la proposition $ \forall x, p(x)$ est vrai si et seulement si la classe de $ p$ est le référentiel d'étude. Dans la pratique, le référentiel est sous-entendu, on ne le précise pas. Il peut arriver qu'il soit nécessaire de le préciser, on note alors $ \forall x\in \E,\ p(x)$ . Considérons le prédicat $ p(x)="x\geqslant 0"$ . La proposition $ \forall x\in \R,\ p(x)$ est fausse tandis que $ \forall x\in \N,\ p(x)$ est vraie.

Définition

Soit $ p$ un prédicat sur un ensemble $ \E$ . Le quantificateur existentiel, noté $ \exists$ (prononcer il existe), transforme un prédicat $ p(x)$ en proposition $ \exists x, p(x)$ . De plus \[\left(\exists x, p(x)\right)=\top \qquad\Longleftrightarrow\qquad \Cl_\E(p)\neq \varnothing\]

Comme précédemment, si cela est nécessaire, on précise le référentiel d'étude. Par exemple $ \exists x\in \R, x^2{<}0$ est une proposition fausse tandis que $ \exists x\in \C, x^2{<}0$ est vraie. Le théorème suivant connecte ces deux quantificateurs et va justifier le raisonnement par contre-exemple.

Théorème

\[\non\left(\forall x, p(x)\right)=\left(\exists x, \non p(x)\right)\qquad\qquad\qquad\non \left(\exists x, p(x)\right)=\left(\forall x, \non p(x)\right)\]

Démonstration

Le second énoncé est la négation du premier (utilisé avec de l'involution). Démontrons alors le premier. \begin{eqnarray*} \non\left(\forall x, p(x)\right) &=&\non\left(\Cl_\E(p)=\E\right)\\ &=&\left(\Cl_\E(p)\neq\E\right)\\ &=&\left(\overline{\Cl_\E(p)}\neq\varnothing\right)\\ &=&\left(\Cl_\E(\non p)\neq\varnothing\right)\\ &=&\left(\exists x, \non p(x)\right)\\ \end{eqnarray*}

Ainsi lorsque l'on veut montrer que $ \forall x, p(x)$ est faux, il suffit de montrer qu'il existe un $ x$ tel que $ p(x)$ soit faux (c'est à dire $ \exists x, \non p(x)$ ).