• Practice
  • About 22 min
  • 5 practice questions

Relations: domain, range and reflexive, symmetric, transitive and equivalence relations

Write a relation as a subset of A × B, find its domain, range and inverse, test it for reflexivity, symmetry and transitivity, build relations of a required type and count relations on a finite set.

If something looks wrong, please tell us.

By the end of this lesson you can

  • Define a relation from A to B and find its domain, co-domain and range.
  • Test a relation on a set for the reflexive, symmetric and transitive properties.
  • Prove that a relation is an equivalence relation and describe its equivalence classes.
  • Add the fewest pairs needed to give a relation a required property.
  • Use 2^(mn) for the number of relations and find the inverse of a relation.

In everyday speech a relation connects people: is the father of, is the teacher of. Mathematics connects objects the same way: a number m is related to n if m divides n; a point is related to a line if it lies on the line. To work with such connections precisely we describe a relation by the list of pairs it connects, and that list is a set of ordered pairs.

Relations as sets of ordered pairs

Here is a picture from coding. In a shift cipher each letter is replaced by the letter three places later in the alphabet, so MATHS becomes PDWKV. The code is the set of pairs {(M, P), (A, D), (T, W), (H, K), (S, V)}, a subset of {M, A, T, H, S} × {P, D, W, K, V}. Similarly the line 3x − y = 0 is the set {(x, 3x) : x ∈ R}, a subset of R × R. Both are relations.

Definition. Let A and B be non-empty sets. A relation R from A to B is a subset of A × B. If (x, y) ∈ R we write xRy and say x is related to y; otherwise x is not related to y. A relation from A to B is not the same as one from B to A. The domain of R is the set of first entries {a ∈ A : (a, b) ∈ R for some b}; the range is the set of second entries {b ∈ B : (a, b) ∈ R for some a}; and B is the co-domain. So the range is a subset of the co-domain.

For any set A, the subsets ∅ and A × A of A × A are the extreme relations on A: ∅ is the empty relation and A × A is the universal relation.

Worked example 1: domain, range and co-domain

Let A = {1, 2, 3, 4}, B = {1, 4, 9, 16, 25} and R = {(a, b) : a ∈ A, b ∈ B, b = a²}. Then R = {(1, 1), (2, 4), (3, 9), (4, 16)}. Domain = {1, 2, 3, 4}, range = {1, 4, 9, 16}, co-domain = B. The element 25 of the co-domain is not in the range. For the curve x = y² in R × R, the domain is [0, ∞) (x cannot be negative) and the range is R.

Reflexive, symmetric and transitive

Let R be a relation on a non-empty set S (that is, R ⊆ S × S). R is

  • reflexive if (a, a) ∈ R for every a ∈ S;
  • symmetric if (a, b) ∈ R ⇒ (b, a) ∈ R;
  • transitive if (a, b) ∈ R and (b, c) ∈ R ⇒ (a, c) ∈ R.

A relation that is reflexive, symmetric and transitive is an equivalence relation, usually written ∼. The set matters as much as the rule. a is a brother of b is not symmetric on the set of all people (a boy may be the brother of his sister, who is not his brother), but it is symmetric on a set of males. Likewise {(1, 1), (2, 2), (3, 3), (1, 2)} is reflexive on {1, 2, 3} but not on {1, 2, 3, 4}, which also needs (4, 4).

Testing a relation R on a set S

  • Reflexive? look at every element
    • Is (a, a) in R for all a ∈ S?
    • One missing (a, a) is enough to fail
  • Symmetric? look at every pair
    • For each (a, b) in R, is (b, a) in R?
    • Pairs (a, a) never cause trouble
  • Transitive? look at chains
    • For each (a, b) and (b, c) in R, is (a, c) in R?
    • No chain at all means it passes
  • Equivalence all three pass
    • Splits S into disjoint classes

Some edge cases follow straight from the definitions. The empty relation is symmetric and transitive (there is no pair that could break the rules), but not reflexive on a non-empty set. The universal relation is always an equivalence relation. A relation with a single pair is transitive.

Worked example 2: a relation that fails one test

On X = {1, 2, 3} let R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1), (2, 3), (3, 2)}. Reflexive: (1, 1), (2, 2), (3, 3) are all present, so yes. Symmetric: the pair (1, 2) has (2, 1), and (2, 3) has (3, 2), so yes. Transitive: (1, 2) and (2, 3) are in R but (1, 3) is not, so no. Hence R is not an equivalence relation.

Worked example 3: a relation from an equation

On N define xRy if x + 3y = 12. Listing: y = 1 gives x = 9, y = 2 gives x = 6, y = 3 gives x = 3, and y = 4 gives x = 0, which is not natural. So R = {(9, 1), (6, 2), (3, 3)}. Not reflexive, since (1, 1) ∉ R. Not symmetric, since (9, 1) ∈ R but (1, 9) ∉ R (1 + 27 ≠ 12). Transitive? A chain (a, b), (b, c) needs some pair to start with b. The only such chain is (3, 3), (3, 3), which gives (3, 3) ∈ R. So R is transitive. Surprising, but correct.

Worked example 4: adding the fewest pairs

