Binary Relation on a Set

Let A be a non-empty set. Every SUBSET of $A\times A$ is called a BINARY RELATION on A.

ILLUSTRATIVE EXAMPLES: (1) Let $A=\{1,2,3\}$ and $R=\{(1,2),(2,2),(3,1),(3,2)\}$. Since $A\times A = \{(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)\}$ and $R\subset A\times A$, R is a binary relation on A. (2) Let N be the natural numbers and $R=\{(a,b)/a,b\in N \text{ and } 2a+b=10\}$. Since $R\subset N\times N$, R is a binary relation on N; explicitly $R=\{(1,8),(2,6),(3,4),(4,2)\}$, giving $\text{domain}(R)=\{1,2,3,4\}$ and (co-domain restricted to what's used, i.e.) range$(R)=\{2,4,6,8\}$. (3) If $R'$ on $Z\times Z$ is defined by 'a$R'$b if $(a+b)$ is even' and R is defined by 'a$R$b if $(a-b)$ is even', these two definitions actually give the SAME relation — the underlying subset is $\{(a,b)/a,b \text{ both even, or both odd}\}$.

Two special extreme cases: (i) since $\phi \subset A\times A$, the EMPTY set $\phi$ is itself always a valid relation on A, called the EMPTY or VOID relation. (ii) since $A\times A \subset A\times A$ (trivially), the whole of $A\times A$ is itself always a valid relation on A, called the UNIVERSAL relation on A, i.e. $R=A\times A$. For example, if $A=\{2,4,6\}$, then $R=A\times A=\{(2,2),(2,4),(2,6),(4,2),(4,4),(4,6),(6,2),(6,4),(6,6)\}$ is the universal relation on A. …