• Practice
  • About 16 min
  • 5 practice questions

Disproving relation properties: the counterexample method

Test relations defined by rules on Z, N and R for the reflexive, symmetric and transitive properties by proving a property in a line or disproving it with one counterexample.

If something looks wrong, please tell us.

To show that a relation has a property for all elements, you need an argument that works in general. To show that it does not, a single counterexample is enough. Exam questions on relation properties are quick if you use this asymmetry: first look for a counterexample, and only if none exists, write the general argument.

The three tests

PropertyTo proveTo disprove
Reflexiveshow that a R a for every afind one a with a R a false
Symmetricassume a R b, show b R afind a, b with a R b but not b R a
Transitiveassume a R b and b R c, show a R cfind a, b, c with a R b and b R c but not a R c

One counterexample kills a property; a general argument proves it. Try 0, 1, a repeated element, and 'bridge' elements such as 0 or 1 when searching for counterexamples.

Worked example 1: x + y = 10 on Z

Reflexive? Take a = 1: 1 + 1 = 2, not 10. So it fails. Symmetric? If x + y = 10 then y + x = 10, so it holds. Transitive? Take 3 R 7 (3 + 7 = 10) and 7 R 3, but 3 R 3 would need 3 + 3 = 10, which is false. So it fails. The relation is symmetric only.

Worked example 2: x·y ≥ 0 on R

Reflexive: a·a = a² ≥ 0 for every real a, so it holds. Symmetric: a·b = b·a, so it holds. Transitive: take a = 1, b = 0, c = −1. Then a·b = 0 ≥ 0 and b·c = 0 ≥ 0, but a·c = −1 < 0. So it fails. The relation is reflexive and symmetric but not transitive. The number 0 is the bridge that breaks it, which is why we try 0 first.

Worked example 3: 'divides' on N

Reflexive: a divides a. Transitive: if a divides b and b divides c then a divides c. Symmetric fails: 2 divides 4 but 4 does not divide 2. So the relation is reflexive and transitive but not symmetric.

Worked example 4: a common prime factor

On the set {2, 3, ..., 12} let x R y mean 'x and y have a common prime factor'. It is reflexive (every x ≥ 2 shares its own prime factors with itself) and symmetric. Transitive fails: 2 R 6 (common factor 2) and 6 R 3 (common factor 3), but 2 and 3 have no common prime factor, so 2 is not related to 3. The relation is reflexive and symmetric but not transitive.

Worked example 5: strict inequality

On Z let x R y mean x < y. Reflexive fails because a < a is false. Symmetric fails: 1 < 2 but 2 < 1 is false. Transitive holds: x < y and y < z give x < z. So it is transitive only.

A short catalogue

RelationReflexiveSymmetricTransitive
x = yyesyesyes
x ≤ y on Ryesnoyes
x < y on Rnonoyes
x + y = 10 on Znoyesno
x and y have a common prime factor, on {2, 3, ...}yesyesno

Traps

  • Proving symmetry by checking one pair: you must show it for all pairs, or find a failing pair.
  • Forgetting the case a = b: the pair (a, a) is allowed when you test transitivity.
  • Calling an empty relation on a non-empty set reflexive: it has no (a, a) pairs.
  • Claiming transitivity because a chain 'looks right' for small numbers; test with 0 and negative numbers.

Key takeaways: disprove with a single example, prove with a general argument. Remember the catalogue: ≤ is reflexive and transitive, < is only transitive, 'divides' is reflexive and transitive, and x + y = 10 is only symmetric.

Check your understanding

  1. 1. The relation x R y means x + y = 10 on the integers. Which description is correct?

    1. Reflexive and symmetric
    2. Symmetric and transitive but not reflexive
    3. An equivalence relation
    4. Symmetric only
    Show answer

    Answer: D. 1 + 1 ≠ 10, so it is not reflexive. It is symmetric. It is not transitive, since 3 R 7 and 7 R 3 but 3 + 3 ≠ 10.

  2. 2. The relation x R y means x·y ≥ 0 on the real numbers. Which description is correct?

    1. An equivalence relation
    2. Reflexive and symmetric but not transitive
    3. Transitive only
    4. Symmetric only
    Show answer

    Answer: B. x² ≥ 0 and xy = yx give reflexive and symmetric. But 1 R 0 and 0 R (−1), while 1·(−1) < 0, so it is not transitive.

  3. 3. On the natural numbers, x R y means 'x divides y'. Which description is correct?

    1. An equivalence relation
    2. Symmetric and transitive but not reflexive
    3. Reflexive and transitive but not symmetric
    4. Reflexive and symmetric but not transitive
    Show answer

    Answer: C. Every number divides itself, and divisibility chains, so reflexive and transitive hold. 2 divides 4 but 4 does not divide 2, so it is not symmetric.

  4. 4. On {2, 3, ..., 12}, x R y means 'x and y share a prime factor'. Which triple shows that R is not transitive?

    1. 2 R 6 and 6 R 3, but 2 is not related to 3
    2. 2 R 4 and 4 R 8, and 2 R 8
    3. 3 R 6 and 6 R 9, and 3 R 9
    4. 2 R 6 and 6 R 12, and 2 R 12
    Show answer

    Answer: A. A counterexample needs a chain whose end pair is not related. 2 and 3 share no prime factor, though 2 R 6 and 6 R 3. The other chains close properly.

  5. 5. On the integers, x R y means x < y. Which description is correct?

    1. Reflexive and transitive
    2. Symmetric and transitive
    3. Transitive only
    4. Reflexive only
    Show answer

    Answer: C. a < a is false, so it is not reflexive. 1 < 2 but 2 < 1 is false, so it is not symmetric. If x < y and y < z, then x < z, so it is transitive.

Privacy · Terms · Refunds · Delivery