# Definition of Total Partial Ordering

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.

-
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
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
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
@Robert: קבוצה is a set, חבורה is a group. The terms are not interchangeable. – Asaf Karagila Nov 20 '11 at 10:44

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.

-
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

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.

-
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