Définitions et généralités

1. Donner la définition rigoureuse d'un ensemble.
2. Quelles sont les manières de définir un ensemble ?
3. Rappeler les opérations sur les ensembles et les définir rigoureusement.
4. Si $A$ est une partie de $B$ que peut-on dire de $A$ par rapport à $B$ hormis que c'est une partie...
5. Qu'appelle-t-on ensembles disjoints ?
6. Donner la définition d'un n-uplet.
7. Discuter à l'oral avec le tuteur des différences entre $n$-uplets et ensembles.

Inclusion v/s appartenance.

Soient $A=\{0, 1, 7, 5, 6, 9\}$ et $B=\{1, 8, 4, 2\}$. Déterminer si les expressions mathématiques suivantes sont vraies ou fausses.

1. $\{1, 2 \} \in A$
2. $ 0 \in A $
3. $A \subset B$
4. $\{1\} \in A$
5. $\{1\} \subset A $ et $B \subset \{1\}$
6. $14 \subset A$
7. $\{14\} \in B$
8. $A \subset A \cup B$

Soient $E$ un ensemble et $A,B \subseteq E$. On considère la relation $\mathcal{R}_e$ suivante :

$$A\mathcal{R}_eB \Longleftrightarrow A \subset B$$

Montrer que $\mathcal{R}_e$ est une relation d'ordre.

1. Déterminer les propriétés d'union, d'intersection et de complémentaire.
2. Comparez vos résultats avec ceux de vos voisins.

Montrer que les ensembles suivants sont égaux :

1. $C=\{ (x,y) \in \R^2 \mid y = x^2\}$ et $D=\{(t^2, t), t \in \R\}$
2. $E=\{(x,y) \in \R^2 \mid y^2=4x\}$ et $F=\{(t^2, 2t) \mid t \in \R\}$

1. Rappeler les définitions d'une fonction et d'une application.
2. Déterminer si les applications suivantes sont bien définies. Justifier le cas échéant.
3. $$\begin{align*}\mathcal{E}_1 : \R & \to \mathbb{R} \\ x &\mapsto \sqrt{x}\end{align*}$$
4. $$\begin{align*}\mathcal{E}_2 : \mathbb{Q} & \to \Z \\ \frac{p}{q} &\mapsto p\end{align*}$$
5. $$\begin{align*}\mathcal{E}_3 : \R & \to \{-1, 0, 1\} \\ x &\mapsto \begin{cases} -1 & \text{si } x < 0 \\ 0 & \text{si } x = 0 \\ 1 & \text{si } x> 0 \end{cases}\end{align*}$$
6. $$\begin{align*}\mathcal{E}_4 : \{ x \in \Z \mid x \%2=0 \} & \to \Z \\ x &\mapsto \frac{x}{2}\end{align*}$$

On considère l'objet mathématique suivant :

$$\begin{align*} f : \R \backslash\{1\} &\to \R \\ x & \mapsto \frac{x+1}{x-1} \end{align*}$$

$f$ est-elle bijective ? Vous utiliserez un raisonnement approprié muni d'une rédaction pour répondre correctement à la question posée.

Les relations données par les graphes ci-dessous sont-elles réflexives ? symétriques ? antisymétrique ? transitives ? Sont-elles d'ordre ou d'équivalence ?

Pour chacune des relations binaires $\mathcal{R}$ suivante, déterminer si elles sont réflexives, symétriques, antisymétriques, transitives. De plus pour les relations qui définissent une relation d'équivalence, décrire leur classes d'équivalences et leur ensemble quotient.

1. $\forall a,b \in \N \quad a\mathcal{R}b \Longleftrightarrow |a-b| \le 2$
2. $\forall a,b \in \mathbb{Q}^* \quad a\mathcal{R}b \Longleftrightarrow ab > 0$
3. $\forall a,b \in \mathbb{Q}^* \quad a\mathcal{R}b \Longleftrightarrow \frac{a}{b} \in \N^*$
4. $\forall a,b \in \mathbb{Q} \quad a\mathcal{R}b \Longleftrightarrow (a-b) \in \N$
5. $\forall a,b \in \R \quad a\mathcal{R}b \Longleftrightarrow a-b=a^2-b^2$

1. Soit $\mathcal{R}$ la relation binaire définie sur $\Z$ par : $$\forall (a,b) \in \Z^2, \: a\mathcal{R}b \Longleftrightarrow a-b \text{ est pair}$$ Montrer que $\mathcal{R}$ est une relation d'équivalence et déterminer ses classes d'équivalences.
2. Soit $n \in \N^*$. Soit $\mathcal{R}_n$ une relation binaire définie sur $\Z$ par : $$\forall (a,b) \in \Z^2, \; a\mathcal{R}_nb \Longleftrightarrow n \text{ divise } a-b$$ Montrer que $\mathcal{R}_n$ est une relation d'équivalence et donner ses différentes classes d'équivalences.

Soit $\mathcal{R}$ une relation binaire sur un ensemble $E$. La relation $\mathcal{R}$ est dite circulaire sur $E$ si et seulement si :

$$\forall a,b,c \in E, \; (a\mathcal{R}b \land b\mathcal{R}c) \Longrightarrow c\mathcal{R}a$$

Montrer que si $\mathcal{R}$ est réflexive est circulaire sur $E$, alors elle est une relation d'équivalence sur $E$.

On considère l'ensemble $A=\{1, 2, 3\}$ et la relation $\mathcal{R} \subseteq A \times A$ définie par :

$$\mathcal{R}=\{(1, 1), (1, 2), (2, 3)\}$$

