53
$\begingroup$

I'm looking for a simple example of a partial order which is not a total order so that I can grasp the concept and the difference between the two.

An explanation of why the example is a partial order but not a total order would also be greatly appreciated.

$\endgroup$
80
$\begingroup$

Think about the subsets of $\{0,1\}$. They are: $\emptyset, \{0\}, \{1\}$, and $\{0,1\}$. Now, we can make these subsets into a partial order with $\subset$. For instance, $\emptyset \subset \{0\}$ and $\{1\} \subset \{0,1\}$. You can show this satisfies the axioms for a partial order:

$A \subset A \\ A \subset B, B \subset C \Rightarrow A \subset C \\ A \subset B, B \subset A \Rightarrow A = B$

But a total order $<$ drops the first axiom above and replaces it with the following:

$x < y$ or $y < x$ for all $x,y$

And we see that our example of subsets of $\{0,1\}$ does not satisfy this. For instance, neither $\{0\} \subset \{1\}$ nor $\{1\} \subset \{0\}$ are true. In a total order, we want to be able to compare any two elements. In a partial order, we don't.

$\endgroup$
  • 4
    $\begingroup$ Roughly speaking, a partial order doesn't require all elements of a set to be "comparable" in the way you described comparison. $\endgroup$ – nbro Dec 8 '17 at 13:06
12
$\begingroup$

Take your favourite set, which is $\,X:=\{a,b\}\,$ and then its power set

$$P(X):=\left\{\emptyset\,,\,X\,,\,\{a\}\,,\,\{b\}\right\}$$

Partial order $\,P(X)\,$ by set inclusion: $\,A\le B\iff A\subset B\;,\;\;A,B\in P(X)\,$

Check the above is a partial not total order.

$\endgroup$
  • 6
    $\begingroup$ My favourite set is $\varnothing$. It represents the emptiness of existence! :-) $\endgroup$ – Asaf Karagila Apr 20 '13 at 19:39
  • 6
    $\begingroup$ @AsafKaragila Do you mean existence of emptiness? $\endgroup$ – Git Gud Apr 20 '13 at 19:40
  • 3
    $\begingroup$ @GitGud: No.${}$ $\endgroup$ – Asaf Karagila Apr 20 '13 at 19:41
  • 1
    $\begingroup$ @Peter: While your point is valid, my comment was merely a result of recent semi-off topic comment exchanges with DonAntonio; and a remark that I usually don't like it when people tell me what is my favourite set. But it was meant as a tongue-in-cheek sort of comment... $\endgroup$ – Asaf Karagila Apr 20 '13 at 19:46
  • 1
    $\begingroup$ @DonAntonio Pero estás diciendo: "Elige tu conjunto favorito, que es..." Quiza "Elige tu conjunto favorito, el mio es..." tendría más sentido! +1 igualmente. $\endgroup$ – Pedro Tamaroff Apr 21 '13 at 17:11
10
$\begingroup$

There are some small differences in the way people define order (partial or total). Roughly speaking, they correspond to the difference between $\lt$ and $\le$. We opt for the $\le $ version. You can undoubtedly adapt the example below to the other version, if that's the one being used in your course.

Let our set be $\{1,2,3,6\}$. If $x$ and $y$ are elements of this set, we will say that $x\le y$ if $x$ divides $y$. So for example $2\le 6$, and $3\le 3$.

Note that it is not true that $2\le 3$, since $2$ does not divide $3$. Also, it is not true that $3\le 2$. The two objects $2$ and $3$ are incomparable with respect to the order just defined.

In a total order $\le$, any two objects $x$ and $y$ are comparable. Either $x\le y$ or $y\le x$ or both. ("Both" happens when $x=y$.)

For a non-mathematical example, let $A$ be the set of all people. If $x$ and $y$ are people, write $x\le y$ if $x=y$ or $x$ is an ancestor of $y$. This is a partial order. However, it is not total, since for example Obama is not an ancestor of Putin, and Putin is not an ancestor of Obama.

$\endgroup$
  • $\begingroup$ if in the same example, I take my set to be {2,3,7,11} then is it partially ordered? I see, no element is related to any other under this relation. $\endgroup$ – Aditi Narware Jan 8 '17 at 11:00
10
$\begingroup$

A total order is a partial order, but a partial order isn't necessarily a total order.

A totally ordered set requires that every element in the set is comparable: i.e. totality: it is always the case that for any two elements $a, b$ in a totally ordered set, $a \leq b$ or $b\leq a$, or both, e.g., when $a = b$. Here, as is often the case $\leq$ is used to represent some ordering relation.

So, for example, $R = \{(a, a), (b, b), (c, c), (d, d)\}$ is trivially, a partial order on $S = \{a, b, c, d\}$. But it is not the case that it is a total order, since we do not have that for every pair of elements in $S$, $(a, b)$ or $(b, a) \in R$.

