Relations - 4

Properties of Relations on a Set

If $R$ is a binary relation then we write $xRy$ whenever $(x,y)\in R$. The predicate $xRy$ is read as $x$ is $R$-related to $y$.

This is similar to the notation $a\subseteq b$ or $a\leq b$.

Consider relations $R,S$ and $L$ on the set of all strings:

$R$-lexicographic ordering.
- This is alphabetic ordering.
$uSv$ if, and only if, $u$ is a sub-string of $v$.
- $\text{an}S\text{ana},\ \text{ana}S\text{banana}$.
- $uSv,\ vSw\Rightarrow uSw$.
  - This means that for any ordering such as $u$ then $v$ the ordering of $u$ and $w$ is also true provided that we know that $v<w$.
$uLv$ if, and only if, $\text{len}(u)\leq \text{len}(v)$.

For any of these relations:

\[\forall u,v \text{ if } uRv \text{ and } vRu\Rightarrow u=v\]

This means if the relation works both ways then they are equal in terms of the ordering.