2
$\begingroup$

Let's say I'm trying to find a bijection from $\mathbb N^\mathbb N$, i.e., the set of all functions from $\mathbb N$ to $\mathbb N$, to some other set, say an open interval $(a,b)∈R$. What do I need to establish, to say there can exist a bijection? I do understand that I need to prove it's both injective and surjective, but how do you do it with a set of functions as the domain?

Let's say I'm trying to see if the injective part is true. So, I need to find a function that takes every possible sequence of natural numbers as input, and associates each of them with one real number in the interval $(a,b)$. But what does it mean to have a sequence of natural numbers as the input of a function? And even if that makes sense, what sort of functions can satisfy such a purpose? I hope I sound sane.

$\endgroup$
5
$\begingroup$

A function from $\mathbb N$ to $\mathbb N$ would be of the form

$$f(1)=n_1, f(2)=n_2, f(3)=n_3, f(4)=n_4, f(5)=n_5, \ldots$$ for particular values of $n_1,n_2,n_3,n_4,n_5,\ldots$, so producing a sequence of natural numbers. You can then regard the function and the sequence as equivalent.

A function from these to the real numbers is much as you might expect, so for example the continued fraction:

$$g(n_1,n_2,n_3,n_4,n_5,\ldots)= n_1 + \cfrac{1}{n_2 + \cfrac{1}{n_3 + \cfrac{1}{n_4 + \cfrac{1}{n_5+\cdots} } } }.$$

To show this is injective (which it is in this case) you need to show that each different sequence produces a different real number

To show this is surjective (which it is not quite in this case - try finding a rational) you need to show that each real number is produced by some sequence

$\endgroup$
  • $\begingroup$ Thank you. I have a related question on this: I understand that if $A$ and $B$ are two sets, and if there exists a bijection from $A$ to $B$, then $|A|=|B|$. But is the converse true? I mean, can I say that if $|A|=|B|$, then there exists a bijection from $A$ to $B$? $\endgroup$ – Train Heartnet Nov 12 '13 at 8:54
  • $\begingroup$ @JobinIdiculla: that is almost the definition of $|A|$. At most, there is a third set $C$ with the same cardinality, so with a bijection from $A$ to $C$ and a bijection from $B$ to $C$, and since they are bijections you can combine them into a single bijection. $\endgroup$ – Henry Nov 12 '13 at 10:24
  • $\begingroup$ Oh, I understand now. Just a related question: Since I'm interested in mapping from $\mathbb N^\mathbb N$ to an interval $(a,b)$ in $\mathbb R$, in the example that you provided, I would have to prove that each sequence produces a different real number contained in that interval. Now, I know that for each sequence of natural numbers, a continued fraction gives a unique irrational number. But how do I tweak the continued fraction, to restrict its output values to a certain interval? $\endgroup$ – Train Heartnet Nov 13 '13 at 7:15
  • $\begingroup$ @JobinIdiculla: If you have numbers $x \in (0,\infty)$ then $\dfrac{ax+b}{x+1} \in (a,b)$. That does not deal with the issue of rational values. $\endgroup$ – Henry Nov 13 '13 at 8:30
6
$\begingroup$

Typically it's not so easy to explicitly write down a bijection. Instead you can use the Cantor-Bernstein-Schroeder theorem.

You can map an interval injectively into $\{0,1\}^{\mathbb N}$ using a base-$2$ representation.

You can map ${\mathbb N}^{\mathbb N}$ injectively into an interval using continued fractions.

$\endgroup$
  • $\begingroup$ Thank you. I have a related question, which I've posted as a comment under Henry's answer. Could you help me with that as well, please? $\endgroup$ – Train Heartnet Nov 12 '13 at 8:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.