$\endgroup$
5
$\begingroup$

Let's keep things simple. Ancestry is a partial order:

  • Transitive: An ancestor to your ancestor is also an ancestors to you.

  • Anti-symmetric: You can't be an ancestor of one of your own ancestors.

  • Partial: Not everyone is either a descendant or ancestor of yours.

$\endgroup$
  • 1
    $\begingroup$ Specifically, it's a strict partial order, since you don't count yourself among your ancestors. $\endgroup$ – stewSquared May 10 '19 at 16:42
3
$\begingroup$

Consider vectors in $\mathbb{R}^n$ partially ordered as follows: $x\succeq y$ iff $x_i\geq y_i$ for each $i=1,2,...n$. For instance, for $n=2$, $(2,2)\succeq(1,0)$ but $(10,1)\not\succeq(2,0)$ and $(2,0)\not\succeq(10,1)$.

$\endgroup$
3
$\begingroup$

I like this example.

The usual $\le$ relation on $\mathbb{N}$ can be defined by

$$a\le b\text{ if and only if there exists $x\in\mathbb{N}$ such that $b=a+x$}.$$

This relation is well known to be a total order.


A very similar relation can be defined using multiplication:

$$a\mid b\text{ if and only if there exists $x\in\mathbb{N}$ such that $b=ax$}.$$

Also $\mid$ is an order relation.

  1. reflexivity is obvious: $a=a\cdot 1$, so $a\mid a$;

  2. also transitivity is easy: if $a\mid b$ and $b\mid c$, then $b=ax$ and $c=by$ for some $x$ and $y$; therefore $c=a(xy)$ and $a\mid c$;

  3. antisymmetry is a bit more difficult, but not so much:

    Assume $a\mid b$ and $b\mid a$; then we have $b=ax$ and $a=by$ for some $x$ and $y$. Substituting yields

    $$a = axy$$

    and, if $a\ne0$, by cancellation we get $1=xy$ from which we derive $x=y=1$ and $a=b$. If instead $a=0$, from $b=ax$ we get again $a=b$.

The relation $\mid$ is not a total order, because $2\nmid 3$ and $3\nmid 2$.

With respect to $\mid$, $1$ is the minimum, because $1\mid b$ for any $b$. The maximum is $0$, because $a\mid 0$ for all $a$, since $0=a\cdot 0$.

The most important property of $\mid$ is that $(\mathbb{N},\mid)$ is a lattice: the infimum and supremum of $\{a,b\}$ are respectively the greatest common divisor and the least common multiple of $a$ and $b$.

$\endgroup$
  • $\begingroup$ Why do you use "if and only if" when defining a new binary relation? Shouldn't it be "if", in the "definition sense"? $\endgroup$ – Maxis Jaisi Jul 31 '17 at 7:52
  • $\begingroup$ @MaxisJaisi Halmos devised ”iff“ for this case, but then it was abused. Lack of previous conventions, contrary to what happens in courses or textbooks, made me (over)careful. $\endgroup$ – egreg Jul 31 '17 at 8:28
  • $\begingroup$ But your "if and only if" is distinct from the logical "if and only if", right? See math.stackexchange.com/questions/566565/… $\endgroup$ – Maxis Jaisi Jul 31 '17 at 9:18
  • $\begingroup$ @MaxisJaisi I don't understand what the problem is. I'm obviously doing definitions, so this is certainly not a “logical symbol”, but a “metalogical” one. How do you call it is a matter of conventions. $\endgroup$ – egreg Jul 31 '17 at 9:21
2
$\begingroup$

A simple example is a set with four elements $S = \{a, b, c, d\}$. We'll define a partial order so that $a$ is the smallest element, $d$ is the largest element, and $b$ and $c$ are intermediate elements that are incomparable with each other. The relation $R \subset S \times S$, where $(x,y) \in R \Leftrightarrow x \leq y$ is given by $$ R = \{(a,a), (a,b), (a,c), (a,d), (b,b), (b,d), (c,c), (c,d), (d,d)\}. $$ I'll leave it for you to check that this is really is a partial order. The important thing to note is that neither $b \leq c$ nor $c \leq b$ is true, so $R$ is not a total order.

EDIT: As A. Rex astutely points out in the comments, the simplest example would be to take just $S = \{b,c\}$ with the partial order relation $R = \{(b,b), (c,c)\}$. Then $b$ and $c$ are incomparable, so $R$ is not a total order.

$\endgroup$
  • 1
    $\begingroup$ Why do you need $a$ and $d$? Why not just have $b$ and $c$ be incomparable? $\endgroup$ – A. Rex Apr 23 '13 at 20:44
  • $\begingroup$ Fair point! Especially since I said I was giving the "simplest" example. :) $\endgroup$ – Michael Joyce Apr 23 '13 at 21:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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