2

My idea was to essentially use ordering by the length of the string (and for strings with the same length, order them is ascending order) to map a string to a number, numbers that start with a $0$ go to a negative integer and things that start with $1$ to a positive integer.

The idea is that if, say, you need to figure out what $f(01)$ is, then this is what you do. $\epsilon = 0.$$ f(0) = -1.$ $f(1) = 1.$ Now take all the 2 length strings $\,00$, $01$, $10$, $11$.

$00$ gets mapped to $-2.$ $f(01) = -3.$ $f(10) = 2$ and $f(11) = 3.$ And so on.

HOW TO PROVE THIS IS $1-1$ AND ONTO?

larry
  • 1,486

5 Answers5

5

Start with $f\colon \{0,1\}^*\to\mathbb N$ by letting $f(\epsilon)=1$ and recursively $f(\alpha x)=2f(\alpha)+x$ if $\alpha\in\{0,1\}^*$ and $x\in\{0,1\}$. By induction we see that this is indeed a map to $\mathbb N$. The map is onto for if we assume the contrary, there is a minimal $n$ not in the image of $f$; clearly $n>1$; write $n=2k+r$ with $r\in\{0,1\}$ and $k\in\mathbb N$. Then $n>k$, hence $k=f(\alpha)$ for some $\alpha$, and then $n=f(\alpha r)$, contradiction. In a similar fashion one show sthat $f$ is injective. Once we have this $f$, we get a bijection $g\colon \{0,1\}^*\to\mathbb Z$ by letting $g(\epsilon)=0$, $g(0\alpha)=f(\alpha)$, $g(1\alpha)=-f(\alpha)$.

Hagen von Eitzen
  • 374,180
3

Hint: There is a finite number of words of given length, enumerate them.

Start with $0$ and then $\pm 1,\pm2,\ldots$

Belgi
  • 23,150
1

Yet another approach is to start by thinking of a string $\sigma\in\{0,1\}^*$ as the binary representation of a non-negative integer. Of course $10,010$, and $0010$ (among others) all represent the same integer, so we have to figure out some way to map them to different integers. One way is to count the leading zeroes and combine that somehow with the binary value. An explicit bijection from ordered pairs of natural numbers to natural numbers would be useful here, and there is a well-known one that’s not too hard to describe, the so-called pairing function. Finally, we want to map $\{0,1\}^*$ onto $\Bbb Z$, not $\Bbb N$, so we need to generate an algebraic sign from each $\sigma$; we can use the first character to do that.

If $\epsilon\ne\sigma\in\{0,1\}^*$, let $\sigma_0$ be the first character of $\sigma$, and let $\widehat\sigma$ be the rest of $\sigma$ after $\sigma_0$ is deleted. This reduced string $\widehat\sigma$ can be interpreted as the binary representation of a unique integer $n(\sigma)$. Let $z(\sigma)$ be the number of leading zeroes in $\widehat\sigma$. For example,

$$n(0)=n(1)=z(0)=z(1)=0\;,$$

and

$$n(0010)=n(1010)=2\quad\text{ and }\quad z(0010)=z(1010)=1\;.$$

Let $\varphi:\Bbb N\times\Bbb N\to\Bbb N$ be the pairing function, and let

$$f:\{0,1\}^*\to\Bbb Z:\sigma\mapsto\begin{cases} 0,&\text{if }\sigma=\epsilon\\ \varphi(\langle z(\sigma),n(\sigma)\rangle)+1,&\text{if }\sigma\ne\epsilon\text{ and }\sigma_0=0\\ -\big(\varphi(\langle z(\sigma),n(\sigma)\rangle)+1\big),&\text{if }\sigma\ne\epsilon\text{ and }\sigma_0=1\;; \end{cases}$$

I’ll leave you to check, if you wish, that this $f$ works.

