Relations

Overview

A relation $R$ is a set of ordered pairs. The domain of $R$ ($\text{dom}R$), the range of $R$ ($\text{ran}R$), and the field of $R$ ($\text{fld}R$) are defined as:

• $x\in \text{dom}R⟺\mathrm{\exists }y,⟨x,y⟩\in R$
• $x\in \text{ran}R⟺\mathrm{\exists }t,⟨t,x⟩\in R$
• $\text{fld}R=\text{dom}R\cup \text{ran}R$

An $n$-ary relation on $A$ is a set of $n$-tuples with each components in $A$. Keep in mind though, a unary ($1$-ary) relation on $A$ is just a subset of $A$ and may not be a relation at all.

A set $A$ is single-valued iff for each $x$ in $\text{dom}A$, there is only one $y$ such that $xAy$. A set $A$ is single-rooted iff for each $y\in \text{ran}A$, there is only one $x$ such that $xAy$.

Reflexivity

A relation $R$ is reflexive on $A$ iff $xRx$ for all $x\in A$. In relational algebra, we define $R$ to be reflexive on $A$ iff $I_A\subseteq R$.

Irreflexivity

A relation $R$ is irreflexive on $A$ iff $\mathrm{\neg }xRx$ for all $x\in A$. That is, it is never the case that $xRx$.

Symmetry

A relation $R$ is symmetric iff whenever $xRy$, then $yRx$. In relational algebra, we define $R$ to be symmetric iff $R^{-1}\subseteq R$.

Antisymmetry

A relation $R$ is antisymmetric iff whenever $x\ne y$ and $xRy$, then $\mathrm{\neg }yRx$.

Asymmetry

A relation $R$ is asymmetric iff whenever $xRy$, then $\mathrm{\neg }yRx$.

Transitivity

A relation $R$ is transitive iff whenever $xRy$ and $yRz$, then $xRz$. In relational algebra, we define $R$ to be transitive iff $R\circ R\subseteq R$.

Connected

A binary relation $R$ on set $A$ is said to be connected if for any distinct $x,y\in A$, either $xRy$ or $yRx$. The relation is strongly connected if for all $x,y\in A$, either $xRy$ or $yRx$.

Trichotomy

A binary relation $R$ on $A$ is trichotomous if for all $x,y\in A$, exactly one of the following holds:

Inverses

Let $F$ be an arbitrary set. The inverse of $F$ is the set $F^{-1}=\{⟨u,v⟩\mid vFu\}$.

Compositions

Let $F$ and $G$ be arbitrary sets. The composition of $F$ and $G$ is the set

Composition of relations is associative.

Restrictions

Let $F$ and $A$ be arbitrary sets. The restriction of $F$ to $A$ is the set

Extensions

A relation $F$ is an extension of another, say $f$, if:

1. $\text{dom}(f)\subseteq \text{dom}(F)$;
2. $F\upharpoonright \text{dom}(f)=f$.

Images

Let $F$ and $A$ be sets. Then the image of $F$ under $A$ is $F[[A]]=\{v\mid \mathrm{\exists }u\in A,uFv\}$.

Inverse Images

Let $F$ and $A$ be sets. Then the inverse image of $F$ under $A$ is

Properties

The following hold for any sets $F$, $A$, $B$, and $\mathcal{A}$:

• The image of unions is the union of the images:
  • $F[[\bigcup \mathcal{A}]]=\bigcup \{F[[A]]\mid A\in \mathcal{A}\}$
• The image of intersections is a subset of the intersection of images:
  • $F[[\bigcap \mathcal{A}]]\subseteq \bigcap \{F[[A]]\mid A\in \mathcal{A}\}$ for $\mathcal{A}\ne \varnothing$
  • Equality holds if $F$ is single-rooted.
• The image of a difference includes the difference of the images:
  • $F[[A]]-F[[B]]\subseteq F[[A-B]]$
  • Equality holds if $F$ is single-rooted.