Relations Example | StudyTution

Relations

• A × B — Cartesian product, all pairs (a, b), a ∈ A and b ∈ B
• A = {1, 4, 7}, B = {1, 16, 49}
• A × B = {(1, 1),(1, 16),(1, 49),(4, 1),(4, 16),(4, 49),(7, 1),(7, 16),(7, 49)}
• B × A = {(1, 1),(16, 1),(49, 1),(1, 4),(16, 4),(49, 4),(1, 7),(16, 7),(49, 7)}
• B × B = {(1, 1),(1, 16),(1, 49),(16, 1),(16, 16),(16, 49),(49, 1),(49, 16),(49, 49)}

Can take Cartesian product of more than two sets

• A × B × A = {(1, 1, 1),(1, 1, 4),(1, 1, 7),(1, 16, 1),(1, 16, 7), . . . ,(7, 49, 1),(7, 49, 16),(7, 49, 49)}

A relation picks out certain tuples in the Cartesian product

• S ⊆ A × B = {(1, 1),(4, 16),(7, 49)}
• S = {(a, b) | (a, b) ∈ A × B, b = a 2}

Examples Of Relations

Divisibility

• Pairs of natural numbers (d, n) such that d|n
• Pairs such as (7, 63),(17, 85),(3, 9), . . .
• D = {(d, n) | (d, n) ∈ N × N, d|n}
• Can also extend to integer divisors
• E = {(d, n) | (d, n) ∈ Z × N, d|n}
• Now (−7, 63),(−17, 85),(−3, 9), . . . are also in E

Prime powers

• Pairs of natural numbers (p, n) such that p is prime and n = p m for some natural number m
• Examples: (3, 1),(5, 625),(7, 343), . . .
• First define primes: P = {p | p ∈ N, factors(p) = {1, p}, p 6= 1}
• Prime powers: PP = {(p, n) | (p, n) ∈ P × N, n = p m for some m ∈ N}

Airline Routes

• An airline flies to set of cities — e.g. Bangalore, Chennai, Delhi, Kolkata, . . .
• Let C denote the set of cities served by the airline
• Some cities are connected by direct flights
• D ⊆ C × C
• Is D reflexive, irreflexive?
• Hopefully irreflexive!

Is D symmetric?

• If there is a direct flight from Bangalore to Delhi, is there always a direct flight back from
• Delhi to Bangalore
• For bigger cities, yes
• For smaller cities, may have a triangular route Chennai → Madurai → Salem → Chennai