Definition:Preordering

From ProofWiki
Jump to: navigation, search

Definition

Let $\mathcal R \subseteq S \times S$ be a relation on a set $S$.


Definition 1

$\mathcal R$ is a preordering on $S$ if and only if:

\((1)\)   $:$   $\mathcal R$ is reflexive      \(\displaystyle \forall a \in S:\) \(\displaystyle a \mathop {\mathcal R} a \)             
\((2)\)   $:$   $\mathcal R$ is transitive      \(\displaystyle \forall a, b, c \in S:\) \(\displaystyle a \mathop {\mathcal R} b \land b \mathop {\mathcal R} c \implies a \mathop {\mathcal R} c \)             


Definition 2

$\mathcal R$ is a preordering on $S$ if and only if:

$(1): \quad \mathcal R \circ \mathcal R = \mathcal R$
$(2): \quad \Delta_S \subseteq \mathcal R$

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 $\left({S, \precsim}\right)$ 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, i.e. that every pair of elements is related by $\precsim$, then $\precsim$ is called a total preordering.

If it is 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.


Also see

  • Results about preorderings can be found here.