Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
  1. In Wikipedia, well-order is defined as a strict total order on a set S with the property that every non-empty subset of S has a least element in this ordering.

    But then later, well-order is defined as a total order on S with the property that every non-empty subset of S has a least element in this ordering.

    As far as I know, a total order and a strict total order are different. One is not the other. So I was wondering if well-order is defined for total order or strict total order or both? If for both, are they equivalent in the sense that if a total order is well-order, then its corresponding strict total order is also well-order? Vice versa?

  2. At the same Wikipedia page, it also says "a well-ordering is a well-founded strict total order". As I clicked into the definition of Well-founded_relation, it says "a binary relation, R, is well-founded (or wellfounded) on a class X if and only if every non-empty subset of X has a minimal element with respect to R". As minimal element is defined for partial order not for strict total order, is it true that well-founded order is a partial order and not a strict total order? So the aforementioned "a well-ordering is a well-founded strict total order" is not well-stated?

Thanks and regards!

share|improve this question

3 Answers 3

up vote 4 down vote accepted

For the first question, taking strict and non-strict orders to be well-ordering is up to you and the way you use it.

However, in set theory it is generally easier to use strict ordering in the definition because it saves the trouble with $x\le y\wedge y\le x$, furthermore we want $\in$ to define some relations and it has to be strict by the axiom of foundation (also known as axiom of regularity in some parts of the globe).

As for minimal elements, they are not only for partial orders - but for any order. If $R$ is some relation on $A$ then $x$ is $R$-minimal if $\forall y (yRx \rightarrow y=x)$, note by the way that if $R$ is not reflexive then this is still true, but you could phrase it as $\forall y\neg(yRx)$ instead, which is clearer.

The best way, in my opinion to understand deeply these choices of definitions is to study some set theory theorems about recursive definitions, transfinite inductions and the needed theorems for those. In these proofs it becomes very clear why one prefer strict relations over non-strict ones.

One final remark, although strict and non-strict total orders are "very different", they only differ by reflexivity which is some vacuous condition that you want to add when it's easier to have it - and you remove it when you find it easier to handle without it.

share|improve this answer

If $\leq$ is a total order on a set $S$, then the new relation $<$ defined by $x < y$ iff ($x \leq y$ and $x \neq y$) is a strict total order on $S$.

If $<$ is a strict total order on a set $S$, then the new relation $\leq$ defined by $x \leq y$ iff ($x < y$ or $x = y$) is a total order on $S$.

In other words, in a fairly evident way one can always exchange a total order for a strict total order and conversely. So it doesn't really matter which definition is taken. One can easily check that the definition of a well-order in one setting carries over to the definition of a well-order in the other setting.

share|improve this answer
1  
This is one of the simplest examples of the clarifying power of category: although set-theoretically a total order and a strict total order on a set are not the same thing, categorically the category of total orders and strict total orders are isomorphic (at least if one defines morphisms correctly). –  Qiaochu Yuan Dec 27 '10 at 8:10
    
Qiaochu: Clarity is for chumps ;-) –  Asaf Karagila Dec 27 '10 at 8:12
    
@Qiaochu [why is this considered a power?] ops I mis-read the English sentence. Never mind! –  user2468 Dec 27 '10 at 8:51


1. If a set is totally ordered, the strict total order is implied.

Definition of total order from Wikipedia:

$\forall a, b, c \in X$

If $a ≤ b$ and $b ≤ a$ then $a = b$ (antisymmetry);
If $a ≤ b$ and $b ≤ c$ then $a ≤ c$ (transitivity);
$a ≤ b$ or $b ≤ a$ (totality).

Definition of strict total order from Wikipedia:

$\forall a, b \in X$

$a < b$ if and only if $a ≤ b$ and $a ≠ b$
$a < b$ if and only if not $b ≤ a$

If you compare the definitions, you will see that there are no conditions under which the second set of rules is invalid, assuming the first set of rules. So, saying that a set is well-ordered if it is totally ordered makes sense, because total order implies existence of strict total order (and hence, well-ordering) on the given set.

2. I am fairly sure that one can use the term 'minimal element' with respect to totally ordered sets also.

share|improve this answer
    
"So, saying that a set is totally ordered if it is well-ordered makes sense" you mean the other way around. The integers have a strict order which is not a well-order. –  Asaf Karagila Dec 27 '10 at 8:10
    
Thank you, made a typo. Asaf, could you please explain why well-order (strict total order) does not work on integers? I am blanking here. :) –  InterestedGuest Dec 27 '10 at 8:21
    
I didn't say that there is none. Just that there is one which is strict and not well-ordered, namely the usual $<$ relation on integers... It has no minimal element so it is not well founded, and therefore not well ordered :) –  Asaf Karagila Dec 27 '10 at 8:31
    
Oh I see what you are saying, I was blanking in a different direction. Thanks. :) –  InterestedGuest Dec 27 '10 at 8:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.