Definition:Partial Ordering

From ProofWiki
Jump to navigation Jump to search

Definition

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


Examples

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


Parallel Lines

Let $S$ denote the set of all infinite straight lines embedded in a cartesian plane.

Let $\LL$ denote the relation on $S$ defined as:

$a \mathrel \LL b$ if and only if:
$a$ is parallel $b$
if $a$ is not parallel to the $y$-axis, then coincides with or lies below $b$
but if $b$ is parallel to the $y$-axis, then $a$ coincides with or lies to the right of $b$


Its dual $\LL^{-1}$ is defined as:

$a \mathrel {\LL^{-1} } b$ if and only if:
$a$ is parallel $b$
if $a$ is not parallel to the $y$-axis, then coincides with or lies above $b$
but if $b$ is parallel to the $y$-axis, then $a$ coincides with or lies to the left of $b$.


Then $\LL$ and $\LL^{-1}$ are partial orderings on $S$.


Ancestry

Let $P$ denote the set of all people who have ever lived.

Let $\DD$ denote the relation on $P$ defined as:

$a \mathrel \DD b$ if and only if $a$ is a descendant of or the same person as $b$.


Its dual $\DD^{-1}$ is defined as:

$a \mathrel {\DD^{-1} } b$ if and only if $a$ is an ancestor of or the same person as $b$.


Then $\DD$ and $\DD^{-1}$ are partial orderings on $P$.


Also see

  • Results about partial orderings can be found here.


Internationalization

Partial Ordering is translated:

In German : Halbordnung


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Partial_Ordering&oldid=619828"