Results 1 to 2 of 2

Math Help - Prove ...is a well-order

  1. #1
    Junior Member
    Joined
    Jul 2008
    Posts
    38

    Prove ...is a well-order

    Given P={1,2,3,...} with usual < ordering
    Let f(n)= the number of distinct prime divisors of n
    (ie: f(1)=0, f(2)=1, f(3)=1, f(4)=1, f(5)=1, f(6)=2,...)

    Now, define \triangleleft on P where:
    a \triangleleft b iff f(a) < f(b) OR [f(a) = f(b) and a < b]

    So, I need to prove that P with \triangleleft is a well-ordering; prove transitive, irreflexive, comparable, and that every non-empty subset has a least element. The last part here is my problem, everything else is fine but I need help proving the least element part.

    I know that if you break up P into sets so that all numbers with 1 unique prime divisor goes into a subset, then all the numbers with 2 unique prime divisors go into a disjoint subset, and so on, where each subset is ordered as usual by <. Then, take the union of these subsets and it can be shown that it still holds the usual ordering of <, but we are now dealing with \triangleleft ordering so it is a well-ordering (since < is a well ordering). As a restatement of my issue, I need help writing this out and actually making it solid. I've been working on it for a while...

    Cheers and thank you!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    You can prove \triangleleft is a well ordering using that < is a well ordering.


    Let X be a non empty subset of P. Then f(X) is a non empty subset of P, which has a least element b for <.

    Consider X\cap f^{-1}(b)\subseteq P, which is also a non empty subset (why?) of P. Once again, it has a least element for <, let say a.

    Prove that a is the least element for \triangleleft in X.
    Last edited by clic-clac; October 14th 2009 at 12:16 PM. Reason: oops
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prove: order ab = ord a * ord b
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: November 20th 2010, 05:10 PM
  2. Prove that a group of order 375 has a subgroup of order 15
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: May 14th 2010, 12:08 AM
  3. Prove that a^k has and order m/d
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: May 2nd 2010, 09:59 PM
  4. Replies: 2
    Last Post: April 3rd 2010, 01:26 AM
  5. Prove that the order of Z(G) is either <e> or G
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 9th 2010, 10:35 PM

Search Tags


/mathhelpforum @mathhelpforum