Classificaton of Binary Relations

Definition 1. Let $\sim$ be a binary relation on a set $X$. We define the following properties of $\sim$:

Property	Condition
Reflexive	\(x \sim x\)
Irreflexive	\(x \not\sim x\)
Symmetric	\(x \sim y \,\rimp\, y\sim x\)
Antisymmetric	\((x \sim y \,\land\, y \sim x) \,\rimp\, x = y\)
Asymmetric	\(x \sim y \,\rimp\, y \not\sim x\)
Transitive	\((x \sim y \,\land\, y\sim z) \,\rimp\, x \sim z\)
Connected	\(x \sim y \,\lor\, y \sim x \,\lor\, x = y\)
Strongly connected	\(x \sim y \,\lor\, y \sim x\)
Left-unique	\((x \,\sim\, z \,\land\, y \sim z) \,\rimp\, x = y\)
Right-unique	\((z \sim x \,\land\, z \sim y) \,\rimp\, x = y\)

The statements in the Condition column are meant to hold either for all $x \in X$; all $x$, $y \in X$; or all $x$, $y$, $z \in X$, accordingly.

Definition 2. Let $\sim$ be a binary relation on two sets $X$ and $Y$.

• $\sim$ is left-total if $\dom{\sim} = X$, i.e.

  \[\forall x \in X \, \exists y \in Y : x \sim y.\]

• $\sim$ is right-total if $\im{\sim} = Y$, i.e.

  \[\forall y \in Y \, \exists x \in X : x \sim y.\]