Results 1 to 10 of 10
Like Tree5Thanks
  • 1 Post By emakarov
  • 1 Post By Plato
  • 1 Post By emakarov
  • 1 Post By emakarov
  • 1 Post By emakarov

Math Help - Bijection between two sets

  1. #1
    Junior Member
    Joined
    Nov 2012
    From
    Poland
    Posts
    40

    Bijection between two sets

    Hello,

    I'd be extremely grateful if anyone could give me a hint on how to create an injective function f: \mathbb{N}^\mathbb{N} \to \{0,1\}^\mathbb{N} .

    Thanks in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Bijection between two sets

    Encode a sequence of natural numbers into a sequence of 0's and 1's. Any data can be encoded into a sequence of 0's and 1's.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2012
    From
    Poland
    Posts
    40

    Re: Bijection between two sets

    Is the following function defined properly?

    \mathbb{N}^\mathbb{N} \to \{0,1\}^\mathbb{N}.

    We take a sequence of natural numbers, first we change the numbers into their binary representations, then we put 0 before each number, except the last one, where we put a 1. For example, f(5)=f((101)_{2})=01011. We do this so that for every sequence of natural numbers the sequence of 0's and 1's is different, because the 1 on odd position signifies the end of sequence for some natural number. We do this because without using only binary representations f(<15,...)=1111... would begin the same as f(<3,3...)=1111... .
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Bijection between two sets

    I am not sure I understand.
    Quote Originally Posted by MachinePL1993 View Post
    We take a sequence of natural numbers
    A finite or infinite sequence? In the end, you need to encode an infinite sequence.

    Quote Originally Posted by MachinePL1993 View Post
    first we change the numbers into their binary representations, then we put 0 before each number, except the last one, where we put a 1.
    Again, why do you want to mark the end of a finite sequence when you have to encode an infinite sequence? Also, does 0110011 encode two numbers 11 and 01 or one number 11001?

    Quote Originally Posted by MachinePL1993 View Post
    We do this so that for every sequence of natural numbers the sequence of 0's and 1's is different, because the 1 on odd position signifies the end of sequence for some natural number.
    By "position," do you mean the position of the digit? How can you control it when binary numbers may have even or odd number of digits?
    Thanks from MachinePL1993
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,957
    Thanks
    1780
    Awards
    1

    Re: Bijection between two sets

    Quote Originally Posted by MachinePL1993 View Post
    give me a hint on how to create an injective function f: \mathbb{N}^\mathbb{N} \to \{0,1\}^\mathbb{N} .
    You are asking a rather complicated question in that it requires several lemmas.

    Note the set \{0,1\}^\mathbb{N} is usually denoted by 2^\mathbb{N}

    Here is a standard theorem: For any infinite set A it is the case that P(A) \sim A^A  \sim 2^A . That theorem takes some work to prove.

    You need the Schroder-Bernstein theorem, use the characteristic function and the fact that A^A\subseteq\mathcal{P}(A\times A)..
    Last edited by Plato; January 2nd 2013 at 01:55 PM.
    Thanks from MachinePL1993
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Bijection between two sets

    Quote Originally Posted by Plato View Post
    Here is a standard theorem: For any set A it is the case that P(A) \sim A^A  \sim 2^A .
    For any infinite set.

    Quote Originally Posted by Plato View Post
    You need the Schroder-Bernstein theorem, use the characteristic function and the fact that A^A\subseteq\mathcal{P}(A\times A)..
    This seems like a nice method: A^A\subseteq\mathcal{P}(A\times A) because a function is a relation, then A\times A\sim A and \mathcal{P}(A)\sim2^A.

    However, encoding natural numbers in binary is also easy. One way is to repeat every bit of a number twice and insert 01 between the numbers. For example, 2 5 4 in binary is 10 101 100, so the encoding is 11000111001101110000.
    Last edited by emakarov; January 2nd 2013 at 11:33 AM.
    Thanks from MachinePL1993
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Nov 2012
    From
    Poland
    Posts
    40

    Re: Bijection between two sets

    Yes I'm encoding an infinite sequence.

    I don't think it matters if the binary representation of a number has even or odd number of digits. I probably wasn't clear on this, but we put the 0's before EVERY digit of a binary representation, not just the first one, and 1 before the last one. If we add a single digit before every digit we will get a string of 0's and 1's that's two times longer than it was before. I flubbed writing my example above, it should be f((101)_{2})=010011. Other example f(8)=f((100)_{2})=010010. In the end the only 1 on an odd position is the one before the last digit in the original representation. I do this, because otherwise the sequences (3,...) (1,1,....), would begin the same way if I were only putting in the sequence the binary representation of numbers. This way for every possible infinite sequence of natural numbers a unique sequence of 0's and 1's would be provided.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Bijection between two sets

    Yes, this makes sense except that 8 is 1000 in binary. I misunderstood post #3 because of the confusion between "number" and "digit" (or "bit").
    Thanks from MachinePL1993
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Nov 2012
    From
    Poland
    Posts
    40

    Re: Bijection between two sets

    Yes, sorry. But putting those mistakes aside, is what I've written above a properly defined function?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Bijection between two sets

    Quote Originally Posted by MachinePL1993 View Post
    But putting those mistakes aside, is what I've written above a properly defined function?
    Yes. You need to say, of course, that encodings of individual numbers are concatenated.
    Thanks from MachinePL1993
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] bijection between two sets of functions
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 2nd 2012, 02:18 AM
  2. Bijection between Sets(again)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: October 20th 2009, 02:27 PM
  3. Bijection between Sets
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 19th 2009, 04:18 PM
  4. Bijection
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: September 11th 2009, 05:28 AM
  5. Bijection in infinite sets
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: May 25th 2008, 03:57 PM

Search Tags


/mathhelpforum @mathhelpforum