Definition:Partial Ordering

From ProofWiki
Jump to navigation Jump to search


Let $\struct {S, \preceq}$ be an ordered set.

Then the ordering $\preceq$ is a partial ordering on $S$ if and only if $\preceq$ is not connected.

That is, if and only if $\struct {S, \preceq}$ has at least one pair which is non-comparable:

$\exists x, y \in S: x \npreceq y \land y \npreceq x$

Also defined as

Some sources define a partial ordering to be the structure known on $\mathsf{Pr} \infty \mathsf{fWiki}$ as an ordering, that is, whose nature (partial or total) is unspecified.

Also known as

A partial ordering as defined here is sometimes referred to as a weak partial ordering, to distinguish it from a strict partial ordering


Arbitrary Example

Let $X = \set {x, y, z}$.

Let $\RR = \set {\tuple {x, x}, \tuple {x, y}, \tuple {x, z}, \tuple {y, y}, \tuple {z, z} }$.

Then $\RR$ is a partial ordering on $X$.

The strict partial ordering on $X$ corresponding to $\RR$ is its reflexive reduction:

$\RR^{\ne} = \set {\tuple {x, y}, \tuple {x, z} }$

Also see

  • Results about partial orderings can be found here.