Definition:Strict Ordering

From ProofWiki
Jump to navigation Jump to search

Definition

Definition 1

Let $\RR$ be a relation on a set $S$.

Then $\RR$ is a strict ordering (on $S$) if and only if the following two conditions hold:

\((1)\)   $:$   Asymmetry      \(\ds \forall a, b \in S:\)    \(\ds a \mathrel \RR b \)   \(\ds \implies \)   \(\ds \neg \paren {b \mathrel \RR a} \)             
\((2)\)   $:$   Transitivity      \(\ds \forall a, b, c \in S:\)    \(\ds \paren {a \mathrel \RR b} \land \paren {b \mathrel \RR c} \)   \(\ds \implies \)   \(\ds a \mathrel \RR c \)             


Definition 2

Let $\RR$ be a relation on a set $S$.

Then $\RR$ is a strict ordering (on $S$) if and only if the following two conditions hold:

\((1)\)   $:$   Antireflexivity      \(\ds \forall a \in S:\) \(\ds \neg \paren {a \mathrel \RR a} \)             
\((2)\)   $:$   Transitivity      \(\ds \forall a, b, c \in S:\) \(\ds \paren {a \mathrel \RR b} \land \paren {b \mathrel \RR c} \implies a \mathrel \RR c \)             


Notation

Symbols used to denote a general strict ordering are usually variants on $\prec$, $<$ and so on.

On $\mathsf{Pr} \infty \mathsf{fWiki}$, to denote a general strict ordering it is recommended to use $\prec$.

To denote the conventional strict ordering in the context of numbers, the symbol $<$ is to be used.


The symbol $\subset$ is deprecated on $\mathsf{Pr} \infty \mathsf{fWiki}$, as it is ambiguous in the literature, and this can be a cause of confusion and conflict.

Hence the symbols $\subsetneq$ and $\subsetneqq$ are used for the (proper) subset relation.


$a \prec b$

can be read as:

$a$ (strictly) precedes $b$.

Similarly:

$a \prec b$

can also be read as:

$b$ (strictly) succeeds $a$.


If, for two elements $a, b \in S$, it is not the case that $a \prec b$, then the symbols $a \nprec b$ and $b \nsucc a$ can be used.


Notation for Inverse Strict Ordering

To denote the dual of an strict ordering, the conventional technique is to reverse the symbol.

Thus:

$\succ$ denotes $\prec^{-1}$

and so:

$a \prec b \iff b \succ a$


Similarly for the standard symbol used to denote a strict ordering on numbers:

$>$ denotes $<^{-1}$

and so on.


Strict vs. Weak Ordering

Some sources define an ordering as we on $\mathsf{Pr} \infty \mathsf{fWiki}$ define a strict ordering.

Hence, in contrast with such a strict ordering, the term weak ordering is often used in this context to mean what we define on $\mathsf{Pr} \infty \mathsf{fWiki}$ as an ordering.

It is essential to be aware of the precise definitions used by whatever text is being studied so as not to fall into confusion.


Partial vs. Total Strict Ordering

It is not demanded of a strict ordering $\prec$, defined in its most general form on a set $S$, that every pair of elements of $S$ is related by $\prec$.

They may be, or they may not be, depending on the specific nature of both $S$ and $\prec$.

If it is the case that $\prec$ is a connected relation, that is, that every pair of distinct elements is related by $\prec$, then $\prec$ is called a strict total ordering.

If it is not the case that $\prec$ is connected, then $\prec$ is called a strict partial ordering.


Beware that some sources use the word partial for a strict ordering which may or may not be connected, while others insist on reserving the word partial for one which is specifically not connected.

It is wise to be certain of what is meant.


As a consequence, on $\mathsf{Pr} \infty \mathsf{fWiki}$ we resolve any ambiguity by reserving the terms for the objects in question as follows:

Strict ordering: a strict ordering whose nature (total or partial) is not specified
Strict partial ordering: a strict ordering which is specifically not total
Strict total ordering: a strict ordering which is specifically not partial.


Also known as

Some sources call this an antireflexive (partial) ordering.


Also see

  • Results about strict orderings can be found here.