From: hiraga@Csli.Stanford.EDU (Yuzuru Hiraga)
Subject: Re: Z <-> Q formula (summary so far)
Summary: summary of the solutions received so far
Keywords: bijection
Organization: Stanford University CSLI
Date: Sat, 3 Oct 1992 10:29:57 GMT


Thanks to all the people who have responded to my problem:
	Find a "simple" formula that expresses a bijection between Z and Q.

The following is a summary of the responses received so far.

The names of those who came up with correct solutions are as follows,
classified by the type of solution (explained below).
[I have omitted reference to those people who have made only comments,
gave solutions that are incorrect/incomplete or which I failed to comprehend.]

* Solution A
  pmontgom@math.orst.edu (Peter Montgomery)
	<Bv927B.Gv0@news.orst.edu>
  petry@pythagoras.math.washington.edu (David Petry)
	<1992Sep29.010120.1729@u.washington.edu>
  aaronm@cybernet.cse.fau.edu (aaron meyerowitz)
	<w0yXRB1w165w@cybernet.cse.fau.edu>

* Solution B1
  somos@ces.cwru.edu (Michael Somos)
	<1a652vINNbbr@usenet.INS.CWRU.Edu>
  chalcraft@uk.tele.nokia.fi (Adam Chalcraft)
	<CHALCRAFT.92Sep28124621@laurel.uk.tele.nokia.fi>
  jgk@osc.COM (Joe Keane)
	<5776@osc.COM>

* Solution B2
  preece@StPaul.c10sd4.NCR.COM (Bently.Preece)
	<preece.2@StPaul.c10sd4.NCR.COM>

=========================================================================

The "formula" mentioned in the problem will be freely interpreted
to include sets of defining equations, including recursive definitions.
Let the mapping be F, meaning either Z->Q or Q->Z, which should be
apparent in the context.
It seems reasonable to suppose F(-n) = -F(n) (thus F(0)=0), and
deal with only the positive numbers (all answers did this).
The solutions fall in two categories:
  A. Find a direct "natural" mapping between Z and Q.
	There was essentially a single case of this type.
  B. Provide a non-overlapping enumeration of Q.
	There were two distinct cases of this type (B1 and B2).

=========================================================================

The type A solution uses the following facts:
  * any positive interger can be uniquely and exhaustively expressed
    in the form:
	P1^e1 * P2^e2 * ... * Pi^ei * ...
    where Pi is the i-th prime (2,3,5,...); and ei (in Z) >= 0,
    where only a finite number of them are non-zero.
  * any positive rational can be uniquely and exhaustively expressed
    in the form:
	P1^f1 * P2^f2 * ... * Pi^fi * ...
    where Pi is the i-th prime; and fi in Z,
    where only a finite number of them are non-zero.
The first is the prime factorization theorem, while the latter,
though elementary, seems less often quoted.

Given the above, the problem reduces to finding a mapping ei <-> fi
for all i, which is straightforward (mapping odd numbers into positive
and even numbers into negative is one example).
Peter Montgomery, David Petry, and aaron meyerowitz came up with
essentially the same solution (and this was also what I had in mind).
The expression that David Petry gave seems the most concise and elegant:
  > Given the rational number A/B, let {p_i} be the set of prime factors of B.
  > Let F(A/B) =  A^2*B^2/product(p_i) .

One minor problem with this type A solution is that there is no simple way
to express "set of prime factors" or their exponents in ordinary notation.

=========================================================================

The type B, enumeration method had two distinct answers.

B1.
The first was given by Michael Somos, Adam Chalcraft, and Joe Keane,
which can be called the "mediant method" (following Michael Somos).
Explained in words, this uses the fact that:
  * for rationals a/b and c/d, its "mediant" (a+c)/(b+d) is an irreducible
    fraction that falls inbetween a/b and c/d, and
  * starting from 0/1 and 1/0 (used only as a "formal" starter),
    recursively taking the mediants will generate a tree that exhaustively
    enumerates all positive rationals.

