Well Ordering

**usagi_killer** · September 6th 2010, 11:23 AM

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!

**emakarov** · September 6th 2010, 01:53 PM

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

**usagi_killer** · September 7th 2010, 07:03 AM

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}\}<br />$

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.

**emakarov** · September 7th 2010, 08:17 AM

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.

**usagi_killer** · September 7th 2010, 10:47 PM

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.

**emakarov** · September 7th 2010, 11:35 PM

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.

**Nguyen** · September 8th 2010, 02:48 AM

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)\}$

**emakarov** · September 8th 2010, 03:03 AM

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.

**Nguyen** · September 8th 2010, 03:35 AM

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.

**emakarov** · September 8th 2010, 04:04 AM

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.

Thread: Well Ordering

LinkBack

Thread Tools

Display

Well Ordering

Similar Math Help Forum Discussions

help with well ordering principle

well ordering principle

well-ordering

Well-Ordering

well ordering

Search Tags