# 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 \text{ and } A \subset B, \text{ and } 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.

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! :-) Apr 20, 2013 at 19:39
• @AsafKaragila Do you mean existence of emptiness? Apr 20, 2013 at 19:40
• @GitGud: No.${}$ Apr 20, 2013 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... Apr 20, 2013 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
Apr 21, 2013 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. Jan 8, 2017 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. May 10, 2019 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"? Jul 31, 2017 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. Jul 31, 2017 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/… Jul 31, 2017 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. Jul 31, 2017 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? Apr 23, 2013 at 20:44
• Fair point! Especially since I said I was giving the "simplest" example. :) Apr 23, 2013 at 21:33

Let $$X$$ and $$Y$$ be two sets, and let $$F$$ equal the set of functions $$f$$ such that $$\DeclareMathOperator{\dom}{dom}\dom(f)\subseteq X$$ and $$\dom(g)\subseteq Y$$. For any two functions $$f$$ and $$g$$ in $$F$$, write $$f\le g$$ if $$\dom(f)\subseteq\dom(g)$$ and $$f(x)=g(x)$$ for all $$x\in\dom(f)$$, i.e. if $$f$$ equals the restriction of $$g$$ to the domain of $$f$$. Then, $$\le$$ is a partial order on $$F$$; it is a total order if and only if $$F$$ is empty or is a singleton.

In fact, if we define a function from $$A$$ to $$B$$ as a subset of $$A\times B$$ satisfying certain conditions, then we recognise that $$f\le g$$ if and only if $$f\subseteq g$$. Thus, this is a special case of the partial order given by inclusion mentioned in other answers.

This example is taken from Paul Hamlos' Naive Set Theory, chapter 14, page 55.