# Math Help - Well Ordering

1. ## Well Ordering

Define a well-ordering relation R on the set of rationals: $S = \{x = \frac{3^n \times 7^m}{11^t} \text{for integers n, m, t} \ge 1\}$

So using the definition of well-ordering from wikipedia, "a well-order relation on a set S is a total order on S with the property that every non-empty subset of S has a least element in this ordering"

In other words we need to ensure that the relation is transitive, antisymmetric and total and that every non empty subset of S has a least element.

I am stuck on how to define such a relation... any help would be appreciated!

2. Question: why does regular order $\le$ on $S$ not work?

One option that does work is the following. Let us define $T$ as a set of triples $\{(n,m,t)\in\mathbb{Z}^3\mid n,m,t\ge 1\}$ and $f:T\to S$ as a function $f(n,m,t)=(3^n\times 7^m)/11^t$. Since 3, 7, and 11 are pairwise relatively prime, $f$ is a bijection. Thus, any well-order $R'$ on $T$ gives rise to a well-order $R=\{(f(w_1),f(w_2))\mid w_1,w_2\in T, (w_1,w_2)\in R'\}$ on $S$.

Now, one can take the lexicographical order on $T$ (see the remark about well-orders in the link).

3. Thanks emakarov.

Say we had $S = \{\frac{3 \times 7}{11}, \frac{3^2 \times 7}{11}, \frac{3^3 \times 7}{11}, \frac{3 \times 7^2}{11}\}
$

So a well ordered relation on a set S is a total order on S with the property that every non-empty subset of S has a least element in this ordering.

So $(x, y) \in R$ if $x \le y$

$R = \{\left(\frac{3 \times 7}{11}, \frac{3^2 \times 7}{11}\right), \left(\frac{3 \times 7}{11}, \frac{3^3 \times 7}{11}\right), \left(\frac{3 \times 7}{11}, \frac{3 \times 7^2}{11}\right), \left(\frac{3^2 \times 7}{11}, \frac{3^3 \times 7}{11}\right), \left(\frac{3^2 \times 7}{11}, \frac{3 \times 7^2}{11}\right), \left(\frac{3^3 \times 7}{11}, \frac{3 \times 7^2}{11}\right), \left(\frac{3 \times 7}{11}, \frac{3 \times 7}{11}\right), \left(\frac{3^2 \times 7}{11}, \frac{3^2 \times 7}{11}\right), \left(\frac{3^3 \times 7}{11}, \frac{3^3 \times 7}{11}\right), \left(\frac{3 \times 7^2}{11}, \frac{3 \times 7^2}{11}\right)\}$

R is a total order on S since it is transitive, total and antisymmetric.

But what I don't get is "with the property that every non-empty subset of S has a least element in this ordering", this has nothing to do with the relation R whatsoever?? If we take any non-empty subset of S then the subset must has a least element, what's the point of creating a relation that is a total order on S?

Thanks again.

4. Hint: the definition of "least" involves R.

To get a better idea, I recommend finding out why the regular order <= is not a well-order on S.

5. Hmm sorry I've thought about it and I still can't really understand why.

I still don't get why we have a define a relation that is a total order on S because if we take any non-empty set of S it must have a least element anyway.

6. Hmm sorry I've thought about it and I still can't really understand why.
If you think that the standard order is a well-order on S, then what is the least element in S?

If we take any non-empty subset of S then the subset must has a least element, what's the point of creating a relation that is a total order on S?
I see two things that need clarification. First, not every set with a total order (or partial order) has the least element. Second, the definition of "least" is relative to the order. One can have a regular $\le$-least element or an R-least element for some completely different order relation R.

Therefore, if S does not have the least element with respect to the standard order $\le$, in order to make S a well-ordered set, one has to come up with some other order R so that S, as well as every proper subset of S, have the R-least element.

By the way, a total order on a finite set is always a well-order. This is because for each element x, either x is the least, or you can find a smaller element; however, you can't find smaller and smaller elements forever because the set is finite. So, your example with finite S and R above does not show everything that is going on.

7. So you are saying that the well-ordering R is:
$R = \{\left(\frac{3 \times 7}{11}, \frac{3^2 \times 7}{11}\right), \left(\frac{3 \times 7}{11}, \frac{3^3 \times 7}{11}\right), \left(\frac{3 \times 7}{11}, \frac{3 \times 7^2}{11}\right), \left(\frac{3^2 \times 7}{11}, \frac{3^3 \times 7}{11}\right), \left(\frac{3^2 \times 7}{11}, \frac{3 \times 7^2}{11}\right), \left(\frac{3^3 \times 7}{11}, \frac{3 \times 7^2}{11}\right), \left(\frac{3 \times 7}{11}, \frac{3 \times 7}{11}\right), \left(\frac{3^2 \times 7}{11}, \frac{3^2 \times 7}{11}\right), \left(\frac{3^3 \times 7}{11}, \frac{3^3 \times 7}{11}\right), \left(\frac{3 \times 7^2}{11}, \frac{3 \times 7^2}{11}\right)\}$

8. Originally Posted by Nguyen
So you are saying that the well-ordering R is:
$\textstyle R = \{\left(\frac{3 \times 7}{11}, \frac{3^2 \times 7}{11}\right), \left(\frac{3 \times 7}{11}, \frac{3^3 \times 7}{11}\right), \left(\frac{3 \times 7}{11}, \frac{3 \times 7^2}{11}\right), \left(\frac{3^2 \times 7}{11}, \frac{3^3 \times 7}{11}\right), \left(\frac{3^2 \times 7}{11}, \frac{3 \times 7^2}{11}\right), \left(\frac{3^3 \times 7}{11}, \frac{3 \times 7^2}{11}\right), \left(\frac{3 \times 7}{11}, \frac{3 \times 7}{11}\right), \left(\frac{3^2 \times 7}{11}, \frac{3^2 \times 7}{11}\right), \left(\frac{3^3 \times 7}{11}, \frac{3^3 \times 7}{11}\right), \left(\frac{3 \times 7^2}{11}, \frac{3 \times 7^2}{11}\right)\}$
Well-ordering on what set? On the finite S consisting of four elements, yes. As I said, any total order on that finite set is a well-order. On the original infinite S, no. It is not even a total order.

9. Originally Posted by emakarov
Well-ordering on what set? On the finite S consisting of four elements, yes. As I said, any total order on that finite set is a well-order. On the original infinite S, no. It is not even a total order.
I mean what are you saying that the well-ordering relation R on the set of rationals: $S = \{x = \frac{3^n \times 7^m}{11^t} \text{for integers n, m, t} \ge 1\}$ is???

I don't seem to understand what answer you are giving usagi_killer.

10. As for the answer to the original question, namely, a well-order on the infinite set S, I described it in my first reply. What we've been discussing after that was why the standard order is not a well-order on S, which implies the need for a different order R.