We assume that $k \geqslant 0$ and that $C$ is a matrix in $\Delta_{k+1}$. We set $P = I_n + C$. We consider the endomorphism $\varphi$ of $\mathcal{M}_n(\mathbb{R})$ defined by $\forall M \in \mathcal{M}_n(\mathbb{R}), \varphi: M \mapsto P^{-1}MP$.
Let $i \in \llbracket 0, k \rrbracket$ and $M \in \Delta_i$. Show that there exists $M'$ in $H_{k+1}$ such that $\varphi(M) = M + M'$.

We assume that $k \geqslant 0$ and that $C$ is a matrix in $\Delta_{k+1}$. We set $P = I_n + C$. We consider the endomorphism $\varphi$ of $\mathcal{M}_n(\mathbb{R})$ defined by $\forall M \in \mathcal{M}_n(\mathbb{R}), \varphi: M \mapsto P^{-1}MP$. The matrix $N$ being the matrix defined in III.A.4, show that there exists $N'$ in $H_{k+1}$ such that $$\varphi(N) = N + NC - CN + N'$$

We assume that $k \geqslant 0$ and that $C$ is a matrix in $\Delta_{k+1}$. We set $P = I_n + C$. We consider the endomorphism $\varphi$ of $\mathcal{M}_n(\mathbb{R})$ defined by $\forall M \in \mathcal{M}_n(\mathbb{R}), \varphi: M \mapsto P^{-1}MP$. Let $T$ be an upper triangular matrix. We set $A = N + T$, $B = \varphi(A)$. Show that $B \in H_{-1}$ and that $$\begin{cases} \forall i \in \llbracket -1, k-1 \rrbracket, \quad B^{(i)} = A^{(i)} \\ B^{(k)} = A^{(k)} + NC - CN \end{cases}$$

Let $n$ be a non-zero natural number and $\Phi_n : \{0,1\}^n \rightarrow \llbracket 0, 2^n - 1 \rrbracket$, $(x_j)_{j \in \llbracket 1,n \rrbracket} \mapsto \sum_{j=1}^{n} x_j 2^{n-j}$.
Specify $\operatorname{Im} \Phi_n$ as a function of $A_n$, where $A_n = \left\{\sum_{j=1}^{n} x_j 2^{n-j}, (x_j)_{j \in \llbracket 1,n \rrbracket} \in \{0,1\}^n\right\}$.

Let $n$ be a non-zero natural number. We set $$\Phi_n : \left|\, \begin{aligned} \{0,1\}^n &\rightarrow \llbracket 0, 2^n - 1 \rrbracket \\ (x_j)_{j \in \llbracket 1,n \rrbracket} &\mapsto \sum_{j=1}^{n} x_j 2^{n-j} \end{aligned} \right.$$ and $A_n = \left\{ \sum_{j=1}^{n} x_j 2^{n-j},\, (x_j)_{j \in \llbracket 1,n \rrbracket} \in \{0,1\}^n \right\}$.
Specify $\operatorname{Im} \Phi_n$ as a function of $A_n$.

Let $n$ be a non-zero natural number. Show by induction $$\forall k \in \llbracket 0, 2^n - 1 \rrbracket, \quad k \in \operatorname{Im} \Phi_n$$ where $\Phi_n : \{0,1\}^n \rightarrow \llbracket 0, 2^n - 1 \rrbracket$, $(x_j)_{j \in \llbracket 1,n \rrbracket} \mapsto \sum_{j=1}^{n} x_j 2^{n-j}$.

Let $n$ be a non-zero natural number. We set $$\Phi_n : \left|\, \begin{aligned} \{0,1\}^n &\rightarrow \llbracket 0, 2^n - 1 \rrbracket \\ (x_j)_{j \in \llbracket 1,n \rrbracket} &\mapsto \sum_{j=1}^{n} x_j 2^{n-j} \end{aligned} \right.$$
Show by induction $$\forall k \in \llbracket 0, 2^n - 1 \rrbracket, \quad k \in \operatorname{Im} \Phi_n.$$

Let $n$ be a non-zero natural number and $\Phi_n : \{0,1\}^n \rightarrow \llbracket 0, 2^n - 1 \rrbracket$, $(x_j)_{j \in \llbracket 1,n \rrbracket} \mapsto \sum_{j=1}^{n} x_j 2^{n-j}$.
Using the results of Q8--Q10, deduce that $\Phi_n$ is bijective.

Let $n$ be a non-zero natural number. We set $$\Phi_n : \left|\, \begin{aligned} \{0,1\}^n &\rightarrow \llbracket 0, 2^n - 1 \rrbracket \\ (x_j)_{j \in \llbracket 1,n \rrbracket} &\mapsto \sum_{j=1}^{n} x_j 2^{n-j} \end{aligned} \right.$$
Deduce that $\Phi_n$ is bijective.