1. Représentation de la relation
2. Représenter $\mathcal{R}$ sous forme de graphe orienté.
3. Représenter $\mathcal{R}$ à l'aide d'une matrice booléenne $M_\mathcal{R}$.
4. Déterminer les propriétés de la relation à partir de ces représentations.
5. Modifier la relation
6. Ajouter des couples pour rendre $\mathcal{R}$ réflexive.
7. Ajouter des couples pour rendre $\mathcal{R}$ symétrique.
8. Ajouter des couples pour rendre $\mathcal{R}$ transitive.

1. Soient $A$ et $B$ deux ensembles finis et $\mathcal{R}$ une relation définie sur $A\times B$. $$A=\{a_1, a_{i+1}, \ldots, a_n\} \quad ; \quad B=\{b_j, b_{j+1}, \ldots, b_m\}$$ On rappelle la définition de la matrice booléenne $M_{\mathcal{R}}$ d'ordre $(n,m)$ associée à la relation $\mathcal{R}$. $$(M_\mathcal{R})_{ij} = \begin{cases} 1 & \text{si } a_i\mathcal{R}b_j \\ 0 &\text{sinon}\end{cases}$$
2. Écrire les algorithmes qui ont, en entrée une matrice booléenne associée à une relation binaire sur un ensemble fini et qui précisent si cette relation est réflexive, symétrique, ou transitive.
3. Soient deux relations $\mathcal{R}$ et $\mathcal{S}$ de $A \times B$, on rappelle que, $\forall x, y \in A \times B$ : $$x(\mathcal{R}+\mathcal{S})y = x(\mathcal{R}\cup\mathcal{S})y$$ $$x(\mathcal{R}\mathcal{S})y = x(\mathcal{R}\cap\mathcal{S})y$$ On définit les deux opérations suivantes sur les matrices booléenne $P$ et $Q$ : $$P \lor Q : (P\lor Q)_{ij}=P_{ij} \lor Q_{ij}$$ $$P \land Q : (P\land Q)_{ij}=P_{ij} \land Q_{ij}$$ Montrer que $M_{\mathcal{R}+\mathcal{S}}=M_{\mathcal{R}}\lor M_{\mathcal{S}}$
4. Montrer que $M_{\mathcal{R}\mathcal{S}}=M_{\mathcal{R}}\land M_{\mathcal{S}}$
5. Donner les algorithmes permettant de calculer $P \lor Q$ et $P \land Q$ avec $P$ et $Q$ comme paramètres.
6. On définit maintenant la composition $\mathcal{R} \circ \mathcal{S}$ de deux relations $\mathcal{R} \subseteq A \times B$ et $\mathcal{S} \subseteq B \times C$ telle que : $$x,y \in A \times C, \; x(\mathcal{R} \circ \mathcal{S})y \Longleftrightarrow \exist z \in B, \; x\mathcal{R}z\land z\mathcal{S}y$$ On définit aussi le produit booléen $A \otimes B$ de deux matrices booléennes d'ordre $(n,p)$ et $(p,m)$ respectivement par : $$(A \otimes B)_{ij}=\underset{k=1}{\overset{p}{\bigvee}}a_{ik}\land b_{kj}$$
7. Vérifier que $\mathcal{R} \circ (\mathcal{S} \circ \mathcal{T})=(\mathcal{R} \circ \mathcal{S}) \circ \mathcal{T}$
8. Montrer que $M_{\mathcal{R} \circ \mathcal{S}} = M_{\mathcal{R}} \otimes M_{\mathcal{S}}$
9. Soit $A=\{a,b,c,d\}$ et $\mathcal{R} \subseteq A^2$ une relation telle que $\mathcal{R}=\{(a,b), (b,c), (c,d)\}$
10. Écrire la matrice booléenne associée à $\mathcal{R}$ et construire son graphe.
11. Construire le graphe de $\mathcal{R}^2$, donner sa matrice et vérifier que la formule du b) permet de la retrouver.
12. Écrire l'algorithme qui permet de calculer le produit booléen de deux matrice booléenne.

On considère l'ensemble $A=\{a,b,c\}$ et la relation définie sur $A$ par :

$$\mathcal{R} = \{(a,b), (b,c)\}$$

1. Construire le graphe de la relation.
2. Décrire les propriétés de la relation.
3. Construire les clôtures de la relation si besoin.

Soit $\mathcal{R}$ une relation définie sur un ensemble $A$ fini.

1. Construire les clôtures de la relation de l'exercice : 13-2c)
2. Montrer que la clôture réflexive de $\mathcal{R}$ est $\mathcal{R}+I_A$ où $I_A$ est définie par : $$\forall x,y \in A, \; xI_Ay \Longleftrightarrow x=y$$
3. Montrer que la clôture symétrique de $\mathcal{R}$ est $\mathcal{R}+\mathcal{R}^{-1}$ où $\mathcal{R}^{-1}$ est définie par : $$\forall x,y \in A, \; x\mathcal{R}^{-1}y \Longleftrightarrow y\mathcal{R}x$$
4. Montrer que la clôture transitive de $\mathcal{R}$ est : $$\mathcal{R}^+ = \underset{k=1}{\overset{|A|}{\sum}}\mathcal{R}^k$$ où $\mathcal{R}^k=\underbrace{\mathcal{R} \circ \mathcal{R}\circ \ldots \circ \mathcal{R}}_{k-fois}$ et $|A|$ est le cardinal de l'ensemble $A$.
5. Écrire les algorithmes de calcul de clôtures réflexives, symétriques et transitives.