Mostra isso $S_{\mathbb{N^*}}$ não é contável.

Question

Deixei $S_{\mathbb{N^*}}$ seja o conjunto de todas as permutações de $\mathbb{N^*}$. Mostra isso$S_{\mathbb{N^*}}$ não é contável.

Deixei $f : \mathbb{N^*} \mapsto S_{\mathbb{N^*}}$ser uma bijeção. Eu apresentei$$ \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} $$ Está claro que $\sigma$é injetivo, mas não sei como mostrar que é sobrejetivo. Você tem alguma dica?

Answer 1

Infelizmente, seu $\sigma$ não precisa ser sobrejetora sem algumas condições $f$. Suponha que$f(k)(k)=1$ para cada $k\in\Bbb N^*$; isso certamente é possível. Então$1$ não pode estar na faixa de $\sigma$.

Seu $\sigma$ será sobrejetora se$f$ tem a propriedade que $\{k\in\Bbb N^*:f(k)(k)\ne m\}$ é infinito para cada um $m\in\Bbb N^*$. Se não, deixe$m=\min(\Bbb N^*\setminus\operatorname{ran}\sigma)$. E se$\sigma(k)=n>m$, qualquer então $f(k)(k)=m$, ou $\sigma(i)=m$ para alguns $i<k$. Este último é impossível, então$f(k)(k)=m$ para todos, exceto um número finito $k\in\Bbb N^*$, é impossível se $\{k\in\Bbb N^*:f(k)(k)\ne m\}$ é infinito.