Find 1-1 and onto mapping from {0,1}* to the integers 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?
 A: 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)$.
A: Hint: There is a finite number of words of given length, enumerate them.
Start with $0$ and then $\pm 1,\pm2,\ldots$
A: 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.
A: 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.
A: "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.
