Brushing Up on Set Theory Struggling with a simple proof: Let $X = \{3^n\mid n > 0\}$ and $Y = \{3n\mid n \geq 0\}$. Prove that $X$ is a subset of $Y$.
I tried Direct Approach and Contrapositive, but I'm not strong enough with my proof skills yet. Can someone show me some steps to doing this? I don't need a direct solution, just some steps to get me in the right direction so I have a good example.

You just need to know a few basic things.


*

*Firstly, to prove $X \subseteq Y$, you can instead consider fixed but arbitrary $x \in X$, and prove that $x \in Y$.

*Secondly, you need to know how to rewrite $\{f(x) \mid x \in X\}$ into a more useful form. Here's how you do it: assume $f : Y \leftarrow X$ is a function. Then:
$$\{f(x) \mid x \in X\} = \{y \in Y \mid \exists x \in X, y=f(x)\}.$$
The form on the right tends to be more useful than the one on the left.
Okay, so lets prove $X \subseteq Y$. We know that:


*

*$X = \{k \in \mathbb{N} \mid \exists a \in \mathbb{N} : k=3^a \;\&\; a>0 \}$

*$Y = \{k \in \mathbb{N} \mid \exists a \in \mathbb{N} : k=3a\}$
So consider $k \in X$, and fix some $a \in \mathbb{N}$ such that $k=3^a$ and $a>0.$ To show that $k \in Y$, we need to find $b \in \mathbb{N}$ such that $k=3b$. That is, we're trying to find $b \in \mathbb{N}$ such that $3^a=3b$. So toy with the equation $3^a = 3b$ until you've got $b$ in terms of $a$, and then prove rigorously that this choice of $b$ really does do the job.
