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
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (210)
Orphanage
Unclass'd (1)
Unproven (472)
Corrections (37)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
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 MSC: 06A99 (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)