Results 1 to 3 of 3

Thread: Finding a linear order on a set

  1. #1
    Oct 2009

    Finding a linear order on a set

    I'm needing a bit of guidance with the following question. I'm not entirely sure what the question is asking, so I'll put down what I know so far.

    "Suppose (A, ≤ ) is a well-ordered set. Let B=R$\displaystyle ^A$ (sorry that should be superscript). Find an explicit linear order on B."

    B is the set of functions which maps from A -> R. As we know A is well ordered, we can think of the map as {$\displaystyle a_1, a_2, ..$} -> R. So B is the set of functions {$\displaystyle f_1, f_2, ..$} : A -> R .

    A and R are both linearly ordered by ≤, so by a definition we have the maps {$\displaystyle f_1, f_2, ..$}: (A,≤) -> (R,≤') are injective maps f: A -> R which preserves the orders (a≤b => f(a) ≤' f(b)).

    I now think I should prove that these injective maps satisfy reflexivity, antisymmetry and transitivity. According to the hint we're giving, the first two should be easy and the third trickier.

    Please suggest how to do these proofs as it seems like whatever I write down is too simple. Also please tell me if what I've written so far is garbage!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Nov 2008
    I don't understand when you say maps in $\displaystyle B$ are injective and preserve order...
    If $\displaystyle B=R^A,$ then an element of $\displaystyle B$ is any function from $\displaystyle A$ to $\displaystyle R.$ I'll do as if we just have $\displaystyle B=R^A,$ maybe there is something I misunderstood

    As you said, since $\displaystyle A$ is well-ordered we can see an element $\displaystyle f$ of B as a sequence $\displaystyle (x_i)_{i\in A}$ were for all $\displaystyle i$ in $\displaystyle A,\ x_i=f(i).$ (from now on, $\displaystyle f=(x_i)$ means $\displaystyle (f(i))_{i\in A}=(x_i)_{i\in A}$)

    You want to order $\displaystyle B$ using the orders of $\displaystyle A$ and $\displaystyle R.$ Intuitively, you can think something like, for any $\displaystyle f=(x_i)$ and $\displaystyle g=(y_i)$ in $\displaystyle B,$ if $\displaystyle \forall i\in A,\ x_i\geq y_i,$ then $\displaystyle f\geq g.$
    But of course, $\displaystyle f$ could be greater than $\displaystyle g$ in some points, $\displaystyle g$ greater than $\displaystyle f$ in others, and that definition of an order of $\displaystyle B$ wouldn't be valid.

    So let's use the fact that $\displaystyle (A,\leq)$ is a well order, and define:
    $\displaystyle \forall f,g\in B,\ f=(x_i),\ g=(y_i),\ \ \ \ f> g\ \Leftrightarrow\ ( \exists j\in A\ \text{s.t.}\ x_j>y_j\ \text{and}\ \forall i<j,\ x_i=y_i)$

    This means that, if you take two map $\displaystyle f,g$ in $\displaystyle B,$ the (strictly) greatest is the "first" (for the well order of $\displaystyle A$) to be strictly greater than the other.

    Finally define , for any $\displaystyle f,g\in B,\ f\geq g \Leftrightarrow (f>g\vee f=g)$

    Prove that this really is a linear order of $\displaystyle B.$
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Oct 2009
    Aha! I remembered that in our class our lecturer mentioned we should think about lexicographic ordering to answer the question, and your answer makes sense perfectly. Thank you very much, your help is greatly appreciated.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: Feb 11th 2011, 09:01 PM
  2. Replies: 1
    Last Post: Oct 30th 2010, 04:30 PM
  3. [SOLVED] finding LI particular solutions of second order linear nonhomogeneous equation
    Posted in the Differential Equations Forum
    Replies: 0
    Last Post: Oct 3rd 2010, 12:24 PM
  4. Replies: 4
    Last Post: Aug 12th 2008, 04:46 AM
  5. Replies: 1
    Last Post: May 11th 2007, 03:01 AM

Search Tags

/mathhelpforum @mathhelpforum