Well-order

In mathematics, a well-order relation (or well-ordering) 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. Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and In Mathematics and Set theory, a total order, linear order, simple order, or (non-strict ordering is a Binary relation In Mathematics, and more specifically Set theory, the empty set is the unique set having no ( Zero) members In Mathematics, especially in Order theory, the greatest element of a subset S of a Partially ordered set (poset is an element of S Equivalently, a well-ordering is a well-founded total order. In Mathematics, a Binary relation, R, is well-founded (or wellfounded) on a class X if and only if every non- empty The set S together with the well-order relation is then called a well-ordered set.

Every element, except a possible greatest element, has a unique successor (next element). In Mathematics, especially in Order theory, the greatest element of a subset S of a Partially ordered set (poset is an element of 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. In Mathematics, especially in Order theory, the greatest element of a subset S of a Partially ordered set (poset is an element of S

Spelling note: The hyphen is frequently omitted in contemporary papers, yielding the spellings wellorder, wellordered, and wellordering.

1 Ordinal numbers
2 Examples
3 Properties
4 Equivalent formulations
5 Order topology
6 See also

Ordinal numbers

Every well-ordered set is uniquely order isomorphic to a unique ordinal number, called the order type of the well-ordered set. In the mathematical field of Order theory an order isomorphism is a special kind of Monotone function that constitutes a suitable notion of Isomorphism In Set theory, an ordinal number, or just ordinal, is the Order type of a Well-ordered set. In Mathematics, especially in Set theory, two Ordered sets XY are said to have the same order type just when they are Order isomorphic 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 basically to assigning ordinal numbers one by one to the objects. Counting is the mathematical action of repeatedly adding (or subtracting one usually to find out how many objects there are or to set aside a desired number of objects (starting The size (number of elements, cardinal number) of a finite set is equal to the order type. This article describes cardinal numbers in mathematics For cardinals in linguistics see Names of numbers in English. 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 order isomorphy, 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. In Mathematics, the cardinality of a set is a measure of the "number of elements of the set" For a countably infinite set the set of possible order types is even uncountable.

Examples

The standard ordering ≤ of the natural numbers is a well-ordering. In Mathematics, a natural number (also called counting number) can mean either an element of the set (the positive Integers or an
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 integers (from the Latin integer, literally "untouched" hence "whole" the word entire comes from the same origin but via French A negative number is a Number that is less than zero, such as −2
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:
1. x = 0
2. x is positive, and y is negative
3. x and y are both positive, and x ≤ y
4. x and y are both negative, and y ≤ x
R can be visualized as follows:

0 1 2 3 4 . In Mathematics, a binary relation (or a dyadic or 2-place relation) is an arbitrary association of elements within a set or with elements of ↔ . . . . -1 -2 -3 . . . . .

R is isomorphic to the ordinal number ω + ω. In Set theory, an ordinal number, or just ordinal, is the Order type of a Well-ordered set.

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:

0 -1 1 -2 2 -3 3 -4 4 . . .

The standard ordering ≤ of the positive real numbers is not a well-ordering, since, for example, the open interval (0, 1) does not contain a least element. In Mathematics, the real numbers may be described informally in several different ways From the ZFC axioms of set theory (including the axiom of choice) one can show that there is a well-order of the reals; it is also possible to show that the ZFC axioms alone are not sufficient to prove the existence of a definable (by a formula) well-order of the reals. Zermelo–Fraenkel set theory with the axiom of choice, commonly abbreviated ZFC, is the standard form of Axiomatic set theory and as such is the most common In Mathematics, the axiom of choice, or AC, is an Axiom of Set theory. 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. The axiom of constructibility is a possible Axiom for Set theory in mathematics that asserts that every set is constructible.

An uncountable subset of real numbers with the standard "≤" is not well-ordered because the real line can only contain countably many disjoint intervals. A countably infinite subset may or may not be a well-order with the standard "≤". 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 points within the set. In Mathematics, informally speaking a limit point of a set S in a Topological space X is a point x in X that can be "approximated" 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 topology of this set, 1 is a limit point of the set. In Mathematics, an order topology is a certain Topology that can be defined on any Totally ordered set. With the ordinary topology (or equivalently, the order topology) of the real numbers it is not.

Properties

In a well-ordered set, every element, unless it is the overall largest, has a unique successor: the smallest element that is larger than it. However, not every element needs to have a predecessor. As an example, consider an ordering of the natural numbers where 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 ω + ω. Note that while every element has a successor (there is no largest element), two elements lack a predecessor: zero and one.

If a set is well-ordered, the proof technique of transfinite induction can be used to prove that a given statement is true for all elements of the set. Transfinite induction is an extension of Mathematical induction to well-ordered sets, for instance to sets of ordinals or cardinals.

The well-ordering theorem, which is equivalent to the axiom of choice, states that every set can be well-ordered. The well-ordering theorem (not to be confused with the Well-ordering axiom) states that every set can be Well-ordered This is important because it makes In Mathematics, the axiom of choice, or AC, is an Axiom of Set theory. The well-ordering theorem is also equivalent to the Kuratowski-Zorn lemma. Zorn's lemma, also known as the Kuratowski-Zorn lemma, is a proposition of Set theory that states Every Partially ordered set in which

In a well-ordered set, every subset with an upper bound has a supremum.

Equivalent formulations

If a set is totally ordered, then the following are equivalent:

The set is well-ordered. In Mathematics and Set theory, a total order, linear order, simple order, or (non-strict ordering is a Binary relation That is, every nonempty subset has a least element.
Transfinite induction works for the entire ordered set. Transfinite induction is an extension of Mathematical induction to well-ordered sets, for instance to sets of ordinals or cardinals.
Every strictly decreasing sequence of elements of the set must terminate after only finitely many steps (assuming the axiom of dependent choice). In Mathematics, the axiom of dependent choices, denoted DC, is a weak form of the Axiom of choice (AC which is still sufficient to develop most of

Order topology

Every well-ordered set can be made into a topological space by endowing it with the order topology. Topological spaces are mathematical structures that allow the formal definition of concepts such as Convergence, connectedness, and continuity. In Mathematics, an order topology is a certain Topology that can be defined on any Totally ordered set.

With respect to this topology there can be two kinds of elements:

isolated points - these are the minimum and the elements with a predecessor
limit points - 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. In Topology, a branch of Mathematics, a point x of a set S is called an isolated point,if there exists a neighborhood of In Mathematics, informally speaking a limit point of a set S in a Topological space X is a point x in X that can be "approximated"

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. In Mathematical analysis and related areas of Mathematics, a set is called bounded, if it is in a certain sense of finite size
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 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. In Mathematics, a cofinal subset is a subset B of a Preordered set A such that for every a in A there is a b

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 ω₁ (omega-one), that is, if and only if the set is countable or has the smallest uncountable order type. In Topology, a branch of Mathematics, a first-countable space is a Topological space satisfying the "first Axiom of countability " In Set theory, an ordinal number, or just ordinal, is the Order type of a Well-ordered set.

Dictionary

-noun

(mathematics) A total order of which every nonempty subset has a least element.

-verb

(mathematics, transitive) To impose a well-order on (a set).

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
network: | |

Contents