# Well-ordered set

1. Aug 16, 2013

### aleph-aleph

I'm reading Cantor's 1883 Grundlagen, it says a set is well-ordered if the set and it's subsets have first element, the next successor (unless it's an empty set or there is no successor). Note that the first element not neccessarily a least element. "Theory of sets" by E. Kamke also give the same definition. However, "Naive Set Theory" by Paul Halmos and many other recent publications say the first element as smallest element. Why is it so?

2. Aug 16, 2013

### Stephen Tashi

Do we want to define a well ordered set so that the null set is a well ordered set or do we want to exclude the null set?

3. Aug 16, 2013

### aleph-aleph

Include the null set.

4. Aug 16, 2013

### verty

I am aware, from reading a few histories and philosophical articles on logic, that, for Cantor, choice was something natural, to be used freely without mention. Also, set theory of the time contained urelements and was not as mathematical as it became later.

A well-ordered set (of elephants, apples, sets, whatever) is such that each subset has a first element. I read "the first element is not necessarily the least element" to mean, a meaningful ordering of the elements is not required, we can supply one by choice alone.

5. Aug 16, 2013

### Stephen Tashi

Then null set is a well ordered set that doesn't have a least element.

6. Aug 18, 2013

### MrAnchovy

The set of negative integers is well-ordered (because it has a first element, -1, and each element i has a successor element i-1). But it does not have a least element.

7. Aug 18, 2013

### Stephen Tashi

If you (or Cantor) are making a distinction between the "first element" of a set and the "least element" of a set, you should define what is meant by the "first element".

The negative integers, under the usual order relation on the integers are not a well ordered set.

8. Aug 18, 2013

### MrAnchovy

A suitable definition (can't remember if Cantor used it) would be the unique element that is not the successor of any other element.

It would also be helpful to understand what is meant by the "least element". In the set of negative integers (which is well ordered under the relation ≥) the "least element" (in the context of set theory) is -1, which is of course the element which is arithmetically the greatest.

The positive integers are not a well ordered set under the usual order relation on American Presidents, but I don't find that remarkable.

I think there is actually a fine distinction that is being missed here. I believe that Cantor approached sets from a constructivist point of view, so that his well-ordered sets were constructed from a first element and a successor function: a function that for any element $k_i$ generates element $k_{i+1}$. Modern set theory approaches the definition from the "other end" - a set is already defined, and in order to detemine whether it is well ordered or not you need a relation to put the elements in order. It is interesting that the authors of this theory decided to use the terms "less than" and "least" to describe this relation rather than "before" and "first".

9. Aug 19, 2013

### aleph-aleph

Cantor didn't define "first element" nor mention "least element" but I think I get what you guys are saying. This is what I get, there is no concept of "relation" to Cantor, for Cantor, "well ordered" kinda means "can be listed in such a way that it has first element". For example set of even number is well ordered because it can be listed as {2,4,6,8,...}, set of integer is well ordered because it can be listed as {0,1,-1,2,-2,...} and set of negative integer is well ordered because it can be listed as {-1,-2,-3,...}. Set of {...,3,2,1} is not well ordered because it has no first element (Kamke 1950). I checked, there is no concept of "relation" in Kamke's book "Theory of sets" but "Naive set theory" by Paul Halmos and modern literatures have the concept of "relation". So, it seems to me that by adding the concept of "relation" and for certain reason unknown to me, the definition of "well ordered" changed.

10. Aug 19, 2013

### micromass

Staff Emeritus
The concept of well-order doesn't apply to sets. You need an order relation on your set in order to make sense of the concept well-order.

So the set of even numbers is not a well-order, since you did not yet specify the order relation. If you say, the set of even numbers equiped with the usual relation, then this is a well-order.
The set of integers under the usual order is not a well-order since it has no least element. However, if you make a special order as $0<1<-1<2<-2<...$, then this special order is a well-order.

The Kamke reference basically says the same thing since it talks in the definition of well-order about "ordered sets" and not just "sets". The classic set theory book by Hausdorff does the same thing.

What has changed however is the meaning of the notation $\{1,2,3,4\}$. Now, we regard the set $\{1,2,3,4\}$ to be completely equal to $\{4,3,2,1\}$. So we just see it as a set.
But before, they considered the notation $\{1,2,3,4\}$ not only to denote a set, but rather an ordered set. So the notation meant that the set was ordered as $1<2<3<4$. This is a convention that is not used anymore.

So both now and historically, to talk about an well-order, we need an ordered set and not just a set.