# Thread: Finding a linear order on a set

1. ## 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!

2. 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.$

3. 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.