Added: In order to prove that your map is a bijection, you’ll have to define it more clearly. Here is one way to do that. For $n\in\Bbb N$ let $\Sigma_n=\{\sigma\in\{0,1\}^*:|\sigma|=n\}$, where $|\sigma|$ is the length of $\sigma$; $|\Sigma_n|=2^n$. For $n>0$ and $i\in\{0,1\}$ let $\Sigma_n^i$ be the set of strings in $\Sigma_n$ that begin with $i$; $|\Sigma_n^0|=|\Sigma_n^1|=2^{n-1}$. Following your basic idea, we’ll send $\epsilon$, the unique member of $\Sigma_0$, to $0$, and for each $n>0$ we’ll send the members of $\Sigma_n^0$ to the first available $2^{n-1}$ positive integers and the members of $\Sigma_n^1$ to their negative counterparts. That is, we’ll send the string $0\in\Sigma_1^0$ to the integer $1$, the string $1\in\Sigma_1^1$ to the integer $-1$, the strings in $\Sigma_2^0=\{00,01\}$ to the integers $2$ and $3$ and the strings in $\Sigma_2^1=\{10,11\}$ to the integers $-2$ and $-3$, the strings in $$\Sigma_3^0=\{000,001,010,011\}$$ to the integers $4,5,6$, and $7$ and the strings in $$\Sigma_3^1=\{100,101,110,111\}$$ to the integers $-4,-5,-6$, and $-7$, and so on. But in order to define $f$, we still have to specify how to assign a specific integer to each string in $\Sigma_n^i$.

Notice that we’re sending the strings in $\Sigma_n^0$ to the integers $2^{n-1},2^{n-1}+1,\ldots,2^n-1$ and the strings in $\Sigma_n^1$ to the negatives of these integers. Each string in $\Sigma_n^0$ can be interpreted as a binary number in the set $\{0,1,\dots,2^{n-1}-1\}$. If we let $b(\sigma)$ denote the binary interpretation of a string $\sigma\in\Sigma_n^0$, the map that I sketched in the previous paragraph can be described by saying that $f(\sigma)=2^{n-1}+b(\sigma)$. If $\sigma\in\Sigma_n^1$, we can interpret all of $\sigma$ after the leading $1$ as a binary number, and it will also be in the set $\{0,1,\ldots,2^{n-1}-1\}$; call this number $b(\sigma)$. The map sketched in the previous paragraph sends $\sigma\in\Sigma_n^1$ to $f(\sigma)=-\left(2^{n-1}+b(\sigma)\right)$.

In other words, you can make your idea precise by defining

$$f:\{0,1\}^*\to\Bbb Z:\sigma\mapsto\begin{cases} 0,&\text{if }\sigma=\epsilon\\ (-1)^i\left(2^{n-1}+b(\sigma)\right),&\text{if }\sigma\in\Sigma_n^i\text{ and }n>0\;. \end{cases}\tag{1}$$

Now your function $f$ is explicitly defined, and you can work on showing that it is both one-to-one and onto. To show that $f$ is onto, let $k$ be any integer, and explain how to construct a string $\sigma\in\{0,1\}^*$ such that $f(\sigma)=k$. If you do this carefully, you’ll actually show that there is exactly one such $\sigma$, which will show that $f$ is also one-to-one.

Brian M. Scott
  • 616,228
  • again, I don't see how this is relevant to my question. – larry Aug 26 '13 at 18:48
  • 1
    @user9915: As André pointed out in the comments, lexicographic order doesn’t work. The map that you attempted to define in your second paragraph isn’t entirely clear; a more explicit version of it could be made to work, but as it stands, it isn’t defined well enough for you to prove anything about it. I chose instead to offer an alternative: I constructed a bijection from ${0,1}^*$ to $\Bbb Z$ whose intuitive basis is comparatively straightforward. – Brian M. Scott Aug 26 '13 at 18:58
  • so i'm still left with original question, how do you show that it is one-to-one and onto. – larry Aug 27 '13 at 03:45
  • "Notice that we’re sending the strings in Σ0n to the integers 2n−1,2n−1+1,…,2n−1 and the strings in Σ1n to the negatives of these integers." What does this mean? – larry Aug 27 '13 at 03:46
  • @user9915: With my second suggestion I gave you a pretty explicit indication of how to get started, but here’s a bit more. Write out $f(\sigma)$ for all strings $\sigma$ of length at most $4$, say. Pay attention to how $f$ works. From that much data, together with the description of $f$, you really ought to be able to figure out how to undo $f$: how to start with an integer $n$ and find the unique $\sigma\in{0,1}^$ such that $f(\sigma)=n$. You will* have to expend some time and thought: it probably won’t just fall into your lap. But something to which you should be accustomes: it’s normal. – Brian M. Scott Aug 27 '13 at 06:38
