Cartesian Product, Relation, Inverse and Complement MCQs: 10 Solved Questions

The notation is short, but one missing ordered pair changes a relation, its inverse, its complement and every later composition. Counting adds another trap: n^2 counts possible pairs in A x A, while 2^(n^2) counts relations on A. Before each answer, write one decisive line: the product universe, the pair reversal, the removed complement pairs or the matched middle element. If ordered pairs need a refresher, Set Theory and Relations for GATE: Closures and Posets establishes the definitions and relation properties used here.

Cartesian product, inverse and complement: a worked reference

For sets A and B, A x B contains each ordered pair (a,b) with a in A and b in B. A relation from A to B is any subset of that product. The inverse R^-1 reverses every pair; the complement removes R from the declared universe, normally (A x B) \ R.

Let A={1,3} and B={x,y}. Then

A x B={(1,x),(1,y),(3,x),(3,y)}.

For R={(1,x),(3,y)}, reversing coordinates gives R^-1={(x,1),(y,3)} from B to A. Removing R from A x B gives R^c={(1,y),(3,x)}. Since |A x B|=4, there are 2^4=16 possible relations.

Audit in this order: write the product universe, mark R, reverse coordinates only for an inverse, remove marked pairs only for a complement, and match the middle element in a composition.

Cartesian-product and relation-count MCQs 1-4

Question 1

Let 𝑈 = {1,2, … , 𝑛}. Let 𝐴 = {(𝑥, 𝑋)|𝑥 ∈ 𝑋, 𝑋 ⊆ 𝑈}. Consider the following two statements on |𝐴|. I. $\mid A \mid = n2^{n-1}$ II. $\mid A \mid = \Sigma_{k=1}^{n} k \begin{pmatrix} n \\ k \end{pmatrix}$ Which of the above statements is/are TRUE?

• A. Only I

• B. Only II

• C. Both I and II

• D. Neither I nor II

Correct answer: C. Both I and II.

Counting by x gives n choices times 2^(n-1) containing subsets, so |A|=n2^(n-1); counting by subset size gives the stated sum. For n=3, they are 3*4=12 and 1*C(3,1)+2*C(3,2)+3*C(3,3)=3+6+3=12.

Question 2

Let A be a finite set of size n. The number of elements in the power set of A × A is:

• A. 2(2ⁿ)

• B. 2^(n²)

• C. 2n

• D. None of the above

Correct answer: B. 2^(n²).

The Cartesian product A x A has n^2 pairs, so its power set contains 2^(n^2) subsets. For A={a,b}, four pairs give 2^4=16 subsets.

Question 3

The number of binary relations on a set with n elements is:

• A. n²

• B. 2^n

• C. 2^(n²)

• D. None of the above

Correct answer: C. 2^(n²).

A relation is any subset of the n^2 pairs in A x A, so independent include-or-exclude choices give 2^(n^2). Here n^2 counts pairs, while 2^n counts subsets of A itself.

Question 4

For a set A containing n elements, how many binary relations can be defined on A?

• A. n²

• B. 2^n

• C. 2^(n²)

• D. None of the above

Correct answer: C. 2^(n²).

For A={p,q}, the product is {(p,p),(p,q),(q,p),(q,q)}, whose 2^4=16 subsets are relations. In general, n^2 available pairs give 2^(n^2) relations.

For union, symmetric difference, set identities and broader Cartesian-product practice, use Set Operations & Cartesian Product MCQs: 12 Solved Questions with Explanations. The next four questions switch to relation set operations, complement and composition; the opening reference distinguishes inverse from complement.

Relation operations and complement MCQs 5-6

Question 5

Match List I with List II. Let R1 = {(1,1),(2,2),(3,3)} and R2 = {(1,1),(1,2),(1,3),(1,4)}. List I A. R1 ∪ R2 B. R1 − R2 C. R1 ∩ R2 D. R2 − R1 List II I. {(1,1),(1,2),(1,3),(1,4),(2,2),(3,3)} II. {(1,1)} III. {(1,2),(1,3),(1,4)} IV. {(2,2),(3,3)} Choose the correct matching.

• A. A-I, B-II, C-IV, D-III

• B. A-I, B-IV, C-III, D-II

• C. A-I, B-III, C-II, D-IV

• D. A-I, B-IV, C-II, D-III

Correct answer: D. A-I, B-IV, C-II, D-III.

The common pair (1,1) makes the intersection II; removing it leaves IV from R1 and III from R2. The union is I, so the match is A-I, B-IV, C-II, D-III.

Question 6

For sets X = {1, 3, 5}, Y = {7, 9} and relation R = {(1, 7), (1, 9), (3, 9), (5, 9)}, the complement of R is:

• A. { (3, 7), (5, 7) }

