Let A = a, b . The number of relations on A that are transitive is

The correct answer is Option (1) → 13

\(A \times A = \{(a, a), (b, b), (a, b), (b, a)\}\) has 4 pairs, so there are

    \(2^{4} = 16\) relations on A

It is easier to count the relations that are not transitive.

A chain needs two pairs \((x, y), (y, z)\). A chain using (a, a) or (b, b) only gives back the other pair of the chain, which is already present. So transitivity can fail only through the chains

    \((a, b), (b, a)\), which needs \((a, a)\)
    \((b, a), (a, b)\), which needs \((b, b)\)

So a relation is not transitive exactly when it contains both (a, b) and (b, a) and misses (a, a) or (b, b) or both:

    \(\{(a, b), (b, a)\}\)
    \(\{(a, b), (b, a), (a, a)\}\)
    \(\{(a, b), (b, a), (b, b)\}\)

    number of transitive relations \(= 16 - 3 = 13\)