Page 1 of 2 12 LastLast
Results 1 to 15 of 16

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

  1. #1
    Member
    Joined
    Apr 2011
    From
    Somwhere in cyberspace.
    Posts
    93
    Thanks
    4

    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...

    Can Q be ordered in such way that it will be isomorphic to (N,&lt;)-image.png

    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?
    Attached Thumbnails Attached Thumbnails Can Q be ordered in such way that it will be isomorphic to (N,&lt;)-image.png  
    Last edited by mrproper; July 28th 2011 at 05:26 AM. Reason: broken diagram
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176

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

    Quote Originally Posted by mrproper View Post
    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...

    Click image for larger version. 

Name:	image.png 
Views:	7 
Size:	4.0 KB 
ID:	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 " \mathbb{Z}\times \mathbb{Z}". You have, in your picture, that 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 \mathbb{Q} is well-ordered anyway. Which should be true...(but a proof escapes me at the moment).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    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 <).
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

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

    Quote Originally Posted by Swlabr View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

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

    Quote Originally Posted by mrproper View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Apr 2011
    From
    Somwhere in cyberspace.
    Posts
    93
    Thanks
    4

    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
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Apr 2011
    From
    Somwhere in cyberspace.
    Posts
    93
    Thanks
    4

    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".
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    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.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    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.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Apr 2011
    From
    Somwhere in cyberspace.
    Posts
    93
    Thanks
    4

    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.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    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.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Member
    Joined
    Apr 2011
    From
    Somwhere in cyberspace.
    Posts
    93
    Thanks
    4

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

    Like picking the pair with least coordinates?
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

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

    Right.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Member
    Joined
    Apr 2011
    From
    Somwhere in cyberspace.
    Posts
    93
    Thanks
    4

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

    Thanks very much!
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    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, ...
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Well ordered-set
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: March 13th 2010, 03:15 PM
  2. A well-ordered set
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: March 9th 2010, 02:22 PM
  3. Well ordered set
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 3rd 2009, 03:36 AM
  4. Set ordered
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: November 23rd 2008, 01:43 PM
  5. What is an ordered pair?
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: February 10th 2008, 12:15 AM

Search Tags


/mathhelpforum @mathhelpforum