We denote $D_n = \left\{ \sum_{j=1}^{n} \frac{x_j}{2^j},\, (x_j)_{j \in \llbracket 1,n \rrbracket} \in \{0,1\}^n \right\}$.
Let $n \in \mathbb{N}^{\star}$. Show that the application $$\Psi_n : \begin{gathered} \{0,1\}^n \rightarrow D_n \\ (x_j)_{j \in \llbracket 1,n \rrbracket} \mapsto \sum_{j=1}^{n} \frac{x_j}{2^j} \end{gathered}$$ is bijective.

Show that if the union of a finite number of vector subspaces $F_1, \ldots, F_r$ of $E$ is a vector subspace, then one of the vector subspaces $F_i$ contains all the others.

Show that if the union of a finite number of vector subspaces $F_1, \ldots, F_r$ of $E$ is a vector subspace, then one of the vector subspaces $F_i$ contains all the others.

We are given $x _ { 0 } \in \mathbb { R } ^ { N }$. We consider the finite real sequences $\left( \alpha _ { k } \right)$ and $\left( \beta _ { k } \right)$, as well as the finite sequences $\left( \tilde { x } _ { k } \right) , \left( \tilde { r } _ { k } \right)$ and $\left( \tilde { p } _ { k } \right)$ of elements of $\mathbb { R } ^ { N }$, constructed according to the following recurrence relations, for $k \in \{ 0 , \ldots , m - 1 \}$, $$\begin{aligned} \alpha _ { k } & = \frac { \left\| \tilde { r } _ { k } \right\| ^ { 2 } } { \left\langle A \tilde { p } _ { k } , \tilde { p } _ { k } \right\rangle } \\ \tilde { x } _ { k + 1 } & = \tilde { x } _ { k } + \alpha _ { k } \tilde { p } _ { k } \\ \tilde { r } _ { k + 1 } & = \tilde { r } _ { k } - \alpha _ { k } A \tilde { p } _ { k } \\ \beta _ { k } & = \frac { \left\| \tilde { r } _ { k + 1 } \right\| ^ { 2 } } { \left\| \tilde { r } _ { k } \right\| ^ { 2 } } \\ \tilde { p } _ { k + 1 } & = \tilde { r } _ { k + 1 } + \beta _ { k } \tilde { p } _ { k } \end{aligned}$$ with $\tilde { x } _ { 0 } = x _ { 0 } , \tilde { r } _ { 0 } = b - A x _ { 0 }$ and $\tilde { p } _ { 0 } = \tilde { r } _ { 0 }$.
Show that the following properties are satisfied:
(i) For all $k \in \{ 0 , \ldots , m - 1 \}$, for all $i \in \{ 0 , \ldots , k - 1 \}$, we have $$\left\langle \tilde { r } _ { i } , \tilde { r } _ { k } \right\rangle = 0 , \left\langle \tilde { p } _ { i } , \tilde { r } _ { k } \right\rangle = 0 , \left\langle \tilde { p } _ { i } , A \tilde { p } _ { k } \right\rangle = 0$$
(ii) For all $k \in \{ 0 , \ldots , m \} , \tilde { x } _ { k }$ is identified with $x _ { k }$, the minimizer of $J$ on $x _ { 0 } + H _ { k }$ defined in question 13.
(iii) For all $k \in \{ 0 , \ldots , m \} , \tilde { r } _ { k }$ is identified with $r _ { k } = b - A x _ { k }$.
(iv) The family $\left( \tilde { p } _ { 0 } , \ldots , \tilde { p } _ { k } \right)$ is a basis of $H _ { k + 1 }$, for all $k \in \{ 0 , \ldots , m - 1 \}$.

Suppose that there exists $f : \mathbb{N} \rightarrow \mathcal{P}(\mathbb{N})$ bijective. By considering $A = \{x \in \mathbb{N} \mid x \notin f(x)\}$, establish a contradiction.

Show that the application $\Phi : \begin{aligned} \mathcal{P}(\mathbb{N}) &\rightarrow \{0,1\}^{\mathbb{N}} \\ A &\mapsto \mathbb{1}_A \end{aligned}$ is bijective.

Show that the application $\Phi : \begin{aligned} \mathcal{P}(\mathbb{N}) &\rightarrow \{0,1\}^{\mathbb{N}} \\ A &\mapsto \mathbb{1}_A \end{aligned}$ is bijective.

Show that the application $$\Psi : \begin{aligned} \{0,1\}^{\mathbb{N}} &\rightarrow [0,1] \\ (x_n) &\mapsto \sum_{n=0}^{+\infty} \frac{x_n}{2^{n+1}} \end{aligned}$$ is well-defined and surjective. Is it injective?

Show that the application $$\Psi : \begin{aligned} \{0,1\}^{\mathbb{N}} &\rightarrow [0,1] \\ (x_n) &\mapsto \sum_{n=0}^{+\infty} \frac{x_n}{2^{n+1}} \end{aligned}$$ is well-defined and surjective. Is it injective?

