Well Ordered
Well OrderedA TotallyOrdered set S is said to be WellOrdered if every non-empty subset of S has a least element.
Partial well-orderings can be defined as PartialOrders that lack infinite descending chains. A recursive function definition on a partially well-ordered domain specifies value in terms of values for 'lesser' values of the argument.
Sequences of symbols form a partial-order under the substring relation which is WellOrdered.
Though set-membership is not an ordering because it is not transitive, well-foundedness seems to be a related idea:
A set S0 is well-founded iff it has no infinite descending membership sequence, S0 has element S1 which has element S2 ...
This is an axiom of ZF[C] SetTheory, but there are other set theories without this axiom, e.g. NewFoundations and HyperSetTheory?. See SemanticSubtyping and <http://en.wikipedia.org/wiki/Axiomatic_set_theory>.
One formulation of the Axiom of Choice (http://www.math.vanderbilt.edu/~schectex/ccc/choice.html) is that every set has a well-ordering. The rationals, for example, do not form a well-ordering under the usual less-than relation, but there is a way of putting them into one-to-one correspondence with the natural numbers, so it can be well-ordered by the total order implied by this correspondence. Any countable set can be well-ordered. These statements do not depend on the axiom of choice, but this one does: The real numbers can be well-ordered. Some consider this idea startling because it is nonconstructive. The AxiomOfChoice says it can be done, but is not specific about what this ordering would look like.
But there is a straightforward way to construct a well-ordering of the positive rationals. Write each one as p/q where p and q have no common factor (other than 1). Order them by ascending value of (p+q), then within each set of p+q values, order by ascending p.
So you get: 1/1, 1/2, 2/1, 1/3, 3/1, 1/4, 2/3, 3/2, 4/1...
You can do the whole set of rationals by putting zero at the start and interleaving each negative after its corresponding positive.
Jerry Bona once said,
"The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?"
This is a joke. In the setting of ordinary set theory, all three of those principles are mathematically equivalent -- i.e., if we assume any one of those principles, we can use it to prove the other two. However, human intuition does not always follow what is mathematically correct. The Axiom of Choice agrees with the intuition of most mathematicians; the Well Ordering Principle is contrary to the intuition of most mathematicians; and Zorn's Lemma is so complicated that most mathematicians are not able to form any intuitive opinion about it.
EditText of this page
(last edited May 9, 2006)
or FindPage with title or text search