# Prove that if x and y belong to the set defined by following definition, then x*y also belongs to the set

We have the following recursive definition of a set

1. The number 1 belongs to set S
2. if x belongs to set S, then so does x+x
3. Only those elements defined by above rules belong to set S

Now, suppose x and y are two elements of set S. Prove that x*y also belongs to set S.

I realize that the set defined by three rules is the set of powers of 2 i.e. {1, 2, 4, 8, 16, 32,.....} and for any two powers of 2, we can use algebra to prove that their product is also a power of 2. But in this case, I need to prove that x*y belongs to set S only by using the recursive definition of set S.

• Can you please elaborate how x = i can be derived from the given definition. From what I see, only positive integers are possible in the set Commented Sep 11, 2022 at 8:46
• $S=\{a,bi\}$ where $a,b$ are powers of $2$? Or we start with $1,i$ are contained in $S$ in point 1. This is not excluded, since also then $1\in S$. Or should it be read "we only know that $1\in S$" in 1.? Commented Sep 11, 2022 at 8:48
• One idea I have is that since we know $x+x \in S$, then maybe it's possible that $x + x + \ldots + x = x\cdot y \in S$, where $x$ is being added $y$ times. If $x,y \in \mathbb{N}$, you could try a strong induction proof. They're just my thoughts though. Commented Sep 11, 2022 at 19:02

Since only the elements defined in this way are in the set, if $$x\in S$$ and $$x\neq 1$$, then $$x/2\in S$$. Suppose that $$x\in S$$ is the smallest element such that there exists $$y\in S$$ with $$xy\not \in S$$. We can't have $$x$$ or $$y$$ equal to $$1$$, so $$x/2 \in S$$. Then $$(x/2)*(2y)=xy\not \in S$$, contradicting minimality of $$x$$.
Fix $$x \in S$$ and use induction on the recursive definition of the assertion that $$y \in S$$. In the base case, $$y = 1$$ and $$x \times y = x \in S$$, by assumption. In the inductive step $$y = y' + y'$$ where $$y' \in S$$ and the inductive hypothesis gives us that $$x \times y' \in S$$, but then $$x\times y = (x \times y') + (x \times y')$$ is also in $$S$$.