Definition:Preordering
Definition
Let $\RR \subseteq S \times S$ be a relation on a set $S$.
Definition 1
$\RR$ is a preordering on $S$ if and only if:
| \((1)\) | $:$ | $\RR$ is reflexive | \(\ds \forall a \in S:\) | \(\ds a \mathrel \RR a \) | ||||
| \((2)\) | $:$ | $\RR$ is transitive | \(\ds \forall a, b, c \in S:\) | \(\ds a \mathrel \RR b \land b \mathrel \RR c \implies a \mathrel \RR c \) |
Definition 2
$\RR$ is a preordering on $S$ if and only if:
- $(1): \quad \RR \circ \RR = \RR$
- $(2): \quad \Delta_S \subseteq \RR$
where:
- $\circ$ denotes relation composition
- $\Delta_S$ denotes the diagonal relation on $S$.
Preordered Set
Let $S$ be a set.
Let $\precsim$ be a preordering on $S$.
Then the relational structure $\struct {S, \precsim}$ is called a preordered set.
Notation
Symbols used to denote a general preordering relation are usually variants on $\lesssim$, $\precsim$ or $\precapprox$.
A symbol for a preordering can be reversed, and the sense is likewise inverted:
- $a \precsim b \iff b \succsim a$
The notation $a \sim b$ is defined as:
- $a \sim b$ if and only if $a \precsim b$ and $b \precsim a$
The notation $a \prec b$ is defined as:
- $a \prec b$ if and only if $a \precsim b$ and $a \not \sim b$
Partial vs. Total Preorderings
Note that this definition of preordering does not demand that every pair of elements of $S$ is related by $\precsim$.
The way we have defined a preordering, they may be, or they may not be, depending on the context.
If it is the case that $\precsim$ is a connected relation, that is, that every pair of elements is related by $\precsim$, then $\precsim$ is called a total preordering.
If it is specifically not the case that $\precsim$ is connected, then $\precsim$ is called a partial preordering.
Also known as
A preordering is also known as a preorder.
Either name can be seen with a hyphen: pre-ordering and pre-order.
Some sources use the term quasiorder or quasi-order.
1964: Steven A. Gaal: Point Set Topology uses the term reflexive partial ordering, but as this can so easily be confused with the concept of a partial ordering this term is not recommended.
Examples
Finite Set Difference on Natural Numbers
Consider the relation $\RR$ on the powerset of the natural numbers:
- $\forall a, b \in \powerset \N: a \mathrel \RR b \iff a \setminus b \text { is finite}$
where $\setminus$ denotes set difference.
Then $\RR$ is a preordering on $\powerset \N$, but not an ordering on $\powerset \N$.
Also see
- Definition:Preorder Category, interpreting preorders as categories.
- Results about preorderings can be found here.