Prove X is a partition of ℕ* and that $X = ℕ$* I am having trouble to prove this exercise for a Real Analysis course. I tried two approaches. However, I am insecure about both of them.
This is the question:
If $X$ is a partition of ℕ* such that:
i) $1 ∈ X$;
ii) For all $n ∈ ℕ$*, if $n ∈ X$, then $2n ∈ X$;
iii) For all $n ∈ ℕ$*, if $n+1 ∈ X$, then $n ∈ X$;
Show that $ X = ℕ$*

First attempt:
I tried using the definition of set partition and a family of subsets. This is my try: 
Let X be a part of $ℕ$* 
Hence, we have a family of subsets with:
${ X_i : i ∈ I}$
$ X_1 = {1} $
$ X_2 = {2n} $ For all $n ∈ ℕ$* 
$ X_3 = {n+1} $ For all $n ∈ ℕ$* and  $n ∉  X_2 $ 
All properties of a partition hold:
$ X_1, X_2 ,X_3 ≠ ø $ 
$ X_1 ∪ X_2 ∪ X_3 = X$ 
$ X_1 ∩ X_2 ∩ X_3 = ø $
$ X_1 ∩ X_2 = ø $
$ X_1 ∩ X_3 = ø $
$X_2 ∩ X_3 = ø $
Finally, $ ⋃ X_i$ = X = $ℕ$*

The second approach is more intuitive and I don't know how to express it mathematically!
The second rule on the question states that:
ii) For all $n ∈ ℕ$*, if $n ∈ X$, then $2n ∈ X$;
So, every number expressed as $2^k$ belongs to X.
And, by the third rule: 
iii) For all $n ∈ ℕ$*, if $n+1 ∈ X$, then $n ∈ X$;
I can get from $2^k$ to any number between $2^k$ and 1, by decreasing $2^k$

Thanks!
 A: Your second approach is correct.
You want to prove that $X = \mathbb{N}$
For being $X$ a subset of $\mathbb{N}$ , then $X \subset\mathbb{N}$
Now we have to proof that $\mathbb{N}\subset X$
So let be $n \in\mathbb{N}$, then it exist some $k \in\mathbb{N}$ with $n=2^{k+1}-p$, where p$\leq k$
For i): $1 \in X \Rightarrow 2 \in X$$\;$ for ii)
For ii) again: $2 \in X \Rightarrow 2^{k+1} \in X \Rightarrow 2^{k+1}-p \in X$ $\;$(because of iii)
So $\mathbb{N}\subset X$
And then $X = \mathbb{N}$
A: First, I assume that when you say $X$  is a partition of $\mathbb N^*$, you mean that $X$ is a subset of $\mathbb N^*$.
"Obviously" $X \subseteq \mathbb N^*$. If would be good that you provide simple arguments on the why.
Let's prove conversely that $\mathbb N^* \subseteq X$ by induction:


*

*$1 \in X$ by hypothesis.

*Suppose that for $n \ge 1$, we have $\{1, \dots, n \} \subseteq \mathbb N^*$ and let's prove that $\{1, \dots, n+1 \} \subseteq \mathbb N^*$.


If $n = 2p$ is even then by induction hypothesis, $p \in X$. And as $p + 1 \le 2p$, you also have $p+1 \in X$ and by hypothesis ii) $2(p+1) = 2p+2 \in X$. Therefore by hypothesis iii) $n+1 = 2p+1 = 2(p+2) - 1 \in X$.
And if $n = 2p+1$ is odd, $p +1$ also belongs to $X$ by induction hypothesis as $1 \le p+1 \le 2p+1$. Therefore $n+1 = 2(p+1)$ is in $X$ by hypothesis ii).
A: I like your second approach. We can formalise your second approach in easy stages like this:
Lemma if $n \in X$, then so is every $m \in \Bbb{N}^*$ with $m < n$.
Proof induction on $n - m$ using rule (iii).
Lemma if $m \in \Bbb{N}^*$, then there is $n \in X$ with $m < n$.
Proof by rules (i) and (ii) and induction, $2^k \in X$ for every $k \in \Bbb{N}$. As the $2^k$ are unbounded there is $k$ such that $m <  2^k$ and we may take $n = 2^k$.
Theorem $X = \Bbb{N}^*$
Proof from the second lemma, if $m \in \Bbb{N}^*$, there is an element $n$ of $X$ with $m < n$ and then from the first lemma $m \in X$.
[Aside: to prove that the $2^k$ are unbounded, you prove by induction on $m$ that for every $m \in \Bbb{N}^*$, there is a $k$ with $m < 2^k$, with $m=1$ and $k =1$ in the base case. Your approach requires three inductions rather than one, but is much closer to the intuition behind the rules.]
