SEM 6 › Discrete Mathematics › Week 09
Discrete Mathematics · Week 09

Relations & Their Properties

Binary relations as subsets of A × B, arrow diagrams and tables, functions as relations, relations on a set, reflexive, symmetric and transitive properties, and equivalence relations.

ITE38221 video · 30 min📄 Lesson 9- Relations.pdf

1Binary relations

Relationships between elements of sets are everywhere. They are expressed as ordered pairs of related elements, so a set of ordered pairs is a binary relation.

Definition 1

A binary relation from A to B is a subset of A × B. It is a set R of ordered pairs (a, b) with a ∈ A and b ∈ B.

  • a R b means (a, b) ∈ R: "a is related to b by R".
  • a R̸ b means (a, b) ∉ R.
Example 9.1.1 — friends and cities
  • A = your friends; B = main cities in Sri Lanka.
  • (a, b) ∈ R if friend a has visited city b.
  • If Kolitha and Sneha have visited Galle, then (Kolitha, Galle) and (Sneha, Galle) are in R. If Sneha hasn't visited Kandy, then (Sneha, Kandy) ∉ R.
  • A friend who visited no city appears in no pair. A city nobody visited is never a second element.
Example 9.1.2 — degree programmes and universities

(a, b) ∈ R if programme a is offered by university b.

  • In R: (Medicine, Colombo), (Engineering, Moratuwa), (Management, Sri Jayewardenepura), (Arts, Ruhuna), (Physical Sciences, Kelaniya)
  • Not in R: (Engineering, Kelaniya), (Architecture, Peradeniya)

Three ways to show a relation

Example 9.1.3: A = {1, 3, 7}, B = {x, y}, R = {(1, x), (1, y), (3, x), (7, y)}

So 7 R y but 7 R̸ x; 3 R x but 3 R̸ y.

1. Set of ordered pairs

R = {(1, x), (1, y), (3, x), (7, y)}

2. Arrow diagram

 A        B
 1 ──────▶ x
 1 ──────▶ y
 3 ──────▶ x
 7 ──────▶ y

3. Table

x y
1 × ×
3 ×
7 ×

2Functions as relations

  • A function f : A → B is a relation: its graph is {(a, b) | b = f(a)} ⊆ A × B.
  • It's a special relation where every element of A is the first element of exactly one pair.
  • Conversely, any relation with that property defines a function.
Examples 9.2.1 and 9.2.2
  • A = {1, 2, 3, 4}, B = {1, 4, 9, 16}, (a, b) ∈ R if b = a². Then R = {(1, 1), (2, 4), (3, 9), (4, 16)}. This is a function (in fact one-to-one).
  • A = {a, b, c, d}, B = {1, 2, 3, 4, 5}, R = {(a, 2), (b, 3), (c, 4), (d, 5)}. Every element of A appears exactly once, so this is a function.
Relations generalise functions

A relation can be one-to-many: one element of A related to several elements of B. Functions can't do that.

3Relations on a set

Definition 2

A relation on a set A is a relation from A to A: a subset of A × A.

Example 9.3.1 — "divides" on A = {1, 2, 3, 4}

R = {(a, b) | a divides b} = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}

Example 9.3.2 — relations on the integers
Relation Rule (1,1) (1,2) (2,1) (1,−1) (2,2)
R₁ a ≤ b ✓ ✓ ✓
R₂ a > b ✓ ✓
R₃ a = b or a = −b ✓ ✓ ✓
R₄ a = b ✓ ✓
R₅ a = b + 1 ✓
R₆ a + b ≤ 3 ✓ ✓ ✓ ✓

4Properties: reflexive, symmetric, transitive

Property Definition In words Digraph picture
Reflexive (Def 3) (a, a) ∈ R for every a ∈ A Every element is related to itself A loop on every node
Symmetric (Def 4) (a, b) ∈ R ⇒ (b, a) ∈ R Every relationship goes both ways Every arrow has a return arrow
Transitive (Def 5) (a, b) ∈ R and (b, c) ∈ R ⇒ (a, c) ∈ R A path of two steps implies a direct link Every 2-step path has a shortcut
Reflexive — Example 9.4.2 on {1, 2, 3, 4}
  • R₁ = {(1,1), (1,2), (2,1), (2,2), (3,4), (4,1), (4,4)}
  • R₂ = {(1,1), (1,2), (2,1)}
  • R₃ = {(1,1), (1,2), (1,4), (2,1), (2,2), (3,3), (4,1), (4,4)}
  • R₄ = {(2,1), (3,1), (3,2), (4,1), (4,2), (4,3)}
  • R₅ = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,3), (2,4), (3,3), (3,4), (4,4)}
  • R₆ = {(3,4)}

