(related to Proposition: Number of Relations on a Finite Set)

According to the definition of relation on a set \(V\) a relation \(R\) is any subset of the Cartesian product \(R\subseteq V\times V\).

According to the fundamental counting principle the cardinality of the Cartesian product is \(|V\times V|=n^2\), if \(V\) is finite a finite set with \(|V|=n\). In particular, the set \(V\times V\) is finite.

It follows from the number of subsets of a given finite set that

\[|R\subseteq V\times V|=2^{n^2}.\]

Thank you to the contributors under CC BY-SA 4.0!




  1. Schmidt G., Ströhlein T.: "Relationen und Graphen", Springer-Verlag, 1989
  2. Aigner, Martin: "Diskrete Mathematik", vieweg studium, 1993