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
    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...2011-11-20
  • 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](http://en.wikipedia.org/wiki/Total_order).2011-11-20
  • 0
    So there is a relation property called totality?2011-11-20
  • 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.2011-11-20
  • 0
    Yes. It means that for every $a,b \in A$ at least one of $aRb$ and $bRa$ holds.2011-11-20
  • 1
    @Robert: קבוצה is a *set*, חבורה is a *group*. The terms are **not** interchangeable.2011-11-20
  • 0
    @AsafKaragila: Thanks for the clarification. Is there someplace where I can find an index of translations of Hebrew math terms to English?2011-11-28
  • 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
    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*.2011-11-20
  • 0
    You're right, my book uses the term: סדר מלא That's what I'm asking about.2011-11-20
  • 0
    @AsafKaragila: Actually my name is Robert, not George :-)2011-11-20
  • 0
    @Robert: I thought so. This translates to *total order* and not *complete order*.2011-11-20
  • 0
    @AsafKaragila: So I guess the definition I wrote is OK :-)2011-11-20
  • 0
    @Robert: Yes, it is okay (although wasteful, as I remarked). I wrote that "between the lines" here.2011-11-20
  • 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
    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.2011-11-20
  • 0
    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?2011-11-20
  • 0
    No, it’s not: a [directed set](http://en.wikipedia.org/wiki/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.2011-11-20
  • 0
    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.2011-11-20
  • 0
    Note that Asaf K. gives the same definition above as I do. So your issue is only the reference?2011-11-20
  • 0
    It clearly does not amount to the same thing: see the example that I gave in my previous comment. There is a difference between *all subsets have a supremum* and *all subsets in which every two elements have an upper bound have a supremum*; the first implies the second, but the second does not imply the first, as the partial order may have pairs of elements with no upper bound.2011-11-20
  • 0
    Yes, I was objecting to citing Wikipedia to support your definition of *complete*, because it doesn’t. I’ve no strong feelings either way about the definition itself. I simply wouldn’t use the term in this connection, because it’s ambiguous; I’d specify just what notion of completeness I had in mind. If I *did* happen to use it, I’d probably mean that every set had both a supremum *and* an infimum.2011-11-20
  • 0
    I removed the reference, thanks.2011-11-21