2
$\begingroup$

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.

  • 0
    Not that I know of. You need to ask someone, or compare the definition of the terms to see whether they match. Moreover some terms have more than one name and it can get confusing at times.2011-11-28

2 Answers 2

5

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. 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.

  • 0
    @AsafKaragila: Really nice answer, thanks.2011-11-21
0

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.

  • 0
    I removed the reference, thanks.2011-11-21