Un subconjunto infinito de una contables conjunto es contable

Question

En mi libro, demuestra que un subconjunto infinito de un coutnable conjunto es contable. Pero no todos los detalles están llenos, y he tratado de llenar en todos los detalles a continuación. Podría alguien decirme si lo que he escrito a continuación es válido?

Deje $S$ ser un subconjunto infinito de una contables set $T$. Desde $T$ es contable, existe un bijection $f: \mathbb{N} \rightarrow T$. Y $S \subseteq T = \{ f(n) \ | \ n \in \mathbb{N} \}$. Deje $n_{1}$ ser el menor entero positivo tal que $f(n_{1}) \in S$. Y continuar donde $n_{k}$ es el menor entero positivo mayor que $n_{k-1}$ tal que $f(n_{k}) \in S$. Y debido a que $S$ es infinito, podemos continuar para siempre. Ahora considere la función $\beta : \mathbb{N} \rightarrow S$ que envía a $k \rightarrow f(n_{k})$.

Así, en orden de $S$ a ser contables, $\beta$ tendría que ser un bijection. $\beta$ es inyectiva ya que si $f(n_{k}) = f(n_{j})$, $n_{k} = n_{j}$ porque $f$ es inyectiva. También podemos concluir $k = j$ debido a los diversos $n_{i}$ elegidos fueron estrictamente creciente.

Edit: $\beta$ también necesita ser surjective. Así, por cada $r \in S$ existe un $q \in \mathbb{N}$ tal que $\beta(q) = f(n_{q}) = r$. Sabemos que $f^{-1}(r) \in \{n_{1}, n_{2}, ..., n_{k} ... \}$, por lo que podemos dejar a $f^{-1}(r) = n_{d}$. Por lo tanto $\beta(d) = f(n_{d}) = r$.

Answer 1

El conjunto $A$ es contable si no es $f:A\to\mathbb N$ que es inyectiva.

Supongamos $B\subseteq A$ $f|_B:B\to\mathbb N$ también es inyectiva, simplemente porque usted restringir una función inyectiva usted no puede contraejemplo la inyectividad.

---

Supongamos que $f:A\to\mathbb N$ es un bijection y $B\subseteq A$ es infinito. Deje $N=\{f(b)\mid b\in B\}$, la imagen de $B$.

Desde $B$ es infinito, tenemos que $N$ es infinito. Vamos a mostrar que un subconjunto infinito de $\mathbb N$ contables:

Definimos inductiva de una función $g:\mathbb N\to N$, $g(0)=\min N$ el número mínimo en $N$. Supongamos $g(n)$ fue definido, vamos a $g(n+1)$ ser el número mínimo en $N$ que es mayor que $g(n)$.

Es obvio que $g$ es un bijection entre el$\mathbb N$$N$. Ahora tenemos que $g^{-1}\circ f|_B:B\to\mathbb N$ es un bijection, como quería.

Answer 2

Para arreglar la última declaración:

Supongamos que $q=f^{-1}(r)$. A continuación, $\{ 0,1,2,\dots,q\}$ es un conjunto finito. Cruzan este con $f^{-1}(S) = \{ n \in \mathbb{N} \;|\; f(n) \in S\}$, y obtener un conjunto finito. Por su definición de la $n_k$'s de este conjunto es $\{n_0,n_1,\dots,n_\ell\}$ algunos $\ell$. Por lo tanto $q=n_\ell$. Por lo tanto, $\beta(\ell)=f(n_\ell)=f(q)=r$. Parcheado.