We denote $D^{\star} = D \backslash \{0\}$. We set for all $(x_n) \in \{0,1\}^{\mathbb{N}}$ $$\Lambda\left((x_n)\right) = \begin{cases} \Psi\left((x_n)\right) & \text{if } \Psi\left((x_n)\right) \in [0,1[ \backslash D^{\star} \\ \frac{\Psi\left((x_n)\right)}{2} & \text{if } \Psi\left((x_n)\right) \in D \cup \{1\} \text{ and } (x_n) \text{ is eventually constant at } 1 \\ \frac{1 + \Psi\left((x_n)\right)}{2} & \text{if } \Psi\left((x_n)\right) \in D^{\star} \text{ and } (x_n) \text{ is eventually constant at } 0 \end{cases}$$
Show that $\Lambda$ realizes a bijection from $\{0,1\}^{\mathbb{N}}$ to $[0,1[$.

Using the recurrence relation $2\beta_{n+1} = \sum_{k=0}^{n} \binom{n}{k} \beta_k \beta_{n-k}$ and the analogous relation $2\alpha_{n+1} = \sum_{k=0}^{n} \binom{n}{k} \alpha_k \alpha_{n-k}$ with $\alpha_0 = \beta_0 = 1$, deduce that $\beta_n = \alpha_n$ for every $n \in \mathbb{N}$.

We denote $D^{\star} = D \setminus \{0\}$ where $D = \bigcup_{n \in \mathbb{N}^{\star}} D_n$ and $D_n = \left\{ \sum_{j=1}^{n} \frac{x_j}{2^j},\, (x_j)_{j \in \llbracket 1,n \rrbracket} \in \{0,1\}^n \right\}$. We set for all $(x_n) \in \{0,1\}^{\mathbb{N}}$ $$\Lambda\left((x_n)\right) = \begin{cases} \Psi\left((x_n)\right) & \text{if } \Psi\left((x_n)\right) \in [0,1[ \setminus D^{\star} \\ \frac{\Psi\left((x_n)\right)}{2} & \text{if } \Psi\left((x_n)\right) \in D \cup \{1\} \text{ and } (x_n) \text{ is eventually constant at } 1 \\ \frac{1 + \Psi\left((x_n)\right)}{2} & \text{if } \Psi\left((x_n)\right) \in D^{\star} \text{ and } (x_n) \text{ is eventually constant at } 0 \end{cases}$$ where $\Psi : \{0,1\}^{\mathbb{N}} \rightarrow [0,1]$, $(x_n) \mapsto \sum_{n=0}^{+\infty} \frac{x_n}{2^{n+1}}$.
Show that $\Lambda$ realizes a bijection from $\{0,1\}^{\mathbb{N}}$ to $[0,1[$.

Using the results of Q33--Q36, conclude that $[0,1[$ is not countable.

6. Show that for all $n \in \mathbb{N}$, for every function $f$ of $S_n$ satisfying $\lim_{x \rightarrow \pm\infty} |f(x)| = \pm\infty$, there exists an element $g \in \mathscr{P}_{n+1}$ such that $f \sim g$ (where $\sim$ is the relation defined in I.2).

Let $n \in \mathbb{N}^*$. For $k \in \mathbb{N}$, we denote $\mathcal{B}(n, k)$ the set of maps $\sigma \in \operatorname{MD}(n+1)$ such that $\sigma(2) - \sigma(1) = k+1$. For $k \in \mathbb{N}$ and $s \in \mathbb{N}$, we denote $\mathcal{C}(n, s, k)$ the set of elements $\sigma$ of $\operatorname{MD}(n+2)$ such that $\sigma(2) - \sigma(1) = s+1, \quad n+2-\sigma(2) = k$.
1. For $m \geq 2$ verify that the map $\operatorname{Opp} : \Sigma_m \rightarrow \Sigma_m$, which to $\sigma \in \Sigma_m$ associates $\eta \in \Sigma_m$ defined by $$\eta(i) = m + 1 - \sigma(i)$$ is a bijection satisfying $\operatorname{Opp}(\operatorname{MD}(m)) = \operatorname{DM}(m)$ and $\operatorname{Opp}(\operatorname{DM}(m)) = \operatorname{MD}(m)$. Verify that if $\sigma \in \Sigma_m$ and if $i, j$ are elements of $\{1, \ldots, m\}$ satisfying $\sigma(j) > \sigma(i)$, $$\sigma(j) - \sigma(i) = 1 + \operatorname{Card}\{k \in \Delta_m \mid \sigma(i) < \sigma(k) < \sigma(j)\}$$

Let $n \in \mathbb{N}^*$. For $k \in \mathbb{N}$, we denote $\mathcal{B}(n, k)$ the set of maps $\sigma \in \operatorname{MD}(n+1)$ such that $\sigma(2) - \sigma(1) = k+1$. For $k \in \mathbb{N}$ and $s \in \mathbb{N}$, we denote $\mathcal{C}(n, s, k)$ the set of elements $\sigma$ of $\operatorname{MD}(n+2)$ such that $\sigma(2) - \sigma(1) = s+1, \quad n+2-\sigma(2) = k$.
2. Under what condition (necessary and sufficient) on $n$ and $k$ is the set $\mathcal{B}(n, k)$ non-empty? Under what condition (necessary and sufficient) on $n$, $s$ and $k$ is the set $\mathcal{C}(n, s, k)$ non-empty?