2.2Relations and their properties
The idea
A relation R on A is a set of ordered pairs from A × A. Its key properties are reflexive, symmetric, antisymmetric and transitive, and each is a rule about the pairs that must (or must not) be present.
Think of it like this: Friendship, "taller than", "is the same age as", "divides": each has its own pattern of pairs that has to appear.
Why it exists
Every "is this an equivalence relation or a partial order" question is a property check; one counter-example is enough to reject.
How it works
- Reflexive: every (a, a) is present. Irreflexive: none is.
- Symmetric: (a, b) ∈ R forces (b, a) ∈ R.
- Antisymmetric: (a, b) and (b, a) both in R only when a = b.
- Transitive: (a, b) and (b, c) force (a, c).
- Equivalence = reflexive + symmetric + transitive. Partial order = reflexive + antisymmetric + transitive.
Worked example: R = {(1,2), (2,3)} on {1,2,3}
Not reflexive, not symmetric, antisymmetric yes, transitive no (needs (1,3)). The lab prints the missing pair.
Now play with it
- →Load "Reflexive, symmetric, not transitive" and read the witness.
- →Click cells to make "Antisymmetric but not a partial order" into a partial order.
Click a matrix cell to add or remove a pair. Row = first element, column = second.
| 1 | 2 | 3 | |
|---|---|---|---|
| 1 | 1 | 1 | 0 |
| 2 | 1 | 1 | 0 |
| 3 | 0 | 0 | 1 |
A relation can be both symmetric and antisymmetric (for example the identity), and can be neither. Empty relation: symmetric, antisymmetric, transitive, irreflexive, but not reflexive (for n ≥ 1).
| Relation on ℤ or a set | Refl | Sym | Antisym | Trans | Kind |
|---|---|---|---|---|---|
| = | ✓ | ✓ | ✓ | ✓ | equivalence and partial order |
| ≤ | ✓ | ✗ | ✓ | ✓ | partial (total) order |
| < | ✗ | ✗ | ✓ | ✓ | strict order |
| a divides b (positive ints) | ✓ | ✗ | ✓ | ✓ | partial order |
| a ≡ b (mod k) | ✓ | ✓ | ✗ | ✓ | equivalence |
| a ≠ b | ✗ | ✓ | ✗ | ✗ | (not transitive) |
| |a − b| ≤ 1 | ✓ | ✓ | ✗ | ✗ | tolerance, not transitive |
| ⊆ on sets | ✓ | ✗ | ✓ | ✓ | partial order |
| ∅ (empty relation) | ✗ | ✓ | ✓ | ✓ | vacuous |
Symmetric and antisymmetric can both hold only if every pair is of the form (a, a).
Check yourself
Which relation on {1,2,3} is both symmetric and antisymmetric?
Exam notes (the dense version)
A relation R on A is a subset of A×A. Reflexive: (a,a) for all a. Irreflexive: no (a,a). Symmetric: (a,b) ⇒ (b,a). Antisymmetric: (a,b) and (b,a) ⇒ a = b. Asymmetric: (a,b) ⇒ (b,a) not in R. Transitive: (a,b),(b,c) ⇒ (a,c). Symmetric and antisymmetric are not opposites: the identity is both; some relations are neither.
Previous year questions: Sets, Relations & Functions (20)
PYQs are grouped by topic, so this is the full set for Sets, Relations & Functions; try the ones that match this subtopic. Open all 20 on the topic page.