9.11: Summary of Relational Properties

Last updated
Save as PDF

Page ID: 48354

Eric Lehman, F. Thomson Leighton, & Alberty R. Meyer
Google and Massachusetts Institute of Technology via MIT OpenCourseWare

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

A relation \(R : A \rightarrow A\) is the same as a digraph with vertices \(A\).

Reflexivity \(R\) is reflexive when

\[\nonumber \forall x \in A. x R x.\]

Every vertex in \(R\) has a self-loop.

Irreflexivity \(R\) is irreflexive when

\[\nonumber \text{NOT}[\exists x \in A. x R x].\]

There are no self-loops in \(R\).

Symmetry \(R\) is symmetric when

\[\nonumber \forall x,y \in A. x R y { IMPLIES } y R x.\]

If there is an edge from \(x\) to \(y\) in \(R\), then there is an edge back from \(y\) to \(x\) as well.

Asymmetry \(R\) is asymmetric when

\[\nonumber \forall x,y \in A. x R y { IMPLIES NOT } y R x.\]

There is at most one directed edge between any two vertices in \(R\), and there are no self-loops.

Antisymmetry R is antisymmetric when

\[\nonumber \forall x \neq y \in A. x R y { IMPLIES NOT } y R x.\]

Equivalently,

\[\nonumber \forall x,y \in A. (x R y { AND } y R x) \text{ IMPLIES } x = y.\]

There is at most one directed edge between any two distinct vertices, but there may be self-loops.

Transitivity \(R\) is transitive when

\[\nonumber \forall x,y,z \in A. (x R y { AND } y R z) \text{ IMPLIES } x R z.\]

If there is a positive length path from \(u\) to \(v\), then there is an edge from \(u\) to \(v\).

Linear \(R\) is linear when

\[\nonumber \forall x \neq y \in A. (x R y { OR } y R x)\]

Given any two vertices in \(R\), there is an edge in one direction or the other between them.

For any finite, nonempty set of vertices of \(R\), there is a directed path going through exactly these vertices.

Strict Partial Order \(R\) is a strict partial order iff \(R\) is transitive and irreflexive iff \(R\) is transitive and asymmetric iff it is the positive length walk relation of a DAG.

Weak Partial Order \(R\) is a weak partial order iff \(R\) is transitive and anti-symmetric and reflexive iff \(R\) is the walk relation of a DAG.

Equivalence Relation \(R\) is an equivalence relation iff \(R\) is reflexive, symmetric and transitive iff \(R\) equals the in-the-same-block-relation for some partition of domain(\(R\)).