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)\) ).