1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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