Corrigé TD N° : 2 Ensembles, Relations binaires et Applications

Correction de l'exercice 1

  1. \(\{9\} \cup \{9\} = \{(9,9)\}\). Faux

    Justification : \(A - B = \{x \in E | x \in A \land x \notin B\}. \)

    D'où :

    \(\{9\} \cup \{9\} = \{9\}\).

  2. \(\{3\} - \{3\} = \{0\}\). Faux

    Justification : \(A - B = \{x \in E | x \in A \land x \notin B\}\).

    D'où :

    \(\{9\} \cup \{9\} = \{9\}\).

  3. \( \{3\} \times \{8\} = \{24\}\). Faux

    Justification : \(E \times F = \{(x,y) | x \in E \land y \in F\}.\)

    D'où : \( \{3\} \times \{8\} = \{(3,8)\}\).

  4. \(\varnothing \subset \{\varnothing\}\). Vrai

    Justification : L'ensemble vide est inclus dans tout ensemble.

Correction de l'exercice 2

        1. \(A \cap B = \{\{a\}\}\)

        2. \(A \cup B = \{\{a\}, \{b\}, \{a, b\}\}\)

        3. \(B \setminus A = \{\{a, b\}\\)

        4. \(A \triangle B = \{\{b\}\}\)

      1. On a :

        \(\{a\} \in A \cap B.\)

        \(\{\{b\}\} \subset A \cup B.\)

        \(\{a\} \notin B \setminus A.\)

        \(\{a,b\} \in A \triangle B.\)

        \(\{\{a\}\} \not\subset A \triangle B.\)

      1. Soit \(x \in E\)

        \(x \in \overline{A \cup B} \Longleftrightarrow x \notin(A \cup B) \\ \Longleftrightarrow x \notin A \wedge x \notin B \\ \Longleftrightarrow x \in \bar{A} \wedge x \in \bar{B} \\ \Longleftrightarrow x \in \bar{A} \cap \bar{B} \\\)

        D'où : \( \overline{A \cup B}=\bar{A} \cap \bar{B} \)

      2. Soit \(x \in E\)

        \(\Longleftrightarrow x \notin(A \cap B) \\ \Longleftrightarrow x \notin A \vee x \notin B \\ \Longleftrightarrow x \in \bar{A} \vee x \in \bar{B} \\\)

        D'où : \(\Longleftrightarrow x \in \bar{A} \cup \bar{B}\)

      3. Soit \(x \in E\)

        \(x \in \bar{B}  \Longrightarrow x \notin B \)

        \( \Longrightarrow x \notin A \text { car } A \subset B \)

        \( \Longrightarrow x \in \bar{A} \\ \)

        D'où : \(A \subset B  \Longrightarrow \bar{B} \subset \bar{A}.\)

      1. \(\overline{A \cup B} \cap \overline{C \cup \bar{A}}  =(\bar{A} \cap \bar{B}) \cap(\bar{C} \)

        \( \cap A) \text { (Lois de Morgan). } \)

        \( =(\bar{A} \cap A) \cap(\bar{B} \cap \bar{C})(\cap \text { est associative). } \)

        \( =\emptyset \cap(\bar{B} \cap \bar{C}) \)

        \( =\emptyset\)

      2. \( \overline{A \cap B} \cup \overline{C \cap \bar{A}}  =(\bar{A} \cup \bar{B}) \cup(\bar{C} \cup A) \text { (Lois de Morgan). } \)

        \( =(\bar{A} \cup A) \cup(\bar{B} \cup \bar{C})(\cup \text { est associative). } \)

        \( =E \cup(\bar{B} \cup \bar{C}) \)

        \( =E\).

Correction de l'exercice 3

    • \(x \in A \triangle B \Leftrightarrow x \in (A \setminus B) \cup (B \setminus A) \)

      \(\Leftrightarrow (x \in A \setminus B) \lor (x \in B \setminus A) \)

      \(\Leftrightarrow (x \in A \land x \notin B) \lor (x \in B \land x \notin A)\)

      \( \Leftrightarrow [(x \in A) \lor (x \in B \land x \notin A)] \land [(x \notin B) \lor (x \in B \land x \notin A)] \)

      \(\Leftrightarrow [(x \in A \lor x \in B) \land (x \in A \lor x \notin A)] \land [(x \notin B \lor x \in B) \land (x \notin B \lor x \notin A)]\)

      \( \Leftrightarrow [x \in (A \cup B) \cap E] \land [x \in E \cap A \cap B] \)

      \(\Leftrightarrow x \in (A \cup B) \land (x \notin A \cap B)\)

      \(\Leftrightarrow x \in (A \cup B) \setminus (A \cap B)\).

      D'où : \(A \triangle B = (A \cup B) \setminus (A \cap B)\).

    • \((A \cap B) \cap \overline{(A \cap C)} =(A \cap B) \cap(\bar{A} \cup \bar{C}) \)

      \(=(A \cap B \cap \bar{A}) \cup(A \cap B \cap \bar{C}) \)

      \( =\emptyset \cup(A \cap B \cap \bar{C}) \)

      \( =A \cap B \cap \bar{C} \)

    • \( (A \cap C) \cap \overline{(A \cap B)}  =(A \cap C) \cap(\bar{A} \cup \bar{B}) \)

      \( =(A \cap C \cap \bar{A}) \cup(A \cap C \cap \bar{B})\)

      \( =\emptyset \cup(A \cap C \cap \bar{B}) \)

      \( =A \cap C \cap \bar{B}\)

  1. \((A \cap B) \Delta(A \cap C)  =((A \cap B) \backslash(A \cap C)) \cup((A \cap C) \backslash(A \cap B))\)

    \(=((A \cap B) \cap \overline{(A \cap C)}) \cup((A \cap C) \cap \overline{(A \cap B)}) \)

    \(=(A \cap B \cap \bar{C}) \cup(A \cap C \cap \bar{B})\)

    \(=A \cap((B \cap \bar{C}) \cup(C \cap \bar{B}))\)

    \( =A \cap((B \backslash C) \cup(C \backslash B)) \)

    \( =A \cap(B \triangle C).\)

Correction de l'exercice 4

On va procéder par double inclusion. Soit \((x,y) \in (A \times B) \cap (C \times D)\). Alors \((x,y) \in A \times B\) et donc \(x \in A\), \(y \in B\). On a aussi \((x,y) \in (C \times D)\), et donc \(x \in C\) et \(y \in D\). Ainsi, \(x \in A \cap C\) et \(y \in B \cap D\). Ceci prouve que \((x,y) \in (A \cap C) \times (B \cap D)\).

Réciproquement, soit \((x,y) \in (A \cap C) \times (B \cap D)\). Alors \(x \in A \cap C\) et donc \(x \in A\) et \(x \in C\).

De même, \(y \in B \cap D\), donc \(y \in B\) et \(y \in D\). Ainsi, \((x,y) \in A \times B\) et \((x,y) \in C \times D\). On conclut que \((x,y) \in (A \times B) \cap (C \times D)\).

En définitive : \((A \times B) \cap (C \times D) = (A \cap C) \times (B \cap D)\)

Correction de l'exercice 5

    • Montrons que \(R\) est une relation d'équivalence.

      1. \(R\) est réflexive ?

        \(R\) est réflexive.

        En effet, on a :

        \(\forall x \in \mathbb{Z} : x - x = 0 \text{ est un multiple de } 3.\)

        D'où : \(\forall x \in \mathbb{Z} : xRx.\)

      2. R est symétrique ?

        \(R\) est symétrique. En effet, on a :

        \( \forall x, y \in \mathbb{Z} : xRy \Rightarrow \exists k \in \mathbb{Z} : x - y = 3k.\)

        \( \Rightarrow \exists k_1 = (-k) \in \mathbb{Z} : y - x = 3k_1.\)

        \( \Rightarrow yRx.\)

      3. \(R\) est transitive ?

        \(R\) est transitive. En effet, on a :

        \(\forall x, y, z \in \mathbb{Z} : (xRy \land yRz) \Rightarrow (\exists k \in \mathbb{Z} : x - y = 3k) \land \exists k_0 \in \mathbb{Z} : y - z = 3k_0.\)

        \( \Rightarrow \exists p = k + k_0 \in \mathbb{Z} : x - z = 3p.\)

        \( \Rightarrow xRz. \)

        Par conséquent : \(R\) est une relation d'équivalence car elle est à la fois réflexive, symétrique et transitive.

    • Déterminons l'ensemble quotient \(\mathbb{Z}/R\).

      Soit \(x \in \mathbb{Z}\), cherchons \(y \in \mathbb{Z}\) tel que \(yRx\).

      \(yRx \Leftrightarrow \exists k \in \mathbb{Z} : y - x = 3k.\)

      \( \Leftrightarrow \exists k \in \mathbb{Z} : y = x + 3k.\)

      Donc :

      \(\forall x \in \mathbb{Z} :\dot{x} = \{x + 3k\} \text{ où } k \in \mathbb{Z}.\)

      Ainsi :

      \( \mathbb{Z}/R = \{\{x + 3k\} \text{ où } k \in \mathbb{Z}, x \in \mathbb{Z}\}.\)

    • Montrons que :

      \(\dot{7} =\dot{4}.\)

      \( x \in\dot{7} \Leftrightarrow \exists k \in \mathbb{Z} : x = 7 + 3k.\)

      \(\Leftrightarrow \exists k \in \mathbb{Z} : x = 4 + 3 + 3k.\)

      \( \Leftrightarrow \exists k_0 = (1 + k) \in \mathbb{Z} : x = 4 + 3k_0.\)

      \(\Leftrightarrow x \in\dot{4}.\)

    • Montrons que "\(\leq\)" est une relation d'ordre sur \(\mathbb{N}^*\).

      1. \(R\) est réflexive ?

        \(R\) est réflexive. En effet, on a :

        \(\forall x \in \mathbb{N}^* : x \text{ divise } x.\)

        D'où :

        \(\forall x \in \mathbb{N}^* : x \leq x.\)

      2. \(R\) est anti-symétrique car :

        \( \forall x, y \in \mathbb{N}^* : (x \leq y) \land (y \leq x) \Rightarrow (x \text{ divise } y) \land (y \text{ divise } x).\)

        \(\Rightarrow x = y.\)

      3. \( R\) est transitive ?

        \(R\) est transitive. En effet, on a :

        \( \forall x, y, z \in \mathbb{N}^* : (x \leq y \land y \leq z) \Rightarrow (x \text{ divise } y) \land (y \text{ divise } z).\)

        \(\Rightarrow x \text{ divise } z.\)

        \( \Rightarrow x \leq z.\)

        Par conséquent : "\(\leq\)" est une relation d'ordre car elle est à la fois réflexive, anti-symétrique et transitive.

    • L'ordre est-il total ?

      "\(\leq\)" est une relation non totalement ordonnée sur \(\mathbb{N}^*\).

      En effet : par exemple les nombres \(x = 2\) et \(y = 9\) ne sont pas comparables.

      On a :

      \( (2 \text{ ne divise pas } 9) \land (9 \text{ ne divise pas } 2).\)

      D'où :

      \( \exists (x, y) \in \mathbb{N}^* \times \mathbb{N}^* : x \nleq y \land y \nleq x.\)

      Par conséquent : "\(\leq\)" est une relation d'ordre partielle.

Correction de l'exercice 6

  1. Montrons que : \( f(A \cup B) = f(A) \cup f(B)\).

    Soit  \(y \in F\).

    \( y \in f(A \cup B) \iff \exists x \in A \cup B, y = f(x).\)

    \( \iff \exists x: ((x \in A) \lor (x \in B)) \land (y = f(x)).\)

    \(\iff \exists x: ((x \in A) \land (y = f(x))) \lor ((x \in B) \land (y = f(x))). \)

    \( \iff [(\exists x \in A) \land (y = f(x))] \lor [(\exists x \in B) \land (y = f(x))]\)

    \( \iff (y \in f(A)) \lor (y \in f(B)).\)

    \(\iff y \in f(A) \cup f(B).\)

    Ainsi, \( f(A \cup B) = f(A) \cup f(B)\).

    • On a : \([-2,1]\cap[0,3]=[0,1]\)

      Donc \(f(A \cap B) = f([0, 1]) = \{ x^2, 0 \leq x \leq 1 \} = [0, 1].\)

      En effet : \(0 \leq x \leq 1 \Rightarrow 0 \leq x^2 \leq 1.\)

      D'autre part, on a :\( f(B) = f([0, 3]) = \{ x^2, 0 \leq x \leq 3 \} = [0, 9].\)

      En effet : \(0 \leq x \leq 3 \Rightarrow 0 \leq x^2 \leq 9.\)

      et

      \( f(A) = f([-2, 1]).\)

      \( = f([-2, 0] \cup [0, 1]).\)

      \( = f([-2, 0]) \cup f([0, 1]).\)

      \( = \{ x^2, -2 \leq x \leq 0 \} \cup [0, 1] .\)

      \( = [0, 4] \cup [0, 1] .\)

      \( = [0, 4] .\)

      Car :

      \( f([0,1]) = [0,1] et f([-2,0]) = \{x^2 \mid -2 \leq x \leq 0\} et -2 \leq x \leq 0 \Rightarrow 0 \leq x^2 \leq 4 .\)

      On a : \(f(A) \cap f(B) = [0,4] \cap [0,9] = [0,4] .\)On voit que : \( [0,1] \subset [0,4] et [0,4] \not\subset [0,1] .\)

      D'où : \( f(A) \cap f(B) \neq f(A \cap B) . \)

    • Soit \(y \in F\) , Quelle condition doit vérifier f pour que : \(f(A) \cap f(B) \subset f(A \cap B)\) .

      \( y \in f(A) \cap f(B) \iff y \in f(A) \land y \in f(B) .\)

      Si \( f\) est injective alors \(x_1 = x_2\) .

      Ainsi,

      \( \exists x \in A \cap B : y = f(x). \)

      D'où :

      \(y \in f(A \cap B) .\)