Classificaton of Binary Relations

🅟 Feb 21, 2026

  🅤 Mar 15, 2026

DEF-RCL.

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

Property Condition
Reflexive \(x\sim x\)
Irreflexive / Strict \(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\neq y\rimp(x\sim y\lor y\sim x)\)
Strongly connected \(x\sim y\lor y\sim x\)
Left-unique / One-to-many / Injective \((x\sim z\land y\sim z)\rimp x=y\)
Right-unique / Many-to-one / Functional \((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.

DEF-RCL-T.

Let $\sim$ be a binary relation on $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 / onto / surjective if $\ran{\sim}=Y$, i.e.

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

PROP-RCL-ITA.

Irreflexivity and transitivity imply asymmetry.

Proof.Let $\sim$ be an irreflexive and transitive relation on $X$. Let $x$, $y\in X$ such that $x\sim y$. If $y\sim x$, then $x\sim x$ by transitivity, contrary to irreflexivity.