Let S = {1, 2, 3} and ρ = {(1, 1), (2, 2), (1, 2), (2, 3)}. (i) Reflexive: (3, 3) is missing, so add (3, 3). (ii) Symmetric: (1, 2) needs (2, 1) and (2, 3) needs (3, 2), so add (2, 1) and (3, 2); alternatively, deleting (1, 2) and (2, 3) would also make it symmetric. (iii) Transitive: the chain (1, 2), (2, 3) needs (1, 3); after adding it, no pair starts with 3, so no new chain appears. (iv) Equivalence: add (3, 3), (2, 1), (3, 2) and (1, 3); symmetry now also needs (3, 1). The result contains all 9 pairs of S × S, so the five pairs to add are (3, 3), (2, 1), (3, 2), (1, 3) and (3, 1), and the equivalence relation obtained is the universal relation.

Worked example 5: proving an equivalence relation

On Z define aRb if a − b is divisible by 5. Reflexive: a − a = 0 = 5 × 0, so aRa. Symmetric: if a − b = 5k for an integer k, then b − a = 5(−k), so bRa. Transitive: if a − b = 5k and b − c = 5m, adding gives a − c = 5(k + m), so aRc. Hence R is an equivalence relation.

Equivalence classes and partitions

An equivalence relation splits its set into disjoint pieces called equivalence classes; such a splitting is a partition. For aRb if a − b is a multiple of 4 on Z, the classes are Z₀ = {..., −8, −4, 0, 4, 8, ...}, Z₁ = {..., −7, −3, 1, 5, 9, ...}, Z₂ = {..., −6, −2, 2, 6, 10, ...} and Z₃ = {..., −5, −1, 3, 7, 11, ...}. They do not overlap and Z = Z₀ ∪ Z₁ ∪ Z₂ ∪ Z₃. Conversely, any partition of S defines an equivalence relation: x ∼ y when x and y lie in the same piece.

Counting relations and the inverse relation

If n(A) = m and n(B) = n, then A × B has mn elements, and every subset of it is a relation, so there are 2^(mn) relations from A to B and 2^(n²) relations on a set of n elements. Of these, 2^(n² − n) are reflexive (the n diagonal pairs are forced, the other n² − n are free) and 2^(n(n + 1)/2) are symmetric. Check with n = 2: there are 2⁴ = 16 relations, 2² = 4 reflexive ones and 2³ = 8 symmetric ones.

The inverse of a relation R from A to B is R⁻¹ = {(b, a) : (a, b) ∈ R}, a relation from B to A. The domain of R becomes the range of R⁻¹ and the range of R becomes its domain. If R = {(1, x), (2, y), (2, z), (3, x)}, then R⁻¹ = {(x, 1), (y, 2), (z, 2), (x, 3)}.

Reflexive: (a, a) for all a. Symmetric: (a, b) ⇒ (b, a). Transitive: (a, b) and (b, c) ⇒ (a, c). Number of relations on an n-element set = 2^(n²).

— Relations in one line

Key takeaways: a relation is a subset of A × B; its range lies inside the co-domain; test the three properties pair by pair and chain by chain; give both the rule and the set; equivalence relations partition their set; and there are 2^(mn) relations from an m-element set to an n-element set.

Check your understanding

  1. 1. How many relations are there on a set with 3 elements?

    1. 9
    2. 64
    3. 512
    4. 81
    Show answer

    Answer: C. A × A has 3² = 9 pairs and each relation is a subset of A × A, so there are 2⁹ = 512 relations.

  2. 2. On A = {1, 2, 3}, the relation R = {(1, 1), (2, 2), (3, 3), (1, 2)} is

    1. reflexive and transitive but not symmetric
    2. an equivalence relation
    3. symmetric but not reflexive
    4. neither reflexive nor transitive
    Show answer

    Answer: A. All three (a, a) pairs are present, so R is reflexive. (1, 2) is in R but (2, 1) is not, so R is not symmetric. The chains (1, 1), (1, 2) and (1, 2), (2, 2) both give (1, 2), which is in R, so R is transitive.

  3. 3. If R = {(2, 5), (3, 7), (4, 5)}, what is the domain of R⁻¹?

    1. {2, 3, 4}
    2. {2, 3, 4, 5, 7}
    3. {5, 7, 5}
    4. {5, 7}
    Show answer

    Answer: D. R⁻¹ = {(5, 2), (7, 3), (5, 4)}. Its first entries are 5 and 7, so its domain is {5, 7}, which is the range of R.

  4. 4. Which of these is an equivalence relation on the set of all lines in a plane?

    1. l R m if l is perpendicular to m
    2. l R m if l is parallel to m (a line counted as parallel to itself)
    3. l R m if l meets m at exactly one point
    4. l R m if l and m are different lines
    Show answer

    Answer: B. Parallelism is reflexive (each line is parallel to itself by convention), symmetric and transitive. Perpendicularity is not reflexive, and if l ⊥ m and m ⊥ n then l is parallel to n, not perpendicular, so it is not transitive.

  5. 5. The empty relation on a non-empty set S is

    1. reflexive only
    2. reflexive, symmetric and transitive
    3. symmetric and transitive but not reflexive
    4. neither symmetric nor transitive
    Show answer

    Answer: C. It has no pair (a, a), so it is not reflexive. It has no pair (a, b) whose reverse could be missing, and no chain whose result could be missing, so it is symmetric and transitive.

Privacy · Terms · Refunds · Delivery