Linear order

A relation on a set $A$ is called a linear order if: ?

• It is also a partial order.
• For all $a,b\in A$, either $(a,b)\in R$ or $(b,a)\in R$.

For example:

$\le$ on $\mathbb{N}$	$\ge$ on $\mathbb{Z}$
Graph of less than or equal to on natural numbers graph G { 2--1 1--0 } Link to original	Graph of greater than or equal to on integer numbers graph G { { m [label="-1"] } m--0 0--1 } Link to original

Example

Let $S$ be a set with more than one element. Show that $\subseteq$ is not a linear order on $P(S)$.

If $S$ has more than one element, then there are at least two different elements, say $x$ and $y$:

• $x\in S$ so $\{x\}\subseteq S$ and so $\{x\}\in P(S)$
• $y\in S$ so $\{y\}\subseteq S$ and so $\{y\}\in P(S)$
• Neither $\{x\}\subseteq \{y\}$ or $\{y\}\subseteq \{x\}$ hold as $x\ne y$.

So $\{x\}$ and $\{y\}$ are two elements in $P(S)$ such that either $\{x\}\subseteq \{y\}$ or $\{y\}\subseteq \{x\}$, so so $\subseteq$ is not a linear order. (It does not form a line.)

graph G {
	{
		a [label="P(s)"]
		x [label="{x}"]
		y [label="{y}"]
	}
	
	x,y--a
}