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

<br /> S_0 = \{\}<br />
<br /> S_i = \{0\} \bigcup \{s + \pi | s \in S_{i-1}\}<br />
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 &gt; 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