- 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
| Property | To prove | To disprove |
|---|---|---|
| Reflexive | show that a R a for every a | find one a with a R a false |
| Symmetric | assume a R b, show b R a | find a, b with a R b but not b R a |
| Transitive | assume a R b and b R c, show a R c | find 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
| Relation | Reflexive | Symmetric | Transitive |
|---|---|---|---|
| x = y | yes | yes | yes |
| x ≤ y on R | yes | no | yes |
| x < y on R | no | no | yes |
| x + y = 10 on Z | no | yes | no |
| x and y have a common prime factor, on {2, 3, ...} | yes | yes | no |
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. The relation x R y means x + y = 10 on the integers. Which description is correct?
- Reflexive and symmetric
- Symmetric and transitive but not reflexive
- An equivalence relation
- 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. The relation x R y means x·y ≥ 0 on the real numbers. Which description is correct?
- An equivalence relation
- Reflexive and symmetric but not transitive
- Transitive only
- 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. On the natural numbers, x R y means 'x divides y'. Which description is correct?
- An equivalence relation
- Symmetric and transitive but not reflexive
- Reflexive and transitive but not symmetric
- 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. On {2, 3, ..., 12}, x R y means 'x and y share a prime factor'. Which triple shows that R is not transitive?
- 2 R 6 and 6 R 3, but 2 is not related to 3
- 2 R 4 and 4 R 8, and 2 R 8
- 3 R 6 and 6 R 9, and 3 R 9
- 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. On the integers, x R y means x < y. Which description is correct?
- Reflexive and transitive
- Symmetric and transitive
- Transitive only
- 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.
Sign in to keep track of the lessons you finish.