Proving that the desired set exists Let $n_2$ be the binary form of $n\in\mathbb N$.  Define the function $F$ on $\mathbb N\times \mathbb N \to \{0,1\}$ by $F(n,i)=1$ if $i$ is less than the length of $n_2$ and the $(i+1)$th digit (counting from the right) of $n_2$ is $1$. Otherwise, $F(n,i)=0$.
Now let's make each natural number a set as follows. Nothing lies in $0$. Only $1$ lies in $1$. For all other $m\ne 0,1$, $n$ lies in $m$ iff $F(m,n)=1$. The problem is to show that for all $k$ and all $n_1,\dots, n_k$ there is a unique $N$ such that $N=\{n_1,\dots, n_k\}$. (There might be a slight confusion with the notation: at the beginning $n_2$ denotes the binary form of $n$, but here the indices don't denote binary or other forms.)
I guess this needs to be proved by induction on $k$? The base case presumably has to be $k=1$ (because the statement doesn't seem to be true for $k=0$), and it's clear. Now suppose we have a set $N_k=\{n_1,\dots, n_k\}$ and suppose we consider a $k+1$st number $n_{k+1}$. I don't really see how to consruct  a number $\{n_1,\dots, n_k, n_{k+1}\}$ out of $\{n_1,\dots, n_k\}$ and $N_k$... Any ideas?
 A: I don't like using the same symbol for a number and for its associated set, especially since the elements of that set are themselves numbers.  So I'm going to put a bar over the number to indicate the set.  (But I'll come back to this in an appendix.)  Then the goal is to prove that for all $ k $ and all $ n _ 1 , \ldots , n _ k $, there is an $ N $ (the actual number) such that $ \overline N $ (the associated set) is $ \{ n _ 1 , \ldots , n _ k \} $.
You wrote the definition so that $ 0 $ and $ 1 $ are special cases, but if I use the same definition for them as for the other numbers, then I still get $ \overline 0 = \{ \} $ but I get $ \overline 1 = \{ 0 \} $ instead of $ \overline 1 = \{ 1 \} $ as you wrote.  So I think that this is a mistake, whether made by you or by whoever posed the question to you.  And besides, I can't solve the problem without making this change, since there is no other $ N $ that I can use to get $ \overline N = \{ 0 \} $, whereas there is another $ N $ (namely, $ 2 $) that gives $ \overline N = \{ 1 \} $.  (Also, there's an application of this idea for which it's important that $ x < N $ whenever $ x \in \overline N $, so we wouldn't want $ 1 \in \overline 1 $.)
With this understanding, here are the first few sets: $$ \eqalign { \overline 0 & = \{ \} \text , \\ \overline 1 & = \{ 0 \} \text , \\ \overline 2 & = \{ 1 \} \text , \\ \overline 3 & = \{ 0 , 1 \} \text , \\ \overline 4 & = \{ 2 \} \text , \\ \overline 5 & = \{ 0 , 2 \} \text , \\ \overline 6 & = \{ 1 , 2 \} \text , \\ \overline 7 & = \{ 0 , 1 , 2 \} \text , \\ & \; \vdots } $$
For example, $ 6 $ in base $ 2 $ is $ 1 1 0 $, so (counting from the right) the $ 1 $st digit is $ 0 $, the $ 2 $nd digit is $ 1 $, the $ 3 $rd digit is $ 1 $, and there are no other digits (although you could take them to also be $ 0 $ if you wanted to).  So the $ ( i + 1 ) $th digit is $ 1 $ precisely when $ i $ is $ 1 $ or $ 2 $.  Thus, $ \overline 6 = \{ 1 , 2 \} $.  (Or if this is wrong, then I haven't understand your description of the problem correctly.)
You could also start counting the digits with $ 0 $ instead of $ 1 $ to avoid having to do $ i + 1 $, but I guess that starting on the right is already one unusual aspect of the counting, so they didn't want to add another.  Still, it's worth noticing that the first digit (from the right) tells you whether or not $ 0 $ belongs to the set, the next digit tells you whether or not $ 1 $ belongs to the set, etc.
Anyway, to reverse this, that is to find the number $ N $ starting with a set $ \overline N = \{ x _ 1 , \ldots , x _ k \} $, you need to find a number whose $ ( i + 1 ) $th binary digit is $ 1 $ precisely when $ i $ belongs to the set.  And that digit contributes $ 2 ^ i $ to the value of the number.  Therefore, assuming that the $ k $ numbers $ x _ 1 , \ldots , x _ k $ are all distinct (no repetition), $$ N = \sum _ { j = 1 } ^ k 2 ^ { x _ k } \text . $$  That is, add up $ 2 ^ x $ for each element $ x $.  For example, starting with $ \{ 1 , 2 \} $, we get $ N = 2 ^ 1 + 2 ^ 2 = 6 $.
So for every (natural) number, we get a set of numbers; and for every (finite) set of numbers, we get a number.  Depending on how much detail you want in your proof, you could prove this by induction on $ k $; that's natural since summation is defined by induction.  But I think that the summation formula will probably satisfy whoever's asking you.  Or if this is something that you thought of on your own, then hopefully this satisfies you!

Appendix:
I said before that I don't like using the same symbol for the number $ N $ and the set $ \overline N $.  And if you write $ 6 = \{ 1 , 2 \} $ outside of the context of this question, then people will probably not like that.  (They may say that it's nonsense, because a number is not a set; or they may say that it's wrong, because really $ 6 = \{ 0 , 1 , 2 , 3 , 4 , 5 \} $; but they almost certainly will not say that it's correct.)  However, if we instead write $ \overline 6 = \{ \overline 1 , \overline 2 \} $, then nobody can object, because we're defining what $ \overline N $ means.  (The fact that $ x < N $ whenever $ \overline x \in \overline N $, allows you to prove that this is a consistent way to define a family of sets; $ \overline 1 \in \overline 1 $ is not allowed in a well-founded set theory such as ZFC.)
So instead of saying that a number is a set whose members are also numbers, we're defining a family of sets (one for each number), each of whose members are also sets in this family.  Then these are actually a famous family of sets called the hereditarily finite sets.  (Finite since they're all finite, hereditarily finite because also their members are finite, their members' members are finite, etc.  Formally, a set is hereditarily finite if and only if it's finite and all of its members are hereditarily finite; and while this looks circular, it's valid as a definition by induction on the set-membership relation in a well-founded pure set theory such as ZFC.)
If you're founding all of mathematics on pure set theory, then you want to have a way to define numbers as sets.  The most common way, named after von Neumann, is to use $ N = \{ x \; | \; x < N \} $; that's what people would be thinking of if they say that $ 6 = \{ 0 , 1 , 2 , 3 , 4 , 5 \} $.  An earlier method, named after Zermelo, is to use $ N = \{ N - 1 \} $ (with $ 0 = \varnothing $ as an exception to get started); then $ 6 = \{ 5 \} $.  But now we can see that the way you wrote things before, where the numbers are the sets, is yet another way to define numbers as sets, although a little more complicated to explain.  And while von Neumann's and Zermelo's methods turn every natural number into a hereditarily finite set, your method turns the natural numbers into all of the hereditarily finite sets, so it's nice.  (Von Neumann's method is nice in another way, in that it generalizes smoothly to certain infinite numbers, the transfinite ordinal numbers.  Zermelo's is nice in that it's minimal; it consists of the smallest and simplest sets that can do the job.  So they all have their charms.)
So now I'm back to saying that OK, $ 6 = \{ 1 , 2 \} $; but only if you're founding all of mathematics (or at least arithmetic) on pure set theory in this new way.
