Dimostralo $S_{\mathbb{N^*}}$ non è numerabile.

Question

Permettere $S_{\mathbb{N^*}}$ essere l'insieme di tutte le permutazioni di $\mathbb{N^*}$. Dimostralo$S_{\mathbb{N^*}}$ non è numerabile.

Permettere $f : \mathbb{N^*} \mapsto S_{\mathbb{N^*}}$essere una biiezione. Ho presentato$$ \sigma(k) = \begin{cases} \min \{ l \mid l\neq f(k)(k) \text{ et } l \neq \sigma(i) \, \forall i \in [1,k-1] \} ,&\text{if }k>1\\ \min \{ l \mid l\neq f(k)(k) \} &\text{if }k=1\\ \end{cases} $$ È chiaro che $\sigma$è iniettiva, ma non so come dimostrare che sia suriettiva. Hai qualche suggerimento?

Answer 1

Sfortunatamente, il tuo $\sigma$ non è necessario essere suriettivi senza alcune condizioni $f$. Supporre che$f(k)(k)=1$ per ciascuno $k\in\Bbb N^*$; questo è certamente possibile. Poi$1$ non può essere nell'intervallo di $\sigma$.

Il tuo $\sigma$ sarà surjective se$f$ ha la proprietà che $\{k\in\Bbb N^*:f(k)(k)\ne m\}$ è infinito per ciascuno $m\in\Bbb N^*$. In caso contrario, lascia$m=\min(\Bbb N^*\setminus\operatorname{ran}\sigma)$. Se$\sigma(k)=n>m$, allora neanche $f(k)(k)=m$, o $\sigma(i)=m$ per alcuni $i<k$. Quest'ultimo è impossibile, quindi$f(k)(k)=m$ per tutti ma finitamente molti $k\in\Bbb N^*$, è impossibile se $\{k\in\Bbb N^*:f(k)(k)\ne m\}$ è infinito.