Results 1 to 4 of 4

Math Help - Linear Orders

  1. #1
    Junior Member
    Joined
    Mar 2009
    Posts
    44

    Linear Orders

    Im doing some self study and I would like to ask question about linear orders.

    Listing all linear orders (total orders) of the set {a,b,c}:

    Is that just: (a,a) < (a,b) < (a,c) < (b,a) < (b,b) < (b,c) < (c,a) < (c,b) < (c,c). Is this correct? There is another way shown in my textbook,but i think this is the correct way.


    Also, how many ways can one linear order a set with n elements?
    I was thinking it would n x n different ways, because in above example with 3 elements i ordered it 9 times? I dont know how to prove this (im very bad at proofs!!!)
    Does anyone know how to explain this with a small simple proof or explanation?

    Much appreciated, Kurac.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie aleph1's Avatar
    Joined
    Feb 2009
    From
    Virginia Beach VA
    Posts
    11
    Quote Originally Posted by kurac View Post
    Im doing some self study and I would like to ask question about linear orders.

    Listing all linear orders (total orders) of the set {a,b,c}:

    Is that just: (a,a) < (a,b) < (a,c) < (b,a) < (b,b) < (b,c) < (c,a) < (c,b) < (c,c). Is this correct? There is another way shown in my textbook,but i think this is the correct way.


    Also, how many ways can one linear order a set with n elements?
    I was thinking it would n x n different ways, because in above example with 3 elements i ordered it 9 times? I dont know how to prove this (im very bad at proofs!!!)
    Does anyone know how to explain this with a small simple proof or explanation?

    Much appreciated, Kurac.
    I am not sure what your notation means. Is (p,g) an open interval, a 2 space coordinate pair or possibly a set {p,q}? In wikipedia a linear order or total order is explained as a binary relation with operator ≤ .

    Using that definition with the following relationship abc (1)

    Then

    aa since a = a (reflexivity)
    ab by (1)
    ac by (1) (transivity)
    ba if and only if b = a which also satisfies (1) (antisymmetry)
    b ≤ b since b = b (reflexivity)
    bc by (1)
    ca if and only if c = a which also satisfies (1) (antisymmetry)(transivity)
    c ≤ b if and only if c = b which also satisfies (1) (antisymmetry)
    c ≤ c since c = c (reflexivity)

    All these 2-tuple relations are true for binary relationship ≤, with assumed ordering relation (1).

    If you intend something else, please explain your notation.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Quote Originally Posted by kurac View Post
    Listing all linear orders (total orders) of the set {a,b,c}:

    Is that just: (a,a) < (a,b) < (a,c) < (b,a) < (b,b) < (b,c) < (c,a) < (c,b) < (c,c). Is this correct? There is another way shown in my textbook,but i think this is the correct way.
    Self-study is often a very dangerous activity.
    The above notation is an example: it is completely wrong.
    A linear order (most often called a total order) on a set is a partial order in which any two terms in the set are comparable.
    Now it is true that any relation is a set of ordered pairs.

    This is for the sake of notation because any linear order is reflexive.
    \Delta  = \left\{ {(a,a),(b,b),(c,c)} \right\}, the diagonal of the set.

    Consider the set \{a,b,c\}. Here is a linear order on the set :\;\;b - c - a.
    Here is the set of pairs in that l.o. : \Delta  \cup \left\{ {(b,c),(b,a),(c,a)} \right\}.
    Note that there are six pairs.

    Here is another example.
    \;\;c - b - a, pairs \Delta  \cup \left\{ {(c,b),(c,a),(b,a)} \right\}

    In all the are 3!=6 such linear orderings.


    Let’s bump it up a couple of notches.
    \Delta  = \left\{ {(a,a),(b,b),(c,c),(d,d),(e,e)} \right\}, the diagonal of the set.

    Consider the set \{a,b,c,d,e\}. Here is a linear order on the set :\;\;e-b- c - a -d .
    Here is the set of pairs in that l.o. : \Delta  \cup \left\{ {(e,b),(e,c),(e,a),(e,d),(b,c),(b,a),(b,d),(c,a),(  c,d),(a,d)} \right\}.
    Notice that there are 15 pairs in the linear ordering.
    There are 5! such each with 15 pairs.

    In general, on a set of n elements there are n! linear orderings with n+\frac{n(n-1)}{2} pairs.
    Last edited by Plato; May 4th 2009 at 03:13 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,326
    Thanks
    1296
    As aleph1 says, your use of pairs like (a,a) or (a,b) is confusing. I think you mean that you have a set of three objects, {a, b, c}, and want orders like a< b< c, a< c< b, b< a< c, b< c< a, c< a< b, and c< b< a. Those are, in fact, the only linear orders on the set {a, b, c}. Notice that we could write those orders with the "<" understood: abc, acb, bac, bca, cab, cba. That is, linear orders are just permutations on the set. For a set with 3 members, there are 3!= 6 permutations and so 6 linear orders. For a set with n members, there are n! permutations and so n! linear orders.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: October 10th 2010, 05:35 AM
  2. Prove there are only two closed linear orders on R
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: September 30th 2009, 12:50 PM
  3. Partial Orders
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 2nd 2009, 08:28 PM
  4. orders of magnitude
    Posted in the Pre-Calculus Forum
    Replies: 1
    Last Post: March 25th 2009, 05:53 PM
  5. Orders of elements
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: January 9th 2009, 11:15 AM

Search Tags


/mathhelpforum @mathhelpforum