Question

Let R be a relation from A to B. Both sets are finite, with |A|=n and |B|=m. Define the complementary relation "R bar" as follows:

R bar={(a, b)|(a,b)∈R}

Calculate |R bar|.

Answer 1

By definition

$$\bar{R}=\left\{\left.(a,b)\right|(a,b)\in R\right\}$$

This means that the set $\bar{R}$ consists of ALL POSSIBLE pairs $\left\{\left.(x,y)\right| x\in A\,\,\,\text{and}\,\,\,y\in B\right\}$ .

Since the set $A$ consists of $|A|=n$ elements, and the set $B$ consists of $|B|=m$ elements, then the number of possible pairs is

$$\left|\bar{R}\right|=n\cdot m$$

since the elements for the pair $(x,y)$ are selected independently of each other.

ANSWER

$$\left|\bar{R}\right|=mn$$