Supongamos que $S \subseteq \mathbb N$ tal que:
- $\forall k \in \mathbb N :2^k \in S$
- $\forall k \ge 1: k \in S \implies k-1 \in S$
Demuestra que $S =\mathbb N$ .
Queda por demostrar que $\mathbb N \subseteq S$ .
Sea $P(n)$ sea la proposición tal que $\left\{ 2^k-n, ...,2^k\right\} \subseteq S$ .
El caso base es cierto ya que $P(0)$ significa $\left\{ 2^k\right\} \subseteq S$ lo cual es cierto según la hipótesis.
Supongamos que $P(n)$ sostiene y considera $P(n+1)$ a partir del supuesto $\left\{ 2^k-n, ...,2^k\right\} \subseteq S$ lo que implica $2^k-n \in S$ A partir de la segunda propiedad de $S$ está claro que $2^k-(n+1)= 2^k-n-1 \in S$ y así $\left\{ 2^k-(n+1), ...,2^k\right\} \subseteq S$ . Dado que esto es cierto para todos los $n$ así que $S =\mathbb N$ .
Editar :
Otra forma que probé: Que $P(n)$ sea la proposición tal que $\left\{ 0, ...,2^n\right\} \subseteq S$ .
El caso base es cierto ya que $2^0 \in S$ lo que es cierto por la primera propiedad de $S$ y por la otra propiedad, vemos que $0 \in S$ .
Supongamos que $P(n)$ sostiene y considera $P(n+1)$ a partir del supuesto $\left\{ 0, ...,2^n\right\} \subseteq S$ El conjunto $\left\{0,...,2^{n+1}\right\}$ puede escribirse como $\left\{0,...,2^{n}\right\} \cup \left\{2^{n}+1,...,2^{n+1}\right\}$ de nuevo a partir de la primera propiedad de $S$ , $2^{n+1} \in S$ la segunda propiedad implica $2^{n+1}-1 \in S$ continuando de esta manera vemos que $\left\{2^{n}+1,...,2^{n+1}\right\} \subseteq S$ y así $$\left\{0,...,2^{n+1}\right\}=\left\{0,...,2^{n}\right\} \cup \left\{2^{n}+1,...,2^{n+1}\right\}\subseteq S$$
Sería muy de agradecer que alguien comprobara la validez de las pruebas.
