# Bijection between two sets

• Jan 2nd 2013, 10:42 AM
MachinePL1993
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}$.

• Jan 2nd 2013, 10:51 AM
emakarov
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.
• Jan 2nd 2013, 11:01 AM
MachinePL1993
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...$ .
• Jan 2nd 2013, 11:13 AM
emakarov
Re: Bijection between two sets
I am not sure I understand.
Quote:

Originally Posted by MachinePL1993
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
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
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?
• Jan 2nd 2013, 11:14 AM
Plato
Re: Bijection between two sets
Quote:

Originally Posted by MachinePL1993
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).$.
• Jan 2nd 2013, 11:31 AM
emakarov
Re: Bijection between two sets
Quote:

Originally Posted by Plato
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
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.
• Jan 2nd 2013, 11:33 AM
MachinePL1993
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.
• Jan 2nd 2013, 11:42 AM
emakarov
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").
• Jan 2nd 2013, 11:49 AM
MachinePL1993
Re: Bijection between two sets
Yes, sorry. But putting those mistakes aside, is what I've written above a properly defined function?
• Jan 2nd 2013, 11:55 AM
emakarov
Re: Bijection between two sets
Quote:

Originally Posted by MachinePL1993
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.