# Example of Partial Order that's not a Total Order and why?

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.

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.

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

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.

• My favourite set is $\varnothing$. It represents the emptiness of existence! :-) – Asaf Karagila Apr 20 '13 at 19:39
• @AsafKaragila Do you mean existence of emptiness? – Git Gud Apr 20 '13 at 19:40
• @GitGud: No.${}$ – Asaf Karagila Apr 20 '13 at 19:41
• @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... – Asaf Karagila Apr 20 '13 at 19:46
• @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. – Pedro Tamaroff Apr 21 '13 at 17:11

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.

• 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. – Aditi Narware Jan 8 '17 at 11:00

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

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.

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

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

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

• Why do you use "if and only if" when defining a new binary relation? Shouldn't it be "if", in the "definition sense"? – Maxis Jaisi Jul 31 '17 at 7:52
• @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. – egreg Jul 31 '17 at 8:28
• But your "if and only if" is distinct from the logical "if and only if", right? See math.stackexchange.com/questions/566565/… – Maxis Jaisi Jul 31 '17 at 9:18
• @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. – egreg Jul 31 '17 at 9:21

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.

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