# Proper subset question

1. Jul 2, 2011

### Samuelb88

1. The problem statement, all variables and given/known data
Let X be the two element set $\{ 0 , 1 \}$. Find a bijective correspondence between $X^{\omega}$ and a proper subset of itself.

2. Relevant equations
Notation. $X^{\omega}$ is the set of all (infinite) ${\omega}-\mathrm{tuples}$ $(x_1 , x_2 , x_3 , ...)$, where $x_i \in X$.

3. The attempt at a solution

My question is about the proper subset part...

I want to say in order to find any such bijection, I'll need to find another infinite proper subset of $X^{\omega}$. My question is, does $X^{\omega - r}$, where $r \in \mathbb{N}$, constitute such a proper subset?

2. Jul 2, 2011

### vela

Staff Emeritus
What would you suggest $X^{\omega-r}$ means? How would it differ from $X^\omega$?

It might help to think about the binary representation of numbers.

3. Jul 2, 2011

### micromass

Staff Emeritus
$$(0,x_2,x_3,x_4,...)$$
That makes sense! I let $\alpha = \{ A \in \{0,1\}^{\omega} : A = (0, x_1, x_2 , ...) \}$ and define $f: \{0,1\}^{\omega} \rightarrow \alpha$ such that $f(x_1, x_2, ...) = (0, x_1, x_2, ...)$, that is, the function that shifts each coordinate position of any $\omega$-tuple in $\{0,1\}^{\omega}$ "up by one" to compensate for the zero in the first coordinate position after I put it through my function. Thanks!