1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proving Total Order

  1. Nov 23, 2008 #1
    1. The problem statement, all variables and given/known data
    Let n be a positive integer and let D(n) be the set of all positive integers d such that d divides n. For example, D(10)={1,2,5,10}. It's easily shown that the divides relation (xRy if x divides y) is a partial ordering on D(n), but for what n is the D(n) totally ordered?


    2. Relevant equations



    3. The attempt at a solution
    I've already verified that for all n, D(n) is a partial ordering. I've also made the observation that, for all n=2^s + 3^t where s,t are natural numbers D(n) is totally ordered. However, I'm having a difficult time proving this. For nonzero s and t, n is prime and D(n) is clearly totally ordered. For the cases where s=0 or t=0, it's more difficult to prove. Any suggestions? Is this the right way to go about this?
     
  2. jcsd
  3. Nov 23, 2008 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Really?

    You've already written a counterexample in this thread. :smile:
     
  4. Nov 23, 2008 #3
    That's my mistake....typo. I meant to say that all prime numbers can be written as a 2^s + 3^t. Also, I've found a counterexample to that criterion, namely 125. So it's back to the drawing board.

    What I know:

    1.) For all n such that n is prime, D(n) is totally ordered.
    2.) Not much else. I've written D(n) up to n=32, and found that the following non-prime n also give totally ordered sets:

    4, 8, 9, 16, 25, 27, 32

    but have no idea how to find some unifying criteria now.

    Arrgh! I understand that once I find a criteria, I must show that for all a,b in D(n) a/b or b/a, but I need to find that criteria first.
     
  5. Nov 23, 2008 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Well, this is all about divisibility, right? We know a lot about divisibility -- the fundamental theorem of arithmetic being the most important structural fact.
     
  6. Nov 23, 2008 #5
    Yah, I was thinking about that. I know that all natural numbers greater than one have a unique prime factorization. So, I suppose that if D(n) contains 2 primes, they will not divide one another. Can I go from there?
     
  7. Nov 23, 2008 #6
    I got it.

    Any n with unique prime factorization containing only one prime factor (not counting its multiplicities) will be totally ordered.

    Nice.
     
  8. Nov 24, 2008 #7

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Yep, that sounds right! And all of your examples are, in fact, prime powers!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Proving Total Order
  1. Prove order of tensor (Replies: 3)

Loading...