Set Theory

Set Theory Logo

Well Orders

A well order (also referred as well-ordering or well-order relation) is a special type of total order where every non-empty subset has a least element. A set with a well-order relation is called a well-ordered set.

For example, the set of natural numbers under the usual order relation forms a well-ordered set.

By definition, any well-ordered set is totally ordered. However, the converse is not true - the set of integers , which is totally ordered, is not well-ordered under the standard ordering (since itself and some its subsets do not have least elements). Although, any finite totally ordered set is well-ordered.

In a well-ordered set, every element (except a possible greatest element) has a unique successor. However, not every element of a well-ordered set needs to have a predecessor.

The well-ordering theorem (also known as Zermelo's theorem) states that every set may be well-ordered. If so, we can find an order on the set of integers \(\mathbb{Z}\) which makes it well-ordered. For example, instead of the regular order relation \(\le,\) we can define the following order:

\[{0 \preccurlyeq - 1 \preccurlyeq 1 \preccurlyeq - 2 \preccurlyeq 2 \preccurlyeq - 3 \preccurlyeq 3 \preccurlyeq \ldots}\]

That's a well order relation on \(\mathbb{Z},\) in which \(0\) is the least element.

The well-ordering theorem is equivalent to the axiom of choice.

Let \(A\) and \(B\) be two partially ordered sets. If there is a function \(f : A \to B\) such that, for every \(x, y \in A,\)

\[x \le y \Rightarrow f\left( x \right) \le f\left( y \right),\]

then the sets \(A\) and \(B\) are said to be order-isomorphic. Isomorphic sets are denoted as \(A \cong B.\)

Order isomorphism preserves well-ordering

See solved problems on Page 2.

Page 1 Page 2