Simple Proof by Induction Problem

[CuppoJava]

Hi,

I devised this problem for myself as part of a bigger question that I'm working on, and am having trouble solving it. I think it involves a nested induction proof but I am not sure how to start. A tip on how to begin would be much appreciated.

Thanks
-Patrick

Homework Statement

$S_0 = \{\}$
$S_i = \{0\} \bigcup \{s + \pi | s \in S_{i-1}\}$
Show that $S_i \subseteq S_{i+1}$ for all $i$.

The Attempt at a Solution

I started by converting the problem to the following form:

$\forall i > 0, 0 \in S_i$
$\forall s \in S_i, s + \pi \in S_{i + 1}$
Show that $\forall s \in S_i, s \in S_{i + 1}$

But I don't know what to do next.

 

[haruspex]

Suppose true up to some i = n. Let x be in S_n. You want to show it is in S_n+1. Trivial if x = 0, otherwise x = y+π for some y in S_n-1. By the inductive hypothesis, since y is in S_n-1 it is also in ...?

 

[CuppoJava]

... therefore $y$ is in $S_n$ according to the assumed hypothesis.
Therefore $y + 1 = x$ is in $S_{n+1}$.
Therefore $S_i \subseteq S_{i+1}$ by induction.

Thank you!
-Patrick