PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: High Entry average rating: No information on entry rating
pre-order (Definition)

Definition

A pre-order on a set $ S$ is a relation $ \lesssim$ on $ S$ satisfying the following two axioms:

reflexivity: $ s \lesssim s$ for all $ s \in S$, and
transitivity: If $ s \lesssim t$ and $ t \lesssim u$, then $ s \lesssim u$; for all $ s,t,u \in S$.

Partial order induced by a pre-order

Given such a relation, define a new relation $ s\sim t$ on $ S$ by

$\displaystyle s\sim t \hbox{ if and only if } s\lesssim t \hbox{ 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
$\displaystyle [s] \leq [t] \hbox{ 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.

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).



"pre-order" is owned by yark. [ full author list (2) | owner history (1) ]
(view preamble)

View style:

See Also: well quasi ordering, partial order

Other names:  pre-ordering, preorder, preordering, quasi-order, quasi-ordering, quasiorder, quasiordering, semi-order, semi-ordering, semiorder, semiordering
Also defines:  pre-ordered, preordered, semi-ordered, semiordered, quasi-ordered, quasiordered

Attachments:
Quasi-order is not defined uniformly (Definition) by boute
preorder as a category (Example) by CWoo
Log in to rate this entry.
(view current ratings)

Cross-references: morphism, objects, small category, antisymmetry, equivalence classes, partial order, equivalence relation, transitivity, reflexivity, axioms, relation
There are 14 references to this entry.

This is version 14 of pre-order, born on 2002-10-01, modified 2006-09-16.
Object id is 3500, canonical name is QuasiOrder.
Accessed 13183 times total.

Classification:
AMS MSC06A99 (Order, lattices, ordered algebraic structures :: Ordered sets :: Miscellaneous)

Pending Errata and Addenda
None.
[ View all 5 ]
Discussion
Style: Expand: Order:
forum policy
quasi-order entry by mathcam on 2005-11-12 11:22:16
Does anyone know why the entry (url below) is empty to me?

http://planetmath.org/encyclopedia/QuasiOrder.html

Might it have something to do with the fact that it's name in the encyclopedia looks like quasi\-order, with a slash in it?

The author says he can see it just fine.

Cam
[ reply | up ]

Interact
post | correct | update request | add derivation | add example | add (any)