Difference between revisions of "Partially ordered set"

Latest revision as of 20:01, 25 April 2009

A partially ordered set $P$ is a pair, $(S, \leq)$ of a set $S$ whose elements are called the elements or vertices of $P$ and an order relation $\leq$ which obeys the following rules:

Reflexivity: $x \leq x$ for all $x \in S$
Anti-symmetry: $x \leq y$ and $y \leq x$ if and only if $x = y$
Transitivity: if $x \leq y$ and $y \leq z$ then $x \leq z$

The name "partially ordered set" is often abbreviated poset.

Sometimes, we abuse notation and use the same letter $P$ for the poset itself and its set of vertices.

Simple examples

We don't verify that the properties stated above hold for these orderings -- a good exercise would be to prove that each of the three properties hold for the following examples.

The set of positive integers has a very natural ordering: we say $x \leq y$ if $y$ is bigger than $x$ , in the sense of further to the right on a number line (or further away from zero). This is the conventional ordering of the positive integers inherited from $\mathbb{Z}$ . It has the special property that any two elements are directly comparable -- note that this is not required of a poset in general. Those posets in which every two elements are comparable are known as totally ordered sets, or chains.

The Boolean lattice over a set $S$ is the poset $P = (\mathcal{P}(S), \leq)$ where $\mathcal{P}(S)$ is the power set (that is, the set of subsets) of $S$ and for $x, y \in \mathcal{P}(S)$ , $x \leq y$ if and only if $x \subseteq y$ . For instance, if $S = \{1, 2, 3\}$ then the poset $P$ has 8 elements among which we have the following relations:

$\emptyset$ is a minimal element of the poset; every other element is larger.
$S = \{1, 2, 3\}$ is a maximal element: every other element is smaller.
Among the other 6 elements, we have the relations $\{1\} \leq \{1, 2\}$ , $\{1\} \leq \{1, 3\}$ , $\{2\} \leq \{1, 2\}$ , $\{2\} \leq \{2, 3\}$ , $\{3\} \leq \{1, 3\}$ , and $\{3\} \leq \{2, 3\}$ , and no others.

There are alternative orderings of the positive integers: for example, one might take the poset $P = (\mathbb{Z}_{> 0}, \leq)$ where $n \leq m$ if and only if $n | m$ . Under this ordering, the positive integers still have a minimal element (1, which divides everything) but are no longer totally ordered. In particular, neither $2 | 3$ nor $3 | 2$ , so the elements 2 and 3 (and in general any pair of relatively prime integers not including 1) are incomparable.

A More Involved Example

Let $R$ be the set of well-formed formulas of Peano arithmetic. In other words, $S$ is the set of all arithmetic statements. We know that some of these statements are provably equivalent to each other. So, let $S$ be the set of equivalence classes of $R$ under the relation of provable equivalence. Let $\hat 0$ denote the set of statements which are provably false, i.e. whose negations are provable, and let $\hat 1$ denote the set of provable statements. By Godel's First Incompleteness Theorem, there exists at least one (and in fact infinitely many) formulas which do not fall into either of these two categories. So, let $P = (S, \leq)$ be the poset such that for $\mathbf{x, y} \in S$ , $\mathbf{x} \leq \mathbf{y}$ if and only if $\exists x \in \mathbf{x}, y \in \mathbf{y}$ such that the formula $x$ provably implies the formula $y$ . That this is in fact a poset follows immediately by the properties of logical implication. This poset has other interesting properties, as well.