Definition:Rank Function for Relation
Definition
Let $\struct {S, \RR}$ be a relational structure.
Let $\struct {T, \prec}$ be a strictly well-ordered set.
Let $\operatorname {rk}: S \to T$ be a mapping such that:
- $\forall x, y \in S: \paren {x \ne y \text { and } \tuple {x, y} \in \RR} \implies \map {\operatorname {rk} } x \prec \map {\operatorname {rk} } y$
$\operatorname {rk}$ is known as a rank function for $\RR$.
Examples
Arbitrary Example $1$
Let $X = \set {x, y, z}$.
Let $\RR$ be the relation on $X$ defined as:
- $\RR = \set {\tuple {x, x}, \tuple {x, y}, \tuple {x, z}, \tuple {y, y}, \tuple {z, z} }$.
Let the mapping $\operatorname {rk}_0: X \to \N$ be defined as:
\(\ds \map {\operatorname {rk}_0} x\) | \(=\) | \(\ds 0\) | ||||||||||||
\(\ds \map {\operatorname {rk}_0} y\) | \(=\) | \(\ds 1\) | ||||||||||||
\(\ds \map {\operatorname {rk}_0} z\) | \(=\) | \(\ds 1\) |
Then $\operatorname {rk}_0$ is a rank function for $\RR$.
Sum of Powers of Prime Factors
Consider the relational structure $\struct {\Z_{>0}, \divides}$ formed from the strictly positive integers $\Z_{>0}$ under the divisor relation $\divides$.
Let $\operatorname {rk}_1: \Z_{<0} \to \N$ defined as:
- $\forall n \in \Z_{<0}: \map {\operatorname {rk}_1} n = \ds \sum_{k \mathop \in \Z_{>0} } \map {i_k} n$
where:
- $\ds n = \prod_{k \mathop \in \Z_{>0} } {p_k}^{\map {i_k} n}$
is the prime decomposition of $n$.
That is, $\operatorname {rk}_1$ is the sum of the exponents of the prime divisors of $n$ in the prime decomposition of $n$.
Then $\operatorname {rk}_1$ is a rank function for $\RR$.
Also see
- Results about rank functions can be found here.
Sources
- 1996: Winfried Just and Martin Weese: Discovering Modern Set Theory. I: The Basics ... (previous) ... (next): Part $1$: Not Entirely Naive Set Theory: Chapter $2$: Partial Order Relations