This can be better understood by the following diagram (by Michael Somos):
  >0/1                                                             1/0
  > :                              1/1                              :
  > :              1/2              :              2/1              :
  > :      1/3      :      2/3      :      3/2      :      3/1      :
  > :  1/4  :  2/5  :  3/5  :  3/4  :  4/3  :  5/3  :  5/2  :  4/1  :
  > :1/5:2/7:3/8:3/7:4/7:5/8:5/7:4/5:5/4:7/5:8/5:7/4:7/3:8/3:7/2:5/1:
  > : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :

Michael Somos gave the mapping F: n -> p(n)/q(n) by the recursive formula:
  > p(1) = q(1) = 1, p(n) = f(n,0), q(n) = f(n,1)
  > f(n,t) = f(floor(n/2),t) + g(ceiling(n/2),t,mod(n,2))
  > g(1,t,e) = mod(t+e, 2),
  > g(n,t,e) = f(floor(n/2),t) if n odd, g(n/2,t,e) if n even

Adam Chalcraft did not give an explicit formula, though mentions
the use of Euclid's algorithm:
  > You can figure out where the rational p/q appears by using Euclid's
  > algorithm to show that p and q are coprime, and noticing when you do
  > "x:=x-y" and when you do "y:=y-x".
  > This gives you a finite sequence of x's and y's.
The Euclidean argument can be used to prove that B1 (as well as B2 below)
are indeed correct.

Joe Keane does not mention the mediants or the tree structure above,
but gives a formula that in effect follows the tree levels in a
straightforward manner (F: n -> q(n)):
  > Define q(0) = 0 and q(1) = 1.
  > If K = 2^k and K <= n < 2*K, then
  > q(K + n) = q(n) / (q(n) + 1), and
  > q(2*K + n) = q(n) + 1.
Some further comments by Joe:
  > The function is about as continuous as you could expect from such a thing.
  > The graph of q(n) versus log n is a fractaloid curve which keeps repeating
  > but gets more filled in as n gets larger.


B2.
The second, given by Bently Preece, follows a completely different line:
  > For the positive integers, let
  >		F(1)    = 1
  >		F(2k)   = F(k)+1	(k > 0)
  >		F(2k+1) = 1 / F(2k)	(k > 0)
This was sort of surprising to me that such a simple formulation will
do the job (yes, I know it works, though I'm yet to come up with an
intuitively simple description of what F(n) is).

It's also interesting whether the recursive forms of B1 and B2
can be solved into explicit forms (though this seems quite difficult).

=========================================================================

Some comments.
The motivation for the problem is that I feel the ordinary argument
given in classrooms to be awkward -- namely, do a zigzag or diagonal
traverse 1/1, 1/2, 2/1, 1/3, 2/2, 3/1, ... and remove the reducibles.
From an educational viewpoint, solution A seems a good substitute
for this (thus "simple" for students).
As for simplicity of form, I find B2 to be quite appealing, though
of course, as noted, this is highly "subjective".

Finding an actual example of bijective mapping is often quite difficult
and interesting, even if the proof of identical cardinality is simple.
Below are some exercise problems [meant for beginners only;
those of you who are well learned in set theory, please don't spoil
the problem for them!]

* Is there a bijection between R=(-infinity, infinity) and an open
  interval, eg. (0,1)?  Yes, y = tan(pi*(x-1/2)) will do.
  Then, how about a mapping between (0,1] and (0,1)?
  The proof that they have the same cardinality is straightforward.
* Along the .999...= 1 thread:
  In his letter to Dedekind, Cantor gave a mapping from RxR to R,
  which Dedekind immediately pointed its flaw.
  To make things simple, let's consider [0,1)x[0,1) -> [0,1).
  Cantor's method was to use the decimal expansions of the pair (x,y)
  and aline the digits alternately, eg. for x=0.12345... and y=0.98765...,
  map it into 0.1928374655...
  * Can you tell the flaw of this argument?
  * Can you fix it?

Once again, thanks to all that responded!!

-Yuzuru Hiraga (hiraga@csli.stanford.edu)
Newsgroups: sci.math,rec.puzzles,comp.theory