Bijection between two sets

**MachinePL1993** · January 2nd 2013, 09:42 AM

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.

**emakarov** · January 2nd 2013, 09:51 AM

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.

**MachinePL1993** · January 2nd 2013, 10:01 AM

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...$ .

**emakarov** · January 2nd 2013, 10:13 AM

I am not sure I understand.

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.

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?

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?

**Plato** · January 2nd 2013, 10:14 AM

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).$ .

**emakarov** · January 2nd 2013, 10:31 AM

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.

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.

**MachinePL1993** · January 2nd 2013, 10:33 AM

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.

**emakarov** · January 2nd 2013, 10:42 AM

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").

**MachinePL1993** · January 2nd 2013, 10:49 AM

Yes, sorry. But putting those mistakes aside, is what I've written above a properly defined function?

**emakarov** · January 2nd 2013, 10:55 AM

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.

Thread: Bijection between two sets

LinkBack

Thread Tools

Display

Bijection between two sets

Re: Bijection between two sets

Re: Bijection between two sets

Re: Bijection between two sets

Re: Bijection between two sets

Re: Bijection between two sets

Re: Bijection between two sets

Re: Bijection between two sets

Re: Bijection between two sets

Re: Bijection between two sets

Similar Math Help Forum Discussions

[SOLVED] bijection between two sets of functions

Bijection between Sets(again)

Bijection between Sets

Bijection

Bijection in infinite sets

Search Tags