• B. { (3, 9), (3, 5) }

• C. { (7, 3), (7, 5) }

• D. { (7, 1), (9, 1), (9, 3), (9, 5) }

Correct answer: A. { (3, 7), (5, 7) }.

From X x Y={(1,7),(1,9),(3,7),(3,9),(5,7),(5,9)}, removing R leaves {(3,7),(5,7)}. Options C and D reverse coordinates, an inverse move rather than a complement.

Composite-relation MCQs 7-8

Question 7

Let R1 be a relation from A = {1, 3, 5, 7} to B = {2, 4, 6, 8} and R2 be another relation from B to C = {1, 2, 3, 4} as defined below: An element x in A is related to an element y in B (under R1) if x + y is divisible by 3. An element x in B is related to an element y in C (under R2) if x + y is even but not divisible by 3. Which is the composite relation R1R2 from A to C?

• A. R1R2 = {(1, 2), (1, 4), (3, 3), (5, 4), (7, 3)}

• B. R1R2 = {(1, 2), (1, 3), (3, 2), (5, 2), (7, 3)}

• C. R1R2 = {(1, 2), (3, 2), (3, 4), (5, 4), (7, 2)}

• D. R1R2 = {(3, 2), (3, 4), (5, 1), (5, 3), (7, 1)}

Correct answer: C. R1R2 = {(1, 2), (3, 2), (3, 4), (5, 4), (7, 2)}.

The rules give R1={(1,2),(1,8),(3,6),(5,4),(7,2),(7,8)} and R2={(2,2),(4,4),(6,2),(6,4),(8,2)}. Joining equal middle values gives 1->2, 3->{2,4}, 5->4, and 7->2, exactly option C.

Question 8

Let R1 be a relation from A = {1,3,5,7} to B = {2,4,6,8} and R2 be another relation from B to C = {1,2,3,4} as defined below (i) an element x in A is related to an element y in B if x + y is divisible by 3 (ii) an element x in B is related to an element y in C if x + y is even but not divisible by 3. Which is the composite relation R1R2 from A to C?

• A. {(1,2), (1,4), (3,3), (5,4), (7,3)}

• B. {(1,2), (1,3), (3,2), (5,2), (7,3)}

• C. {(1,2), (3,2), (3,4), (5,4), (7,2)}

• D. {(3,2), (3,4), (5,1), (5,3), (7,1)}

Correct answer: C. {(1,2), (3,2), (3,4), (5,4), (7,2)}.

The trace is 1->{2,8}->2, 3->6->{2,4}, 5->4->4, and 7->{2,8}->2. Deduplicating endpoints gives {(1,2),(3,2),(3,4),(5,4),(7,2)}.

Symmetric-difference ordering MCQ 9

Question 9

Consider the following relation on subsets of the set $S$ of integers between 1 and 2014. For two distinct subsets $U$ and $V$ of $S$ we say $U < V$ if the minimum element in the symmetric difference of the two sets is in $U$. Consider the following two statements: $S1$: There is a subset of $S$ that is larger than every other subset. $S2$: There is a subset of $S$ that is smaller than every other subset. Which one of the following is CORRECT?

• A. Both $S1$ and $S2$ are true

• B. $S1$ is true and $S2$ is false

• C. $S2$ is true and $S1$ is false

• D. Neither $S1$ nor $S2$ is true

Correct answer: A. Both $S1$ and $S2$ are true.

For every proper V, the least element of S triangle V lies in S, so S<V and the full set is smallest. For every nonempty V, the least element of empty-set triangle V lies in V, so V<empty-set and the empty set is largest. The same direction appears immediately on base set {1,2}, proving both statements.

Ordered-string counting MCQ 10: a constrained Cartesian power

Question 10

Let T = {p, q, r, s, t}. How many strings of length 4 can be formed from T if no symbol may be repeated?

• A. 120

• B. 625

• C. 360

• D. More than one of the above

• E. None of the above

Correct answer: A. 120.

With five symbols and no repetition, the number of ordered 4-tuples is 5*4*3*2=120. By contrast, |T^4|=5^4=625 allows repetition.

Cartesian product and relation MCQs: answer map and next step

The compact key is 1-C; 2-B; 3-C; 4-C; 5-D; 6-A; 7-C; 8-C; 9-A; 10-A.

Now reproduce four checks without looking: for A={p,q}, |A x A|=4 and the relation count is 16; Question 6 leaves R^c={(3,7),(5,7)}; Questions 7-8 contain 3->6->{2,4}; and Question 10 gives 5*4*3*2=120.

The Discrete Mathematics MCQs hub broadens practice across the subject.

Use GATE Guidance by Sanchit Sir when you want the complete Relations lesson path. When you are ready to apply the method under timed mixed practice, move to the GATE Test Series.