Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Proper subset question

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

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

    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 [itex]X^{\omega}[/itex]. My question is, does [itex]X^{\omega - r}[/itex], where [itex]r \in \mathbb{N}[/itex], constitute such a proper subset?
  2. jcsd
  3. Jul 2, 2011 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Education Advisor

    What would you suggest [itex]X^{\omega-r}[/itex] means? How would it differ from [itex]X^\omega[/itex]?

    It might help to think about the binary representation of numbers.
  4. Jul 2, 2011 #3
    To help you, consider the set of all tuples


    so the set of all tuples with 0 as first element. Try to use that set somewhere...
  5. Jul 2, 2011 #4
    That makes sense! I let [itex]\alpha = \{ A \in \{0,1\}^{\omega} : A = (0, x_1, x_2 , ...) \} [/itex] and define [itex]f: \{0,1\}^{\omega} \rightarrow \alpha[/itex] such that [itex]f(x_1, x_2, ...) = (0, x_1, x_2, ...)[/itex], that is, the function that shifts each coordinate position of any [itex]\omega[/itex]-tuple in [itex]\{0,1\}^{\omega}[/itex] "up by one" to compensate for the zero in the first coordinate position after I put it through my function. Thanks!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook