Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Trichotomy proof

  1. Jan 25, 2012 #1
    1. The problem statement, all variables and given/known data
    I was trying to prove trichotomy for natural numbers.

    2. Relevant equations
    [itex]n > m \Leftrightarrow \exists k \neq 0 (n = m + k)[/itex]
    [itex]n < m \Leftrightarrow \exists k \neq 0 (m = n + k)[/itex]

    Trichotomy means in a set
    [itex] \forall n \forall m ( n = m \vee n> m \vee n<m) [/itex]

    3. The attempt at a solution
    I need an hint, a push in the right direction.

    thank you :)
  2. jcsd
  3. Jan 25, 2012 #2


    User Avatar
    Science Advisor

    Using what basis? There are many different ways of defining the natural numbers and different ways of defining "<". Typically, "Trichotomy" is taken as part of the definitionof "<" for the natural numbers. How are you defining "<"?

    A standard method is "<" is a binary relation on the natural numbers satisfying
    1) If m< n and p is any natural number then m+p< n+p.
    2) If m< n and 0< p, then mp< np.
    3) If m and n are natural numbers then one and only one must be true:
    a) m= n.
    b) m< n.
    c) n< m.

    An equivalent definition is
    "There exist a subset of the natural numbers, P, satifying
    1) If m and n are both in P then mn is in P.
    2) If m and n are both in P then m+ n is in P.
    3) if m is a natural number then one and only one must be true:
    a) m= 0.
    b) m is in P.
    c) -m is in P.

    It is (3), of course, that is equivalent to "trichotomy". If you have that definition of "order", you define "<" by "a< b if and only if b- a is in P.
    Last edited by a moderator: Jan 25, 2012
  4. Jan 25, 2012 #3
    I define < and > like i've written in the Relevant Equations section.
    I define the natural numbers in a non rigorous way, just as an intuitive concept.
    Addition is a binary relation with those property.

    [itex]a+b \in N[/itex]
    [itex]a+b = b+a[/itex]
    [itex](a+b)+c = a+(b+c)[/itex]
    There is one only element, and it's 0, for which [itex]a+0 = a[/itex]

    I'm trying to prove some facts starting from those definitions. Trichotomy would be nice to prove, since i can use it to prove other things.
    Last edited: Jan 25, 2012
  5. Jan 25, 2012 #4
    I just realized that my definition of trichotomy is wrong, or incorrect. Usually [itex]\vee[/itex] is the inclusive or, but in this case should be the exclusive or since all 3 propositions can't be true, and not even two of them can.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook