Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
preorder [2007/03/30 20:40] vkuncak |
preorder [2007/03/30 20:52] vkuncak |
||
---|---|---|---|
Line 2: | Line 2: | ||
A (reflexive) preorder relation $\rho$ on set $A$ is a binary relation $r \subseteq A^2$ that is reflexive and transitive, that is, these two properties hold: | A (reflexive) preorder relation $\rho$ on set $A$ is a binary relation $r \subseteq A^2$ that is reflexive and transitive, that is, these two properties hold: | ||
+ | |||
* $x \mathop{\rho} x$ | * $x \mathop{\rho} x$ | ||
+ | |||
* $x \mathop{\rho} y\ \land\ y \mathop{\rho} z \ \rightarrow\ x \mathop{\rho} z$ | * $x \mathop{\rho} y\ \land\ y \mathop{\rho} z \ \rightarrow\ x \mathop{\rho} z$ | ||
- | |||
- | |||
===== Constructing a partial order from a preorder ===== | ===== Constructing a partial order from a preorder ===== | ||
- | Let $\rho$ be a preorder. Define relation $\sim$ by | + | Intuitively, preorder differs from partial order in that there are distinct elements that have same ordering properties with respect to other elements. For such elements we therefore have $x \rho y$ and $y \rho x$. By identifying these elements we obtain a partial order. |
+ | |||
+ | More precisely, let $\rho$ be a preorder. Define relation $\sim$ by | ||
\begin{equation*} | \begin{equation*} | ||
x \sim y \ \iff\ x \mathop{\rho} y\ \land\ y \mathop{\rho} x | x \sim y \ \iff\ x \mathop{\rho} y\ \land\ y \mathop{\rho} x |