|
|
|
Viewing Version
13
of
'pre-order'
|
[ view 'pre-order'
|
back to history
]
| Title of object: |
pre-order |
| Canonical Name: |
QuasiOrder |
| Type: |
Definition |
| Created on: |
2002-10-01 09:54:10 |
| Modified on: |
2006-09-16 04:05:28 |
| Classification: |
msc:06A99 |
| Defines: |
pre-ordered, preordered, semi-ordered, semiordered, quasi-ordered, quasiordered |
| Synonyms: |
pre-order=pre-ordering
pre-order=preorder
pre-order=preordering
pre-order=quasi-order
pre-order=quasi-ordering
pre-order=quasiorder
pre-order=quasiordering
pre-order=semi-order
pre-order=semi-ordering
pre-order=semiorder
pre-order=semiordering |
Revision comment (for changes between this and next version):
Preamble:
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
%\def\lesssim{\preceq} % this was used to work around a bug, but shouldn't be needed now
|
Content:
\PMlinkescapeword{satisfy}
\section*{Definition}
A \emph{pre-order} on a set $S$ is a relation $\lesssim$ on $S$ satisfying the following two axioms:
\begin{description}
\item reflexivity: $s \lesssim s$ for all $s \in S$, and
\item transitivity: If $s \lesssim t$ and $t \lesssim u$, then $s \lesssim u$; for all $s,t,u \in S$.
\end{description}
\section*{Partial order induced by a pre-order}
Given such a relation, define a new relation $s\sim t$ on $S$ by
\[
s\sim t \mathrm{ if and only if } s\lesssim t \mathrm{ and } t \lesssim s.
\]
Then $\sim$ is an equivalence relation on $S$, and $\lesssim$ induces a partial order $\leq$ on the set $S/\sim$ of equivalence classes of $\sim$ defined by
\[
[s] \leq [t] \mathrm{ if and only if } s \lesssim t,
\]
where $[s]$ and $[t]$ denote the equivalence classes of $s$ and $t$. In particular, $\leq$ does satisfy antisymmetry, whereas $\lesssim$ may not.
\section*{Pre-orders as categories}
A pre-order $\lesssim$ on a set $S$ can be considered as a small category, in the which the objects are the elements of $S$ and there is a unique morphism from $x$ to $y$ if $x\lesssim y$ (and none otherwise).
|
|
|
|
|
|
