2 Attachment(s)

Can Q be ordered in such way that it will be isomorphic to (N,<)

The question is in the title. No matter how strange and useless it will be, can the set of all rational numbers be ordered in a way that it will be isomorphic to the set of all natural numbers. I think, I have an intuitive answer:

The set of all integers may be ordered in at least one such way:

0 0

1 +1

2 -1

3 2

4 -2

5 3

... ...

Which is simply the function f(n) = -n/2 if n is even and f(n) = n+1/2 if n is odd.

Then we may try this ordering on ordered pairs. Something like this...

Attachment 21907

I sure can write a computer program that calculates the sequential number of each pair in the previous diagram so I'll get a one to one correspondence between N and Z x Z-{0} so I'll have the desired ordering. But is there a way to make this more precise? Like define the function someway more exactly. After all there is no theorem that states that if there is a program there is a function, corresponding to the program? Right?

Re: Can Q be ordered in such way that it will be isomorphic to (N,<)

Quote:

Originally Posted by

**mrproper** The question is in the title. No matter how strange and useless it will be, can the set of all rational numbers be ordered in a way that it will be isomorphic to the set of all natural numbers. I think, I have an intuitive answer:

The set of all integers may be ordered in at least one such way:

0 0

1 +1

2 -1

3 2

4 -2

5 3

... ...

Which is simply the function f(n) = -n/2 if n is even and f(n) = n+1/2 if n is odd.

Then we may try this ordering on ordered pairs. Something like this...

Attachment 21907
I sure can write a computer program that calculates the sequential number of each pair in the previous diagram so I'll get a one to one correspondence between N and Z x Z-{0} so I'll have the desired ordering. But is there a way to make this more precise? Like define the function someway more exactly. After all there is no theorem that states that if there is a program there is a function, corresponding to the program? Right?

Unfortunately, the rational numbers are more complicated than just "$\displaystyle \mathbb{Z}\times \mathbb{Z}$". You have, in your picture, that $\displaystyle 0=\frac{0}{1}\leq \ldots\leq \frac{0}{-2}=0$, so everything in between *must* be equal, which will contradict your order isomorphism.

However, if we assume the axiom of choice then we can apply the well-ordering principle and so one can well-order the rationals. This ordering will yield your order-isomorphism. What you are trying to show is that $\displaystyle \mathbb{Q}$ is well-ordered anyway. Which should be true...(but a proof escapes me at the moment).

Re: Can Q be ordered in such way that it will be isomorphic to (N,<)

There exists a well ordering T of Q such that (Q T) is isomorphic with (N <).

Re: Can Q be ordered in such way that it will be isomorphic to (N,<)

Quote:

Originally Posted by

**Swlabr** if we assume the axiom of choice then we can apply the well-ordering principle and so one can well-order the rationals.

We don't need the axiom of choice to prove there exists a well ordering of Q.

Re: Can Q be ordered in such way that it will be isomorphic to (N,<)

Quote:

Originally Posted by

**mrproper** there is no theorem that states that if there is a program there is a function, corresponding to the program? Right?

Given any one of a certain class of definitions of 'program' we do have the theorem that every (numerical) program computes a corresponding recursive function.

Re: Can Q be ordered in such way that it will be isomorphic to (N,<)

So my idea fails because every rational number may be represented as quotient of different pairs of integers, i.e. (1,2), (2,4), (4,8), (-2,-4) etc. So the mapping is not one-to-one, at least when defined as z1/z2=q

Re: Can Q be ordered in such way that it will be isomorphic to (N,<)

And this is very dumb of me, but I just realized that the recursion theorem in the textbook I'm reading might be just an attempt to specify a "class" of such "programs".

Re: Can Q be ordered in such way that it will be isomorphic to (N,<)

Even though each rational is represented by infinitely many ordered pairs of integers, it's still not hard to come up with a relation T on Q such that (Q T) is isomorphic with (N <).

First, construct some function h on Q that, for each member p of Q, we have that h(p) is a a particluar ordered pair of integers. Then use h and lexicographic ordering to define the relation T.

Re: Can Q be ordered in such way that it will be isomorphic to (N,<)

Under Church's thesis, it is simply the class of programs. To see the reasonableness of that thesis, we prove for lots of different kinds of (numerical) programs (Turing machine, register machine, do-while routine, actual computer program, etc.) that they each compute a recursive function.

The converse holds by proof. Given any recursive function, there is, for example, a Turing machine that computes that function.

Re: Can Q be ordered in such way that it will be isomorphic to (N,<)

Now it looks so obvious. Anyway for any given rational, I have a set of infinitely many ordered pairs of integers of which I choose one to represent this rational. Then just order the pairs lexicographically and get ordering of Q that will be isomorphic to N.

Re: Can Q be ordered in such way that it will be isomorphic to (N,<)

But to avoid having to use the axiom of choice, you need to define the way you pick from among the infinite number of ordered pairs. But that's easy to do.

Re: Can Q be ordered in such way that it will be isomorphic to (N,<)

Like picking the pair with least coordinates?

Re: Can Q be ordered in such way that it will be isomorphic to (N,<)

Re: Can Q be ordered in such way that it will be isomorphic to (N,<)

Re: Can Q be ordered in such way that it will be isomorphic to (N,<)

And use "least" in some sense that works, such as along the lines of the ordering you mentioned:

0, -1, 1, -2, 2, ...