How many true inclusion relations are there of the form A subset B, where A and B are subsets of a set S with n elements?

GATE 1987 · Discrete Mathematics · Relations · medium

Answer: The number of inclusion pairs (A, B) with A subset-or-equal B among subsets of an n-element set is 3^n. For strict inclusion (A proper subset B, A != B) the count is 3^n - 2^n.

1. Identify per-element options: For A to be a subset of B, for each x in S there are exactly 3 valid membership patterns: (1) x in neither A nor B, (2) x in B but not A, (3) x in both A and B. The pattern 'x in A but not B' is forbidden.
2. Apply the product rule: Since the choices for different elements are independent, multiply the 3 options per element over all n elements: total pairs (A,B) with A subset B = 3^n.