R₃ and R₅ are reflexive: they contain all of (1,1), (2,2), (3,3), (4,4). The others are not: none of R₁, R₂, R₄, R₆ contains (3,3).

Also (9.4.1): "x and y have the same mother and father" is reflexive, since everyone is related to themselves.

Symmetric
  • "a is a friend of b" (9.4.3): if x is y's friend, y is x's friend. Symmetric.
  • R = {(1,1), (1,3), (3,1), (5,3), (3,5), (3,3)} on {1, 3, 5} (9.4.4): every pair has its reverse. Symmetric.
  • a < b on ℕ (9.4.5): 1 < 2 but not 2 < 1. Not symmetric.
Transitive
  • "Same hometown" (9.4.6): x and y share a hometown, y and z share one, so x and z do too. Transitive.
  • R = {(p, q), (q, r), (p, r)} on {p, q, r} (9.4.7): p→q→r and p→r is there. Transitive.
🧪 Try it — Relation property checker (with digraph & matrix)
Fast checking method
  • Reflexive: look for every (a, a). One missing loop means not reflexive.
  • Symmetric: for each pair (a, b), look for (b, a).
  • Transitive: for each pair (a, b), look at every pair starting with b, say (b, c). Then (a, c) must be there.
  • One counterexample is enough to show a property fails. Say which pair breaks it.

5Equivalence relations

Definition

A relation on A is an equivalence relation if it is reflexive, symmetric and transitive.

Example 9.4.8

R = {(1,1), (2,2), (3,3), (1,2), (2,1), (2,3), (3,2), (1,3), (3,1)} on {1, 2, 3} is reflexive, symmetric and transitive, so it is an equivalence relation.

Example 9.4.9 — a R b if 7 | (a − b), on ℤ
  • Reflexive: a − a = 0, which is divisible by 7. So a R a. ✓
  • Symmetric: if 7 | (a − b), then b − a = −(a − b) is also divisible by 7. So a R b ⇒ b R a. ✓
  • Transitive: if 7 | (a − b) and 7 | (b − c), then a − c = (a − b) + (b − c) is divisible by 7. So a R b and b R c ⇒ a R c. ✓

So R is an equivalence relation. This is congruence mod 7 from Week 6. Its "classes" are the congruence classes.

Recognising equivalence relations

Relations of the form "has the same ___ as" are usually equivalence relations: the same hometown, the same birthday, the same parents, the same remainder mod m, parallel lines.

Relations like ≤, <, divides, "is taller than" are not: they fail symmetry.

Exam focus

Expect:

  • Listing the pairs of a relation (e.g. a > b, a + b = 4, a | b on given sets)
  • Drawing the arrow diagram and table
  • Deciding reflexive / symmetric / transitive for given pair sets with reasons
  • Deciding these properties for real-life relations ("taller than", "same birthday", "common grandparent")
  • Proving a relation is an equivalence relation, like Example 9.4.9 (parallel lines; m | (a − b))

6Quick revision sheet

Concept Remember it as
Binary relation Subset of A × B; a R b ⇔ (a, b) ∈ R
Representations Ordered pairs · arrow diagram · table / 0–1 matrix
Function Relation where each a appears exactly once as first element
Relation on A Subset of A × A
Reflexive (a, a) for all a: loops everywhere
Symmetric (a, b) ⇒ (b, a)
Transitive (a, b), (b, c) ⇒ (a, c)
Equivalence Reflexive + symmetric + transitive
Classic equivalences Same hometown, 7 | (a − b), parallel lines
Not equivalence <, ≤ (not symmetric), friends (not transitive)

?Self-check quiz

11 questions on this week. Answer them all, then press Check my answers. Your best and latest scores are saved and shown on the subject page.

← PreviousCounting — Product & Sum Rules, Permutations & CombinationsNext →n-ary Relations & Relational Databases