Well-order
Transitive binary relations | |||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| |||||||||||||||||||||||||||||||
![]() ![]() All definitions tacitly require the homogeneous relation be transitive: for all if and then |
In
Every non-empty well-ordered set has a least element. Every element s of a well-ordered set, except a possible
If ≤ is a
Every well-ordered set is uniquely
The observation that the
Ordinal numbers
Every well-ordered set is uniquely
For an infinite set the order type determines the
Examples and counterexamples
Natural numbers
The standard ordering ≤ of the natural numbers is a well ordering and has the additional property that every non-zero natural number has a unique predecessor.
Another well ordering of the natural numbers is given by defining that all even numbers are less than all odd numbers, and the usual ordering applies within the evens and the odds:
This is a well-ordered set of order type ω + ω. Every element has a successor (there is no largest element). Two elements lack a predecessor: 0 and 1.
Integers
Unlike the standard ordering ≤ of the natural numbers, the standard ordering ≤ of the integers is not a well ordering, since, for example, the set of negative integers does not contain a least element.
The following binary relation R is an example of well ordering of the integers: x R y if and only if one of the following conditions holds:
- x = 0
- x is positive, and y is negative
- x and y are both positive, and x ≤ y
- x and y are both negative, and |x| ≤ |y|
This relation R can be visualized as follows:
R is isomorphic to the ordinal number ω + ω.
Another relation for well ordering the integers is the following definition: if and only if
This well order can be visualized as follows:
This has the order type ω.
Reals
The standard ordering ≤ of any
An uncountable subset of the real numbers with the standard ordering ≤ cannot be a well order: Suppose X is a subset of well ordered by ≤. For each x in X, let s(x) be the successor of x in ≤ ordering on X (unless x is the last element of X). Let whose elements are nonempty and disjoint intervals. Each such interval contains at least one rational number, so there is an injective function from A to There is an injection from X to A (except possibly for a last element of X, which could be mapped to zero later). And it is well known that there is an injection from to the natural numbers (which could be chosen to avoid hitting zero). Thus there is an injection from X to the natural numbers, which means that X is countable. On the other hand, a countably infinite subset of the reals may or may not be a well order with the standard ≤. For example,
- The natural numbers are a well order under the standard ordering ≤.
- The set has no least element and is therefore not a well order under standard ordering ≤.
Examples of well orders:
- The set of numbers has order type ω.
- The set of numbers has order type ω2. The previous set is the set of limit pointswithin the set. Within the set of real numbers, either with the ordinary topology or the order topology, 0 is also a limit point of the set. It is also a limit point of the set of limit points.
- The set of numbers has order type ω + 1. With the order topology of this set, 1 is a limit point of the set, despite being separated from the only limit point 0 under the ordinary topology of the real numbers.
Equivalent formulations
If a set is totally ordered, then the following are equivalent to each other:
- The set is well ordered. That is, every nonempty subset has a least element.
- Transfinite induction works for the entire ordered set.
- Every strictly decreasing sequence of elements of the set must terminate after only finitely many steps (assuming the axiom of dependent choice).
- Every subordering is isomorphic to an initial segment.
Order topology
Every well-ordered set can be made into a topological space by endowing it with the order topology.
With respect to this topology there can be two kinds of elements:
- isolated points — these are the minimum and the elements with a predecessor.
- natural numbers
For subsets we can distinguish:
- Subsets with a maximum (that is, subsets that are bounded by themselves); this can be an isolated point or a limit point of the whole set; in the latter case it may or may not be also a limit point of the subset.
- Subsets that are unbounded by themselves but bounded in the whole set; they have no maximum, but a supremum outside the subset; if the subset is non-empty this supremum is a limit point of the subset and hence also of the whole set; if the subset is empty this supremum is the minimum of the whole set.
- Subsets that are unbounded in the whole set.
A subset is cofinal in the whole set if and only if it is unbounded in the whole set or it has a maximum that is also maximum of the whole set.
A well-ordered set as topological space is a
See also
- Tree (set theory), generalization
- Ordinal number
- Well-founded set
- Well partial order
- Prewellordering
- Directed set
References
- MR 3016456.
- .
- ISBN 978-0-471-31716-6.