• Practice
  • About 16 min
  • 5 practice questions

Relations: products, counts and properties

Work with Cartesian products, find the domain and range of relations given by equations, count relations, and test reflexive, symmetric and transitive properties quickly.

If something looks wrong, please tell us.

Relation questions test three skills: handling Cartesian products, reading a relation given by a rule, and deciding which properties a relation has. Each has a standard trap. A product of sets is a set of ordered pairs, so order matters; a rule over N quietly removes some pairs; and a single missing pair is enough to break symmetry or transitivity. This lesson gives a fast routine for each.

Cartesian products

A × B = {(a, b) : a ∈ A, b ∈ B} and n(A × B) = n(A) × n(B). Products distribute over union and intersection: A × (B ∪ C) = (A × B) ∪ (A × C) and A × (B ∩ C) = (A × B) ∩ (A × C). A × B = B × A only when A = B or one of the sets is empty. If A × B is given, A is the set of first entries and B the set of second entries.

Worked example 1: a product with an intersection

Let A = {1, 2}, B = {3, 4} and C = {4, 5}. Find A × (B ∩ C). B ∩ C = {4}, so A × (B ∩ C) = {(1, 4), (2, 4)}. Check the law: A × B = {(1, 3), (1, 4), (2, 3), (2, 4)} and A × C = {(1, 4), (1, 5), (2, 4), (2, 5)}. Their common pairs are (1, 4) and (2, 4), the same answer.

Counting relations

A relation from A to B is any subset of A × B, so with n(A) = p and n(B) = q there are 2^(pq) relations; a relation on A, with n(A) = p, is a subset of A × A, so there are 2^(p²) of them. The count includes the empty relation. Note that relations from A to B and from B to A are equal in number, because both products have pq pairs.

Worked example 2: a relation given by an equation

R = {(x, y) : x, y ∈ N, x + 2y = 10}. Find the domain and range. Try y = 1, 2, 3, ...: y = 1 gives x = 8; y = 2 gives x = 6; y = 3 gives x = 4; y = 4 gives x = 2; y = 5 gives x = 0, which is not natural, so stop. R = {(8, 1), (6, 2), (4, 3), (2, 4)}, the domain is {2, 4, 6, 8} and the range is {1, 2, 3, 4}. Run through the variable with the larger coefficient, and stop at the first value that fails.

Testing properties quickly

  • Reflexive: every (a, a) must be present. One missing diagonal pair breaks it.
  • Symmetric: for each (a, b), look for (b, a). Pairs (a, a) never cause trouble.
  • Transitive: for each pair (a, b), look at every pair starting with b, (b, c), and check (a, c) is present.
  • For relations on numbers, reason from the rule: a counter-example disproves, and a short algebraic argument proves.

Worked example 3: an equivalence relation on Z

Define a R b on Z if a − b is divisible by 3. Reflexive: a − a = 0 is divisible by 3. Symmetric: if 3 divides a − b, then 3 divides b − a = −(a − b). Transitive: if 3 divides a − b and b − c, it divides their sum a − c. So R is an equivalence relation. By contrast, a R b if |a − b| ≤ 1 on R is reflexive and symmetric but not transitive: (1, 2) and (2, 3) are in it but |1 − 3| = 2, so (1, 3) is not.

Familiar relations to know

Properties of some standard relations
RelationReflexiveSymmetricTransitive
a ≤ b on RYesNoYes
a < b on RNoNoYes
a divides b on NYesNoYes
a − b even on ZYesYesYes
|a − b| ≤ 1 on RYesYesNo

n(A × B) = pq and there are 2^(pq) relations from A to B. To break a property, one counter-example is enough; to prove it, argue for every pair.

— Rule to remember

Key takeaways

Products distribute over union and intersection, and their size multiplies. For relations given by an equation over N, list values until one fails. Test reflexive on the diagonal, symmetric by reversing, and transitive by chaining every pair. Learn the standard relations in the table, because they recur as options.

Check your understanding

  1. 1. If n(A × B) = 15 and n(A) = 3, how many relations are there from B to A?

    1. 2^8
    2. 15
    3. 2^15
    4. 2^5
    Show answer

    Answer: C. n(B) = 15 ÷ 3 = 5, so n(B × A) = 5 × 3 = 15 and there are 2^15 relations from B to A.

  2. 2. R = {(x, y) : x, y ∈ N, 2x + y = 9}. What is the range of R?

    1. {1, 2, 3, 4}
    2. {1, 3, 5, 7, 9}
    3. {0, 1, 3, 5, 7}
    4. {1, 3, 5, 7}
    Show answer

    Answer: D. x = 1, 2, 3, 4 give y = 7, 5, 3, 1; x = 5 gives y = −1, not natural. The range is {1, 3, 5, 7}; {1, 2, 3, 4} is the domain.

  3. 3. The relation 'a divides b' on N is

    1. reflexive and transitive but not symmetric
    2. an equivalence relation
    3. symmetric and transitive but not reflexive
    4. reflexive and symmetric but not transitive
    Show answer

    Answer: A. a divides a; if a divides b and b divides c then a divides c; but 2 divides 4 while 4 does not divide 2.

  4. 4. On Z, a R b if a − b is even. Then R is

    1. reflexive only
    2. symmetric only
    3. transitive but not symmetric
    4. an equivalence relation
    Show answer

    Answer: D. a − a = 0 is even; if a − b is even so is b − a; and (a − b) + (b − c) = a − c is even when both parts are.

  5. 5. On A = {1, 2, 3}, R = {(1, 2), (2, 3)}. What is the least number of pairs that must be added to make R transitive?

    1. 2
    2. 3
    3. 0
    4. 1
    Show answer

    Answer: D. (1, 2) and (2, 3) require (1, 3). After adding it, no new chains appear, so one pair is enough.

Privacy · Terms · Refunds · Delivery