Recursively defined set subset proof

Question

Consider the subset $S$ of the set of integers recursively defined by

BASIS STEP: $3 \in S$.

RECURSIVE STEP: If $x \in S$ and $y \in S$, then $x+y \in S$.

Q: Show that the set $S$ is the set of all positive integers that are multiples of $3$.

This is an example from Rosen's Discrete Mathematics and Its Applications. It first proves that $A$, the set of all positive integers divisible by $3$, is a subset of $S$. I understand this part.

Then $S \subseteq A$ proof is given as the following:

To prove that $S$ is a subset of $A$, we use the recursive definition of $S$. First, the basis step of the definition specifies that $3$ is in $S$. Because $ 3 = 3\times 1$, all elements specified to be in $S$ in this step are divisible by $3$ and are therefore in $A$. To finish the proof, we must show that all integers in $S$ generated using the second part of the recursive definition are in $A$. This consists of showing that $x+y$ is in $A$ whenever $x$ and $y$ are elements of $S$ also assumed to be in A. Now if $x$ and $y$ are both in $A$, it follows that $3\mid x$ and $3 \mid y$. It follows that $3 \mid x+y$, completing the proof.

If we are assuming $x,y$ to be in $A$, how does this show $S \subseteq A$?

Answer 1

This is a proof by induction, showing that if $z\in S$ i.e. created from the recursive scheme, then $z\in A$. The induction is done over how many recursive steps were applied in order to create an element in $S$. Bellow is how the proof looks like if we do it carefully written out in multiple explicit steps. The point is that we are assuming $x$ and $y$ to be in $A$ by using induction.

Base step: 0 recursive steps, thus the element $3$ which sure is divisible by 3 i.e. $3=3\cdot 1$.

Induction assumption: If $x\in S$ is created by at most $n$ applications of the recursive steps, then $x\in A$.

Inductuion step: Assume that $z\in S$ is created in $n+1$ applications of the recursive step. Then $z=x+y$ for some elements $x,y\in S$ which were created in at most $n$ applications of the recursive step. Thus the Induction assumption implies that $x,y\in A$ i.e. $3\> | \>x$ and $3 \>|\>y$. But then $3\> | \>x+y$ (by algebra we know from before), and thus $x+y \in A$.

Answer 2

You have to show that :

$S \subseteq A$.

To do this, you have to follow the two-steps definition of $S$ :

(i) $3 \in $; but $3$ is divisible by $3$. Thus : $3 \in A$.

(ii) this is the iduction step. We assume the induction hypotheses, i.e. that if $x,y \in S$ such that $x+y \in S$, and $x,y \in A$, then also $x+y \in A$.

But if $x,y \in A$, then they are both divisble by $3$; thus also $x+y$ is, i.e. $x+y \in A$.