1

We modify your proposal, keeping the general spirit, perhaps, except for the use of the lexicographic order. As in your proposal, the empty word goes to $0$, words that begin with a $0$ go to positives, and words that begin with a $1$ go to negatives.

We deal with the positives. For any word $w=a_1a_2\cdots a_k$ that begins with $0$, as a preliminary step map the word to the number $$f(w)=(a_1+1)10^0+(a_2+1)10^1+(a_3+1)10^2+\cdots +(a_k+1)10^{k-1}.$$ By basic properties of decimal expansion, different words are mapped to different numbers.

If $w$ is a word that begins with $0$, define the rank $\rho_0(w)$ of $w$ to be the number of words $x$ that begin with $0$ such that $f(x)\le f(w)$. So $\rho_0(w)=1$ if $w$ is the word that begins with $0$, and has smallest "$f$" value, and $\rho_0(w)=2$ if $w$ has the second smallest $f$ value, and so on.

Map the unique word that begins with $0$ and has rank $i$ to $i$. By the construction, the set of words that begin with $0$ is mapped in a one-to-one way onto way to the set of positive integers.

Do something analogous with words that begin with $1$, defining a rank function $\rho_1$ on these, and mapping the word $w$ that begins with $1$ and and such that $\rho_1(w)=i$ to the integer $-i$.

In this way we obtain a concrete though unatractive one-to-one onto map from $\{0,1\}^\ast$ to the integers.

André Nicolas
  • 507,029
  • what is the rank for? – larry Aug 27 '13 at 03:46
  • "By basic properties of decimal expansion, different words are mapped to different numbers." What? – larry Aug 27 '13 at 03:50
  • It is crucial in defining the mapping. Just a fancy way of saying it is the position of our word under $f$. Remember, we are dealing separately (but similarly) with words that start with $0$ and words that start with $1$. For now, we are discussing words that start with $0$. Then the word $w_1$ of rank $1$ is the word that has the smallest $f$-value. The word $w_2$ of rank $2$ is the word that has the second-smallest $f$-value. The word of rank $3$ is the word which has third smallest $f$-value, and so on. It is kind of like your notion of ordering the words lexicographically. (Cont) – André Nicolas Aug 27 '13 at 03:53
  • You intended the first word to be mapped to $1$, the second to $2$, and so on. So you also had a notion of rank, which was position in the dictionary ordering. That doesn't quite work, because dictionary order is funny, it lists $0,00,000$, and so on first, so there are infinitely many words before we reach $01$. What I did was to use the same idea, but avoiding that peculiarity of dictionary ordering. There are other ways to do it, this one happened to be quick. – André Nicolas Aug 27 '13 at 03:56
  • Thanks. But it seems you merely stated that it was 1-1 and onto. Is there a proof? – larry Aug 27 '13 at 04:00
  • We just need to understand how $f$ works. Take the word $00110$. Replace $0$ by $1$ and $1$ by $2$. We get $11221$. This gets mapped to the integer with ordinary decimal expansion $f(w)=12211$ (unfortunately, the way I set it up, we reverse at the end). This $12211$ is an ordinary number. Different strings, different numbers. – André Nicolas Aug 27 '13 at 04:03
  • The proof is simply that every string that starts with $0$ has a unique rank, by the definition of rank. – André Nicolas Aug 27 '13 at 04:04
0

"Proofs" depend on how much one may assume. This is a special case of the general fact that the set of finite sequences with entries from a given nonempty finite (even countable) set is countably infinite. One proof is indicated in Enderton's A Mathematical Introduction to Logic (1972), theorem 0B.

Ganong
  • 1