Relations and Functions
Swipe left or right to change slide
Relation, empty and universal
✎ Note: A relation R on A is a set of ordered pairs (a, b) with a, b ∈ A. Write (a, b) ∈ R or aRb. Empty relation = no pair; universal relation = all pairs A × A. Both are called trivial relations.
Reflexive, symmetric, transitive
✎ Note: Check the three properties one by one. To prove a property, take general elements (a, b, c). To disprove it, one counter-example is enough – give actual numbers.
Equivalence relation and classes
✎ Note: A relation that is reflexive, symmetric AND transitive is an equivalence relation. It splits A into disjoint equivalence classes: every element is in exactly one class.
SOLVED EXAMPLE – Prove an equivalence relation (Ex 1.1 type)
Step 1: R on Z: (a, b) ∈ R if a − b is divisible by 3. Reflexive: a − a = 0, and 0 is divisible by 3.
Step 2: Symmetric: if 3 divides a − b, then 3 divides −(a − b) = b − a.
Why: −k is also an integer.
Step 3: Transitive: add the two differences.
Step 4: All three hold:
SOLVED EXAMPLE – Counter-example (Ex 1.1 type)
Step 1: R on R: (a, b) ∈ R if a ≤ b². Reflexive? Try a = ½:
Step 2: So (½, ½) ∉ R:
Why: one counter-example is enough.
Exam tip: To show a relation is NOT reflexive/symmetric/transitive, write one actual counter-example with numbers. Writing only “not symmetric” gets no marks.
Practice only – this does not count as a test.
Practice only – this does not count as a test.
Log in to save your progress.