Let F : ZxZ -> Z be defined by f ( (a,b) ) = a + 2 b
*********
*CLAIM* There exists a subset X of the integers having the property that
********* the restriction of F to X^2 is bijective onto Z
**********************
Lemma: Let X be a finite subset of Z such that F restricted to X^2 is injective.
Let n an element in Z not in the image of F restricted to X^2.
Then there exists a subset Y of Z, containing X, such that
F restricted to Y^2 is injective, and the image of F restricted to Y^2
contains n.
Proof:
If X is the empty set, let Y be the set { 0, n }.
In the case n is not 0, the image of F restricted to Y^2 is then { 0, n, 2n, 3 n },
all distinct, showing that F so restricted is injective. In the case that n is 0,
the image of F restricted to Y^2 is { 0 } and F so restricted is injective.
If X is not empty, let N = max { | k | : k is in X union {n} } + 1.
Let u > 10 N, v < - 10 N, with u + 2 v = n.
Let Y = X union {u,v} .
The image of F restricted to Y^2 contians n, so
it remains only to show that F restricted to Y^2 is injective.
Y^2 = X ^2 union X x { u } union X x {v} union {u} x X union {v} x X union
{u,v}^2.
F is injective on each of the pair-wise disjoint parts of Y^2 unioned,
so it will suffice to show that the images of F on each of these
are pair-wise disjoint.
if s is in the image of F on X^2, |s - 0| < 3 N.
if s is in the image of F on X x { u }, |s - 2u| < N.
if s is in the image of F on X x { v}, |s - 2v| < N.
if s is in the image of F on {u} x X, |s - u| < 2 N.
if s is in the image of F on {v} x X, |s - v| < 2 N.
if s is in the image of F on {u,v}^2,
s is in { 3 u, 3 v, u + 2 v, v + 2 u }.
The fact that numbers 0, 2u, 2v, u, v, 3u, 3v, are all spaced at least 10 N apart
shows that the images of F on X^2, Xx{u}, Xx{v}, {u}xX, {v}xX, and the set
{3 u, 3 v}, are all pair-wise disjoint.
Let A be the union of these, i.e. A = image F on X^2 union image F on Xx{u} ... union {3 u, 3 v}
It remains to show that { u + 2 v, v + 2 u } is disjoint from A.
We had u + 2 v = n by construction. |n - 0| < N gives |u + 2 v - 0 | < N,
and by assumption n was not im the image of F on X^2, so
u + 2 v is not in A.
Let s = v + 2 u.
Then s - (-3v) = 2 u + 4 v = 2 n, so that | s - (- 3v)| = | 2 n | < 2 N
| u + 2 v | < N gives |3/2 u - ( -3v )| < 3/2 N
Combining, |s - 3/2 u| < 3/2 N + 2 N < 4 N
But 3/2 u is at least 5 N distant from 0, u, v, 2 u, 2 v, 3 u, and 3 v,
so that s cannot be in A, and cannot be u + 2 v = n.
This completes proof of the Lemma.
************************
To prove the claim, let Kn be an enumeration of the integers.
There exists a sequence of sets Bn having the properties
1) Bn+1 contains Bn
2) F is injective on Bn^2
3) The image of F on Bn^2 contains Kj for all j <= n
For let B1 be the set { 0, K1 }.
Given Bn, if Bn already contains Kn+1 let Bn+1 = Bn.
Ohterwise, by the Lemma there exists Bn+1 containing Bn such that
F is injective on Bn+1^2 and the image of F on Bn+1^2 contains Kn+1.
Now let X be the union of all of the Bn.
Any two elements of X^2 are both contained in Bn^2 for some n, thus
F is injective on X^2. Given any integer, there is some Kn equal to it,
which is then in the image of F on Bn^2, and so in the image of F on X^2,
making F surjective onto the integers.
This completes the proof of the claim.