Well Orders

Solved Problems

Solution.

1. By definition, a partially ordered set is a well order if it is a total order and every non-empty subset has a least element. For the empty set \(\varnothing,\) both these conditions are vacuously true. (We cannot prove that they are false, so they are considered to be true.) Therefore, the empty set \(\varnothing\) is a well order.
2. The set \(\left\{ {12,3, - 4, - 7,0,-2,-11,5,1} \right\}\) is finite and totally ordered by the usual "less than" (\(\lt\)) relation:
   \[ -11 \lt -7 \lt -4 \lt -2 \lt 0 \lt 1 \lt 3 \lt 5 \lt 12.\]
   Hence, this is a well order.
3. The set \(\left\{ {- \sqrt{2} ,0,\sqrt{2} ,2\sqrt{2} ,3\sqrt{2}, \ldots } \right\}\) is well-ordered since there is an order preserving one-to-one mapping (order isomorphism) between the given set and the well-ordered subset of \(\mathbb{Z}\) with the least element \(-1:\)
   \[\left\{ { - 1,0,1,2,3, \ldots } \right\}\]
4. The set \(2\mathbb{N}\) is order isomorphic to \(\mathbb{N}.\) Therefore it is well-ordered.
5. The first elements of the set \(\left\{ {\frac{1}{{a - 1}} \,\big|\, a \in \mathbb{N}, a \gt 1} \right\}\) are given by
   \[1,\frac{1}{2},\frac{1}{3},\frac{1}{4},\frac{1}{5}, \ldots \]
   As it can be seen, \(a_n \to 0\) as \(n \to \infty.\) This set does not have a least element and is not a well-order under the standard ordering \(\le.\)

Solution.

1. The given set is finite and totally ordered:
   \[{\sqrt{2} \lt \sqrt{3} \lt \sqrt{5} \lt \sqrt{7} \lt \sqrt{11} }.\]
   Hence, it is well-ordered.
2. The set \(3\mathbb{Z} - 5\) is order isomorphic to the set of integers \(\mathbb{Z}.\) Both these sets are not well-ordered under the standard ordering relation.
3. The denominator \(a\) of the fraction \({\frac{1}{a}}\) ranges from \(1\) to \(100.\) So this is a finite totally ordered set of rational numbers with the least element \({\frac{1}{100}}.\) It is a well order.
4. The set \(\left\{ {a \mid a \in \mathbb{Q} ,a \gt 5} \right\}\) is not a well order under standard ordering. For example, the following subset of rational numbers does not have a least element:
   \[\left\{ {5 + \frac{1}{2},5 + \frac{1}{3},5 + \frac{1}{4}, \ldots } \right\}\]
5. The set \(\left\{ {a \mid a \in \mathbb{Z} ,a \ge 10} \right\}\) is well-ordered, since every its non-empty subset contains positive integers and has a least element.

Solution.

If we consider the usual ordering, the set \(\mathbb{Q}^+\) is not well-ordered, because there are subsets that have no least element. For example, the subset \(\left\{ {\frac{1}{{{2^n}}} \,\bigg|\, n \in \mathbb{N}} \right\}\) does not have a least element.

However, according to the well-ordering theorem, we can construct a well order on \(\mathbb{Q}^+\). One of the algorithms looks as follows:

1. Reduce the rationals to lower terms (when the numerator and denominator have no common factors other than \(1\)).
2. Order the rationals \(\frac{m}{n}\) by ascending value of \(m + n.\)
3. Within a subset with the same value of \(m + n,\) order the rationals by ascending value of \(m.\)

So the order is given by

With this ordering, the set of positive integers \(\mathbb{Q}^+\) becomes well-ordered.

Solution.

Consider a non-empty subset of the interval \(\left[ {2,5} \right]\) - for example, the open interval \(\left( {3,4} \right).\) For any \(x \in \left( {3,4} \right),\) we can find a number \(y\) such that \(y \in \left( {3,4} \right)\) and \(y \lt x.\) This means that the subset \(\left( {3,4} \right)\) has no least element. Hence, the original interval \(\left[ {2,5} \right]\) is not well-ordered under the usual ordering relation.