Well-order
Encyclopedia
In mathematics
, a well-order relation (or well-ordering) on a set S is a strict total order on S with the property that every non-empty subset
of S has a least element in this ordering. Equivalently, a well-ordering is a well-founded
strict total order. The set S together with the well-order relation is then called a well-ordered set.
Every element s, except a possible greatest element
, has a unique successor (next element), namely the least element of the subset of all elements greater than s. Every subset which has an upper bound has a least upper bound
. There may be elements (besides the least element) which have no predecessor.
If a set is well-ordered (or even if it merely admits a wellfounded relation), the proof technique of transfinite induction
can be used to prove that a given statement is true for all elements of the set.
The observation that the natural numbers are well-ordered by the usual less-than relation is commonly called the well-ordering principle
(for natural numbers).
The well-ordering theorem
, which is equivalent to the axiom of choice, states that every set can be well-ordered. The well-ordering theorem is also equivalent to the Kuratowski-Zorn lemma.
Spelling note: The hyphen is frequently omitted in contemporary papers, yielding the spellings wellorder, wellordered, and wellordering.
, called the order type
of the well-ordered set. The position of each element within the ordered set is also given by an ordinal number. In the case of a finite set, the basic operation of counting
, to find the ordinal number of a particular object, or to find the object with a particular ordinal number, corresponds to assigning ordinal numbers one by one to the objects. The size (number of elements, cardinal number
) of a finite set is equal to the order type. Counting in the everyday sense typically starts from one, so it assigns to each object the size of the initial segment with that object as last element. Note that these numbers are one more than the formal ordinal numbers according to the isomorphic order, because these are equal to the number of earlier objects (which corresponds to counting from zero). Thus for finite n, the expression "n-th element" of a well-ordered set requires context to know whether this counts from zero or one. In a notation "β-th element" where β can also be an infinite ordinal, it will typically count from zero.
For an infinite set the order type determines the cardinality, but not conversely: well-ordered sets of a particular cardinality can have many different order types. For a countably infinite set the set of possible order types is even uncountable.
s is a well-ordering and has the additional property that every nonzero 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.
s, the standard ordering ≤ of the integer
s is not a well-ordering, since, for example, the set of negative integers does not contain a least element.
The following relation R is an example of well-ordering of the integers: x R y
if and only if
one of the following conditions holds:
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: x ≤z y iff
(|x| < |y| or (|x| = |y| and x ≤ y)). This well-order can be visualized as follows:
This has the order type
ω.
s is not a well-ordering, since, for example, the open interval (0, 1) does not contain a least element. From the ZFC axioms of set theory (including the axiom of choice) one can show that there is a well-order of the reals. Also Sierpinski proved that ZF + GCH imply the axiom of choice and hence a well-order of the reals. Nonetheless, it is possible to show that the ZFC+GCH axioms alone are not sufficient to prove the existence of a definable (by a formula) well-order of the reals. However it is consistent with ZFC that a definable well-ordering of the reals exists—for example, it is consistent with ZFC that V=L, and it follows from ZFC+V=L that a particular formula well-orders the reals, or indeed any set.
An uncountable subset of real numbers with the standard ordering "≤" cannot be a well-order because the open intervals (x,s(x)) for the different x would be nonempty and disjoint, where s(x) is the successor of x, and each interval would contain its own rational number. A countably infinite subset of the reals may or may not be a well-order with the standard "≤".
Examples of well-orders:
, then the following are equivalent to each other:
by endowing it with the order topology
.
With respect to this topology there can be two kinds of elements:
For subsets we can distinguish:
A subset is cofinal
in the whole set if and only if it is unbounded in the whole set or it has a maximum which is also maximum of the whole set.
A well-ordered set as topological space is a first-countable space
if and only if it has order type less than or equal to ω1 (omega-one
), that is, if and only if the set is countable or has the smallest uncountable order type.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, a well-order relation (or well-ordering) on a set S is a strict total order on S with the property that every non-empty subset
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
of S has a least element in this ordering. Equivalently, a well-ordering is a well-founded
Well-founded relation
In mathematics, a binary relation, R, is well-founded on a class X if and only if every non-empty subset of X has a minimal element with respect to R; that is, for every non-empty subset S of X, there is an element m of S such that for every element s of S, the pair is not in R:\forall S...
strict total order. The set S together with the well-order relation is then called a well-ordered set.
Every element s, except a possible greatest element
Greatest element
In mathematics, especially in order theory, the greatest element of a subset S of a partially ordered set is an element of S which is greater than or equal to any other element of S. The term least element is defined dually...
, has a unique successor (next element), namely the least element of the subset of all elements greater than s. Every subset which has an upper bound has a least upper bound
Supremum
In mathematics, given a subset S of a totally or partially ordered set T, the supremum of S, if it exists, is the least element of T that is greater than or equal to every element of S. Consequently, the supremum is also referred to as the least upper bound . If the supremum exists, it is unique...
. There may be elements (besides the least element) which have no predecessor.
If a set is well-ordered (or even if it merely admits a wellfounded relation), the proof technique of transfinite induction
Transfinite induction
Transfinite induction is an extension of mathematical induction to well-ordered sets, for instance to sets of ordinal numbers or cardinal numbers.- Transfinite induction :Let P be a property defined for all ordinals α...
can be used to prove that a given statement is true for all elements of the set.
The observation that the natural numbers are well-ordered by the usual less-than relation is commonly called the well-ordering principle
Well-ordering principle
The "well-ordering principle" is a property of ordered sets. A set X is well ordered if every subset of X has a least element. An example of a well ordered set is the set of natural numbers. An example of set that is not well ordered is the set of integers...
(for natural numbers).
The well-ordering theorem
Well-ordering theorem
In mathematics, the well-ordering theorem states that every set can be well-ordered. A set X is well-ordered by a strict total order if every non-empty subset of X has a least element under the ordering. This is also known as Zermelo's theorem and is equivalent to the Axiom of Choice...
, which is equivalent to the axiom of choice, states that every set can be well-ordered. The well-ordering theorem is also equivalent to the Kuratowski-Zorn lemma.
Spelling note: The hyphen is frequently omitted in contemporary papers, yielding the spellings wellorder, wellordered, and wellordering.
Ordinal numbers
Every well-ordered set is uniquely order isomorphic to a unique ordinal numberOrdinal number
In set theory, an ordinal number, or just ordinal, is the order type of a well-ordered set. They are usually identified with hereditarily transitive sets. Ordinals are an extension of the natural numbers different from integers and from cardinals...
, called the order type
Order type
In mathematics, especially in set theory, two ordered sets X,Y are said to have the same order type just when they are order isomorphic, that is, when there exists a bijection f: X → Y such that both f and its inverse are monotone...
of the well-ordered set. The position of each element within the ordered set is also given by an ordinal number. In the case of a finite set, the basic operation of counting
Counting
Counting is the action of finding the number of elements of a finite set of objects. The traditional way of counting consists of continually increasing a counter by a unit for every element of the set, in some order, while marking those elements to avoid visiting the same element more than once,...
, to find the ordinal number of a particular object, or to find the object with a particular ordinal number, corresponds to assigning ordinal numbers one by one to the objects. The size (number of elements, cardinal number
Cardinal number
In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality of sets. The cardinality of a finite set is a natural number – the number of elements in the set. The transfinite cardinal numbers describe the sizes of infinite...
) of a finite set is equal to the order type. Counting in the everyday sense typically starts from one, so it assigns to each object the size of the initial segment with that object as last element. Note that these numbers are one more than the formal ordinal numbers according to the isomorphic order, because these are equal to the number of earlier objects (which corresponds to counting from zero). Thus for finite n, the expression "n-th element" of a well-ordered set requires context to know whether this counts from zero or one. In a notation "β-th element" where β can also be an infinite ordinal, it will typically count from zero.
For an infinite set the order type determines the cardinality, but not conversely: well-ordered sets of a particular cardinality can have many different order types. For a countably infinite set the set of possible order types is even uncountable.
Natural numbers
The standard ordering ≤ of the natural numberNatural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
s is a well-ordering and has the additional property that every nonzero 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:
- 0 2 4 6 8 ... 1 3 5 7 9 ...
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 numberNatural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
s, the standard ordering ≤ of the integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s is not a well-ordering, since, for example, the set of negative integers does not contain a least element.
The following relation R is an example of well-ordering of the integers: x R y
Binary relation
In mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...
if and only if
If and only if
In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
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:
- 0 1 2 3 4 ... -1 -2 -3 ...
R is isomorphic to the ordinal number
Ordinal number
In set theory, an ordinal number, or just ordinal, is the order type of a well-ordered set. They are usually identified with hereditarily transitive sets. Ordinals are an extension of the natural numbers different from integers and from cardinals...
ω + ω.
Another relation for well-ordering the integers is the following definition: x ≤z y iff
IFF
IFF, Iff or iff may refer to:Technology/Science:* Identification friend or foe, an electronic radio-based identification system using transponders...
(|x| < |y| or (|x| = |y| and x ≤ y)). This well-order can be visualized as follows:
- 0 -1 1 -2 2 -3 3 -4 4 ...
This has the order type
Order type
In mathematics, especially in set theory, two ordered sets X,Y are said to have the same order type just when they are order isomorphic, that is, when there exists a bijection f: X → Y such that both f and its inverse are monotone...
ω.
Reals
The standard ordering ≤ of the positive real numberReal number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
s is not a well-ordering, since, for example, the open interval (0, 1) does not contain a least element. From the ZFC axioms of set theory (including the axiom of choice) one can show that there is a well-order of the reals. Also Sierpinski proved that ZF + GCH imply the axiom of choice and hence a well-order of the reals. Nonetheless, it is possible to show that the ZFC+GCH axioms alone are not sufficient to prove the existence of a definable (by a formula) well-order of the reals. However it is consistent with ZFC that a definable well-ordering of the reals exists—for example, it is consistent with ZFC that V=L, and it follows from ZFC+V=L that a particular formula well-orders the reals, or indeed any set.
An uncountable subset of real numbers with the standard ordering "≤" cannot be a well-order because the open intervals (x,s(x)) for the different x would be nonempty and disjoint, where s(x) is the successor of x, and each interval would contain its own rational number. A countably infinite subset of the reals may or may not be a well-order with the standard "≤".
- The natural numbers are a well-order.
- The set {1/n : n =1,2,3,...} has no least element and is therefore not a well-order.
Examples of well-orders:
- The set of numbers { - 2-n | 0 ≤ n < ω } has order type ω.
- The set of numbers { - 2-n - 2-m-n | 0 ≤ m,n < ω } has order type ω². The previous set is the set of limit pointLimit pointIn mathematics, a limit point of a set S in a topological space X is a point x in X that can be "approximated" by points of S in the sense that every neighbourhood of x with respect to the topology on X also contains a point of S other than x itself. Note that x does not have to be an element of S...
s within 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 { - 2-n | 0 ≤ n < ω } ∪ { 1 } has order type ω + 1. With the order topologyOrder topologyIn mathematics, an order topology is a certain topology that can be defined on any totally ordered set. It is a natural generalization of the topology of the real numbers to arbitrary totally ordered sets...
of this set, 1 is a limit point of the set. With the ordinary topology (or equivalently, the order topology) of the real numbers it is not.
Equivalent formulations
If a set is totally orderedTotal order
In set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...
, then the following are equivalent to each other:
- The set is well-ordered. That is, every nonempty subset has a least element.
- Transfinite inductionTransfinite inductionTransfinite induction is an extension of mathematical induction to well-ordered sets, for instance to sets of ordinal numbers or cardinal numbers.- Transfinite induction :Let P be a property defined for all ordinals α...
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 choiceAxiom of dependent choiceIn mathematics, the axiom of dependent choices, denoted DC, is a weak form of the axiom of choice which is still sufficient to develop most of real analysis...
). - Every subordering is isomorphic to an initial segment.
Order topology
Every well-ordered set can be made into a topological spaceTopological space
Topological spaces are mathematical structures that allow the formal definition of concepts such as convergence, connectedness, and continuity. They appear in virtually every branch of modern mathematics and are a central unifying notion...
by endowing it with the order topology
Order topology
In mathematics, an order topology is a certain topology that can be defined on any totally ordered set. It is a natural generalization of the topology of the real numbers to arbitrary totally ordered sets...
.
With respect to this topology there can be two kinds of elements:
- isolated pointIsolated pointIn topology, a branch of mathematics, a point x of a set S is called an isolated point of S, if there exists a neighborhood of x not containing other points of S.In particular, in a Euclidean space ,...
s - these are the minimum and the elements with a predecessor - limit pointLimit pointIn mathematics, a limit point of a set S in a topological space X is a point x in X that can be "approximated" by points of S in the sense that every neighbourhood of x with respect to the topology on X also contains a point of S other than x itself. Note that x does not have to be an element of S...
s - this type does not occur in finite sets, and may or may not occur in an infinite set; the infinite sets without limit point are the sets of order type ω, for example N.
For subsets we can distinguish:
- Subsets with a maximum (that is, subsets which are bounded by itself); 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 which are unbounded by itself 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 which are unbounded in the whole set.
A subset is cofinal
Cofinal (mathematics)
In mathematics, let A be a set and let ≤ be a binary relation on A. Then a subset B of A is said to be cofinal if it satisfies the following condition:This definition is most commonly applied when A is a partially ordered set or directed set under the relation ≤. Also, the notion of cofinal...
in the whole set if and only if it is unbounded in the whole set or it has a maximum which is also maximum of the whole set.
A well-ordered set as topological space is a first-countable space
First-countable space
In topology, a branch of mathematics, a first-countable space is a topological space satisfying the "first axiom of countability". Specifically, a space X is said to be first-countable if each point has a countable neighbourhood basis...
if and only if it has order type less than or equal to ω1 (omega-one
First uncountable ordinal
In mathematics, the first uncountable ordinal, traditionally denoted by ω1 or sometimes by Ω, is the smallest ordinal number that, considered as a set, is uncountable. It is the supremum of all countable ordinals...
), that is, if and only if the set is countable or has the smallest uncountable order type.
See also
- Well-ordering theoremWell-ordering theoremIn mathematics, the well-ordering theorem states that every set can be well-ordered. A set X is well-ordered by a strict total order if every non-empty subset of X has a least element under the ordering. This is also known as Zermelo's theorem and is equivalent to the Axiom of Choice...
- Ordinal numberOrdinal numberIn set theory, an ordinal number, or just ordinal, is the order type of a well-ordered set. They are usually identified with hereditarily transitive sets. Ordinals are an extension of the natural numbers different from integers and from cardinals...
- Well-founded set
- Well partial order
- PrewellorderingPrewellorderingIn set theory, a prewellordering is a binary relation that is transitive, wellfounded, and total. In other words, if \leq is a prewellordering on a set X, and if we define \sim byx\sim y\iff x\leq y \land y\leq x...
- Directed setDirected setIn mathematics, a directed set is a nonempty set A together with a reflexive and transitive binary relation ≤ , with the additional property that every pair of elements has an upper bound: In other words, for any a and b in A there must exist a c in A with a ≤ c and b ≤...