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.

This is a pretty basic question, but my book doesn't give a formal logical definition of total partial ordering.

For a given full partial ordering relation R is anti-symmetric, reflexive, transitive and :

$\forall a,b \in A [ a \neq b \rightarrow ( aRb \wedge \neg bRa ) \vee ( \neg aRb \wedge bRa ) ]$

Is that the correct definition?

Edit

Thank's to Asaf for correcting my mistranslation from Hebrew to English. The book also calls it a linearly ordered set or a chain.

share|improve this question
    
I suppose I could write the "then" part as aRb XOR bRa but I don't know if there's an accepted symbol for that... –  Robert S. Barnes Nov 20 '11 at 10:01
1  
What you’ve defined there is usually called a strict total order, a strict linear order, or (rarely) a strict simple order; see this article. –  Brian M. Scott Nov 20 '11 at 10:05
    
So there is a relation property called totality? –  Robert S. Barnes Nov 20 '11 at 10:12
1  
There’s a property of a partial order being linear or being total; this property isn’t normally referred to as totality or linearity, however. –  Brian M. Scott Nov 20 '11 at 10:18
1  
@Robert: קבוצה is a set, חבורה is a group. The terms are not interchangeable. –  Asaf Karagila Nov 20 '11 at 10:44
show 3 more comments

2 Answers 2

up vote 5 down vote accepted

The original confusion between total and order comes from a mistranslation of the word מלא in Hebrew, hence my answer dealing with both terms.

A total order is a partial ordering in which every two elements are comparable, that is to say what you wrote:

Let $(A,R)$ be a partially ordered set. We say that $R$ is a total order if for all $a,b$ one of the following is true:

  1. $a=b$, or
  2. $aRb$, or
  3. $bRa$.

Due to the anti-symmetry of $R$, if both 2 and 3 hold we have that 1 holds, so if $a\neq b$ we must have that only one of the conditions hold.

A total order is also called linear often.


A complete partial order $(A,R)$ is a partial order such that for every nonempty $B\subseteq A$ there exists $y\in A$ such that:

  1. $\forall x\in B, xRy$ (that is $y$ is an upper bound of $B$), and
  2. $\forall a\in A\left(\forall x\in B\left(xRa\right)\rightarrow bRa\right)$ (every other upper bound of $B$ is an upper bound of $B\cup\lbrace y\rbrace$).

This $y$ is called the least upper bound of $B$.


Example: The real numbers with the usual ordering is a complete and total order.

However total orders need not be complete; and complete orders need not be total.

  1. The rational numbers with the usual order is a totally ordered, but $\{x\in\mathbb Q\mid x^2<2\}$ does not have a least upper bound (which would have to be $\sqrt 2$. An irrational number).

  2. The subsets of $\mathbb N$ ordered by inclusion give a complete order which is not total. This is due to the fact $\{0\}$ and $\{1\}$ are incomparable (neither is a subset of the other), but every collection of subsets has a least upper bound - namely its union.


Within a general partially ordered set $(A,R)$ we can talk about subsets of $A$ which are linearly ordered by $R$. Such subset is called a chain. Formally, $B\subseteq A$ is called a chain (in $R$) if:

For every $a,b\in B$ we have either $a=b$, $aRb$ or $bRa$.

An example of a chain in a non-linear order is $\bigg\lbrace A_i = \{n\in\mathbb N\mid n<i\}\bigg\rbrace$. This is a chain in the partial order of $\mathcal P(\mathbb N)$.


Claim: Let $(A,R)$ be a partially ordered set, then $R$ is a total order of $A$ if and only if every nonempty $B\subseteq A$ is a chain in $R$.

Proof: If $R$ is a total order, then every restriction to a subset of $A$ is still a total order; on the other hand if every subset is a chain, then in particular $A$ forms a chain and thus it is linearly ordered.

share|improve this answer
    
I wasn’t going to guess at a source language, but I share your suspicion that complete is a mistranslation of something that in this context should be translated total. –  Brian M. Scott Nov 20 '11 at 10:30
    
You're right, my book uses the term: סדר מלא That's what I'm asking about. –  Robert S. Barnes Nov 20 '11 at 10:34
    
@AsafKaragila: Actually my name is Robert, not George :-) –  Robert S. Barnes Nov 20 '11 at 10:41
    
@Robert: I thought so. This translates to total order and not complete order. –  Asaf Karagila Nov 20 '11 at 10:41
    
@AsafKaragila: So I guess the definition I wrote is OK :-) –  Robert S. Barnes Nov 20 '11 at 13:47
show 2 more comments

The definition of complete partial order (on $X$) I know is a partial order (on $X$) for which each subset (of $X$) has a supremum.

But then, there is no such thing as a correct definition.

share|improve this answer
    
This is not the definition in the cited Wikipedia article. It defines a directed complete partial order as one in which every directed subset has a supremum, and an $\omega$-complete partial order as one in which every non-decreasing $\omega$-chain has a supremum. –  Brian M. Scott Nov 20 '11 at 10:25
    
To my understanding that means the same thing. I maybe should have written out "supremum wrt this order". Is that not what "directed subset" means? –  Raphael Nov 20 '11 at 10:39
    
No, it’s not: a directed set is one in which every pair of elements has an upper bound. Consider the relation of equality on a $2$-element set $\{a,b\}$: it’s vacuously complete, since the order has no non-trivial directed sets, and $\{a,b\}$ is a subset with no supremum. –  Brian M. Scott Nov 20 '11 at 10:50
    
I still think that for an order (not preorder) this amounts to the same thing. If every subset has a supremum, you trivially get one for every pair. Conversely, if all pairs have a supremum, you can construct one for every subset. –  Raphael Nov 20 '11 at 17:10
    
Note that Asaf K. gives the same definition above as I do. So your issue is only the reference? –  Raphael Nov 20 '11 at 17:14
show 3 more comments

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.