\[x\ R\ y = (x, y) \in R\]

\(x\) is domain, \(y\) is range

S = {(1, a), (2, b), (3, c)}

domain(S) = {1, 2, 3}

codomain(S) = {a, b, c}

Difference between codomain and range see: https://www.mathsisfun.com/sets/domain-range-codomain.html

Maximum of number of relations on set A

\[2^{|\mathcal{P}(A)|} = 2^{|A|^{2}}\]

Number of Relations

S = {1, 2, 3,…n}

Relation #
Reflexive \(2^{n^2-n}\)
Irreflexive \(2^{n^2-n}\)
Symmetric \(2^{\frac{n^2+n}{2}}\)
Antisymmetric* \(2^{n} \times 3^{\frac{n^2-n}{2}}\)
Asymmetric* \(3^{\frac{n^2-n}{2}}\)
transitive no easy way to calculate


* 3 means every pair of non-diagonal element have three choices (0,1), (1,0), (0,0)